×

zbMATH — the first resource for mathematics

Improving the feasibility pump. (English) Zbl 1170.90443
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
PDF BibTeX XML Cite
Full Text: DOI
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
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.