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.

Made available in DSpace on 2014-07-29T16:02:20Z (GMT). No. of bitstreams: 1 Dissertacao Jose Carlos Rubianes Silva.pdf: 825326 bytes, checksum: f8797d1d8d333606ebad1d9941d5d26d (MD5) Previous issue date: 2011-02-18 / In this dissertation we consider a primal convex optimization problem and we study variants of subgradient method applied to the dual problem obtained via a Lagrangian function. We analyze the conditional subgradient method developed by Larsson et al, which is a variant of the usual subgradient method. In this variant, the subgradients are conditioned to a constraint set, more specifically, the behavior of the objective function outside of the constraint set is not taken into account. One motivation for studying such methods is primarily its simplicity, in particular, these methods are widely used in large-scale problems. The subgradient method, when applied to a dual problem, is relatively effective to obtain a good approximation of a dual solution and the optimal value, but it is not efficient to obtain primal solutions. We study a strategy to obtain good approximations of primal solutions via conditional subgradient method, under suitable additional computational costs. This strategy consists of constructing an ergodic sequence of solutions of the Lagrangian subproblems.We show that the limit points of this ergodic sequence are primal solutions. We consider different step sizes rule, in particular, following the ideas of Nedic and Ozdaglar, using the constant step size rule, we present estimates of the ergodic sequence and primal solutions and / or the feasible set. / Nesta dissertação consideramos um problema de otimização convexo e estudamos variações do método subgradiente aplicado ao problema dual obtido via uma função Lagrangiana. Estudamos o método subgradiente condicional desenvolvido por Larsson et al, o qual é uma simples variação do método subgradiente usual . A principal diferença é que os subgradientes são condicionados a um conjunto restrição, mais especificamente, o comportamento da função fora do conjunto restrição não é levado em conta. Uma motivação para estudar tais métodos consiste principalmente na sua simplicidade, em especial, estes métodos são bastante usados em problemas de grande porte. O método subgradiente, quando aplicado a um problema dual, é relativamente eficaz para obter boas aproximações de soluções duais e do valor ótimo, no entanto, não possue a mesma eficiência para obter soluções primais. Analisamos uma estratégia para obter boas aproximações de soluções primais via método subgradiente condicional, com pouco custo computacional adicional. Esta estratégia consiste em construir uma sequência ergódica das soluções obtidas durante a resolução dos subproblemas Lagrangianos. Mostraremos que os pontos limites desta sequência ergódica são soluções primais. Consideramos diferentes regras para o tamanho do passo, em particular, seguindo as idéias de Nedic e Ozdaglar, apresentamos estimativas da sequência ergódica com o conjunto de soluções primais e/ou o conjunto viável quando usamos a regra de passos constantes.

<p>Sweden experiences heavy snowfall during the winter season and cost effective road maintenance is significantly affected by the routing of snowplows. The routing problem becomes more complex as the SwedishNational Road Administration (Vägverket) sets operational requirements such as satisfying a time window for each road segment. </p><p>This thesis focuses on route optimization for snowplows after snowfall; to develop and implement an algorithm for finding combinations of generated routes which minimize the total cost. The results are compared to those stated in the licentiate thesis by Doctoral student Nima Golbaharan (2001). </p><p>The algorithm calculates a lower bound to the problem using a Lagrangian master problem. A common subgradient approach is used to find near-optimal dual variables to be sent to a column-generation program which returns routes for the snowplows. A greedy heuristic chooses a feasible solution, which gives an upper bound to the problem. This entire process is repeated as needed. </p><p>This method for routing snowplows produces favorable results with a relatively small number of routes and are comparable to Golbaharan's results. An interesting observation involves the allocation of vehicles in which certain depots were regularly over- or under-utilized. This suggests that the quantity and/or distribution of available vehicles may not be optimal.</p>

The purpose of this research is to develop a model and solution methodology for selecting and scheduling timely and cost-effective maintenance, rehabilitation, and reconstruction activities (M & R) for each pavement section in a highway network and allocating the funding levels through a finite multi-period horizon within the constraints imposed by budget availability in each period, frequency availability of activities, and specified minimum pavement quality requirements. M & R is defined as a chronological sequence of reconstruction, rehabilitation, and major/minor maintenance, including a "do nothing" activity. A procedure is developed for selecting an M & R activity for each pavement section in each period of a specified extended planning horizon. Each activity in the sequence consumes a known amount of capital and generates a known amount of effectiveness measured in pavement quality. The effectiveness of an activity is the expected value of the overall gains in pavement quality rating due to the activity performed on a highway network over an analysis period. It is assumed that the unused portion of the budget for one period can be carried over to subsequent periods. Dynamic Programming (DP) and Branch-and-Bound (B-and-B) approaches are combined to produce a hybrid algorithm for solving the problem under consideratioin. The algorithm is essentially a DP approach in the sense that the problem is divided into smaller subproblems corresponding to each single period problem. However, the idea of fathoming partial solutions that could not lead to an optimal solution is incorporated within the algorithm to reduce storage and computational requirements in the DP frame using the B-and-B approach. The imbedded-state approach is used to reduce a multi-dimensional DP to a one-dimensional DP. For bounding at each stage, the problem is relaxed in a Lagrangean fashion so that it separates into longest-path network model subproblems. The values of the Lagrangean multipliers are found by a subgradient optimization method, while the Ford-Bellman network algorithm is employed at each iteration of the subgradient optimization procedure to solve the longest-path network problem as well as to obtain an improved lower and upper bound. If the gap between lower and upper bound is sufficiently small, then we may choose to accept the best known solutions as being sufficiently close to optimal and terminate the algorithm rather than continue to the final stage.

Sweden experiences heavy snowfall during the winter season and cost effective road maintenance is significantly affected by the routing of snowplows. The routing problem becomes more complex as the SwedishNational Road Administration (Vägverket) sets operational requirements such as satisfying a time window for each road segment. This thesis focuses on route optimization for snowplows after snowfall; to develop and implement an algorithm for finding combinations of generated routes which minimize the total cost. The results are compared to those stated in the licentiate thesis by Doctoral student Nima Golbaharan (2001). The algorithm calculates a lower bound to the problem using a Lagrangian master problem. A common subgradient approach is used to find near-optimal dual variables to be sent to a column-generation program which returns routes for the snowplows. A greedy heuristic chooses a feasible solution, which gives an upper bound to the problem. This entire process is repeated as needed. This method for routing snowplows produces favorable results with a relatively small number of routes and are comparable to Golbaharan's results. An interesting observation involves the allocation of vehicles in which certain depots were regularly over- or under-utilized. This suggests that the quantity and/or distribution of available vehicles may not be optimal.

In this study, a Lagrangean heuristic based on Lagrangean relaxation and subgradient optimization is proposed for the two-stage modular capacitated facility location problem. The objective is to minimize the cost of locating and operating plants and warehouses, plus the cost of transporting goods at both echelons to satisfy the demand of customers. The difference of our study from the two-stage capacitated facility location problem is the existence of multiple capacity levels as a candidate for each plant in the problem. Each capacity level has a minimum production capacity which has to be satisfied to open the relevant capacity level. Obviously, a single capacity level can be selected for an opened facility location. In the second echelon, the warehouses are capacitated and have unique fixed and variable costs for opening and operating. Multiple sourcing is allowed in both transportation echelons. Firstly, we develop a mixed integer linear programming model for the two-stage modular capacitated facility location problem. Then we develop a Lagrangean heuristic to solve the problem efficiently. Our Lagrangean heuristic consists of three main components: Lagrangean relaxation, subgradient optimization and a primal heuristic. Lagrangean relaxation is employed for obtaining the lower bound, subgradient optimization is used for updating the Lagrange multipliers at each iteration, and finally a three-stage primal heuristic is created for generating the upper bound solutions. At the first stage of the upper bound heuristic, global feasibility of the plants and warehouses is inspected and a greedy heuristic is executed, if there is a global infeasibility. At the next stage, an allocation heuristic is used to assign customers to warehouses and warehouses to plants sequentially. At the final stage of the upper bound heuristic, local feasibilities of the plants are investigated and infeasible capacity levels are adjusted if necessary. In order to show the efficiency of the developed heuristic, we have tested our heuristic on 280 problem instances generated randomly but systematically. The results of the experiments show that the developed heuristic is efficient and effective in terms of solution quality and computational effort especially for large instances.

As air traffic congestion grows, air traffic flow management (ATFM) is becoming a great concern. ATFM deals with air traffic and the efficient utilization of the airport and airspace. Air traffic efficiency is heavily influenced by unanticipated factors, or uncertainties, which can come from several sources such as mechanical breakdown; however, weather is the main unavoidable cause of uncertainty. Because weather is unpredictable, it poses a critical challenge for ATFM in current airport and airspace operations. Convective weather results in congestion at airports as well as in airspace sectors. During times of congestion, the decision as how and when to send aircraft toward an airspace sector in the presence of weather is difficult. To approach this problem, we first propose a two-stage stochastic integer program by emphasizing a given single sector. By considering ground delay, cancellation, and cruise speed for each flight on the ground in the first stage, as well as air holding and diversion recourse actions for each flight in the air in the second stage, our model determines how aircraft are sent toward a sector under the uncertainty of weather. However, due to the large number of weather scenarios, the model is intractable in practice. To overcome the intractability, we suggest a rolling horizon method to solve the problem to near optimal. Lagrangian relaxation and subgradient method are used to justify the rolling horizon method. Since the rolling horizon method can be solved in real time, we can apply it to actual aircraft schedules to reduce the costs incurred on the ground as well as in airspace. We then extend our two-stage model to a multistage stochastic program, which increases the number of possible weather realizations and results a more efficient schedule in terms of costs. The rolling horizon method as well as Lagrangian relaxation and subgradient method are applied to this multistage model. An overall comparison among the previously described methodologies are presented.

The purpose of this research is to develop a model and solution methodology for selecting and scheduling timely and cost-effective maintenance, rehabilitation, and reconstruction activities (M & R) for each pavement section in a highway network and allocating the funding levels through a finite multi-period horizon within the constraints imposed by budget availability in each period, frequency availability of activities, and specified minimum pavement quality requirements. M & R is defined as a chronological sequence of reconstruction, rehabilitation, and major/minor maintenance, including a "do nothing" activity. A procedure is developed for selecting an M & R activity for each pavement section in each period of a specified extended planning horizon. Each activity in the sequence consumes a known amount of capital and generates a known amount of effectiveness measured in pavement quality. The effectiveness of an activity is the expected value of the overall gains in pavement quality rating due to the activity performed on a highway network over an analysis period. It is assumed that the unused portion of the budget for one period can be carried over to subsequent periods. Dynamic Programming (DP) and Branch-and-Bound (B-and-B) approaches are combined to produce a hybrid algorithm for solving the problem under consideratioin. The algorithm is essentially a DP approach in the sense that the problem is divided into smaller subproblems corresponding to each single period problem. However, the idea of fathoming partial solutions that could not lead to an optimal solution is incorporated within the algorithm to reduce storage and computational requirements in the DP frame using the B-and-B approach. The imbedded-state approach is used to reduce a multi-dimensional DP to a one-dimensional DP. For bounding at each stage, the problem is relaxed in a Lagrangean fashion so that it separates into longest-path network model subproblems. The values of the Lagrangean multipliers are found by a subgradient optimization method, while the Ford-Bellman network algorithm is employed at each iteration of the subgradient optimization procedure to solve the longest-path network problem as well as to obtain an improved lower and upper bound. If the gap between lower and upper bound is sufficiently small, then we may choose to accept the best known solutions as being sufficiently close to optimal and terminate the algorithm rather than continue to the final stage.

Submitted by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-26T12:20:46Z No. of bitstreams: 2 Dissertação - Vando Antônio Adona - 2014.pdf: 1128475 bytes, checksum: a2d00afcaef383726904cf6e6fd3527d (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Approved for entry into archive by Luciana Ferreira (lucgeral@gmail.com) on 2015-03-27T10:48:07Z (GMT) No. of bitstreams: 2 Dissertação - Vando Antônio Adona - 2014.pdf: 1128475 bytes, checksum: a2d00afcaef383726904cf6e6fd3527d (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) / Made available in DSpace on 2015-03-27T10:48:07Z (GMT). No. of bitstreams: 2 Dissertação - Vando Antônio Adona - 2014.pdf: 1128475 bytes, checksum: a2d00afcaef383726904cf6e6fd3527d (MD5) license_rdf: 23148 bytes, checksum: 9da0b6dfac957114c6a7714714b86306 (MD5) Previous issue date: 2014-12-18 / Conselho Nacional de Pesquisa e Desenvolvimento Científico e Tecnológico - CNPq / We consider an optimization problem for which the objective function is the sum of convex functions, not necessarily differentiable. We study a subgradient method that executes the iterations incrementally selecting each component function sequentially and processing the subgradient iteration individually. We analyze different alternatives for choosing the step length, highlighting the convergence properties for each case. We also analyze the incremental model in other methods, considering proximal iteration and combinations of subgradient and proximal iterations. This incremental approach has been very successful when the number of component functions is large. / Consideramos um problema de otimização cuja função objetivo consiste na soma de funções convexas, não necessariamente diferenciáveis. Estudamos um método subgradiente que executa a iteração de forma incremental, selecionando cada função componente de maneira sequencial e processando a iteração subgradiente individualmente. Analisamos diferentes alternativas para a escolha do comprimento de passo, destacando as propriedades de convergência para cada caso. Abordamos também o modelo incremental em outros métodos, considerando iteração proximal e combinações de iterações subgradiente e proximal. Esta abordagem incremental tem sido muito bem sucedida quando o número de funções componentes é grande.

In this doctoral thesis, we propose new iterative methods for solving a class of convex optimization problems. In general, we consider problems in which the objective function is composed of a finite sum of convex functions and the set of constraints is, at least, convex and closed. The iterative methods we propose are basically designed through the combination of incremental subgradient methods and string-averaging algorithms. Furthermore, in order to obtain methods able to solve optimization problems with many constraints (and possibly in high dimensions), generally given by convex functions, our analysis includes an operator that calculates approximate projections onto the feasible set, instead of the Euclidean projection. This feature is employed in the two methods we propose; one deterministic and the other stochastic. A convergence analysis is proposed for both methods and numerical experiments are performed in order to verify their applicability, especially in large scale problems. / Nesta tese de doutorado, propomos novos métodos iterativos para a solução de uma classe de problemas de otimização convexa. Em geral, consideramos problemas nos quais a função objetivo é composta por uma soma finita de funções convexas e o conjunto de restrições é, pelo menos, convexo e fechado. Os métodos iterativos que propomos são criados, basicamente, através da junção de métodos de subgradientes incrementais e do algoritmo de média das sequências. Além disso, visando obter métodos flexíveis para soluções de problemas de otimização com muitas restrições (e possivelmente em altas dimensões), dadas em geral por funções convexas, a nossa análise inclui um operador que calcula projeções aproximadas sobre o conjunto viável, no lugar da projeção Euclideana. Essa característica é empregada nos dois métodos que propomos; um determinístico e o outro estocástico. Uma análise de convergência é proposta para ambos os métodos e experimentos numéricos são realizados a fim de verificar a sua aplicabilidade, principalmente em problemas de grande escala.