The integration of an interior-point cutting plane method within a branch-and-price algorithm |
| |
Authors: | Email author" target="_blank">Samir?ElhedhliEmail author Jean-Louis?Goffin |
| |
Institution: | (1) Department of Management Sciences, University of Waterloo, 200 University Ave., W. Waterloo, ON, Ca N2L 3G1;(2) GERAD/Faculty of Management, McGill university, 1001 Sherbrooke, W. Montreal, Qc, Ca H3A 1G5 |
| |
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 ![lsquo](/content/tb63fxrdbj3x4vyu/xxlarge8216.gif) central![rsquo](/content/tb63fxrdbj3x4vyu/xxlarge8217.gif) dual solution by applying the analytic centre cutting plane method (ACCPM) on the dual of the full master problem. First, we introduce some modifications to ACCPM. We propose a new procedure to recover primal feasibility after adding cuts and use, for the first time, a dual Newton s 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. We compare against Cplex-MIP 7.5 as well as a classical branch-and-price algorithm.Mathematics Subject Classification (1991): 20E28, 20G40, 20C20 |
| |
Keywords: | branch-and-price Column generation Lagrangean relaxation interior-point methods ACCPM |
本文献已被 SpringerLink 等数据库收录! |
|