Shift-and-propagate. (English) Zbl 1360.90297
Summary: In recent years, there has been a growing interest in the design of general purpose primal heuristics for use inside complete mixed integer programming solvers. Many of these heuristics rely on an optimal LP solution, which may take a significant amount of time to find. In this paper, we address this issue by introducing a pre-root primal heuristic that does not require a previously found LP solution. This heuristic, named \(\mathsf {Shift-and-Propagate}\), applies domain propagation techniques to quickly drive a variable assignment towards feasibility. Computational experiments indicate that this heuristic is a powerful supplement to existing rounding and propagation heuristics.
MSC:
| 90C59 | Approximation methods and heuristics in mathematical programming |
| 90C11 | Mixed integer programming |
| 90C10 | Integer programming |
Software:
Octane; SCIP; Gurobi; COIN-OR; DINS; FEASPUMP; CPLEX; XPRESS; SYMPHONY; Cbc; MIPLIB2003; MIPLIB; Chaff; SoPlexReferences:
| [1] | Achterberg, T.: SCIP—a framework to integrate constraint and mixed integer programming. Tech. Rep. 04-19, Zuse Institute Berlin (2004). http://www.zib.de/Publications/abstracts/ZR-04-19/ · Zbl 1087.90052 |
| [2] | Achterberg, T.: Constraint integer programming. Ph.D. thesis, TU Berlin (2007) · Zbl 1169.90414 |
| [3] | Achterberg, T., Berthold, T.: Improving the feasibility pump. Discret. Optim. Spec. Issue 4(1), 77-86 (2007) · Zbl 1170.90443 · doi:10.1016/j.disopt.2006.10.004 |
| [4] | Achterberg, T., Koch, T., Martin, A.: MIPLIB 2003. Oper. Res. Lett. 34(4), 1-12 (2006) · Zbl 1133.90300 · doi:10.1016/j.orl.2005.07.009 |
| [5] | Achterberg, T.; Berthold, T.; Hendel, G.; Klatte, D. (ed.); Lüthi, HJ (ed.); Schmedders, K. (ed.), Rounding and propagation heuristics for mixed integer programming, 71-76 (2012), Berlin · Zbl 1306.90100 · doi:10.1007/978-3-642-29210-1_12 |
| [6] | Andersen, E., Andersen, K.: Presolving in linear programming. Math. Program. 71, 221-245 (1995) · Zbl 0846.90068 |
| [7] | Balas, E., Ceria, S., Dawande, M., Margot, F., Pataki, G.: OCTANE: a new heuristic for pure 0-1 programs. Oper. Res. 49(2), 207-225 (2001) · Zbl 1163.90654 · doi:10.1287/opre.49.2.207.13535 |
| [8] | Balas, E., Schmieta, S., Wallace, C.: Pivot and shift—a mixed integer programming heuristic. Discret. Optim. 1(1), 3-12 (2004) · Zbl 1087.90052 · doi:10.1016/j.disopt.2004.03.001 |
| [9] | Bertacco, L., Fischetti, M., Lodi, A.: A feasibility pump heuristic for general mixed-integer problems. Discret. Optim. Spec. Issue 4(1), 63-76 (2007) · Zbl 1169.90415 · doi:10.1016/j.disopt.2006.10.001 |
| [10] | Berthold, T.: Primal heuristics for mixed integer programs. Diploma thesis, Technische Universität Berlin (2006) |
| [11] | Berthold, T.; Kalcsics, J. (ed.); Nickel, S. (ed.), Heuristics of the branch-cut-and-price-framework SCIP, 31-36 (2008), Berlin · Zbl 1209.90356 · doi:10.1007/978-3-540-77903-2_5 |
| [12] | Berthold, T.: Measuring the impact of primal heuristics. Oper. Res. Lett. 41(6), 611-614 (2013) · Zbl 1287.90037 · doi:10.1016/j.orl.2013.08.007 |
| [13] | Berthold, T.; Feydy, T.; Stuckey, PJ; Lodi, A. (ed.); Milano, M. (ed.); Toth, P. (ed.), Rapid learning for binary programs, No. 6140, 51-55 (2010), Berlin · Zbl 1285.68151 |
| [14] | Bessiere, C.; Rossi, F. (ed.); Beek, P. (ed.); Walsh, T. (ed.), Constraint propagation, 29-83 (2006), Amsterdam · doi:10.1016/S1574-6526(06)80007-6 |
| [15] | Bixby, R.E., Ceria, S., McZeal, C.M., Savelsbergh, M.W.: An updated mixed integer programming library: MIPLIB 3.0. Optima 58, 12-15 (1998) |
| [16] | Bixby, RE; Fenelon, M.; Gu, Z.; Rothberg, E.; Wunderling, R.; Powell, M. (ed.); Scholtes, S. (ed.), MIP: theory and practice—closing the gap, 19-49 (2000), Dordrecht · Zbl 0986.90025 · doi:10.1007/978-0-387-35514-6_2 |
| [17] | Brearley, A., Mitra, G., Williams, H.: Analysis of mathematical programming problems prior to applying the simplex algorithm. Math. Program. 8, 54-83 (1975) · Zbl 0317.90037 · doi:10.1007/BF01580428 |
| [18] | COIN-OR branch-and-cut MIP solver. https://projects.coin-or.org/Cbc. Accessed 15 Dec 2014 · Zbl 1201.90207 |
| [19] | Danna, E., Rothberg, E., Pape, C.L.: Exploring relaxation induced neighborhoods to improve MIP solutions. Math. Program. A 102(1), 71-90 (2004) · Zbl 1131.90036 · doi:10.1007/s10107-004-0518-7 |
| [20] | FICO Xpress-Optimizer. http://www.fico.com/en/Products/DMTools/xpress-overview/Pages/Xpress-Optimizer.aspx. Accessed 15 Dec 2014 |
| [21] | Fischetti, M., Salvagnin, D.: Feasibility pump 2.0. Math. Program. C 1, 201-222 (2009) · Zbl 1180.90208 · doi:10.1007/s12532-009-0007-3 |
| [22] | 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 |
| [23] | Fischetti, M., Glover, F., Lodi, A.: The feasibility pump. Math. Program. 104(1), 91-104 (2005) · Zbl 1077.90039 · doi:10.1007/s10107-004-0570-3 |
| [24] | Ghosh, S.; Fischetti, M. (ed.); Williamson, DP (ed.), DINS, a MIP improvement heuristic, No. 4513, 310-323 (2007), Heidelberg · Zbl 1136.90419 · doi:10.1007/978-3-540-72792-7_24 |
| [25] | Glover, F., Laguna, M.: General purpose heuristics for integer programming - part I. J. Heuristics 2(4), 343-358 (1997a) · Zbl 0887.90123 · doi:10.1007/BF00132504 |
| [26] | Glover, F., Laguna, M.: General purpose heuristics for integer programming—part II. J. Heuristics 3(2), 161-179 (1997b) · Zbl 0898.90094 · doi:10.1023/A:1009631530787 |
| [27] | Glover, F., Løkketangen, A., Woodruff, D.L.: Scatter search to generate diverse MIP solutions. In: Laguna, M., González-Velarde, J.L. (eds.) Computing Tools for Modeling, Optimization and Simulation. Operations Research/Computer Science Interfaces Series, vol. 12, pp. 299-317. Springer US (2000) |
| [28] | GUROBI Optimizer. http://www.gurobi.com/products/gurobi-optimizer/gurobi-overview. Accessed 15 Dec 2014 |
| [29] | Hansen, P., Mladenović, N., Urošević, D.: Variable neighborhood search and local branching. Comput. Oper. Res. 33(10), 3034-3045 (2006) · Zbl 1086.90042 · doi:10.1016/j.cor.2005.02.033 |
| [30] | Harvey, W.D., Ginsberg, M.L.: Limited discrepancy search. Int. Jt. Conf. Artif. Intell. 14, 607-615 (1995) |
| [31] | Hendel, G.: New rounding and propagation heuristics for mixed integer programming. Bachelor’s thesis, TU Berlin (2011) |
| [32] | Ibm, ILOG CPLEX Optimizer. http://www-01.ibm.com/software/integration/optimization/cplex-optimizer/. Accessed 15 Dec 2014 |
| [33] | Jussien, N., Lhomme, O.: Local search with constraint propagation and conflict-based heuristics. Artif. Intell. 139(1), 21-45 (2002) · Zbl 1015.68056 · doi:10.1016/S0004-3702(02)00221-7 |
| [34] | 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) · doi:10.1007/s12532-011-0025-9 |
| [35] | Lin, S., Kernighan, B.W.: An effective heuristic algorithm for the travelling-salesman problem. Oper. Res. 21, 498-516 (1973) · Zbl 0256.90038 · doi:10.1287/opre.21.2.498 |
| [36] | Lodi, A.: The heuristic (dark) side of MIP solvers. In: Talbi, E.G. (ed.) Hybrid Metaheuristics, Studies in Computational Intelligence, vol. 434, pp. 273-284. Springer, Berlin (2013). doi:10.1007/978-3-642-30671-6_10 · Zbl 1209.90356 |
| [37] | Løkketangen, A.: Heuristics for 0-1 mixed integer programming. In: Pardalos, P.M., Resende, M.G.C. (eds.) Handbook of Applied Optimization. Oxford University Press (2002) |
| [38] | Løkketangen, A., Glover, F.: Solving zero/one mixed integer programming problems using Tabu search. Eur. J. Oper. Res. 106, 624-658 (1998) · Zbl 0991.90091 · doi:10.1016/S0377-2217(97)00295-6 |
| [39] | Mareček, J.: Exploiting structure in integer programs. Ph.D. thesis, University of Nottingham (2011) |
| [40] | Minton, S., Johnston, M.D., Philips, A.B., Laird, P.: Solving large-scale constraint satisfaction and scheduling problems using a heuristic repair method. In: Proceedings of the eighth National conference on Artificial intelligence, pp. 17-24. AAAI Press (1990) |
| [41] | Moskewicz, M.W., Madigan, C.F., Zhao, Y., Zhang, L., Malik, S.: Chaff: Engineering an efficient SAT solver. In: Annual ACM IEEE Design Automation Conference, pp. 530-535. ACM (2001) |
| [42] | Pesant, G., Quimper, C.G., Zanarini, A.: Counting-based search: branching heuristics for constraint satisfaction problems. J. Artif. Intell. Res. 43(1), 173-210 (2012) · Zbl 1237.68193 |
| [43] | Rothberg, E.: An evolutionary algorithm for polishing mixed integer programming solutions. INFORMS J. Comput. 19(4), 534-541 (2007) · Zbl 1241.90092 · doi:10.1287/ijoc.1060.0189 |
| [44] | Rothberg, E.: Personal communication (2013) · Zbl 0814.90093 |
| [45] | Ruml, W.: Incomplete tree search using adaptive probing. In: International Joint Conference on Artificial Intelligence, pp. 235-241 (2001) · Zbl 1306.90100 |
| [46] | Savelsbergh, M.W.P.: Preprocessing and probing techniques for mixed integer programming problems. ORSA J. Comput. 6, 445-454 (1994) · Zbl 0814.90093 · doi:10.1287/ijoc.6.4.445 |
| [47] | SCIP. Solving Constraint Integer Programs. http://scip.zib.de/. Accessed 15 Dec 2014 · Zbl 1169.90415 |
| [48] | Selman, B., Kautz, H.A., Cohen, B.: Noise strategies for improving local search. In: Proceedings of the twelfth national conference on Artificial intelligence (vol. 1), AAAI ’94, pp. 337-343. American Association for Artificial Intelligence (1994) |
| [49] | SoPlex. An open source LP solver implementing the revised simplex algorithm. http://soplex.zib.de/. Accessed 15 Dec 2014 · Zbl 1170.90443 |
| [50] | SYMPHONY. development home page. https://projects.coin-or.org/SYMPHONY. Accessed 15 Dec 2014 |
| [51] | Wallace, C.: ZI round, a MIP rounding heuristic. J. Heuristics 16(5), 715-722 (2010) · Zbl 1201.90207 · doi:10.1007/s10732-009-9114-6 |
| [52] | Walser, J.P.: Integer Optimization by Local Search, Lecture Notes in Computer Science, vol. 1637. Springer, Berlin (1999) · Zbl 0934.90053 · doi:10.1007/3-540-48369-1 |
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.
