Optimization Online


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

Samir Elhedhli (elhedhls***at***management.mcgill.ca)
Jean-Louis Goffin (goffin***at***management.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

  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 Programming Society