The Integration of an Interior-Point Cutting-Plane Method within a Branch-and-Price Algorithm

Samir Elhedhli (elhedhlsmanagement.mcgill.ca)
Jean-Louis Goffin (goffinmanagement.mcgill.ca)

Abstract: This paper presents a novel integration of interior point cutting plane methods within branch-and-price algorithms. Unlike the classical method, columns are generated at a ``central'' dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce improvements to ACCPM. We propose a new procedure to recover primal feasibility after adding cuts and use, for the first-time, a dual Newton method to calculate the new analytic centre after branching. Second, we discuss the integration of ACCPM within the branch-and-price algorithm. We detail the use of ACCPM as the search goes deep in the branch and bound tree, making full utilization of past information as a warm start. We exploit dual information from ACCPM to generate incumbent feasible solutions and to guide branching. Finally, the overall approach is implemented and tested for the bin-packing problem and the capacitated facility location problem with single sourcing

Keywords: branch-and-price, column generation, Lagrangean relaxation, interior-point methods, ACCPM

Category 1: Integer Programming (Other )

Category 2: Applications -- OR and Management Sciences (Other )

Citation: GERAD Technical Report G-2001-??

Download: [Postscript]

Entry Submitted: 03/19/2001
Entry Accepted: 03/19/2001
Entry Last Modified: 03/19/2001

Modify/Update this entry