Algoritmos de feixe para programação linear inteira mista.

Abstract

Modelos de optimização são muito comuns na literatura das áreas da Investigação Operacional e das Ciências de Gestão. Neste trabalho, abordamos a resolução de uma classe de modelos de optimização conhecidos por modelos de programação linear disjuntiva, que se caracterizam por serem problemas de programação linear cuja região de admissibilidade é união de poliedros. Quase todos os problemas de optimização com- binatória (como o problema do caixeiro viajante, por exemplo) podem ser modelados como problemas de programação linear disjuntiva. Problemas de programação linear disjuntiva (incluindo muitos dos problemas de op- timização combinatória) são melhor resolvidos por métodos do tipo enumerativo (de- nominados branch-and-bound), eventualmente combinados com métodos de planos cortantes (denominados branch-and-cut). No caso de problemas de optimização combi- natória, os cortes mais e cazes são os que constituem facetas do poliedro associado. No caso de problemas sem estrutura identi cável, os cortes mais profundos propostos em [17] são vistos, em geral, como uma boa opção. Contudo, a sua caracterização obriga à resolução de um adequado problema de optimização cuja resolução algébrica obriga à duplicação de estruturas de dados. Em geral, não são conhecidas simpli cações se o problema possuir estrutura. Neste trabalho, mostramos como é possível gerar cortes mais profundos para problemas com estrutura como é o caso, por exemplo, dos problemas de optimização combinatória. Para a resolução do problema de optimização subjacente à caracterização do corte mais profundo, usaremos algoritmos de feixe (do inglês, bundle methods). O desenvol- vimento que efectuámos encontra-se fundamentalmente relacionado com o algoritmo proposto por P. Wolfe na década de 70 [128], que determina o ponto pertencente ao invólucro convexo de um conjunto nito de pontos que está mais próximo da origem, no sentido da norma Euclidiana. Assim, propomos uma generalização do algoritmo de P. Wolfe [128] para qualquer métrica, diferenciável ou não. Tal como aquele, o algoritmo que propomos é composto por um ciclo externo e um ciclo interno, termina ao m de um número nito de iterações e gera a mesma sucessão de pontos quando a métrica é a Euclidiana. O algoritmo foi implementado como gerador de cortes disjuntivos mais separadores em alguns problemas de programação inteira, com e sem estrutura, para uma selecção de problemas teste da MIPLIB e da ORLIB. Efectuámos um trabalho de síntese, inspirado em [91] e [43], no qual se demonstram que alguns cortes combinatórios bem conhecidos são válidos para determinadas relaxa- ções disjuntivas do problema de optimização combinatória subjacente. A identi cação dessas relaxações permitirá obter cortes mais profundos de acordo com a metodologia mencionada no parágrafo anterior. Os cortes combinatórios analisados dizem respeito aos problemas de partição por cliques, corte máximo, subdigrafo acíclico, ordenamento linear, cobertura de conjuntos e caixeiro viajante assimétrico. As provas apresentadas nesta dissertação usam argumentos primais e constituem uma alternativa às provas apresentadas em [91], cujo autor usou argumentos duais. Finalmente, procurou-se pôr em prática algumas das metodologias sugeridas num problema especí co de optimização combinatória. A versão assimétrica do problema do caixeiro viajante é um problema de optimização combinatória que tem vindo a servir de plataforma de teste para diversos métodos de resolução em optimização combinatória. Este facto e a importância de descobrir bons limites inferiores para este problema motivou a proposta de um algoritmo do tipo Lagrangeano para obter um limite inferior para o valor óptimo do problema do caixeiro viajante assimétrico, melhor do que o que advém do problema de afectação, através da resolução sucessiva de problemas de afectação. O algoritmo é um método de primeira ordem baseado na função de penalidade exponencial cujas direcções de deslocamento são de nidas com base numa relaxação disjuntiva que se propõe ser de dois tipos: uma baseada em ciclos e a outra baseada em cliques.Optimization models are very common in the Operations Research and Management Science literature. In this work, it is proposed the study of the solution of a class of optimization models known by disjunctive convex programs, witch are characterized as linear programs whose feasible region is the union of polyhedra. Almost any com- binatorial optimization problems (like the traveling salesman problem, for example) can be modeled as a disjunctive linear problem. Disjunctive linear programs (including many of the combinatorial optimization pro- blems) are best solved by methods of the enumerative type (called branch-and-bound) or combined with cutting planes methods (called branch-and-cut). In the case of combinatorial optimization problems, the most e cient cuts are the ones that induce facets of the associated polyhedron. In the case of problems without identi able structure, deepest cuts, considered in [17], are seen, in general, as a good option. However, its characterization compels to the resolution of one adequate optimization problem whose algebraic resolution involves the duplication of data structures. In general, simpli cations are not known if the problem possesses structure. In this work, we show how to to generate deepest cuts for problems with structure as it is the case, for example, of the combinatorial optimization problems. We will use bundle methods to solving the optimization problem underlying the characterization of the deepest cut. Our development is related to P. Wolfe's algorithm, developed in the 70's [128], for the problem of nding the nearest point of smallest Euclidean norm in the convex hull of a given nite point set. We consider a generalization of P. Wolfe's algorithm [128] for any metric, di erentiable or not. The algorithm we propose is composed of an external cycle and an internal cycle, stops after a nite number of iterations and generates the same iterates as Wolfe's algorithm for the Euclidean metric. The algorithm was implemented as a deepest disjunctive cut generator for some integer programming problems, with and without structure, and numerical results were obtained for a selection of test problems from MIPLIB and ORLIB. We made a synthesis work, inspired by [91] and [43], in which we demonstrate that some well known combinatorial cuts are valid for speci c disjunctive relaxations of the underlying combinatorial optimization problem. The identi cation of these relaxations will allow to get deeper cuts according to the methodology mentioned in the previous paragraph. Combinatorial problems that were analyze are clique partitioning, max- cut, acyclic subdigraph, linear ordering, covering partitioning and asymmetric trave- ling salesman problems. The proofs presented in this dissertation use primal arguments and are alternatives to the proofs in [91], whose author used dual arguments. Finally, it was looked to put in practice some of the methodologies suggested, in a speci c combinatorial optimization problem. The asymmetric version of the traveling salesman problem is a combinatorial problem frequently used as test platform for solutions methods in combinatorial optimization. This fact and the importance as nding good lower bounds for this problem motivated the proposal of an algorithm of the Lagrangean type, to get lower bounds for the optimal value of the asymmetric traveling salesman problem, that dominates the bound that comes from the assignment relaxation, through the solving of a sequence of assignment problems. The algorithm that we propose is a rst-order method based on the exponential penalty function. Directions of movement are derived from a disjunctive relaxation that we propose being one of two possible classes, one based on cycles, the other based on cliques.underlying combinatorial optimization problem. The identi cation of these relaxations will allow to get deeper cuts according to the methodology mentioned in the previous paragraph. Combinatorial problems that were analyze are clique partitioning, max- cut, acyclic subdigraph, linear ordering, covering partitioning and asymmetric trave- ling salesman problems. The proofs presented in this dissertation use primal arguments and are alternatives to the proofs in [91], whose author used dual arguments. Finally, it was looked to put in practice some of the methodologies suggested, in a speci c combinatorial optimization problem. The asymmetric version of the traveling salesman problem is a combinatorial problem frequently used as test platform for solutions methods in combinatorial optimization. This fact and the importance as nding good lower bounds for this problem motivated the proposal of an algorithm of the Lagrangean type, to get lower bounds for the optimal value of the asymmetric traveling salesman problem, that dominates the bound that comes from the assignment relaxation, through the solving of a sequence of assignment problems. The algorithm that we propose is a rst-order method based on the exponential penalty function. Directions of movement are derived from a disjunctive relaxation that we propose being one of two possible classes, one based on cycles, the other based on cliques.