P. Munari and J. Gondzio
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. 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.