×

Repairing MIP infeasibility through local branching. (English) Zbl 1278.90273

Summary: Finding a feasible solution to a generic mixed-integer linear program (MIP) is often a very difficult task. Recently, two heuristic approaches called feasibility pump and local branching have been proposed to address the problem of finding a feasible solution and improving it, respectively. In this paper we introduce and analyze computationally a hybrid algorithm that uses the feasibility pump method to provide, at very low computational cost, an initial (possibly infeasible) solution to the local branching procedure. The overall procedure is reminiscent of Phase I of the two phase simplex algorithm, in which the original LP is augmented with artificial variables that make a known infeasible starting solution feasible and then the augmented model is solved to iteratively reduce that infeasibility by driving the values of the artificial variables to zero. As such, our approach can also to used to find (heuristically) a minimum-cardinality set of constraints whose removal converts an infeasible MIP into a feasible one-a very important piece of information in the analysis of infeasible MIP models.
Often, in practical applications finding a good feasible solution is the main order of business. At this purpose, local search methods generally start by a feasible solution and eventually improve it until a fixed point is reached and the algorithm is aborted. Sometimes, however, finding such a first feasible solution is hard and can be unnecessary since an initial slightly infeasible solution can be repaired to become feasible and eventually improved. We propose to integrate in the above spirit two recent algorithms for general-purpose MIPs-namely feasibility pump and local branching-which were originally proposed to separately cope with the issues of finding an initial feasible solution and improve it.

MSC:

90C11 Mixed integer programming
90C59 Approximation methods and heuristics in mathematical programming
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Fischetti, M.; Lodi, A., Local branching, Mathematical Programming, 98, 23-47 (2003) · Zbl 1060.90056
[2] 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
[3] Balas, E.; Martin, C. H., Pivot-and-complement: a heuristic for 0-1 programming, Management Science, 26, 86-96 (1980) · Zbl 0442.90060
[4] Balas, E.; Schmieta, S.; Wallace, C., Pivot and shift—a mixed integer programming heuristic, Discrete Optimization, 1, 3-12 (2004) · Zbl 1087.90052
[5] Danna, E.; Rothberg, E.; Le Pape, C., Exploring relaxation induced neighborhoods to improve MIP solutions, Mathematical Programming, 102, 71-90 (2005) · Zbl 1131.90036
[6] Fischetti, M.; Polo, C.; Scantamburlo, M., A local branching heuristic for mixed-integer programs with 2-level variables, Networks, 44, 61-72 (2004) · Zbl 1055.90054
[7] Glover, F.; Laguna, M., General purpose heuristics for integer programming: Part I, Journal of Heuristics, 2, 343-358 (1997) · Zbl 0887.90123
[8] Glover, F.; Laguna, M., General purpose heuristics for integer programming: Part II, Journal of Heuristics, 3, 161-179 (1997) · Zbl 0898.90094
[9] Glover, F.; Laguna, M., Tabu search (1997), Kluwer Academic Publisher: Kluwer Academic Publisher Boston, Dordrecht, London · Zbl 0930.90083
[10] Hansen, P.; Mladenovíc, N.; Urosevíc, D., Variable neighborhood search and local branching, Computers and Operations Research, 33, 3034-3045 (2006) · Zbl 1086.90042
[11] Hillier, F. S., Efficient heuristic procedures for integer linear programming with an interior, Operations Research, 17, 600-637 (1969) · Zbl 0176.49902
[12] Ibaraki, T.; Ohashi, T.; Mine, H., A heuristic algorithm for mixed-integer programming problems, Mathematical Programming Study, 2, 115-136 (1974)
[13] Løkketangen, A., Heuristics for 0-1 mixed-integer programming, (Pardalos, P. M.; Resende, M. G.C., Handbook of applied optimization (2002), Oxford University Press: Oxford University Press Oxford), 474-477
[14] 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
[15] Nediak M, Eckstein J. Pivot, Cut, and Dive: A Heuristic for 0-1 Mixed Integer Programming Research Report RUTCOR, Rutgers University 2001, RRR 53-2001.; Nediak M, Eckstein J. Pivot, Cut, and Dive: A Heuristic for 0-1 Mixed Integer Programming Research Report RUTCOR, Rutgers University 2001, RRR 53-2001.
[16] Fischetti, M.; Glover, F.; Lodi, A., The feasibility pump, Mathematical Programming, 104, 91-104 (2005) · Zbl 1077.90039
[17] Amaldi, E.; Pfetsch, M. E.; Trotter, L. E., On the maximum feasible subsystem problem, IISs and IIS-hypergraphs, Mathematical Programming, 95, 533-554 (2003) · Zbl 1023.90070
[18] Chinneck, J., Fast heuristics for the maximum feasible subsystem problem, INFORMS Journal on Computing, 13, 210-223 (2001) · Zbl 1238.90093
[19] Gleeson, J.; Ryan, J., Identifying minimally infeasible subsystems of inequalities, ORSA Journal on Computing, 2, 61-63 (1990) · Zbl 0752.90050
[20] Achterberg T, Koch T, Martin A. The mixed integer programming library: MIPLIB, \(2003 \langle;\) http://miplib.zib.de \(\rangle;\).; Achterberg T, Koch T, Martin A. The mixed integer programming library: MIPLIB, \(2003 \langle;\) http://miplib.zib.de \(\rangle;\).
[21] Mladenovíc, N.; Hansen, P., Variable neighborhood search, Computers Operations Research, 24, 1097-1100 (1997) · Zbl 0889.90119
[22] Achterberg T, Berthold T. Improving the feasibility pump. Technical Report, ZIB, Berlin 2005, 05-42.; Achterberg T, Berthold T. Improving the feasibility pump. Technical Report, ZIB, Berlin 2005, 05-42. · Zbl 1170.90443
[23] Double-Click sas. Personal communication, 2001.; Double-Click sas. Personal communication, 2001.
[24] Miller AJ. Personal communication, 2003.; Miller AJ. Personal communication, 2003.
[25] Klau GW, Personal communication, 2002.; Klau GW, Personal communication, 2002.
[26] Rothberg E. Personal communication, 2002.; Rothberg E. Personal communication, 2002.
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.