Using the primal-dual interior point algorithm within the branch-price-and-cut method

Autor(es)

Munari, Pedro ^[1] ; Gondzio, Jacek ^[2]

Afiliação do(s) autor(es)

^[1] Univ Sao Paulo, Inst Ciencias Matemat Computacao, BR-13560970 Sao Carlos, SP - Brazil

^[2] Univ Edinburgh, Sch Math, Edinburgh EH9 3JZ, Midlothian - Scotland

• Tipo de documento: Artigo Científico
• Fonte: Computers & Operations Research; v. 40, n. 8, p. 2026-2036, AUG 2013.
• Citações Web of Science: 14

Resumo

Branch-price-and-cut has proven to be a powerful method for solving integer programming problems. It combines decomposition techniques with the generation of both columns and valid inequalities and relies on strong bounds to guide the search in the branch-and-bound tree. In this paper, we present how to improve the performance of a branch-price-and-cut method by using the primal-dual interior point algorithm. We discuss in detail how to deal with the challenges of using the interior point algorithm with the core components of the branch-price-and-cut method. The effort to overcome the difficulties pays off in a number of advantageous features offered by the new approach. We present the computational results of solving well-known instances of the vehicle routing problem with time windows, a challenging integer programming problem. The results indicate that the proposed approach delivers the best overall performance when compared with a similar branch-price-and-cut method which is based on the simplex algorithm. (C) 2013 Elsevier Ltd. All rights reserved. (AU)

• Processo FAPESP: 12/05486-6 - Usando o algoritmo primal-dual de pontos interiores no método branch-price-and-cut
• Beneficiário: Pedro Augusto Munari Junior
• Modalidade de apoio: Bolsas no Exterior - Estágio de Pesquisa - Doutorado
• Processo FAPESP: 08/09040-7 - Aspectos teóricos e computacionais para a implementação eficiente de métodos de otimização linear
• Beneficiário: Pedro Augusto Munari Junior
• Modalidade de apoio: Bolsas no Brasil - Doutorado