VTechWorks staff will be away for the Thanksgiving holiday beginning at noon on Wednesday, November 27, through Friday, November 29. We will resume normal operations on Monday, December 2. Thank you for your patience.

Browsing by Author "Lee, Youngho"

Now showing 1 - 3 of 3
  • Thumbnail Image
    Enhanced model representations for an intra-ring synchronous optical network design problem allowing demand splitting
    Sherali, Hanif D.; Smith, J. Cole; Lee, Youngho (INFORMS, 2000)
    In this paper, we consider a network design problem arising in the context of deploying synchronous optical networks (SONET) using a unidirectional path switched ring architecture, a standard of transmission using optical fiber technology. Given several rings of this type, the problem is to find an assignment of nodes to possibly multiple rings, and to determine what portion of demand traffic between node pairs spanned by each ring should be allocated to that ring. The constraints require that the demand traffic between each node pair should be satisfiable given the ring capacities, and that no more than a specified maximum number of nodes should be assigned to each ring. The objective function is to minimize the total number of node-to-ring assignments, and hence, the capital investment in add-drop multiplexer equipments. We formulate the problem as a mixed-integer programming model, and propose several alternative modeling techniques designed to improve the mathematical representation of this problem. We then develop various classes of valid inequalities for the problem along with suitable separation procedures for tightening the representation of the model, and accordingly, prescribe an algorithmic approach that coordinates tailored routines with a commercial solver (CPLEX). We also propose a heuristic procedure which enhances the solvability of the problem and provides bounds within 5-13% of the optimal solution. Promising computational results are presented that exhibit the viability of the overall approach and that lend insights into various modeling and algorithmic constructs.
  • Thumbnail Image
    Network Design and Analysis Problems in Telecommunication, Location-Allocation, and Intelligent Transportation Systems
    Park, Taehyung (Virginia Tech, 1998-06-22)
    This research is concerned with the development of algorithmic approaches for solving problems that arise in the design and analysis of telecommunication networks, location-allocation distribution contexts, and intelligent transportation networks. Specifically, the corresponding problems addressed in these areas are a local access and transport area (LATA) network design problem, the discrete equal-capacity p-median problem (PMED), and the estimation of dynamic origin-destination path ows or trip tables in a general network. For the LATA network problem, we develop a model and apply the Reformulation-Linearization Technique (RLT) to construct various enhanced tightened versions of the proposed model. We also design efficient Lagrangian dual schemes for solving the linear programming relaxation of the various enhanced models, and construct an effective heuristic procedure for deriving good quality solutions in this process. Extensive computational results are provided to demonstrate the progressive tightness resulting from the enhanced formulations and their effect on providing good quality feasible solutions. The results indicate that the proposed procedures typically yield solutions having an optimality gap of less than 2% with respect to the derived lower bound, within a reasonable effort that involves the solution of a single linear program. For the discrete equal-capacity p-median problem, we develop various valid inequalities, a separation routine for generating cutting planes via specific members of such inequalities, as well as an enhanced reformulation that constructs a partial convex hull representation that subsumes an entire class of valid inequalities via its linear programming relaxation. We also propose suitable heuristic schemes for solving this problem, based on sequentially rounding the continuous relaxation solutions obtained for the various equivalent formulations of the problem. Extensive computational results are provided to demonstrate the effectiveness of the proposed valid inequalities, enhanced formulations, and heuristic schemes. The results indicate that the proposed schemes for tightening the underlying relaxations play a significant role in enhancing the performance of both exact and heuristic solution methods for solving this class of problems. For the estimation of dynamic path ows in a general network, we propose a parametric optimization approach to estimate time-dependent path ows, or origin-destination trip tables, using available data on link traffic volumes for a general road network. Our model assumes knowledge of certain time-dependent link ow contribution factors that are a dynamic generalization of the path-link incidence matrix for the static case. We propose a column generation approach that uses a sequence of dynamic shortest path subproblems in order to solve this problem. Computational results are presented on several variants of two sample test networks from the literature. These results indicate the viability of the proposed approach for use in an on-line mode in practice. Finally, we present a summary of our developments and results, and offer several related recommendations for future research.
  • Thumbnail Image
    The polyhedral structure of certain combinatorial optimization problems with application to a naval defense problem
    Lee, Youngho (Virginia Tech, 1992-06-05)
    This research deals with a study of the polyhedral structure of three important combinatorial optimization problems, namely, the generalized upper bounding (GUS) constrained knapsack problem, the set partitioning problem, and the quadratic zero-one programming problem, and applies related techniques to solve a practical combinatorial naval defense problem. In Part I of this research effort, we present new results on the polyhedral structure of the foregoing combinatorial optimization problems. First, we characterize a new family of facets for the GUS constrained knapsack polytope. This family of facets is obtained by sequential and simultaneous lifting procedures of minimal GUS cover inequalities. Second, we develop a new family of cutting planes for the set partitioning polytope for deleting any fractional basic feasible solutions to its underlying linear programming relaxation. We also show that all the known classes of valid inequalities belong to this family of cutting planes, and hence, this provides a unifying framework for a broad class of such valid inequalities. Finally, we present a new class of facets for the boolean quadric polytope, obtained by applying a simultaneous lifting procedure. The strong valid inequalities developed in Part I, such as facets and cutting planes, can be implemented for obtaining exact and approximate solutions for various combinatorial optimization problems in the context of a branch-and-cut procedure. In particular, facets and valid cutting planes developed for the GUS constrained knapsack polytope and the set partitioning polytope can be directly used in generating tight linear programming relaxations for a certain scheduling polytope that arises from a combinatorial naval defense problem. Furthermore, these tight formulations are intended not only to develop exact solution algorithms, but also to design powerful heuristics that provide good quality solutions within a reasonable amount of computational effort. Accordingly, in Part ll of this dissertation, we present an application of such polyhedral results in order to construct effective approximate and exact algorithms for solving a naval defense problem. tn this problem, the objective is to schedule a set of illuminators in order to strike a given set of targets using surface-to-air missiles in naval battle-group engagement scenarios. The problem is conceptualized as a production floor shop scheduling problem of minimizing the total weighted flow time subject to time-window job availability and machine-downtime unavailability side constraints. A polynomial-time algorithm is developed for the case when ail the job processing times are equal (and unity without loss of generality) and the data are all integer. For the general case of scheduling jobs with unequal processing times, we develop three alternative formulations and analyze their relative strengths by comparing their respective linear programming relaxations. The special structures inherent in a particular strong zero-one integer programming model of the problem enable us to derive some classes of strong valid inequalities from the facets of the GUB constrained knapsack polytope and the set-packing polytope. Furthermore, these special structures enable us to construct several effective approximate and exact algorithms that provide solutions within specified tolerances of optimality, with an effort that admits real-time processing in the naval battle-group engagement scenario. Computational results are presented using suitable realistic test data.