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.
| Identifer | oai:union.ndltd.org:VTETD/oai:vtechworks.lib.vt.edu:10919/28199 |
| Date | 12 July 2007 |
| Creators | Ghoniem, Ahmed |
| Contributors | Industrial and Systems Engineering, Sherali, Hanif D., Bish, Ebru K., Koelling, C. Patrick, Sarin, Subhash C. |
| Publisher | Virginia Tech |
| Source Sets | Virginia Tech Theses and Dissertation |
| Detected Language | English |
| Type | Dissertation |
| Format | application/pdf |
| Rights | In Copyright, http://rightsstatements.org/vocab/InC/1.0/ |
| Relation | ghoniem-dissertation.pdf |
Page generated in 0.0041 seconds