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

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 ho...

Full description

Saved in:
Bibliographic Details
Published in:Computers & operations research 2013-08, Vol.40 (8), p.2026-2036
Main Authors: Munari, Pedro, Gondzio, Jacek
Format: Article
Language:English
Subjects:
Algorithms
Applied sciences
Branch & bound algorithms
Branch-price-and-cut
Column generation
Exact sciences and technology
Flows in networks. Combinatorial problems
Inequalities
Integer programming
Logistics
Mathematical problems
Mathematical programming
Operational research and scientific management
Operational research. Management science
Operations research
Primal-dual interior point algorithm
Routes
Searching
Studies
Transportation problem (Operations research)
Trees
Vehicle routing problem
Vehicles
Windows (intervals)
Citations: Items that this one cites
Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary: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.
ISSN:0305-0548
1873-765X
0305-0548
DOI:10.1016/j.cor.2013.02.028