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 条

[1] Achterberg T., Constraint integer programming, (2007)
[2] Achterberg T., Berthold T., Improving the feasibility pump, Discrete Optim., 4, 1, pp. 77-86, (2007)
[3] Baena D., Castro J., Using the analytic center in the feasibility pump, Oper. Res. Lett., 39, 5, pp. 310-317, (2011)
[4] Balas E., Martin C.H., Pivot and complement—a heuristic for 0–1 programming, Manage. Sci., 26, 1, pp. 86-96, (1980)
[5] Balas E., Schmieta S., Wallace C., Pivot and shift—a mixed integer programming heuristic, Discrete Optim., 1, 1, pp. 3-12, (2004)
[6] Bertacco L., Fischetti M., Lodi A., A feasibility pump heuristic for general mixed-integer problems, Discrete Optim., 4, 1, pp. 63-76, (2007)
[7] Bixby R.E., Solving real-world linear programs: a decade and more of progress, Oper. Res., 50, 1, pp. 3-15, (2002)
[8] Bixby R.E., Rothberg E., Progress in computational mixed integer programming—a look back from the other side of the tipping point, Ann. Oper. Res., 149, pp. 37-41, (2007)
[9] Danna E., Rothberg E., Le Pape C., Exploring relaxation induced neighborhoods to improve MIP solutions, Math. Program., 102, pp. 71-90, (2005)
[10] De Santis M., Lucidi S., Rinaldi F., A new class of functions for measuring solution integrality in the feasibility pump approach, SIAM Journal on Optimization, 23, 3, pp. 1575-1606, (2013)

← 1 2 3 →