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

---

Project POSC / EIA / 57203 / 2004, Models, algorithms and tools for large scale integer optimization

---

Âmbito do projecto:

A Programação Inteira é uma técnica da Investigação Operacional largamente usada na modelação e resolução de problemas reais. Na última década, houve um enorme incremento na investigação em geração de colunas e no método da partição e geração de colunas, devido ao seu sucesso na resolução de grandes instâncias de problemas de programação inteira e de optimização combinatória, usando modelos reformulados através da decomposição de Dantzig-Wolfe.

É hoje possível abordar problemas reais maiores e mais complexos, considerando as principais restrições e questões suscitadas em problemas reais, como restrições temporais e laborais, e obter soluções optimizadas usáveis. A investigação nesta área tem tido um enorme impacto económico em áreas como logística e distribuição, ou a indústria de transportes aéreos. O encaminhamento de veículos e o planeamento de pessoal tripulante são exemplos de problemas hoje resolvidos rotineiramente, com soluções que representam grandes economias anuais.

A geração de colunas é conhecida por ser robusta, mas de convergência lenta. Esforços de investigação recentes são dedicados à obtenção de algoritmos mais rápidos. Isto pode ser conseguido com métodos de estabilização e aceleração, e com formulações mais fortes.

Em investigação anterior, introduzimos a ideia de usar cortes duais óptimos adicionais, e obtivemos um algoritmo que resolve a relaxação linear de instâncias difíceis do problema de corte cinco vezes mais rápido. Recentemente, derivámos cortes duais para todos os nós da árvore de partição e geração de colunas. Experiências preliminares mostram boas reduções nos tempos computacionais.

Reforçar as formulações matemáticas com cortes também proporciona melhores algoritmos. Os nossos resultados computacionais preliminares mostram que o uso de novas famílias de inequações válidas superaditivas (derivadas de restrições de saco de mochila) reforça modelos com variáveis binárias, sem induzir modificações muito complexas no subproblema.

Finalmente, hibridizar geração de colunas com heurísticas complexas, como Pesquisa Local Iterativa, Pesquisa em Vizinhanças Variáveis ou Pesquisa Local Guiada também parece ser um meio promissor de obter soluções de alta qualidade durante o processo.

A implementação destas ideias para diversos problemas é melhor conseguida com novas ferramentas computacionais. A prática comum é o desenvolvimento de código específico. Pretendemos desenvolver um conjunto de classes em C++ com dois diferentes usos possíveis: como "caixa-preta" e como "caixa-de-ferramentas". No primeiro caso, o utilizador só precisa de especificar, numa linguagem de alto nivel, o modelo e a decomposição. No segundo caso, o utilizador pode estender classes existentes para implementar ferramentas particulares, como solucionadores do subproblema e heurísticas.

Usando estas ferramentas e as novas ideias referidas, iremos desenvolver algoritmos ao nível do estado da arte para problemas de corte, de lotes e de programação de operações.

Scope of project:

Integer Programming is a technique of Operations Research widely applied in modeling and solving real problems. In the last decade, there has been a huge increase in research in column generation and branch-and-price (column generation combined with branch-and-bound), due to their success in solving very large instances of integer programming and combinatorial optimization problems, using reformulated models obtained by Dantzig-Wolfe decomposition.

It is now possible to tackle larger and more complex real problems, considering the main constraints and issues that arise in real problems, such as time and labor constraints, often ignored before, and to get usable optimized solutions. Research on this area has had a huge economic impact in areas as logistics and distribution, or the airline industry. Vehicle scheduling and routing problems and airline crew scheduling problems are examples of problems now solved routinely, providing solutions that represent very large annual savings.

Column generation is known to be robust, but to have slow convergence. Recent research efforts are now being devoted to obtaining faster algorithms. This can be achieved using stabilization and acceleration methods, and stronger formulations.

In prior research, we introduced the idea of using extra optimal dual cuts, and got an algorithm that solved the linear programming relaxation of some hard instances of the cutting stock problems five times faster. Recently, we derived dual cuts usable in all the nodes of the branch-and-price tree. Preliminary experiments show good reductions in computational times.

Strengthening mathematical models with cuts also provides better algorithms. Our preliminary computational results show that the use of new families of supperadditive valid inequalities (derived from knapsack constraints) strengthens reformulated models with binary variables, without inducing excessively complex modifications to the subproblem.

Finally, hybridizing column generation with complex heuristics, such as Iterated Local Search (ILS), Variable Neighborhood Search (VNS) and Guided Local Search (GLS) also seems to be a promising way of obtaining high quality solutions in the process.

The implementation of these ideas for several problems is better achieved developing better computational tools. Common practice when developing branch-and-price algorithms is to develop code specific to the problem in hand. We intend to develop a set of C++ classes with two different possible uses: as a “black-box” and as a “tool-box”. In the first case, the user only needs to specify, in a high-level language, a model and the decomposition to be used. In the second case, the user can extend existing classes to implement problem specific features, such as subproblem solvers and heuristics.

Using these tools, and the new ideas referred to above, we aim at developing leading state-of-the-art algorithms for cutting-stock, and lot sizing and scheduling problems.

Publicações:

Artigos

Cláudio Alves, J.M. Valério de Carvalho, A Stabilized Branch-and-Price-and-Cut Algorithm for the Multiple Length Cutting Stock Problem, Computers and Operations Research, 35, 4, pp. 1315-1328, 2008.

François Clautiaux, Cláudio Alves, Jose Valério de Carvalho, "A survey of dual-feasible and superadditive functions", Annals of Operations Research, DOI: 10.1007/s10479-008-0453-8, 2008.

Cláudio Alves, J.M. Valério de Carvalho, "A branch-and-price-and-cut algorithm for the pattern minimization problem", RAIRO Operations Research, 42, pp. 435-453, 2008.

Cláudio Alves, J.M. Valério de Carvalho, "New Integer Programming Formulations and an Exact Algorithm for the Ordered Cutting Stock Problem", Journal of the Operational Research Society, 59, pp. 1520–1531, 2008.

François Clautiaux, Cláudio Alves, J.M. Valério de Carvalho, "New stabilization procedures for the cutting stock problem ", under revision for INFORMS Journal on Computing, 2008.

Cláudio Alves, Rita Macedo, José Valério de Carvalho, "New Lower Bounds Based on Column Generation and Constraint Programming for the Pattern Minimization Problem", submetido a Computers and Operations Research, 2008

Artigos em Livro

C. Alves, G. Belov, G. Scheithauer, J.M. Valério de Carvalho. "Gomory Cuts from a Position-Indexed Formulation of 1D Stock Cutting", in Intelligent Decision Support, Festschrift for Hermann Gehring, (Eds. A. Bortfeldt, J. Homberger, H. Kopfer, G. Pankratz and R. Strangmeier), Gabler /Deutscher Universitätsverlag, pp. 3-14, 2008, ISBN-10:3-8349-0930-0.

Outros Artigos

Cláudio Alves, Rita Macedo, José Valério de Carvalho, Um novo limite inferior baseado num modelo de Programação por Restrições para o Problema de Minimização de Padrões, submetido a Investigação Operacional, 2008

Artigos em Actas

F. Alvelos and J.M. Valério de Carvalho, A local search heuristic based on column generation applied to the binary multicommodity flow problem, Proceedings of the "International Network Optimization Conference 2007", Spa, Belgium, 2007, pp.6 (with refereeing)

Cláudio Alves, J.M. Valério de Carvalho, Solving the Assortment and Trim Loss Problem with Branch-and-Price-and-Cut, Proceedings of ORP3 Meeting, Guimarães, September 12-15, 2007, pp. 161--166.

Comunicações

François Clautiaux, Cláudio Alves, José Valério de Carvalho, "A comparative analysis and computational study of dual-feasible functions for bin-packing problems", 4th ESICUP (European Special Interest Group in Cutting and Packing) Meeting, Universidade de Tóquio, Tóquio, Japão, 2007.

François Clautiaux, Cláudio Alves, José Valério de Carvalho, "A comparative analysis and computational study of dual-feasible functions for bin-packing problems: lower bounds", EURO XXII, 22nd European Conference on Operational Research, July, 8-12, 2007, Prague, República Checa, 2007.

F. Alvelos and J. M. Valério de Carvalho, "Local Search in Branch-and-Price Algorithms", Optimization 2007, July, 22-25 2007, Porto, Portugal.

Cláudio Alves and J. M. Valério de Carvalho, New ways of deriving dual cuts for the Cutting Stock Problem, Optimization 2007, Porto, Portugal, July 22-25, 2007.

F. Clautiaux, C. Alves, J. M. Valério de Carvalho, Stabilization procedures for the cutting stock problem, ROADEF'08, Clermont-Ferrand, France, February 25-27, 2008.

Cláudio Alves and J. M. Valério de Carvalho, An Improved Model for the Pattern Minimization Problem, 2nd ESICUP (European Special Interest Group in Cutting and Packing) Meeting, Southampton, UK, April 14-16, 2005.

Cláudio Alves and J. M. Valério de Carvalho, An Improved Model for the Pattern Minimization Problem, 2nd ESICUP (European Special Interest Group in Cutting and Packing) Meeting, Southampton, UK, April 14-16, 2005.

J. M. Valério de Carvalho, "Branch-and-price-and-cut: application in the cutting stock problem", 6th International Workshop in Cutting and Packing and Related Topics, European Special Interest Group in Cutting and Packing, Lauterbad, Germany, Sept. 14-18, 2005.

Cláudio Alves, J. M. Valério de Carvalho, Exact algorithms for 1-Dimensional Cutting Stock Problems: Recent Improvements, 6th International Workshop in Cutting and Packing and Related Topics, European Special Interest Group in Cutting and Packing, Lauterbad, Germany, September 13-17, 2005.

Cláudio Alves, J. M. Valério de Carvalho, A Stabilized Branch-and-Price-and-Cut Algorithm for the Multiple Length Cutting Stock Problem, 3rd ESICUP (European Special Interest Group in Cutting and Packing) Meeting, Porto, Portugal, March 16-18, 2006.

Cláudio Alves and J. M. Valério de Carvalho, Novas formulações e um algoritmo exacto para o problema de corte ordenado, IO2006, 12º Congresso da APDIO, Lisboa, Portugal, October 8-11, 2006.

Cláudio Alves, J.M. Valério de Carvalho, Solving the assortment and trim loss minimisation problem using branch-and-price-and-cut, 7th International Workshop in Cutting and Packing and Related Topics, Leiria, Portugal, September 2007.

Alves, C.; Valério de Carvalho, J. M. - An improved branch-and-price-and-cut algorithm for the Pattern Minimization Problem. I Congresso de Estatística e Investigação Operacional da Galiza e Norte de Portugal; VII Congreso Galego de Estatítica e Investigación de Operacións. Guimarães: Outubro, 2005. texto completo. 6 páginas, publicado em CD-ROM.

Barbosa, V.; Alves, C.; Alvelos, F. - Ferramentas computacionais de suporte ao método de partição e geração de colunas. I Congresso de Estatística e Investigação Operacional da Galiza e Norte de Portugal; VII Congreso Galego de Estatítica e Investigación de Operacións. Guimarães: Outubro, 2006. texto completo. 6 páginas, publicado em CD-ROM.

Oliveira, J.A.V. - Pesquisa de Vizinhança Variável para o “Serial Batching Problem”. , I Congresso de Estatística e Investigação Operacional da Galiza e Norte de Portugal, VII Congreso Galego de Estatística e Investigación de Operacións. Guimarães: Outubro, 2005. texto completo. 6 páginas, publicado em CD-ROM.

Rodrigues, P.; Oliveira, J.A.V. - , Planeamento de Operações num Sistema Automático de Armazenamento para Minimizar a Soma Ponderada de Atrasos. , I Congresso de Estatística e Investigação Operacional da Galiza e Norte de Portugal, VII Congreso Galego de Estatística e Investigación de Operacións. Guimarães: Outubro, 2005. texto completo. 6 páginas, publicado em CD-ROM.

Vitorino,A.;Macedo, M.;Silva, R.; Oliveira, J.A.V. - , Neighborhoods for Graph Coloring Problem. , I Congresso de Estatística e Investigação Operacional da Galiza e Norte de Portugal, VII Congreso Galego de Estatística e Investigación de Operacións. Guimarães: texto completo. Outubro, 2005. texto completo.

J.A. Oliveira, “Heurísticas para a Sequenciação de Tarefas em Máquinas Paralelas”. VIII Congreso Galego de Estatística e Investigación de Operacións. Santiago Compostela, Novembro 2007, pp.6.

P. Cerqueira, L. Dias, J.A. Oliveira, “Programação de Fusões numa Fundição”. VIII Congreso Galego de Estatística e Investigación de Operacións. Santiago Compostela, Novembro 2007, pp.6.

B. Costa, L. Dias, J.A. Oliveira, G. Pereira, “Modelos de Simulação do Sistema de Abastecimento de Linhas de Produção”. VIII Congreso Galego de Estatística e Investigación de Operacións. Santiago Compostela, Novembro 2007, pp.6.

P. Miranda, S. Cunha, J.A. Oliveira, “Análise da Metodologia de Simulação em Projectos de Transporte de Paletes por AGVs”. VIII Congreso Galego de Estatística e Investigación de Operacións. Santiago Compostela, Novembro 2007, pp.6.

F. Koblasa, L.S. Dias, J.A. Oliveira, G. Pereira. “Heuristic Approach as a way to Improve Scheduling in ERP/APS Systems”. 15th European Concurrent Engineering Conference (ECEC2008). Porto, April 2008, pp.5.

V. Pavel, L.S. Dias, J.A. Oliveira, G. Pereira. “Using 3D Simulation in an Internal Logistic Process”. 15th European Concurrent Engineering Conference (ECEC2008). Porto, April 2008, pp.5.

B. Costa, L.S. Dias, J.A. Oliveira, G. Pereira, “Simulation as a Tool for Planning a Material Delivery System to Manufacturing Lines”. International Engineering Management Conference Europe 2008 (IEMC2008). Estoril, June 2008, pp.5.

P. Cerqueira, L. Dias, J.A. Oliveira, “Scheduling Operations in a Foundry industry”. First International Conference on Business Sustainability 2008 (BS08). Ofir, June 2008, pp.7.

P. Miranda, S. Cunha, J.A. Oliveira, “Simulation Methodology to design a AGV transportation System”. First International Conference on Business Sustainability 2008 (BS08). Ofir, June 2008, pp.6.

J.A. Oliveira, “Heuristic methods to scheduling operations in parallel machines”. 10th International Chemical and Biological Engineering Conference. Braga September 2008, pp.6.

Team:

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

Cláudio Manuel Martins Alves

Filipe Pereira Pinto da Cunha e Alvelos

José António Vasconcelos Oliveira

Vítor Manuel Meneses Barbosa (research grant)

Helena Isabel Teixeira Ribeiro Leite (research grant)

Carlos Miguel Marques Peixoto (research grant)

Funding:

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