Structure-driven fix-and-propagate heuristics for mixed integer programming. (English) Zbl 1432.90091
Summary: Primal heuristics play an important role in the solving of mixed integer programs (MIPs). They often provide good feasible solutions early and help to reduce the time needed to prove optimality. In this paper, we present a scheme for start heuristics that can be executed without previous knowledge of an LP solution or a previously found integer feasible solution. It uses global structures available within MIP solvers to iteratively fix integer variables and propagate these fixings. Thereby, fixings are determined based on the predicted impact they have on the subsequent domain propagation. If sufficiently many variables can be fixed that way, the resulting problem is solved first as an LP, and then as an auxiliary MIP if the rounded LP solution does not provide a feasible solution already. We present three primal heuristics that use this scheme based on different global structures. Our computational experiments on standard MIP test sets show that the proposed heuristics find solutions for about 60% of the instances and by this, help to improve several performance measures for MIP solvers, including the primal integral and the average solving time.
MSC:
| 90C11 | Mixed integer programming |
| 90C10 | Integer programming |
| 90C59 | Approximation methods and heuristics in mathematical programming |
Keywords:
mixed integer programming; primal heuristics; start heuristics; fix-and-propagate; large neighborhood search; IP; MIPReferences:
| [1] | Achterberg, T.: Conflict analysis in mixed integer programming. Discrete Optim. 4(1), 4-20 (2007) · Zbl 1169.90414 |
| [2] | Achterberg, T.: Constraint Integer Programming. Ph.D. thesis, Technische Universität Berlin (2007) · Zbl 1430.90427 |
| [3] | Achterberg, T., Berthold, T.: Improving the feasibility pump. Discrete Optim. 4(1), 77-86 (2007) · Zbl 1170.90443 |
| [4] | Achterberg, T.; Berthold, T.; Hendel, G.; Klatte, D. (ed.); Lüthi, H-J (ed.); Schmedders, K. (ed.), Rounding and propagation heuristics for mixed integer programming, 71-76 (2012), Berlin · Zbl 1306.90100 |
| [5] | Achterberg, T., Bixby, R.E., Gu, Z., Rothberg, E., Weninger, D.: Presolve reductions in mixed integer programming. Technical Report 16-44, ZIB, Takustr. 7, 14195 Berlin (2016) · Zbl 07290858 |
| [6] | Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 1-12 (2006) · Zbl 1133.90300 |
| [7] | Achterberg, T., Raack, C.: The MCF-separator: detecting and exploiting multi-commodity flow structures in MIPs. Math. Program. Comput. 2(2), 125-165 (2010) · Zbl 1200.65042 |
| [8] | Achterberg, T., Wunderling, R.: Mixed integer programming: analyzing 12 years of progress. In: Facets of Combinatorial Optimization, pp. 449-481. Springer (2013) · Zbl 1317.90206 |
| [9] | Andrade, C.E., Ahmed, S., Nemhauser, G.L., Shao, Y.: A hybrid primal heuristic for finding feasible solutions to mixed integer programs. Eur. J. Oper. Res. 263(1), 62-71 (2017) · Zbl 1380.90193 |
| [10] | Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.: Conflict graphs in solving integer programming problems. Eur. J. Oper. Res. 121(1), 40-55 (2000) · Zbl 0959.90034 |
| [11] | Atamtürk, A., Nemhauser, G.L., Savelsbergh, M.W.: The mixed vertex packing problem. Math. Program. 89(1), 35-53 (2000) · Zbl 1033.90095 |
| [12] | Bergman, D., Cire, A.A., van Hoeve, W.-J., Yunes, T.: BDD-based heuristics for binary optimization. J. Heuristics 20(2), 211-234 (2014) |
| [13] | Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discrete Optim. 4(1), 63-76 (2007) · Zbl 1169.90415 |
| [14] | Berthold, T.: Primal heuristics for mixed integer programs. Diploma thesis, Technische Universität Berlin (2006) |
| [15] | Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611-614 (2013) · Zbl 1287.90037 |
| [16] | Berthold, T.: Heuristic algorithms in global MINLP solvers. Ph.D. thesis, Technische Universität Berlin (2014) |
| [17] | Berthold, T.: RENS—the optimal rounding. Math. Program. Comput. 6(1), 33-54 (2014) · Zbl 1304.90147 |
| [18] | Berthold, T.; Dörner, KF (ed.); Ljubic, I. (ed.); Pflug, G. (ed.); Tragler, G. (ed.), Improving the performance of MIP and MINLP solvers by integrated heuristics, 19-24 (2017), Cham · Zbl 1375.90322 |
| [19] | Berthold, T.; Feydy, T.; Stuckey, PJ; Lodi, A. (ed.); Milano, M. (ed.); Toth, P. (ed.), Rapid learning for binary programs, 51-55 (2010), Berlin · Zbl 1285.68151 |
| [20] | Berthold, T., Gleixner, A.M.: Undercover—a primal heuristic for MINLP based on sub-MIPs generated by set covering. In: Bonami, P., Liberti, L., Miller, A.J., Sartenaer, A. (eds.), Proceedings of the EWMINLP, pp. 103-112 (2010) |
| [21] | Berthold, T., Perregaard, M., Mészáros, C.: Four good reasons to use an interior point solver within a MIP solver. Technical Report 17-42, ZIB, Takustr. 7, 14195 Berlin (2017) · Zbl 1397.90278 |
| [22] | Bixby, R.E.: A brief history of linear and mixed-integer programming computation. Documenta Math., pp. 107-121 (2012) · Zbl 1270.90003 |
| [23] | Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.P.: An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12-15 (1998) |
| [24] | Bixby, RE; Fenelon, M.; Gu, Z.; Rothberg, E.; Wunderling, R.; Powell, MJD (ed.); Scholtes, S. (ed.), MIP: Theory and practice—closing the gap, 19-49 (2000), Dordrecht · Zbl 0986.90025 |
| [25] | COR@L. MIP Instances (2014). http://coral.ie.lehigh.edu/data-sets/mixed-integer-instances/. Accessed 02 July 2018 |
| [26] | Dakin, R.J.: A tree-search algorithm for mixed integer programming problems. Comput. J. 8(3), 250-255 (1965) · Zbl 0154.42004 |
| [27] | Danna, E., Rothberg, E., Pape, C.L.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. 102(1), 71-90 (2004) · Zbl 1131.90036 |
| [28] | Dey, S., Iroume, A., Molinaro, M., Salvagnin, D.: Improving the randomization step in feasibility pump. arXiv preprint arXiv:1609.08121 (2016) · Zbl 1391.90426 |
| [29] | Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104(1), 91-104 (2005) · Zbl 1077.90039 |
| [30] | Fischetti, M., Lodi, A.: Local branching. Math. Program. 98(1-3), 23-47 (2003) · Zbl 1060.90056 |
| [31] | Fischetti, M., Lodi, A.: Repairing MIP infeasibility through local branching. Comput. Oper. Res. 35(5), 1436-1445 (2008). Special Issue: Algorithms and Computational Methods in Feasibility and Infeasibility · Zbl 1278.90273 |
| [32] | Fischetti, M.; Lodi, A.; Cochran, JJ (ed.); Cox, LA (ed.); Keskinocak, P. (ed.); Kharoufeh, JP (ed.); Smith, JC (ed.), Heuristics in mixed integer programming (2010), New York |
| [33] | Fischetti, M., Monaci, M.: Proximity search for 0-1 mixed-integer convex programming. J. Heuristics 20(6), 709-731 (2014) · Zbl 1360.90173 |
| [34] | Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. Comput. 1, 201-222 (2009) · Zbl 1180.90208 |
| [35] | Fügenschuh, A.; Martin, A.; Aardal, K. (ed.); Nemhauser, GL (ed.); Weismantel, R. (ed.), Computational integer programming and cutting planes, 69-122 (2005), Amsterdam · Zbl 1278.90269 |
| [36] | Gamrath, Gerald; Berthold, Timo; Heinz, Stefan; Winkler, Michael, Structure-Based Primal Heuristics for Mixed Integer Programming, 37-53 (2015), Tokyo |
| [37] | Gamrath, G., Berthold, T., Heinz, S., Winkler, M.: Structure-driven fix-and-propagate heuristics for mixed integer programming. Technical Report 17-56, ZIB, Takustr. 7, 14195 Berlin (2017) · Zbl 1432.90091 |
| [38] | Gardi, F.: Toward a mathematical programming solver based on local search. Habilitation thesis, Université Pierre et Marie Curie (2013) |
| [39] | Ghosh, S.: DINS, a MIP improvement heuristic. In: Fischetti, M., Williamson, D.P. (eds.) Proceedings of 12th International IPCO Conference on Integer Programming and Combinatorial Optimization, vol. 4513 of LNCS, pp. 310-323. Springer, Berlin (2007) · Zbl 1136.90419 |
| [40] | Gleixner, A., Eifler, L., Gally, T., Gamrath, G., Gemander, P., Gottwald, R.L., Hendel, G., Hojny, C., Koch, T., Miltenberger, M., r, B.M., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schlösser, F., Serrano, F., Shinano, Y., Viernickel, J.M., Vigerske, S., Weninger, D., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 5.0. Technical Report 17-61, ZIB, Takustr. 7, 14195 Berlin (2017) |
| [41] | Guastaroba, G., Savelsbergh, M., Speranza, M.: Adaptive kernel search: a heuristic for solving mixed integer linear programs. Eur. J. Oper. Res 263(3), 789-804 (2017) · Zbl 1380.90290 |
| [42] | Guzelsoy, M., Nemhauser, G., Savelsbergh, M.: Restrict-and-relax search for 0-1 mixed-integer programs. EURO J. Comput. Optim. 1, 1-18 (2013) · Zbl 1296.90081 |
| [43] | Hansen, P., Mladenović, N., Urošević, D.: Variable neighborhood search and local branching. Comput. Oper. Res. 33(10), 3034-3045 (2006) · Zbl 1086.90042 |
| [44] | Hendel, G.: IPET interactive performance evaluation tools. https://github.com/GregorCH/ipet. Accessed 02 July 2018 |
| [45] | Johnson, E.L., Padberg, M.W.: Degree-two inequalities, clique facets, and biperfect graphs. N-Holl. Math. Stud. 66, 169-187 (1982) · Zbl 0523.52009 |
| [46] | Koc, U., Mehrotra, S.: Generation of feasible integer solutions on a massively parallel computer using the feasibility pump. Oper. Res. Lett. 45, 652-658 (2017) · Zbl 1409.90117 |
| [47] | Koch, T., Achterberg, T., Andersen, E., Bastert, O., Berthold, T., Bixby, R.E., Danna, E., Gamrath, G., Gleixner, A.M., Heinz, S., Lodi, A., Mittelmann, H., Ralphs, T., Salvagnin, D., Steffy, D.E., Wolter, K.: MIPLIB 2010. Math. Program. Comput. 3(2), 103-163 (2011) |
| [48] | Land, A.H., Doig, A.G.: An automatic method of solving discrete programming problems. Econometrica 28(3), 497-520 (1960) · Zbl 0101.37004 |
| [49] | Lazić, J.: Variable and single neighbourhood diving for MIP feasibility. Yugosl. J. Oper. Res. 26(2), 131-157 (2016) |
| [50] | Lodi, A.; Jünger, M. (ed.); Liebling, TM (ed.); Naddef, D. (ed.); Nemhauser, GL (ed.); Pulleyblank, WR (ed.); Reinelt, G. (ed.); Rinaldi, G. (ed.); Wolsey, LA (ed.), Mixed integer programming computation, 619-645 (2010), Berlin · Zbl 1187.90206 |
| [51] | Lodi, A.; Talbi, E-G (ed.), The heuristic (dark) side of MIP solvers, 273-284 (2013), Berlin |
| [52] | Lodi, A., Tramontani, A.: Performance variability in mixed-integer programming. In: Theory Driven by Influential Applications, chapter 1, pp. 1-12. INFORMS (2013) |
| [53] | Maher, S.J., Fischer, T., Gally, T., Gamrath, G., Gleixner, A., Gottwald, R.L., Hendel, G., Koch, T., Lübbecke, M.E., Miltenberger, M., Müller, B., Pfetsch, M.E., Puchert, C., Rehfeldt, D., Schenker, S., Schwarz, R., Serrano, F., Shinano, Y., Weninger, D., Witt, J.T., Witzig, J.: The SCIP Optimization Suite 4.0. Technical Report 17-12, ZIB, Takustr. 7, 14195 Berlin (2017) |
| [54] | Marchand, H., Wolsey, L.A.: Aggregation and mixed integer rounding to solve MIPs. Oper. Res. 49(3), 363-371 (2001) · Zbl 1163.90671 |
| [55] | Margot, F.; Jünger, M. (ed.); Liebling, TM (ed.); Naddef, D. (ed.); Nemhauser, GL (ed.); Pulleyblank, WR (ed.); Reinelt, G. (ed.); Rinaldi, G. (ed.); Wolsey, LA (ed.), Symmetry in integer linear programming, 647-686 (2010), Berlin |
| [56] | Munguía, L.-M., Ahmed, S., Bader, D.A., Nemhauser, G.L., Shao, Y.: Alternating criteria search: a parallel large neighborhood search algorithm for mixed integer programs. Comput. Optim. Appl. 69(1), 1-24 (2017) · Zbl 1392.90085 |
| [57] | Pryor, J., Chinneck, J.W.: Faster integer-feasibility in mixed-integer linear programs by branching to force change. Comput. Oper. Res. 38(8), 1143-1152 (2011) · Zbl 1208.90122 |
| [58] | Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19(4), 534-541 (2007) · Zbl 1241.90092 |
| [59] | Salvagnin, D.; Simonis, H. (ed.), Detecting and exploiting permutation structures in MIPs, No. 8451, 29-44 (2014), Berlin · Zbl 1418.90240 |
| [60] | Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6, 445-454 (1994) · Zbl 0814.90093 |
| [61] | Wallace, C.: ZI round, a MIP rounding heuristic. J. Heuristics 16(5), 715-722 (2010) · Zbl 1201.90207 |
| [62] | Winkler, M.: Presolving for pseudo-Boolean optimization problems. Diploma thesis, Technische Universität Berlin (2014) |
| [63] | Witzig, J.; Berthold, T.; Heinz, S.; Salvagnin, D. (ed.); Lombardi, M. (ed.), Experiments with conflict analysis in mixed integer programming, 211-220 (2017), Cham · Zbl 1489.68261 |
| [64] | Wunderling, R.: Paralleler und objektorientierter Simplex-Algorithmus. Ph.D. thesis, Technische Universität Berlin (1996) · Zbl 0871.65048 |
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.
