This dissertation is concerned with the development of algorithmic approaches for solving the minisum location and location-allocation problems in which the Euclidean metric is used to measure distances. To overcome the nondifferentiability difficulty associated with the Euclidean norm function, specialized solution procedures are developed for both the location and the location-allocation problems. For the multifacility location problem (EMFLP), two equivalent convex differentiable reformulations are proposed. The first of these is formulated directly in the primal space, and relationships between its Karush-Kuhn-Tucker (KKT) conditions and the necessary and sufficient optimality conditions for EMFLP are established in order to explore the use of standard convex differentiable nonlinear programming algorithms that are guaranteed to converge to KKT solutions. The second equivalent differentiable formulation is derived via a Lagrangian dual approach based on the optimum of a linear function over a unit ball (circle). For this dual approach, which recovers Francis and Cabot's (1972) dual problem, we also characterize the recovery of primal location decisions, hence settling an issue that has remained open since 1972. In another approach for solving EMFLP, conjugate or deflected subgradient based algorithms along with suitable line-search strategies are proposed. The subgradient deflection method considered is the Average Direction Strategy (ADS) imbedded within the Variable Target Value Method (VTVM). The generation of two types of subgradients that are employed in conjunction with ADS are investigated. The first type is a simple valid subgradient that assigns zero components corresponding to the nondifferentiable terms in the objective function. The second type expends more effort to derive a low-norm member of the subdifferential in order to enhance the prospect of obtaining a descent direction. Furthermore, a Newton-based line-search is also designed and implemented in order to enhance the convergence behavior of the developed algorithm. Various combinations of the above strategies are composed and evaluated on a set of test problems. Computational results for all the proposed algorithmic approaches are presented, using a set of test problems that include some standard problems from the literature. These results exhibit the relative advantages of employing the new proposed procedures. Finally, we study the capacitated Euclidean distance location-allocation problem. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. We develop a branch-and-bound algorithm that implicitly/partially enumerates the vertices of the feasible region of the transportation constraints in order to determine a global optimum for this nonconvex problem. For deriving lower bounds on node subproblems, a specialized variant of the Reformulation-Linearization Technique (RLT) is suitably designed which transforms the representation of this nonconvex problem from the original defining space into a higher dimensional space associated with a lower bounding (largely linear) convex program. The maximum of the RLT relaxation based lower bound that is obtained via a deflected subgradient strategy applied to a Lagrangian dual formulation of this problem, and another readily computed lower bound in the projected location space is considered at each node of the branch-and-bound tree for fathoming purposes. In addition, certain cut-set inequalities in the allocation space, and objective function based cuts in the location space are generated to further tighten the lower bounding relaxation. Computational experience is provided on a set of randomly generated test problems to investigate both the RLT-based and the projected location- space lower bounding schemes. The results indicate that the proposed global optimization approach for this class of problem offers a promising viable solution procedure. In fact, for two instances available available in the in the literature, we report significantly improved solutions. The dissertation concludes with recommendations for further research for this challenging class of problems. Data for the collection of test problems is provided in the Appendix to facilitate further testing in this area. / Ph. D.

No description available.

A variety of practical network optimization problems arising in the context of public supply and commercial transportation, emergency response and risk management, engineering design, and industrial planning are addressed in this study. The decisions to be made in these problems include the location of supply centers, the routing, allocation and scheduling of flow between supply and demand locations, and the design of links in the network. This study is concerned with the development of optimization models and the analysis of five such problems, and the subsequent design and testing of exact and heuristic algorithms for solving these various network optimization problems. The first problem addressed is the time-dependent shortest pair of disjoint paths problem. We examine computational complexity issues, models, and algorithms for the problem of finding a shortest pair of disjoint paths between two nodes of a network such that the total travel delay is minimized, given that the individual arc delays are time-dependent. It is shown that this problem, and many variations of it, are nP-Hard and a 0-1 linear programming model that can be used to solve this problem is developed. This model can accommodate various degrees of disjointedness of the pair of paths, from complete to partial with respect to specific arcs. Next, we examine a minimum-risk routing problem and pursue the development, analysis, and testing of a mathematical model for determining a route that attempts to reduce the risk of low probability-high consequence accidents related with the transportation of hazardous materials (hazmat). More specifically, the problem addressed in this study involves finding a path that minimizes the conditional expectation of a consequence, given that an accident occurs, subject to the expected value of the consequence being lesser than or equal to a specified level n, and the probability of an accident on the path being also constrained to be no more than some value h. Various insights into related modeling issues are also provided. The values n and h are user-prescribed and could be prompted by the solution of shortest path problems that minimize the respective corresponding linear risk functions. The proposed model is a discrete, fractional programming problem that is solved using a specialized branch-and-bound approach. The model is also tested using realistic data associated with a case concerned with routing hazmat through the roadways of Bethlehem, Pennsylvania. The third problem deals with the development of a resource allocation strategy for emergency and risk management. An important and novel issue addressed in modeling this problem is the effect of loss in coverage due to the non-availability of emergency response vehicles that are currently serving certain primary incidents. This is accommodated within the model by including in the objective function a term that reflects the opportunity cost for serving an additional incident that might occur probabilistically on the network. A mixed-integer programming model is formulated for the multiple incident - multiple response problem, and we show how its solution capability can be significantly enhanced by injecting a particular structure into the constraints that results in an equivalent alternative model representation. Furthermore, for certain special cases of the MIMR problem, efficient polynomial-time solution approaches are prescribed. An algorithmic module composed of these procedures, and used in concert with a computationally efficient LP-based heuristic scheme that is developed, has been incorporated into an area-wide incident management decision support system (WAIMSS) at the Center for Transportation Research, Virginia Tech. The fourth problem addressed in this study deals with the development of global optimization algorithms for designing a water distribution network, or expanding an already existing one, that satisfies specified flow demands at stated pressure head requirements. The nonlinear, nonconvex network problem is transformed into the space of certain design variables. By relaxing the nonlinear constraints in the transformed space via suitable polyhedral outer approximations and applying the Reformulation-Linearization Technique (RLT), a tight linear lower bounding problem is derived. This problem provides an enhancement and a more precise representation of previous lower bounding relaxations that use similar approximations. Computational experience on three standard test problems from the literature is provided. For all these problems, a proven global optimal solution within a tolerance of 10 -4 % and/or within 1$ of optimality is obtained. For the two larger instances dealing with the Hanoi and New York test networks that have been open for nearly three decades, the solutions derived represent significant improvements, and the global optimality has been verified at the stated level of accuracy for these problems for the very first time in the literature. A new real network design test problem based on the Town of Blacksburg Water Distribution System is also offered to be included in the available library of test cases, and related computational results on deriving global optimal solutions are presented. The final problem addressed in this study is concerned with a global optimization approach for solving capacitated Euclidean distance multifacility location-allocation problems, as well as the development of a new algorithm for solving the generalized lp distance location-allocation problem. There exists no global optimization algorithm that has been developed and tested for this class of problems, aside from a total enumeration approach. Beginning with the Euclidean distance problem, we design depth-first and best-first branch-and-bound algorithms based on a partitioning of the allocation space that finitely converges to a global optimum for this nonconvex problem. For deriving lower bounds at node subproblems in these partial enumeration schemes, we employ two types of procedures. The first approach computes a lower bound via a simple projected location space lower bounding (PLSB) subproblem. The second approach derives a significantly enhanced lower bound by using a Reformulation-Linearization Technique (RLT) to transform an equivalent representation of the original nonconvex problem into a higher dimensional linear programming relaxation. In addition, certain cut-set inequalities generated in the allocation space, objective function based cuts derived in the location space, and tangential linear supporting hyperplanes for the distance function are added to further tighten the lower bounding relaxation. The RLT procedure is then extended to the.general lp distance problem for 1 < p < 2. Various issues related to the selection of branching variables, the design of heuristics via special selective backtracking mechanisms, and the study of the sensitivity of the proposed algorithm to the value of p in the lp - norm, are computationally investigated. Computational experience is also provided on a set of test problems to investigate both the PLSB and the RLT-lower bounding schemes. The results indicate that the proposed global optimization approach using the RLT-based scheme offers a promising viable solution procedure. In fact, among the problems solved, for the only two test instances previously available in the literature for the Euclidean distance case that were posed in 1979, we report proven global optimal solutions within a tolerance of 0.1% for the first time. It is hoped that the modeling, analysis, insights, and concepts provided for these various network based problems that arise in diverse routing, location, distribution, and design contexts, will provide guidelines for studying many other problems that arise in related situations. / Ph. D.

The containership design problem involves optimizing a nonconvex objective function over a design space that is restricted by a set of constraints defined in terms of nonconvex functions. An application of standard nonlinear optimization methods to such a problem can at best attain a local optimum that need not be a global optimum. This thesis investigates the application of alternative modeling, approximation, and global optimization techniques for developing a multidisciplinary approach to the containership design problem. The problem involves five design variables, which prioritized according to their relative importance in the model are: design draft, depth at side, speed, overall length, and maximum beam. Five constraints are imposed on the design, viz., an equality constraint to enforce the balance between the weight and the displacement, a linear inequality constraint on the length to depth ratio that is implied by the lightship weight formulation for the design to be acceptable, an inequality constraint on the metacentric height to ensure that the design satisfies the Coast Guard wind heel criterion, an inequality on the freeboard to ensure the minimum required freeboard governed by the code of federal regulations for freeboard (46 CFR 42), and an inequality constraint on the rolling period to ensure that the design satisfies the minimum required rolling period criterion. The objective function employed is the required freight rate, expressed in dollars per metric ton per nautical mile in order to recover annualized construction and operational costs. The model also accommodates various practical issues in a manner suitable to improve its representability. For example, it takes into account the discrete container stowage issue. The carrying capacity (number of containers) is expressed as a continuous function of the principal dimensions by using a linear response surface fit that in turn makes the objective function continuous. The weight-displacement balance is maintained by including draft as a design variable and imposing an equality constraint on the weight and displacement rather than introducing an internal loop to calculate draft at each iteration. This speeds up the optimization process. Also, the weight is formulated independent of the draft to ensure independence of the weight and the displacement, which simplifies the optimization process. The time for loading and unloading containers at a given port is a function of the number of cranes available. The number of cranes is formulated as a function of the length of the ship, and the resulting expression is made continuous through a linear response surface fit. To solve this problem, we design two approaches based on employing a sequence of polynomial programming approximations, each within two alternative branch-and-bound frameworks. In the first approach, we construct a polynomial programming approximation to the containership design problem using the Response Surface Methodology (RSM) and solve this model to global optimality using the software package BARON (Branch-and-Reduce Optimization Navigator - see Sahinidis, 1996), although the Reformulation-Linearization Technique (RLT)-based procedure of Sherali and Tuncbilek (1992, 1997) offers a viable alternative (BARON itself incorporates some elements of the latter approach). The resulting solution is refined by the application of a local search method. This procedure is integrated into two alternative branch-and-bound frameworks. The motivation is that the solution of the nonconvex polynomial approximations is likely to yield solutions in the near vicinity of the true underlying global optimum, and hence, the application of a local search method initiated at such a solution has a greater prospect of detecting such a global optimum. In the second approach, we utilize a continuous-space branch-and-bound procedure based on linear programming (LP) relaxations. These relaxations are generated through an approximation scheme that first utilizes RSM to derive polynomial approximations to the objective function and the constraints, and then applies the RLT to obtain an LP relaxation. The initial stage of this lower bounding step generates a tight, nonconvex polynomial programming relaxation for the problem, and the subsequent step constructs an LP relaxation to the resulting polynomial program via a suitable RLT procedure. The underlying motivation for these two steps is to generate a tight outer approximation of the convex envelope of the objective function over the convex hull of the feasible region. The solution obtained using the polynomial approximations is treated as a lower bound. A local search method is applied to this solution to compute an upper bound. This bounding step is then integrated into two alternative branch-and-bound frameworks. The node partitioning schemes are especially designed so that the gaps resulting from these two levels of approximations are induced to approach zero in the limit, thereby ensuring convergence to a (near) global optimum. A comparison of the containership design obtained from the designed algorithmic approaches with that obtained from the application of the nonlinear optimization methods as in previous research, exhibits a significant improvement in the design parameters translating to a significant amount of annual cost savings. For a typical containership of the size pertaining to a test case addressed in this work, having a gross weight of 90,000 metric tons, an annual transportation capacity of 99,000 containers corresponding to an annual deadweight of 1,188,000 metric tons, and logging 119,000 nautical miles annually, the improvement in the prescribed design translates to an annual estimated savings of $ 1,862,784 (or approximately $ 1.86 million) and an estimated 27 % increase in the return on investment over the life of the ship. The main contribution of this research is that it develops a detailed formulation and a more precise model of the containership design problem, along with suitable response surface and global optimization methodologies for prescribing an improved modeling and algorithmic approach for the highly nonconvex containership design problem. / Master of Science

This dissertation addresses the development of enhanced formulations for minimax and mixed-integer programming models for certain industrial and logistical systems, along with the design and implementation of efficient algorithmic strategies. We first examine the general class of minimax mixed-integer 0-1 problems of the type that frequently arise in decomposition approaches and in a variety of location and scheduling problems. We conduct an extensive polyhedral analysis of this problem in order to tighten its representation using the Reformulation-Linearization/Convexification Technique (RLT), and demonstrate the benefits of the resulting lifted formulations for several classes of problems. Specifically, we investigate RLT-enhanced Lagrangian dual formulations for the class of minimax mixed-integer 0-1 problems in concert with deflected/conjugate subgradient algorithms. In addition, we propose two general purpose lifting mechanisms for tightening the mathematical programming formulations associated with such minimax optimization problems. Next, we explore novel continuous nonconvex as well as lifted discrete formulations for the notoriously challenging class of job-shop scheduling problems with the objective of minimizing the maximum completion time (i.e., minimizing the makespan). In particular, we develop an RLT-enhanced continuous nonconvex model for the job-shop problem based on a quadratic formulation of the job sequencing constraints on machines. The tight linear programming relaxation that is induced by this formulation is then embedded in a globally convergent branch-and-bound algorithm. Furthermore, we design another novel formulation for the job-shop scheduling problem that possesses a tight continuous relaxation, where the non-overlapping job sequencing constraints on machines are modeled via a lifted asymmetric traveling salesman problem (ATSP) construct, and specific sets of valid inequalities and RLT-based enhancements are incorporated to further tighten the resulting mathematical program. The efficacy of our enhanced models is demonstrated by an extensive computational experiment using classical benchmark problems from the literature. Our results reveal that the LP relaxations produced by the lifted ATSP-based models provide very tight lower bounds, and directly yield a 0\% optimality gap for many benchmark problems, thereby substantially dominating other alternative mixed-integer programming models available for this class of problems. Notably, our lifted ATSP-based formulation produced a 0\% optimality gap via the root node LP relaxation for 50\% of the classical problem instances due to Lawrence. We also investigate enhanced model formulations and specialized, efficient solution methodologies for applications arising in four particular industrial and sports scheduling settings. The first of these was posed to us by a major trucking company (Volvo Logistics North America), and concerns an integrated assembly and routing problem, which is a unique study of its kind in the literature. In this context, we examine the general class of logistical systems where it is desirable to appropriately ascertain the joint composition of the sequences of vehicles that are to be physically connected along with determining their delivery routes. Such assembly-routing problems occur in the truck manufacturing industry where different models of vehicles designed for a network of customers need to be composed into compatible groups (assemblies) and subsequently dispatched via appropriately optimized delivery routes that are restricted by the particular sequence in which the trucks are connected. A similar structure is exhibited in the business of shipping goods via boat-towed barges along inland waterways, or via trains through railroad networks. We present a novel modeling framework and column generation-based optimization approach for this challenging class of joint vehicle assembly-routing problems. In addition, we suggest several extensions to accommodate particular industrial restrictions where assembly sequence-dependent delivery routes are necessary, as well as those where limited driver- and equipment-related resources are available. Computational experience is provided using large-scale realistic data to demonstrate the applicability of our suggested methodology in practice. The second application addressed pertains to a production planning problem faced by a major motorcycle manufacturing firm (Harley-Davidson Motor Company). We consider the problem of partitioning and sequencing the production of different manufactured items in mixed-model assembly lines, where each model has various specific options and designated destinations. We propose a mixed-integer programming formulation (MPSP1) for this problem that sequences the manufactured goods within production batches in order to balance the motorcycle model and destination outputs as well as the load demands on material and labor resources. An alternative (relaxed) formulation (MPSP2) is also presented to model a closely related case where all production decisions and outputs are monitored within a common sequence of batches, which permits an enhanced tighter representation via an additional set of hierarchical symmetry-defeating constraints that impart specific identities amongst batches of products under composition. The latter model inspires a third set partitioning-based formulation in concert with an efficient column generation approach that directly achieves the joint partitioning of jobs into batches along with ascertaining the sequence of jobs within each composed batch. Finally, we investigate a subgradient-based optimization strategy that exploits a non-differentiable optimization formulation, which is prompted by the flexibility in the production process as reflected in the model via several soft-constraints, thereby providing a real-time decision-making tool. Computational experience is presented to demonstrate the relative effectiveness of the different proposed formulations and the associated optimization strategies for solving a set of realistic problem instances. The third application pertains to the problem of matching or assigning subassembly parts in assembly lines, where we seek to minimize the total deviation of the resulting final assemblies from a vector of nominal and mean quality characteristic values. We introduce three symmetry-defeating enhancements for an existing assignment-based model, and highlight the critical importance of using particular types of symmetry-defeating hierarchical constraints that preserve the model structure. We also develop an alternative set partitioning-based formulation in concert with a column generation approach that efficiently exploits the structure of the problem. A special complementary column generation feature is proposed, and we provide insights into its vital role for the proposed column generation strategy, as well as highlight its benefits in the broader context of set partitioning-based formulations that are characterized by columns having relatively dense non-zero values. In addition, we develop several heuristic procedures. Computational experience is presented to demonstrate the relative effectiveness of the different adopted strategies for solving a set of realistic problem instances. Finally, we analyze a doubles tennis scheduling problem in the context of a training tournament as prompted by a tennis club in Virginia, and develop two alternative 0-1 mixed-integer programming models, each with three different objective functions that attempt to balance the partnership and the opponentship pairings among the players. Our analysis and computational experience demonstrate the superiority of one of these models over the other, and reflect the importance of model structure in formulating discrete optimization problems. Furthermore, we design effective symmetry-defeating strategies that impose certain decision hierarchies within the models, which serve to significantly enhance algorithmic performance. In particular, our study provides the insight that the special structure of the mathematical program to which specific tailored symmetry-defeating constraints are appended can greatly influence their pruning effect. We also propose a novel nonpreemptive multi-objective programming strategy in concert with decision hierarchies, and highlight its effectiveness and conceptual value in enhancing problem solvability. Finally, four specialized heuristics are devised and are computationally evaluated along with the exact solution schemes using a set of realistic practical test problems. Aside from the development of specialized effective models and algorithms for particular interesting and challenging applications arising in different assembly, routing, and scheduling contexts, this dissertation makes several broader contributions that emerge from the foregoing studies, which are generally applicable to solving formidable combinatorial optimization problems. First, we have shown that it is of utmost importance to enforce symmetry-defeating constraints that preserve the structure of mathematical programs to which they are adjoined, so that their pruning effects are most efficiently coupled with the branch-and-bound strategies that are orchestrated within mathematical programming software packages. In addition, our work provides the insight that the concept of symmetry compatible formulations plays a crucial role in the effectiveness of implementing any particular symmetry-defeating constraints. In essence, if the root node LP solution of the original formulation does not conform relatively well with the proposed symmetry-defeating hierarchical constraints, then a significant branching effort might be required to identify a good solution that is compatible with the pattern induced by the selected symmetry-defeating constraints. Therefore, it is advisable to enforce decision hierarchies that conform as much as possible with the problem structure as well as with the initial LP relaxation. Second, we have introduced an alternative concept for defeating symmetry via augmented objective functions. This concept prompts the incorporation of objective perturbation terms that discriminate amongst subsets of originally undistinguishable solution structures and, in particular, leads to the development of a nonpreemptive multiobjective programming approach based on, and combined with, symmetry-defeating constraints. Interestingly, nonpreemptive multiobjective programming approaches that accommodate symmetry-defeating hierarchical objective terms induce a root node solution that is compatible with the imposed symmetry-defeating constraints, and hence affords an automated alternative to the aforementioned concept of symmetry compatible formulations. Third, we have proposed a new idea of complementary column generation in the context of column generation approaches that generally provide a versatile framework for analyzing industrial-related, integrated problems that involve the joint optimization of multiple operational decisions, such as assembly and routing, or partitioning and scheduling. In such situations, we have reinforced the insight that assignment-related problems that involve collections of objects (production batches, final assemblies, etc.) whose permutation yields equivalent symmetric solutions may be judiciously formulated as set partitioning models. The latter can then be effectively tackled via column generation approaches, thereby implicitly obviating the foregoing combinatorial symmetric reflections through the dynamic generation of attractive patterns or columns. The complementary column generation feature we have proposed and investigated in this dissertation proves to be particularly valuable for such set partitioning formulations that involve columns having relatively dense non-zero values. The incorporation of this feature guarantees that every LP iteration (involving the solution of a restricted master program and its associated subproblem) systematically produces a consistent set of columns that collectively qualify as a feasible solution to the problem under consideration. Upon solving the problem to optimality as a linear program, the resultant formulation encompasses multiple feasible solutions that generally include optimal or near-optimal solutions to the original integer-restricted set partitioning formulation, thereby yielding a useful representation for designing heuristic methods as well as exact branch-and-price algorithms. In addition, using duality theory and considering set partitioning problems where the number of patterns needed to collectively compose a feasible solution is bounded, we have derived a lower bound on the objective value that is updated at every LP phase iteration. By virtue of this sequence of lower bounds and the availability of upper bounds via the restricted master program at every LP phase iteration, the LP relaxation of the set partitioning problem is efficiently solved as using a pre-specified optimality tolerance. This yields enhanced algorithmic performance due to early termination strategies that successfully mitigate the tailing-off effect that is commonly witnessed for simplex-based column generation approaches. / Ph. D.

In formulating discrete optimization problems, it is not only important to have a correct mathematical model, but to have a well structured model that can be solved effectively. Two important characteristics of a general integer or mixed-integer program are its size (the number of constraints and variables in the problem), and its strength or tightness (a measure of how well it approximates the convex hull of feasible solutions). In designing model formulations, it is critical to ensure a proper balance between compactness of the representation and the tightness of its linear relaxation, in order to enhance its solvability. In this dissertation, we consider these issues pertaining to the modeling of mixed-integer 0-1 programming problems in general, as well as in the context of several specific real-world applications, including a telecommunications network design problem and an airspace management problem. We first consider the Reformulation-Linearization Technique (RLT) of Sherali and Adams and explore the generation of reduced first-level representations for mixed-integer 0-1 programs that tend to retain the strength of the full first-level linear programming relaxation. The motivation for this study is provided by the computational success of the first-level RLT representation (in full or partial form) experienced by several researchers working on various classes of problems. We show that there exists a first-level representation having only about half the RLT constraints that yields the same lower bound value via its relaxation. Accordingly, we attempt to a priori predict the form of this representation and identify many special cases for which this prediction is accurate. However, using various counter-examples, we show that this prediction as well as several variants of it are not accurate in general, even for the case of a single binary variable. Since the full first-level relaxation produces the convex hull representation for the case of a single binary variable, we investigate whether this is the case with respect to the reduced first-level relaxation as well, and show similarly that it holds true only for some special cases. Empirical results on the prediction capability of the reduced, versus the full, first-level representation demonstrate a high level of prediction accuracy on a set of random as well as practical, standard test problems. Next, we focus on a useful modeling concept that is frequently ignored while formulating discrete optimization problems. Very often, there exists a natural symmetry inherent in the problem itself that, if propagated to the model, can hopelessly mire a branch-and-bound solver by burdening it to explore and eliminate such alternative symmetric solutions. We discuss three applications where such a symmetry arises. For each case, we identify the indistinguishable objects in the model which create the problem symmetry, and show how imposing certain decision hierarchies within the model significantly enhances its solvability. These hierarchies render an otherwise virtually intractable formulation computationally viable using commercial software. For the first problem, we consider a problem of minimizing the maximum dosage of noise to which workers are exposed while working on a set of machines. We next examine a problem of minimizing the cost of acquiring and utilizing machines designed to cool large facilities or buildings, subject to minimum operational requirements. For each of these applications, we generate realistic test beds of problems. The decision hierarchies allow all previously intractable problems to be solved relatively quickly, and dramatically decrease the required computational time for all other problems. For the third problem, we investigate 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 a placement 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 that exhibit the viability of the overall approach and that lend insights into various modeling and algorithmic constructs are presented. Following this we turn our attention to the modeling and analysis of several issues related to airspace management. Currently, commercial aircraft are routed along certain defined airspace corridors, where safe minimum separation distances between aircraft may be routinely enforced. However, this mode of operation does not fully utilize the available airspace resources, and may prove to be inadequate under future National Airspace (NAS) scenarios involving new concepts such as Free-Flight. This mode of operation is further compounded by the projected significant increase in commercial air traffic. (Free-Flight is a paradigm of aircraft operations which permits the selection of more cost-effective routes for flights rather than simple traversals between designated way-points, from various origins to different destinations.) We begin our study of Air Traffic Management (ATM) by first developing an Airspace Sector Occupancy Model (AOM) that identifies the occupancies of flights within three dimensional (possibly nonconvex) regions of space called sectors. The proposed iterative procedure effectively traces each flight's progress through nonconvex sector modules which comprise the sectors. Next, we develop an Aircraft Encounter Model (AEM), which uses the information obtained from AOM to efficiently characterize the number and nature of blind-conflicts (i.e., conflicts under no avoidance or resolution maneuvers) resulting from a selected mix of flight-plans. Besides identifying the existence of a conflict, AEM also provides useful information on the severity of the conflict, and its geometry, such as the faces across which an intruder enters and exits the protective shell or envelope of another aircraft, the duration of intrusion, its relative heading, and the point of closest approach. For purposes of evaluation and assessment, we also develop an aggregate metric that provides an overall assessment of the conflicts in terms of their individual severity and resolution difficulty. We apply these models to real data provided by the Federal Aviation Administration (FAA) for evaluating several Free-Flight scenarios under wind-optimized and cruise-climb conditions. We digress at this point to consider a more general collision detection problem that frequently arises in the field of robotics. Given a set of bodies with their initial positions and trajectories, we wish to identify the first collision that occurs between any two bodies, or to determine that none exists. For the case of bodies having linear trajectories, we construct a convex hull representation of the integer programming model of Selim and Almohamad, and exhibit the relative effectiveness of solving this problem via the resultant linear program. We also extend this analysis to model a situation in which bodies move along piecewise linear trajectories, possibly rotating at the end of each linear translation. For this case, we again compare an integer programming approach with its linear programming convex hull representation, and exhibit the relative effectiveness of solving a sequence of problems based on applying the latter construct to each time segment. Returning to Air Traffic Management, another future difficulty in airspace resource utilization stems from a projected increase in commercial space traffic, due to the advent of Reusable Launch Vehicle (RLV) technology. Currently, each shuttle launch cordons off a large region of Special Use Airspace (SUA) in which no commercial aircraft are permitted to enter for the specified duration. Of concern to airspace planners is the expense of routinely disrupting air traffic, resulting in circuitous diversions and delays, while enforcing such SUA restrictions. To provide a tool for tactical and planning purposes in such a context within the framework of a coordinated decision making process between the FAA and commercial airlines, we develop an Airspace Planning Model (APM). Given a set of flights for a particular time horizon, along with (possibly several) alternative flight-plans for each flight that are based on delays and diversions due to special-use airspace (SUA) restrictions prompted by launches at spaceports or weather considerations, this model prescribes a set of flight-plans to be implemented. The model formulation seeks to minimize a delay and fuel cost based objective function, subject to the constraints that each flight is assigned one of the designated flight-plans, and that the resulting set of flight-plans satisfies certain specified workload, safety, and equity criteria. These requirements ensure that the workload for air-traffic controllers in each sector is held under a permissible limit, that any potential conflicts which may occur are routinely resolvable, and that the various airlines involved derive equitable levels of benefits from the overall implemented schedule. In order to solve the resulting 0-1 mixed-integer programming problem more effectively using commercial software (CPLEX-MIP), we explore the use of various facetial cutting planes and reformulation techniques designed to more closely approximate the convex hull of feasible solutions to the problem. We also prescribe a heuristic procedure which is demonstrated to provide solutions to the problem that are either optimal or are within 0.01% of optimality. Computational results are reported on several scenarios based on actual flight data obtained from the Federal Aviation Administration (FAA) in order to demonstrate the efficacy of the proposed approach for air traffic management (ATM) purposes. In addition to the evaluation of these various models, we exhibit the usefulness of this airspace planning model as a strategic planning tool for the FAA by exploring the sensitivity of the solution provided by the model to changes both in the radius of the SUA formulated around the spaceport, and in the duration of the launch-window during which the SUA is activated. / Ph. D.

Traffic incidents routinely impact the flow of vehicles on roadways. These incidents need to be identified, and responded to in a timely fashion in order to keep traffic moving safely and efficiently. One of the main areas of transportation research that remains of contemporary interest is the study of travel times. Travel time information technologies, until very recently, have not been efficient enough to provide instantaneous information for managing traffic flow. The Virginia Department of Transportation (VDOT) currently operates a number of surveillance technologies. Of particular interest to us are Automatic Vehicle Identification (AVI) tag readers to assimilate travel time information. One of VDOT's latest research thrusts has been to develop efficient algorithms for estimating link travel times using such advanced technologies. To achieve this purpose, VDOT is currently monitoring volunteer tagged cars by using AVI tag readers fixed at certain specific locations. This thesis focuses on devising an efficient methodology to capture as much travel time information as possible, by solving a Reader Location Problem that maximizes the benefit accruing from measuring travel time variability with respect to freeways. This problem is formulated as a quadratic 0-1 optimization problem. The objective function parameters in the optimization problem represent certain benefit factors resulting from the ability to measure travel time variability along various origin-destination paths. A simulation study using the INTEGRATION package is performed to derive these benefit factors for various types of freeway sections, and two composite functions that measure benefits for O-D paths that are comprised of several such sections are presented. The simulation results are presented as generic look-up tables, and can be used for any freeway section for the purpose of computing the associated benefit factor coefficient. An optimization approach based on the Reformulation-Linearization Technique coupled with Semidefinite Programming concepts is designed to solve the formulated reader location problem. This approach can be used to derive alternative equivalent formulations of the problem that vary in the degree of tightness of their underlying linear programming relaxations. Four such model representations are explored by using the software package, AMPL-CPLEX 6.5.3, to solve them for some sample transportation networks. The sensitivity of the reader locations to the different proposed benefit factor composite functions is also investigated. The results indicate that the first level continuous RLT relaxation to problem RL produces a tight underlying representation and that the optimal solution obtained for this relaxation tends to be very close to the actual integer optimum. Moreover, it is found that the optimal locations of the readers are insensitive to either the traffic, or the benefit factor used, or the density of the graph, when these factors are considered individually. However, a combination of two or more of these factors can lead to a change in the optimal locations of the readers. / Master of Science

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. / Ph. D.

This dissertation is devoted to the development of new flow-based formulations for the asymmetric traveling salesman problem (ATSP) and to the demonstration of their applicability in effectively solving some scheduling problems. The ATSP is commonly encountered in the areas of manufacturing planning and scheduling, and transportation logistics. The integration of decisions pertaining to production and shipping, in the supply chain context, has given rise to an additional and practical relevance to this problem especially in situations involving sequence-dependent setups and routing of vehicles. Our objective is to develop new ATSP formulations so that algorithms can be built by taking advantage of their relaxations (of integer variables, thereby, resulting in linear programs) to effectively solve large-size problems. In view of our objective, it is essential to have a formulation that is amenable to the development of an effective solution procedure for the underlying problem. One characteristic of a formulation that is helpful in this regard is its tightness. The tightness of a formulation usually refers to the quality of its approximation to the convex hull of integer feasible solutions. Another characteristic is its compactness. The compactness of a formulation is measured by the number of variables and constraints that are used to formulate a given problem. Our formulations for the ATSP and the scheduling problems that we address are both tight and compact. We present a new class of polynomial length formulations for the asymmetric traveling salesman problem (ATSP) by lifting an ordered path-based model using logical restrictions in concert with the Reformulation-Linearization Technique (RLT). We show that a relaxed version of this formulation is equivalent to a flow-based ATSP model, which, in turn, is tighter than the formulation based on the exponential number of Dantzig-Fulkerson-Johnson (DFJ) subtour elimination constraints. The proposed lifting idea is applied to derive a variety of new formulations for the ATSP, and a detailed analysis of these formulations is carried out to show that some of these formulations are the tightest among those presented in the literature. Computational results are presented to exhibit the relative tightness of our formulations and the efficacy of the proposed lifting process.> While the computational results demonstrate the efficacy of employing the proposed theoretical RLT and logical lifting ideas, yet it remains of practical interest to take due advantage of the tightest formulations. The key requirement to accomplish this is the ability to solve the underlying LP relaxations more effectively. One approach, to that end, is to solve these LP relaxations to (near-) optimality by using deflected subgradient methods on Lagrangian dual formulations. We solve the LP relaxation of our tightest formulation, ATSP6, to (near-) optimality by using a deflected subgradient algorithm with average direction strategy (SA_ADS) (see Sherali and Ulular [69]). We also use two nondifferentiable optimization (NDO) methods, namely, the variable target value method (VTVM) presented by Sherali et al. [66] and the trust region target value method (TRTV) presented by Lim and Sherali [46], on the Lagrangian dual formulation of ATSP6. The preliminary results show that the near-optimal values obtained by the VTVM on solving the problem in the canonical format are the closest to the target optimal values. Another approach that we use is to derive a set of strong valid inequalities based on our tighter formulations through a suitable surrogation process for inclusion within the more compact manageable formulations. Our computational results show that, when the dual optimal solution is available, the associated strong valid inequalities generated from our procedure can successfully lift the LP relaxation of a less tight formulation, such as ATSP2R¯, to be as tight as the tightest formulation, such as ATSP6. We extend our new formulations to include precedence constraints in order to enforce a partial order on the sequence of cities to be visited in a tour. The presence of precedence constraints within the ATSP framework is encountered quite often in practice. Examples include: disassembly optimization (see Sarin et al. [62]), and scheduling of wafers/ ICs on automated testing equipments in a semiconductor manufacturing facility (see Chen and Hsia [17]); among others. Our flow-based ATSP formulation can very conveniently capture these precedence constraints. We also present computational results to depict the tightness of our precedence-constrained asymmetric traveling salesman problem (PCATSP) formulations. We, then, apply our formulations to the hot strip rolling scheduling problem, which involves the processing of hot steel slabs, in a pre-specified precedence order, on one or more rollers. The single-roller hot strip rolling scheduling problem can be directly formulated as a PCATSP. We also consider the multiple-roller hot strip rolling scheduling problem. This gives rise to the multiple-asymmetric traveling salesman problem (mATSP). Not many formulations have been presented in the literature for the mATSP, and there are none for the mATSP formulations involving a precedence order among the cities to be visited by the salesmen, which is the case for the multiple-roller hot strip rolling scheduling problem. To begin with, we develop new formulations for the mATSP and show the validity of our formulations, and present computational results to depict their tightness. Then, we extend these mATSP formulations to include a pre-specified, special type of precedence order in which to process the slabs, and designate the resulting formulations as the restricted precedence-constrained multiple-asymmetric traveling salesman problem (rPCmATSP) formulations. We directly formulate the multiple-roller hot strip rolling scheduling problem as a rPCmATSP. Furthermore, we consider the hot strip rolling scheduling problem with slab selection in which not all slabs need to be processed. We model the single-roller hot strip rolling scheduling problem with slab selection as a multiple-asymmetric traveling salesman problem with exactly two traveling salesmen. Similarly, the multiple-roller hot strip rolling scheduling problem with slab selection is modeled as a multiple-asymmetric traveling salesman problem with (m+1) traveling salesmen. A series of computational experiments are conducted to exhibit the effectiveness of our formulations for the solution of hot strip rolling scheduling problems. Furthermore, we develop two mixed-integer programming algorithms to solve our formulations. These are based on Benders&#900; decomposition [13] and are designated Benders&#900; decomposition and Modified Benders&#900; methods. In concert with a special type of precedence order presented in the hot strip rolling scheduling problems, we further introduce an adjustable density ratio of the associated precedence network and we use randomly generated test problems to study the effect of various density ratios in solving these scheduling problems. Our experimentation shows the efficacy of our methods over CPLEX. Finally, we present a compact formulation for the job shop scheduling problem, designated as JSCD (job shop conjunctive-disjunctive) formulation, which is an extension of our ATSP formulations. We use two test problems given in Muth and Thompson [53] to demonstrate the optimal schedule and the lower bound values obtained by solving the LP relaxations of our formulations. However, we observe that the lower bound values obtained by solving the LP relaxations of all variations of our JSCD formulation equal to the maximum total processing time among the jobs in the problem. / Ph. D.

This dissertation develops efficient solution techniques for general and problem-specific applications within nonconvex optimization, exploiting the constructs of the Reformulation-Linearization Technique (RLT). We begin by developing a technique to enhance general problems in nonconvex optimization through the use of a new class of RLT cuts, called semidefinite cuts. While these cuts are valid for any general problem for which RLT is applicable, we demonstrate their effectiveness in optimizing a nonconvex quadratic objective function over a simplex. Computational results indicate that on average, the semidefinite cuts have reduced the number of nodes in the branch-and-bound tree by a factor of 37.6, while decreasing solution time by a factor of 3.4. The semidefinite cuts have also led to a significant reduction in the optimality gap at termination, in some cases producing optimal solutions for problems that could not be solved using RLT alone. We then narrow our focus to the class of mixed-integer programming (MIP) problems, and develop a modification of Benders' decomposition method using concepts from RLT and lift-and-project cuts. This method is particularly motivated by the class of two-stage stochastic programs with integer recourse. The key idea is to design an RLT or lift-and-project cutting plane scheme for solving the subproblems where the cuts generated have right-hand sides that are functions of the first-stage variables. An illustrative example is provided to elucidate the proposed approach. The focus is on developing a first comprehensive finitely convergent extension of Benders' methodology for problems having 0-1 mixed-integer subproblems. We next address a specific challenging MIP application known as the facility layout problem, and we significantly improve its formulation through outer-linearization techniques and concepts from disjunctive programming. The enhancements produce a substantial increase in the accuracy of the layout produced, while at the same time, providing a dramatic reduction in computational effort. Overall, the maximum error in department size was reduced from about 6% to nearly zero, while solution time decreased by a factor of 110. Previously unsolved test problems from the literature that had defied even approximate solution methods have been solved to exact optimality using our proposed approach. / Ph. D.