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

Author(s)

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

Affiliation

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

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

• Document type: Journal article
• Source: Computers & Operations Research; v. 40, n. 8, p. 2026-2036, AUG 2013.
• Web of Science Citations: 14

Abstract

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)

• FAPESP's process: 12/05486-6 - Using the primal-dual interior point algorithm within the branch-price-and-cut method
• Grantee: Pedro Augusto Munari Junior
• Support Opportunities: Scholarships abroad - Research Internship - Doctorate
• FAPESP's process: 08/09040-7 - Theoretical and computational issues for the efficient implementation of linear optimization methods
• Grantee: Pedro Augusto Munari Junior
• Support Opportunities: Scholarships in Brazil - Doctorate