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

P. Munari, J. Gondzio

Research output: Contribution to journalArticlepeer-review

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.
Original languageEnglish
Pages (from-to)2026-2036
Number of pages11
JournalComputers and Operations Research
Volume40
Issue number8
DOIs
Publication statusPublished - 1 Aug 2013

Fingerprint

Dive into the research topics of 'Using the primal-dual interior point algorithm within the branch-price-and-cut method'. Together they form a unique fingerprint.

Cite this