Systems Engineering Optimization and Operations Research (SEOOR) Algoritmi R&D Centre University of Minho

---

Project POSI / 1999 / SRI / 35568, Algorithms for Large Scale Integer Programming

---

Âmbito do projecto:

A Programação Inteira é uma técnica do âmbito da Investigação Operacional que tem vindo a ser largamente aplicada ao longo das últimas décadas na modelação e resolução de problemas reais. Recentemente, tem havido um renovado interesse na técnica de geração de colunas por ter sido utilizada com sucesso na resolução de problemas maiores e mais complexos, considerando restrições que eram frequentemente ignoradas no passado.

É hoje possível resolver modelos que incluem as principais questões suscitadas em problemas reais, como restrições temporais e laborais, fornecendo soluções usáveis optimizadas. Este trabalho tem tido um enorme impacto económico em áreas como a logística e a distribuição, ou a indústria de transportes aéreos. Problemas de escalonamento e de encaminhamento de veículos com restrições temporais e de planeamento de escalas de pessoal tripulante são dois exemplos de tipos de problemas que hoje podem ser resolvidos rotineiramente, proporcionando soluções que representam grandes economias anuais.

A geração de colunas foi também combinada com sucesso com o método da partição e avaliação sucessivas para obter a solução óptima inteira de instâncias maiores de alguns problemas de programação inteira e de optimização combinatória. O desenvolvimento de algoritmos baseados na combinação destes dois métodos é bastante recente, embora eles sejam já conhecidos há mais de três décadas. Esta técnica foi designada por método da partição e geração de colunas. Usando esta metodologia, foi possível resolver instâncias maiores de muitos problemas de programação inteira.

A grande maioria dos modelos desenvolvidos têm variáveis binárias. Há, no entanto, muitos problemas importantes que têm variáveis inteiras gerais, como o problema de corte de stocks, o problema de fluxo multicomodidade geral e muitos problemas na área de planeamento de operações. Em trabalho anterior, desenvolvemos uma abordagem para o problema de corte que fornece directamente uma metodologia que pode ser usada na resolução de muitos problemas com variáveis inteiras gerais, usando o método da partição e geração de colunas. Esta abordagem é aplicável em problemas que podem ser representados como modelos de fluxo em rede, possivelmente com restrições adicionais.

A ideia central é a seguinte: as soluções são representadas através de uma decomposição de fluxos, e procura-se uma decomposição de fluxo inteira usando uma estratégia de partição que impõe restrições nos fluxos. Pode ser mostrado que esta metodologia é equivalente à decomposição de Dantzig-Wolfe, pelo que fornece relaxações de igual qualidade. No entanto, fornece uma perspectiva que pode ser usada para derivar regras de partição mais balanceadas e poderosas, como as que resultam de partições efectuadas sobre hiperplanos, e cortes primais expressos em função das variáveis originais. É sabido que estas questões são de importância crucial.

Os processos de geração de colunas têm habitualmente caudas longas e convergência lenta. Em trabalho anterior, introduzimos a ideia de usar cortes duais na resolução da relaxação linear do problema de corte de stocks. Foi mostrado que inserindo um número polinomial de cortes duais no problema primal restrito ajudava a reduzir o número de colunas geradas, o número de pivots degenerados, e o tempo computacional.

O âmbito deste projecto é o desenvolvimento algoritmos ao nível do estado da arte para resolver problemas de programação de operações usando estas novas ideias.

Scope of project:

Integer Programming is a technique of Operations Research that has been widely applied in the last decades in modeling and solving real problems. Recently, there is a renewed interest in column generation since it has been successfully used to solve larger and more complex real problems, considering constraints that were often ignored before. It is now possible to solve models that include the main issues that arise in real problems, such as time and labor constraints, and provide usable optimized solutions. This work has had a huge economic impact in areas as logistics and distribution, or the airline industries. Time constrained vehicle scheduling and routing problems and airline crew scheduling problems are two examples of problems that can now be solved routinely, providing solutions that represent very large annual savings.

Column generation has also been successfully combined with branch-and-bound to obtain the optimum integer solution of larger instances of some integer programming and combinatorial optimization problems. The development of algorithms based on this combination is fairly recent, even though both methods are known for more than three decades. This technique has been denoted as branch-and-price. Using this methodology, it has been possible to solve larger instances of many integer programming problems.

Most of the models that were developed have binary variables. There are, however, many important problems that have general integer variables, as the cutting-stock problem, the general multicommodity flow problem and many problems in the area of scheduling. We developed an approach for the solution of cutting-stock problems that directly provides a framework to be used in the solution of many problems with general integer variables using branch-and-price. The approach is applicable to problems that can be represented as network flow models, possibly with side constraints.

The main idea is as follows: solutions are represented by flow decomposition, and we search a integer flow decomposition by using a branching strategy that imposes constraints on the flows. It can be shown that this methodology is equivalent to Dantzig-Wolfe decomposition, so the models have equal strength. However, it provides additional insight, that can be used to derive more balanced and powerful branching rules, as the ones that result from hyperplane branching, and primal cuts expressed in terms of the original variables.

It is known that these issues are of crucial importance.

Column generation processes are known to have long tails, and slow convergence. We introduced the idea of using dual cuts in the solution of linear programming relaxation of cutting-stock problems. We showed that inserting a polynomial number of dual cuts in the restricted master problem helps reducing the number of columns generated, the number of degenerate pivots, and computational time.

The scope of this project is to develop state-of-the-art algorithms for the solution of cutting-stock, scheduling and multicommodity models using these new ideas.

.

Publications:

Book Chapter

Hatem Ben Amor, J.M. Valério de Carvalho, "Cutting Stock Problems", in "Column Generation", Guy Desaulniers, Jacques Desrosiers, and Marius M. Solomon (eds.), pp. 131-162, Springer, 2005, ISBN: 0-387-25485-4

Papers

J.M. Valério de Carvalho, "LP Models for Bin-Packing and Cutting Stock Problems", European Journal of Operational Research, 141, 2, 253-273, 2002.

J.M. Valério de Carvalho, "A note on branch-and-price algorithms for the one-dimensional cutting stock problem", Computational Optimization and Applications, 21, 3, 339-340, 2002

J.M. Valério de Carvalho, "Using extra dual cuts to accelerate convergence in column generation", INFORMS Journal on Computing, 17, 2, pp. 175-182, 2005.

Hatem Ben Amor, Jacques Desrosiers, J.M. Valério de Carvalho, "Dual-optimal Inequalities for Stabilized Column Generation", Operations Research 54 (3) 2006, pp. 454--463.

Lopes, M.P; Valério de Carvalho, J.M., A branch-and-price algorithm for scheduling parallel machines with sequence dependent setup times, European Journal of Operational Research, 176, 3, pp. 1508-1527, 2007.

Filipe Alvelos, J. M. Valério de Carvalho, "An extended model and a column generation algorithm for the planar multicommodity flow problem", Networks, Volume 50, Issue 1, pp. 3-16, 2007.

Papers in Proceedings

Filipe Alvelos, J. M. Valério de Carvalho, Antonio Frangioni, "Comparing Lagrangean approaches for Multicommodity Network Design problems", EURO/INFORMS 2003, 6-10 Julho, Instambul, Turquia, 2003

Filipe Alvelos, J. M. Valério de Carvalho, "Comparing Branch-and-price Algorithms for the Unsplittable Multicommodity Flow Problem", Proceedings do INOC 2003, International Network Optimization Conference, Paris, 2003

Filipe Alvelos, J. M. Valério de Carvalho, "Using Cycle Variables to Accelerate Column Generation in Planar Multicommodity Flows", Proceedings do INOC 2005, International Network Optimization Conference, Lisboa, 2005.

Other papers

F.Alvelos, J.M. Valério de Carvalho, "Aplicação do método de partição e geração de colunas ao problema fluxo multicomodidade inteiro", Investigação Operacional, 21, 1, 71-92, 2001.

Cláudio M. Alves e J.M. Valério de Carvalho, "Planeamento de rotas num sistema de recolha de desperdícios de madeira", Investigação Operacional, 24,1, pp. 21-43, 2004.

Communications

Filipe Alvelos e J.M. Valério de Carvalho, "A branch-and-price algorithm for the multicommodity flow problem", Eleventh Young Operational Research Conference, Cambridge, U.K., March 28-30, 2000.

J.M.Valério de Carvalho, "Branch-and-price with general integer variables", ISMP'2000, International Symposium in Mathematical Programming, Atlanta, USA, 7-11 Agosto 2000.

J.M.Valério de Carvalho, "Using extra dual cuts to accelerate convergence in column generation", INFORMS San Antonio Fall 2000, San Antonio, USA, 5-8 Novembro 2000

J.M.Valério de Carvalho, "A branch-and-price algorithm for the one-dimensional cutting stock problem", IFORS 2002, 16th Triennial Conference of the International Federation of Operational Research Societies, Edinburgh, 8-12 Julho 2002 (integrada na stream convidada Cutting and Packing (SICUP workshop) organizada por J.M. Valério de Carvalho).

Cláudio Alves and J. M. Valério de Carvalho, "A stabilized branch-and-price algorithm for the variable sized bin-packing problem", Optimization Days, Montréal, 5-8 Maio 2003.

Filipe Alvelos, J. M. Valério de Carvalho, Antonio Frangioni, "Comparing Lagrangean approaches for Multicommodity Network Design problems", EURO/INFORMS 2003, 6-10 Julho, Instambul, Turquia, 2003.

A. Frangioni, F. Alvelos, J. M. Valério de Carvalho, "Comparing Lagrangean approaches for Multicommodity Network Design problems", XXXIV Conferenza Annuale Associazione Italiana di Ricerca Operativa, Venezia, September, 2003.

Filipe Alvelos, J. M. Valério de Carvalho, "Accelerating Column Generation for Planar Multicommodity Flow Problems", EURO/INFORMS 2003, 6-10 Julho, Instambul, Turquia, 2003

F. Alvelos, J. M. Valério de Carvalho, "Comparing Branch-and-price Algorithms for the Unsplittable Multicommodity Flow Problem", Proceedings of the "International Network Optimization Conference", pp. 7-12, October 27-29, 2003, Evry/Paris, France.

Cláudio Alves and J. M. Valério de Carvalho, "Integer Variable Sized Bin-packing Problems", Fifth Workshop on Cutting, Packing, and Related Topics, September, 9-11, Sao Paulo, Brazil, 2003

J. M. Valério de Carvalho, "Branch-and-Price and Other Topics in Column Generation", Fifth Workshop on Cutting, Packing, and Related Topics, September, 9-11, Sao Paulo, Brazil, 2003

Manuel Lopes, J.M. Valério de Carvalho, "Solving Parallel Machine Scheduling Problems by Column Generation", Optimization 2004 - Fifth International Conference on Optimization, Faculdade de Ciências da Universidade de Lisboa, Lisboa, 25-28 de Julho de 2004.

Cláudio Alves, J.M. Valério de Carvalho, "Accelerating Column Generation for the Single and Variable Sized Bin-Packing Problem", Optimization 2004 - Fifth International Conference on Optimization, Faculdade de Ciências da Universidade de Lisboa, Lisboa, 25-28 de Julho de 2004.

J.M. Valério de Carvalho, "Método de partição e geração de colunas em programação inteira", IO 2000, 9º Congresso da APDIO, Setúbal, 16-19 Abril 2000.

Filipe Alvelos e J.M. Valério de Carvalho, "Aplicação do método de partição e geração de colunas ao problema de fluxo multicomodidade", IO 2000, 9º Congresso da APDIO, Setúbal, 16-19 Abril 2000.

Manuel Lopes e J.M. Valério de Carvalho, "Problemas de programação de máquinas paralelas não-idênticas", IO 2000, 9º Congresso da APDIO, Setúbal, 16-19 Abril 2000.

J.M. Valério de Carvalho, "Uso de cortes duais extra para acelerar processos de geração de colunas", IO 2000, 9º Congresso da APDIO, Setúbal, 16-19 Abril 2000.

Manuel J. Pereira Lopes, J. M. Valério de Carvalho, "Aplicação do método de partição e geração de colunas ao problema de programação de máquinas paralelas não-idênticas", io 2002, 10º Congresso da APDIO, Guimarães, 24-27 Março 2002.

Filipe Alvelos, J. M. Valério de Carvalho, "Fluxos multicomodidade e partição e geração de colunas em redes planares", io 2002, 10º Congresso da APDIO, Guimarães, 24-27 Março 2002.

Cláudio Alves, J. M. Valério de Carvalho, "Geração Estabilizada de Colunas Para Problemas de Empacotamento e Corte", IO2004 - 11º Congresso da APDIO, Faculdade de Engenharia da Universidade do Porto, 4-7 de Abril de 2004.

Filipe Alvelos, J. M. Valério de Carvalho, "Implementação do Método de Partição e Geração de Colunas", IO2004 - 11º Congresso da APDIO, Faculdade de Engenharia da Universidade do Porto, 4-7 de Abril de 2004.

Carina Pimentel, Filipe Alvelos, J. M .Valério de Carvalho, "Um Algoritmo de Partição e Geração de Colunas para um Problema de Lotes de Produção Multi-Artigo", IO2004 - 11º Congresso da APDIO, Faculdade de Engenharia da Universidade do Porto, 4-7 de Abril de 2004.

Manuel Pereira Lopes, José Valério de Carvalho, "Solving Parallel Machine Scheduling Problems by Column Generation", IO2004 - 11º Congresso da APDIO, Faculdade de Engenharia da Universidade do Porto, 4-7 de Abril de 2004.

Team:

José Manuel Vasconcelos Valério de Carvalho (coordinator)

Filipe Pereira Pinto da Cunha e Alvelos

Cláudio Manuel Martins Alves

Manuel Joaquim Pereira Lopes

António Jorge da Silva Trindade Duarte

Carina Maria Oliveira Pimentel (research grant)

Vítor Manuel Meneses Barbosa (research grant)

Funding:

União Europeia – Fundos Estruturais Governo da República Portuguesa