Optimization Online


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

Pedro Munari (munari***at***icmc.usp.br)
Jacek Gondzio (J.Gondzio***at***ed.ac.uk)

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.

Keywords: branch-price-and-cut, column generation, primal-dual interior point method, vehicle routing problem

Category 1: Integer Programming

Citation: Computers & Operations Research, 2013. http://dx.doi.org/10.1016/j.cor.2013.02.028


Entry Submitted: 11/05/2012
Entry Accepted: 11/05/2012
Entry Last Modified: 03/28/2013

Modify/Update this entry

  Visitors Authors More about us Links
  Subscribe, Unsubscribe
Digest Archive
Search, Browse the Repository


Coordinator's Board
Classification Scheme
Give us feedback
Optimization Journals, Sites, Societies
Mathematical Optimization Society