Techn. Hochsch., Diss., 2002--Aachen.

Dans ce document, nous étudions deux problèmes de sectorisation et proposons plusieurs méthodes de résolution exactes basées sur la décomposition de Dantzig-Wolfe et la génération de colonnes. Nous proposons deux modélisations en fonction de la manière d’appréhender l’objectif du problème qui consiste à obtenir des secteurs compacts. Pour chacune des modélisations, nous comparons des approches de résolution exactes basées sur des formulations compactes ou sur des formulations étendues obtenues par la décomposition de Dantzig-Wolfe. Le premier type de modèles proposé définit la fonction objectif à la manière d’un problème de p-median. Concernant les méthodes de résolution pour ce type de modèle, l’accent est mis sur l’accélération de la convergence de l’algorithme de génération de colonnes en mettant en place des techniques d’agrégation de contraintes afin de réduire la dégénérescence de l’algorithme du simplexe. Les expérimentations numériques montrent que la méthode d’agrégation de contraintes proposée permet effectivement de réduire le nombre d’itérations dégénérées. Cependant, elle ne suffit pas à accélérer l’algorithme de branch-and-price. Le choix d’utilisation de la formulation compacte ou de la formulation étendue dépend du type d’instances résolu. Le second type de modèles formule l’objectif d’une manière assez proche de celui des problèmes de p-centre. L’utilisation d’un tel objectif complexifie la résolution des sous-problèmes de génération de colonnes. L’accent est donc mis sur la conception d’algorithmes de branch-and-bound et de programmation dynamique pour les résoudre efficacement. Les expériences montrent que l’algorithme de branch-and-price surpasse les approches de résolution utilisant une formulation compacte du problème. / In this document, we study two districting problems and propose several exact methods, based on Dantzig-Wolfe decomposition and column generation, to solve them. For each model, we compare exact approaches based either on compact formulations or on extended formulations obtained using Dantzig-Wolfe decomposition. The first type of model that we propose defines the objective function in a p-median problem fashion. Regarding the methods used to solve that kind of model, we emphasize accelerating the convergence of the column generation algorithm by designing constraint aggregation techniques in order to reduce the degeneracy in the simplex algorithm. Numerical experiments show that this constraint aggregation method indeed reduces the proportion of degenerated iterations. However, it is not enough to speed up the branch-and-price algorithm. Choosing to tackle the problem through either a compact formulation or an extended formulation depends on the structure of the instances to solve. The second type of model formulates the objective function in a way quite similar to that of p-centre problems. Using such an objective function induces complex column generation subproblems. We focus on designing branch-and-bound and dynamic programming algorithms in order to solve them efficiently. Experiments show that the branch-and-price approach surpasses any proposed method based on compact formulations of the problem.

O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura / The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms

O problema de dimensionamento de lotes com restrições de capacidade (CLSP) consiste em determinar um plano de produção que satisfaça a demanda requerida, respeitando as limitações de capacidade, com o menor custo possível, ou seja, minimizando os custos de produção, estocagem e preparação de máquina. Encontrar uma solução factível para o CLSP, considerando tempo de preparação de máquina, é NP-completo. Nesta dissertação, para a resolução do CLSP, utiliza-se a decomposição de Dantzig-Wolfe e o procedimento de geração de colunas, encontrando bons limitantes inferiores. Duas diferentes estratégias de decomposição são exploradas, decomposição por itens e períodos. Para a obtenção de uma solução inteira para o problema (limitante superior) foram exploradas heurísticas lagrangianas, onde a solução inicial para as heurísticas provém da geração de colunas. Os limitantes obtidos podem ser utilizados em métodos exatos, como por exemplo, em algoritmos do tipo branch-and-price. Experimentos computacionais, baseados em exemplares gerados aleatoriamente, foram realizados e os resultados analisados, as variações dos parâmetros das instâncias foram sugeridas na literatura / The Capacitated Lot Sizing Problem (CLSP) consists in determining a production plan such that all demands are met and the total costs of production, inventory and setup are minimized. Since the problem to find a feasible solution to the CLSP with setup times is NP-complete, large problem instances have been solved by heuristic methods. In this dissertation, we are particularly concerned in using the methodology of Dantzig-Wolfe decomposition and column generation to generate good bounds to the CLSP with setup times and costs. Here, we analyse two types of decomposition which are based on items and time periods (lower bound) and some lagrangian-based heuristics (upper bound). Numerical results based on randomly generated intances suggest that highquality lower bounds are obtained by column generation algorithms, such as well as upper bounds by heuristics. These bounds are useful in exact solution methods, such as branch-and-price algorithms

Submitted by Aelson Maciera (aelsoncm@terra.com.br) on 2017-09-26T19:15:52Z No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Approved for entry into archive by Ronildo Prado (bco.producao.intelectual@gmail.com) on 2018-01-26T18:36:20Z (GMT) No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Approved for entry into archive by Ronildo Prado (bco.producao.intelectual@gmail.com) on 2018-01-26T18:36:39Z (GMT) No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) / Made available in DSpace on 2018-01-26T18:42:45Z (GMT). No. of bitstreams: 1 DissCDAC.pdf: 10114021 bytes, checksum: b3e4f52846924539caadab8587fe2250 (MD5) Previous issue date: 2017-03-10 / Conselho Nacional de Desenvolvimento Científico e Tecnológico (CNPq) / This work aims at treating the Dynamic Vehicle Allocation Problem (DVAP) in the context of the Brazilian Freight Transportation system. The problem consists of allocating empty vehicles to different terminals so as to attend the demand of freight transport during a predetermined planning horizon while maximizing the profit from these services. These type of decisions arise in customized freight transport services and in between-terminals operations of consolidation freight services. Given the size of the resulting models of real life problems confronted by third party logistics operators are large for using exact solution methods, heuristic methods have been used for giving good quality solution at the expense of optimality guarantee. In this context, the objective of this work is to contribute with solution methods that provide optimality guarantee or quality solution certificates for treating large-scale problems in reasonable computational times. The methods utilized are lagrangean relaxation, using subgradient optimization, and DantzigWolfe decomposition together with a lagrangian heuristic and factibilization method, respectively. Computational experiments are presented and analyzed for randomly generated instances and real-world instances from a brasilian freight operator. The latter method shows great potential for treating large-scale problems. / Este trabalho aborda o problema de Alocação Dinâmica de Veículos (PADV) no contexto de Transporte Rodoviário de Carga. O problema envolve alocar veículos de carga para atender a demanda de transporte de carga prevista entre terminais durante um horizonte de tempo multiperíodos e finito. O objetivo e maximizar o lucro gerado pelos serviços completados. Este tipo de decisões surge nos serviços de transporte de carga de lotação e na parcela de transporte de transferência dos serviços de transporte de carga consolidada. Dado que o tamanho dos problemas que enfrentam as transportadoras logísticas sÃo consideravelmente grandes parase resolver com métodos exatos em tempos computacionais aceitáveis, tem-se utilizado métodos heurísticos para dar boas soluções sem garantia de otimalidade mas em tempos toleráveis a estes problemas. Neste contexto, pretende-se contribuir com métodos de solução que proporcionem garantia de otimalidade e/ou boas soluções aproximadas, acompanhadas de certificados de otimalidade ou de qualidade de solução, para tratar problemas de porte em tempos razoáveis. Os métodos propostos estao baseados em relaxação lagrangiana, utilizando o método de otimização do subgradiente, e na decomposto de Dantzig Wolfe, utilizando a técnica de geração de colunas, além de heurísticas lagrangianas e de factibilização acopladas nestes métodos. Experimentos computacionais usando instâncias geradas aleatoriamente e baseados em dados reais de transportadoras brasileiras sao apresentados e analisados, para as duas abordagens, mostrando seus potenciais de aplicação pratica, principalmente para problemas de grande porte.

This thesis aims to study the theoretical complexity and empirical performance of decomposition algorithms. We focus on linear programs with a block-angular structure. Decomposition algorithms used to be the only way to solve large-scale special structured problems, in terms of memory limit and CPU time. However, with the advances in computer technology over the past few decades, many large-scale problems can now be solved simply by using some general purpose LP software, without exploiting the problems' inner structures. A question arises naturally, should we solve a structured problem with decomposition, or directly solve it as a whole? We try to understand how a problem's characteristics influence its computational performance, and compare the relative efficiency of algorithms with and without decomposition. Two comparisons are conducted in our research: first, the Dantzig-Wolfe decomposition method (DW) versus the simplex method (simplex); second, the analytic center cutting plane method (ACCPM) versus the interior point method (IPM). These comparisons fall into the two main solution approaches in linear programming: simplex-based algorithms and IPM-based algorithms. Motivated by our observations of ACCPM and DW decomposition, we devise a hybrid algorithm combining ACCPM and DW, which are the counterparts of IPM and simplex in the decomposition framework, to take the advantages of both: the quick convergence rate of IPM-based methods, as well as the accuracy of simplex-based algorithms. A large set of 316 instances is incorporated in our experiments, so that different dimensioned problems with primal or dual block-angular structures are covered to test our conclusions.

This thesis aims to study the theoretical complexity and empirical performance of decomposition algorithms. We focus on linear programs with a block-angular structure. Decomposition algorithms used to be the only way to solve large-scale special structured problems, in terms of memory limit and CPU time. However, with the advances in computer technology over the past few decades, many large-scale problems can now be solved simply by using some general purpose LP software, without exploiting the problems' inner structures. A question arises naturally, should we solve a structured problem with decomposition, or directly solve it as a whole? We try to understand how a problem's characteristics influence its computational performance, and compare the relative efficiency of algorithms with and without decomposition. Two comparisons are conducted in our research: first, the Dantzig-Wolfe decomposition method (DW) versus the simplex method (simplex); second, the analytic center cutting plane method (ACCPM) versus the interior point method (IPM). These comparisons fall into the two main solution approaches in linear programming: simplex-based algorithms and IPM-based algorithms. Motivated by our observations of ACCPM and DW decomposition, we devise a hybrid algorithm combining ACCPM and DW, which are the counterparts of IPM and simplex in the decomposition framework, to take the advantages of both: the quick convergence rate of IPM-based methods, as well as the accuracy of simplex-based algorithms. A large set of 316 instances is incorporated in our experiments, so that different dimensioned problems with primal or dual block-angular structures are covered to test our conclusions.

As the Army transitions to the Army Force Generation (ARFORGEN) deployment cycle, it must adjust its many operations in support of ARFORGEN. Specifically, the Initial Military Training (IMT) must be able to adjust the scheduling of its classes for newly enlisted service members to finish training such that they fulfill Brigade Combat Team (BCT) requirements within their common due windows. We formulate this problem as a lot streaming problem. Lot streaming splits a batch of jobs into sublots,which are then processed over the machines in an overlapping fashion. To schedule classes for the IMT, there are two stages that must be coordinated: Basic Training (BT) and Advanced Individual Training (AIT). For the Army Force Generation problem, the classes are considered as sublots that are streamed from one stage to the next. For this process, the model formulation must address determination of class sizes and scheduling of soldiers and classes at the two stages such that (1) the start times of the soldiers at Stage 2 are greater than their completion times at Stage 1, and (2) the assignment of requisite number of soldiers is made to each BCT, so as to minimize the total flow time. We propose a decomposition-based approach for the solution of this problem. In an effort to decompose the problem, the original lot streaming problem is reformulated such that the master problem selects an optimal combination of schedules for training classes and assigning soldiers to BCTs. A complete schedule selected in the master problem includes the assignments of soldiers to classes in BT, AIT, and their assignments to the BCTs, so as to minimize the total flow time as well as earliness and tardiness for regular Army units. Earliness and Tardiness are defined as the length of the time a soldier waits before and after the due date, respectively, of the BCT to which he or she is assigned. Our decomposition-based method enables solution of larger problem instances without running out of memory, and it affords CPU time reductions when compared with the CPU times required for these problem instances obtained via direct application of CPLEX 12.1. Our investigation into the structure of the problem has enabled further improvement of the proposed decomposition-based method. This improvement is achieved because of a result, which we show, that the first and second-stage scheduling problems need not be solved as one combined subproblem, but rather, they can be solved sequentially, the first stage problem followed by the second stage problem. The combination of Stage 1 and Stage 2 problems as one subproblem creates several additional enumerations of possible schedules the model must generate. By reducing this number of enumerations, the computational effort involved in solving the model reduces significantly, thereby allowing reductions in CPU time. In the Sequential approach, the completion times of soldiers determined at Stage 1 are passed to Stage 2 as bounds on their completion times at Stage 2. We prove that solving the combined subproblem sequentially as two subproblems is optimal when the first stage has no limit on the batch size and the ready times of the soldiers at Stage 1 are the same. For the Army Force Generation problem, we use unequal ready times, and therefore, solving the scheduling problems for the first two stages as sequential subproblems can lead to suboptimal solutions. Our experimental investigation shows efficacy of solving larger-sized problem instances with this method. We also recommend various potential additions to improve the Sequential approach for application to the overall Army problem. We have also demonstrated the use of our methodology to a real-life problem instance. Our methodology results in schedules for IMT with an estimated 28% reduction in mean flow time for soldiers over what is currently experienced in practice. We apply this Sequential approach to various extensions of the problem on hand that pertain to hybrid flow shop and agile manufacturing environments. Results of our computational investigation show the effectiveness of using the Sequential approach over direct solution by CPLEX from the viewpoint of both optimality gap and the CPU time required. In particular, we consider two different model configurations for a hybrid flow shop and three different model configurations for an agile manufacturing facility. / Ph. D.

This thesis proposes equilibrium models to link the wholesale and retail electricity markets which allow for reconciliation of the differing time scales of responses of producers (e.g., hourly) and consumers (e.g., monthly) to changing prices. Electricity market equilibrium models with time of use (TOU) pricing scheme are formulated as large-scale variational inequality (VI) problems, a unified and concise approach for modeling the equilibrium. The demand response is dynamic in these models through a dependence on the lagged demand. Different market structures are examined within this context. With an illustrative example, the welfare gains/losses are analyzed after an implementation of TOU pricing scheme over the single pricing scheme. An approximation of the welfare change for this analysis is also presented. Moreover, break-up of a large supplier into smaller parts is investigated. For the illustrative examples presented in the dissertation, overall welfare gains for consumers and lower prices closer to the levels of perfect competition can be realized when the retail pricing scheme is changed from single pricing to TOU pricing. These models can be useful policy tools for regulatory bodies i) to forecast future retail prices (TOU or single prices), ii) to examine the market power exerted by suppliers and iii) to measure welfare gains/losses with different retail pricing schemes (e.g., single versus TOU pricing). With the inclusion of linearized DC network constraints into these models, the problem size grows considerably. Dantzig-Wolfe (DW) decomposition algorithm for VI problems is used to alleviate the computational burden and it also facilitates model management and maintenance. Modification of the DW decomposition algorithm and approximation of the DW master problem significantly improve the computational effort required to find the equilibrium. These algorithms are applied to a two-region energy model for Canada and a realistic Ontario electricity test system. In addition to empirical analysis, theoretical results for the convergence properties of the master problem approximation are presented for DW decomposition of VI problems.

Un problème d'ordonnancement cyclique consiste à ordonner dans le temps l'exécution répétitive d'un ensemble d'opérations liées par des contraintes de précédence, en utilisant un nombre limité de ressources. Ces problèmes ont des applications immédiates dans les systèmes de production ou en informatique parallèle. Particulièrement, ils permettent de modéliser l'ensemble des contraintes de précédence et de ressource à prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une opération représente une instance d'une instruction dans un programme. L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel désigne une méthode efficace pour l'optimisation de boucles qui permet la réalisation en parallèle des opérations des différentes itérations de la boucle. Dans cette thèse, nous nous intéressons principalement au problème d'ordonnancement périodique qui est un cas particulier de l'ordonnancement cyclique et qui est également la base du pipeline logiciel. Le terme ordonnancement modulo désigne un ordonnancement périodique tel que l'allocation de ressources pour une opération donnée n'est pas modifiée d'une itération sur l'autre. Pour résoudre le problème, nous nous intéressons aux formulations de programmation linéaire en nombres entiers, et notamment à la résolution du problème par des techniques de séparation, évaluation, génération de colonnes, relaxation lagrangienne et des méthodes hybrides. En particulier, nous proposons des nouvelles formulations basées sur des variables binaires représentant l'exécution d'ensembles d'instructions en parallèle. Enfin, les méthodes développées ont été validées sur des jeux d'instances industrielles pour des processeurs de type VLIW. Un problème d'ordonnancement cyclique consiste à ordonner dans le temps l'exécution répétitive d'un ensemble d'opérations liées par des contraintes de précédence, en utilisant un nombre limité de ressources. Ces problèmes ont des applications immédiates dans les systèmes de production ou en informatique parallèle. Particulièrement, ils permettent de modéliser l'ensemble des contraintes de précédence et de ressource à prendre en compte pour l'ordonnancement d'instructions dans les processeurs de type VLIW (Very Long Instruction Word). Dans ce cas, une opération représente une instance d'une instruction dans un programme. L'ordonnancement d'instructions de boucles internes est connu sous le nom de pipeline logiciel. Le pipeline logiciel désigne une méthode efficace pour l'optimisation de boucles qui permet la réalisation en parallèle des opérations des différentes itérations de la boucle. Dans cette thèse, nous nous intéressons principalement au problème d'ordonnancement périodique qui est un cas particulier de l'ordonnancement cyclique et qui est également la base du pipeline logiciel. Le terme ordonnancement modulo désigne un ordonnancement périodique tel que l'allocation de ressources pour une opération donnée n'est pas modifiée d'une itération sur l'autre. Pour résoudre le problème, nous nous intéressons aux formulations de programmation linéaire en nombres entiers, et notamment à la résolution du problème par des techniques de séparation, évaluation, génération de colonnes, relaxation lagrangienne et des méthodes hybrides. En particulier, nous proposons des nouvelles formulations basées sur des variables binaires représentant l'exécution d'ensembles d'instructions en parallèle. Enfin, les méthodes développées ont été validées sur des jeux d'instances industrielles pour des processeurs de type VLIW.