×

zbMATH — the first resource for mathematics

A feasibility pump heuristic for general mixed-integer problems. (English) Zbl 1169.90415
Summary: Finding a feasible solution of a given Mixed-Integer Programming (MIP) model is a very important (\(\mathcal {NP}\)-complete) problem that can be extremely hard in practice. Very recently, Fischetti, Glover and Lodi proposed a heuristic scheme for finding a feasible solution to general MIPs, called a Feasibility Pump (FP). According to the computational analysis reported by these authors, FP is indeed quite effective in finding feasible solutions of hard 0-1 MIPs. However, MIPs with general-integer variables seem much more difficult to solve by using the FP approach.
In this paper we elaborate on the Fischetti-Glover-Lodi approach and extend it in two main directions, namely (i) handling as effectively as possible MIP problems with both binary and general-integer variables, and (ii) exploiting the FP information to drive a subsequent enumeration phase.
Extensive computational results on large sets of test instances from the literature are reported, showing the effectiveness of our improved FP scheme for finding feasible solutions to hard MIPs with general-integer variables.

MSC:
90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDF BibTeX XML Cite
Full Text: DOI
References:
[1] T. Achterberg, SCIP—a framework to integrate constraint and mixed integer programming, Technical report 04-19, Zuse Institute, Berlin, 2004. Available at http://www.zib.de/Publications/abstracts/ZR-04-19/
[2] T. Achterberg, T. Berthold, Improving the feasibility pump, Technical report, Zuse Institute, Berlin, September 2005 · Zbl 1170.90443
[3] T. Achterberg, T. Koch, A. Martin, MIPLIB 2003, Technical report 05-28, Zuse Institute, Berlin, 2005. Available at http://www.zib.de/PaperWeb/abstracts/ZR-05-28/
[4] Balas, E.; Ceria, S.; Dawande, M.; Margot, F.; Pataki, G., OCTANE: A new heuristic for pure 0-1 programs, Operations research, 49, 207-225, (2001) · Zbl 1163.90654
[5] Balas, E.; Martin, C.H., Pivot-and-complement: A heuristic for 0-1 programming, Management science, 26, 86-96, (1980) · Zbl 0442.90060
[6] Balas, E.; Schmieta, S.; Wallace, C., Pivot and shift—A mixed integer programming heuristic, Discrete optimization, 1, 3-12, (2004) · Zbl 1087.90052
[7] J.W. Chinneck, J. Patel, Faster MIP solutions through better variable ordering, ISMP 2003, Copenhagen, August 2003
[8] Dash Xpress-Optimizer 16.01.05: Getting started and reference manual, Dash Optimization Ltd, 2004. http://www.dashoptimization.com/
[9] Danna, E.; Rothberg, E.; Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Mathematical programming, 102, 71-90, (2005) · Zbl 1131.90036
[10] Fischetti, M.; Lodi, A., Local branching, Mathematical programming, 98, 23-47, (2003) · Zbl 1060.90056
[11] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Mathematical programming, 104, 91-104, (2005) · Zbl 1077.90039
[12] Glover, F.; Laguna, M., General purpose heuristics for integer programming: part I, Journal of heuristics, 2, 343-358, (1997) · Zbl 0887.90123
[13] Glover, F.; Laguna, M., General purpose heuristics for integer programming: part II, Journal of heuristics, 3, 161-179, (1997) · Zbl 0898.90094
[14] Glover, F.; Laguna, M., Tabu search, (1997), Kluwer Academic Publisher Boston, Dordrecht, London · Zbl 0930.90083
[15] Hillier, F.S., Effcient heuristic procedures for integer linear programming with an interior, Operations research, 17, 600-637, (1969) · Zbl 0176.49902
[16] Ibaraki, T.; Ohashi, T.; Mine, H., A heuristic algorithm for mixed-integer programming problems, Mathematical programming study, 2, 115-136, (1974)
[17] ILOG Cplex 9.1: User’s manual and reference manuals, ILOG, S.A., 2004. http://www.ilog.com/
[18] Løkketangen, A., Heuristics for 0-1 mixed-integer programming, (), 474-477
[19] Løkketangen, A.; Glover, F., Solving zero/one mixed integer programming problems using tabu search, European journal of operational research, 106, 624-658, (1998) · Zbl 0991.90091
[20] H.D. Mittelmann, Benchmarks for optimization software: Testcases. http://plato.asu.edu/topics/testcases.html
[21] M. Nediak, J. Eckstein, Pivot, cut, and dive: A heuristic for 0-1 mixed integer programming, Research report RRR 53-2001, RUTCOR, Rutgers University, October 2001
[22] L. Peeters, Cyclic railway timetable optimization, ERIM Ph.D. Series, Erasmus University Rotterdam, June, 2003
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.