Improving the feasibility pump. (English) Zbl 1170.90443

Achterberg, Tobias; Berthold, Timo

Discrete Optim. 4, No. 1, 77-86 (2007).

Summary: The feasibility pump described by M. Fischetti, F. Glover and A. Lodi [Math. Program. 104, No. 1 (A), 91–104 (2005; Zbl 1077.90039)] and it L. Bertacco, M. Fischetti and A. Lodi [A feasibility pump heuristic for general mixed-integer problems, Technical Report OR/05/5, DEIS-Università di Bologna, Italy (2005)] has proved to be a very successful heuristic for finding feasible solutions of mixed integer programs. The quality of the solutions in terms of the objective value, however, is sometimes quite poor. This paper proposes a slight modification of the algorithm in order to find better solutions. Extensive computational results show the success of this variant: for 89 out of 121 MIP instances the modified version produces improved solutions in comparison to the original feasibility pump.

MSC:

90C11	Mixed integer programming
90C59	Approximation methods and heuristics in mathematical programming

Keywords:

mixed integer programming; primal heuristics; feasibility pump

Software:

Benchmarks for Optimization Software; CPLEX; Decision tree for optimization software; FEASPUMP; MIPLIB; MIPLIB2003; Octane; Tabu search

References:

[1]	T. Achterberg, T. Koch, A. Martin, The mixed integer programming library: Miplib 2003. http://miplib.zib.de
[2]	Achterberg, T.; Koch, T.; Martin, A., Miplib 2003, Operations research letters, 34, 4, 1-12, (2006) · Zbl 1133.90300
[3]	Balas, E.; Ceria, S.; Dawande, M.; Margot, F.; Pataki, G., OCTANE: A new heuristic for pure 0-1 programs, Operations research, 49, 2, 207-225, (2001) · Zbl 1163.90654
[4]	Balas, E.; Martin, C.H., Pivot-and-complement: A heuristic for 0-1 programming, Management science, 26, 1, 86-96, (1980) · Zbl 0442.90060
[5]	Balas, E.; Schmieta, S.; Wallace, C., Pivot and shift—a mixed integer programming heuristic, Discrete optimization, 1, 1, 3-12, (2004) · Zbl 1087.90052
[6]	L. Bertacco, M. Fischetti, A. Lodi, A feasibility pump heuristic for general mixed-integer problems, Technical Report OR/05/5, DEIS-Università di Bologna, Italy, May 2005 · Zbl 1169.90415
[7]	Danna, E.; Rothberg, E.; Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Mathematical programming, 102, 1, 71-90, (2005) · Zbl 1131.90036
[8]	Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Mathematical programming, 104, 1, 91-104, (2005) · Zbl 1077.90039
[9]	Fischetti, M.; Lodi, A., Local branching, Mathematical programming, 98, 1-3, 23-47, (2003) · Zbl 1060.90056
[10]	Glover, F.; Laguna, M., General purpose heuristics for integer programming — part I, Journal of heuristics, 3, (1997) · Zbl 0887.90123
[11]	Glover, F.; Laguna, M., General purpose heuristics for integer programming — part II, Journal of heuristics, 3, (1997) · Zbl 0898.90094
[12]	Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publisher Boston, Dordrecht, London · Zbl 0930.90083
[13]	Glover, F.; Løkketangen, A.; Woodruff, D.L., Scatter search to generate diverse MIP solutions, (), 299-317
[14]	Hillier, F.S., Efficient heuristic procedures for integer linear programming with an interior, Operations research, 17, 600-637, (1969) · Zbl 0176.49902
[15]	ILOG, Cplex. http://www.ilog.com/products/cplex
[16]	Løkketangen, A.; Glover, F., Solving zero/one mixed integer programming problems using tabu search, European journal of operations research, 106, 624-658, (1998) · Zbl 0991.90091
[17]	H. Mittelmann, Decision tree for optimization software: Benchmarks for optimization software. http://plato.asu.edu/bench.html, 2003
[18]	M. Nediak, J. Eckstein, Pivot, cut, and dive: A heuristic for 0-1 mixed integer programming, Technical Report RRR 53-2001, Rutgers University, 2001
[19]	Saltzman, R.M.; Hillier, F.S., A heuristic ceiling point algorithm for general integer linear programming, Management science, 38, 2, 263-283, (1992) · Zbl 0777.90035