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

---

Project POSI/ SRI/ 48873 / 2002, Application of Branch-and-Price Algorithms in Scheduling

---

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, which 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.

In this project, we intend to develop state-of-the-art algorithms for the solution of some scheduling problems using these new ideas.

Publicações:

PhD Thesis:

António Jorge Trindade da Silva Duarte, Aplicação de partição e geração de colunas ao agendamento de máquinas paralelas, Universidade do Minho, Janeiro de 2006.

Artigos:

C. Pimentel, F. Alvelos, J. M. Valério de Carvalho, “Mathematical Programming Models for Integrated Lot Sizing and Scheduling - A Survey”. submitted, 2007.

C. Pimentel, F. Alvelos, J. M. Valério de Carvalho, “Comparing Dantzig-Wolfe decompositions and branch-and-price algorithms for the multi-item capacitated lot sizing problem”, under revision for Optimization Methods and Software, 2008.

Outros Artigos:

Carina Maria Oliveira Pimentel, Filipe Pereira e Alvelos, J.M. Valério de Carvalho, "Algoritmos de partição e geração de colunas para dimensionamento de lotes de produção", Investigação Operacional, 26, pp. 129-146, 2006.

Comunicações:

Carina Pimentel, Filipe Alvelos, António Duarte, J. M. Valério de Carvalho, " Scheduling models for a knitting planning problem", Prooceedings of 3rd World Conference on Production and Operations Management, Gakushuin University,Tokyo, August 5-8, 2008.

C. Pimentel, F. Alvelos and J. M. Valério de Carvalho, "Application of multiple Dantzig-Wolfe decomposition to a lot sizing problem", EURO XXII, 22nd European Conference on Operational Research, July, 8-12, 2007, Prague, República Checa, 2007.

Carina Pimentel, Filipe Alvelos, Valério de Carvalho, Dantzig-Wolfe decompositions for a lot sizing problem, VII International Workshop on Cutting, Packing and Related Topics, Leiria, 2007.

Filipe Alvelos, J. M.Valério de Carvalho, Local search in branch-and-price algorithms, VII International Workshop on Cutting, Packing and Related Topics, Leiria, 2007.

J.M. Valério de Carvalho, "Branch-and-price: application in the cutting stock problem", I Congresso de Estatística e Investigação Operacional da Galiza e Norte de Portugal, VII Congresso Galego de Estatística e Investigación de Operacións, Guimarães, 26--28 Outubro, 2005 (sessão plenária)

Pimentel, C.; Alvelos, F.; Valério de Carvalho, J.M. - Algoritmos de partição e geração de colunas para dimensionamento de lotes de produção. I Congresso de Estatística e Investigação Operacional da Galiza e Norte de Portugal. Guimarães: Outubro, 2005. texto completo. 6 páginas, publicado em CD-ROM.

Team:

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

António Jorge da Silva Trindade Duarte

Carina Maria Oliveira Pimentel (research grant)

Tiago José da Costa Gomes (research grant)

Simão Pedro de Pinho Soares (research grant)

Paulo Ricardo Carvalho Vilaça (research grant)

Funding:

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