Boosting the feasibility pump

被引：22
作者：
Boland N.L. [1 ]
Eberhard A.C. [2 ]
Engineer F.G. [3 ]
Fischetti M. [4 ]
Savelsbergh M.W.P. [1 ]
Tsoukalas A. [2 ]
机构：
[1] The University of Newcastle, Callaghan
[2] Royal Melbourne Institute of Technology, Melbourne
[3] SK Innovation, Seoul
[4] University of Padova, Padova
来源：
Savelsbergh, Martin W. P. (martin.savelsbergh@newcastle.edu.au) | 1600年 / Springer Verlag卷 / 06期
关键词：
65K05; 90C10; 90C11;
D O I：
10.1007/s12532-014-0068-9
中图分类号：
学科分类号：
摘要：
The feasibility pump (FP) has proved to be an effective method for finding feasible solutions to mixed integer programming problems. FP iterates between a rounding procedure and a projection procedure, which together provide a sequence of points alternating between LP feasible but fractional solutions, and integer but LP infeasible solutions. The process attempts to minimize the distance between consecutive iterates, producing an integer feasible solution when closing the distance between them. We investigate the benefits of enhancing the rounding procedure with a clever integer line search that efficiently explores a large set of integer points. An extensive computational study on benchmark instances demonstrates the efficacy of the proposed approach. © 2014, Springer-Verlag Berlin Heidelberg and Mathematical Optimization Society.
引用
收藏
页码：255 / 279
页数：24
相关论文
共 27 条
  • [11] Eckstein J., Nediak M., Pivot, cut, and dive: a heuristic for 0–1 mixed integer programming, J. Heurist., 13, pp. 471-503, (2007)
  • [12] Faaland B.H., Hillier F.S., Interior path methods for heuristic integer programming procedures, Oper. Res., 27, 6, pp. 1069-1087, (1979)
  • [13] Fischetti M., Glover F., Lodi A., The feasibility pump, Math. Program., 104, pp. 91-104, (2005)
  • [14] Fischetti M., Lodi A., Local branching, Math. Program., 98, pp. 23-47, (2003)
  • [15] Fischetti M., Salvagnin D., Feasibility pump 2.0, Math. Program. Comput., 1, pp. 201-222, (2009)
  • [16] Glover F., Laguna M., General purpose heuristics for integer programming. Part I, J. Heurist., 2, pp. 343-358, (1997)
  • [17] Glover F., Laguna M., General purpose heuristics for integer programming. Part II, J. Heuristics, 3, pp. 161-179, (1997)
  • [18] Halicka M., Analyticity of the central path at the boundary point in semidefinite programming, Eur. J. Oper. Res., 143, 2, pp. 311-324, (2002)
  • [19] Hanafi S., Lazic J., Mladenovic N., Variable neighbourhood pump heuristic for 0–1 mixed integer programming feasibility, Electron. Notes Discrete Math., 36, pp. 759-766, (2010)
  • [20] Hillier F.S., Efficient heuristic procedures for integer linear programming with an interior, Oper. Res., 17, 4, pp. 600-637, (1969)
123