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

Technical Report ERGO-12-012

P. Munari and J. Gondzio

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. To the best of our knowledge, the use of this algorithm within a full branch-price-and-cut framework has never been reported in the literature. 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 confirm that the proposed approach delivers the best overall performance when compared with standard branch-price-and-cut methods available in the literature.

Key words: Branch-Price-and-Cut, Column Generation, Interior Point Methods, Vehicle Routing Problem with Time Windows.

PDF ERGO-12-012.pdf.

Written: November 4, 2012, revised February 6, 2013.
Published: Computers and Operations Research 40 (2013) No 8, pp. 2026–2036.

Related Software:
HOPDM Higher Order Primal Dual Method.