×

Nutmeg: a MIP and CP hybrid solver using branch-and-check. (English) Zbl 1459.90133

Summary: This paper describes the implementation of Nutmeg, a solver that hybridizes mixed integer linear programming and constraint programming using the branch-and-cut style of logic-based Benders decomposition known as branch-and-check. Given a high-level constraint programming model, Nutmeg automatically derives a mixed integer programming master problem that omits global constraints with weak linear relaxations, and a constraint programming subproblem identical to the original model. At every node in the branch-and-bound search tree, the linear relaxation computes dual bounds and proposes solutions, which are checked for feasibility of the omitted constraints in the constraint programming subproblem. In the case of infeasibility, conflict analysis generates Benders cuts, which are appended to the linear relaxation to cut off the candidate solution. Experimental results show that Nutmeg’s automatic decomposition outperforms pure constraint programming and pure mixed integer programming on problems known to have successful implementations of logic-based Benders decomposition, but performs poorly on general problems, which lack specific decomposable structure. Nonetheless, Nutmeg outperforms the standalone approaches on one problem with no known decomposable structure, providing preliminary indications that a hand-tailored decomposition for this problem could be worthwhile. On the whole, Nutmeg serves as a valuable tool for novice modelers to try hybrid solving and for expert modelers to quickly compare different logic-based Benders decompositions of their problems.

MSC:

90C11 Mixed integer programming
90C57 Polyhedral combinatorics, branch-and-bound, branch-and-cut

Software:

CHUFFED; SCIP; MiniZinc; GCG
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Achterberg, T., Conflict analysis in mixed integer programming, Discrete Optim, 4, 1, 4-20 (2007) · Zbl 1169.90414 · doi:10.1016/j.disopt.2006.10.006
[2] Achterberg, T., SCIP: solving constraint integer programs, Math Program Comput, 1, 1, 1-41 (2009) · Zbl 1171.90476 · doi:10.1007/s12532-008-0001-1
[3] Albareda-Sambola, M.; Fernández, E.; Laporte, G., The capacity and distance constrained plant location problem, Comput Oper Res, 36, 597-611 (2009) · Zbl 1163.90583 · doi:10.1016/j.cor.2007.10.017
[4] Beck JC (2010) Checking-up on branch-and-check. In: Cohen D (ed) Principles and practice of constraint programming - CP 2010, lecture notes in computer science, vol 6308. Springer, Berlin, pp 84-98
[5] Belov G, Stuckey PJ, Tack G, Wallace M (2016) Improved linearization of constraint programming models. In: Rueher M (ed) Principles and practice of constraint programming: 22nd international conference, CP 2016, Toulouse, France, September 5-9, 2016. proceedings. Springer International Publishing, pp 49-65
[6] Benchimol, P.; van Hoeve, WJ; Régin, JC; Rousseau, LM; Rueher, M., Improved filtering for weighted circuit constraints, Constraints, 17, 3, 205-233 (2012) · Zbl 1309.90115 · doi:10.1007/s10601-012-9119-x
[7] Benders, JF, Partitioning procedures for solving mixed-variables programming problems, Numerische mathematik, 4, 1, 238-252 (1962) · Zbl 0109.38302 · doi:10.1007/BF01386316
[8] Bensana, E.; Lemaitre, M.; Verfaillie, G., Earth observation satellite management, Constraints, 4, 3, 293-299 (1999) · Zbl 0963.90507 · doi:10.1023/A:1026488509554
[9] Chu GG Improving combinatorial optimization. Ph.D. thesis, University of Melbourne (2011). http://hdl.handle.net/11343/36679
[10] Conforti, M.; Cornuéjols, G.; Zambelli, G., Integer programming, vol 271 (2014), Berlin: Springer, Berlin · Zbl 1307.90001
[11] Davies TO, Gange G, Stuckey PJ (2017) Automatic logic-based Benders decomposition with MiniZinc. In: AAAI, pp 787-793
[12] Feydy T, Stuckey PJ (2009) Lazy clause generation reengineered. In: Gent IP (ed) Principles and practice of constraint programming - CP 2009: 15th international conference, CP 2009 lisbon, portugal, september 20-24, 2009 proceedings. Springer, Berlin, pp 352-366
[13] Focacci, F.; Lodi, A.; Milano, M., Optimization-oriented global constraints, Constraints, 7, 3-4, 351-365 (2002) · Zbl 1028.68024 · doi:10.1023/A:1020589922418
[14] Fontaine D, Michel L, Van Hentenryck P (2014) Constraint-based Lagrangian relaxation. In: O’sullivan B (ed) Principles and practice of constraint programming: 20th international conference, CP 2014, Lyon, France, September 8-12, 2014. proceedings. lecture notes in computer science, vol 8656. Springer International Publishing, pp 324-339
[15] Gamrath, G., Generic branch-cut-and-price (2010), Technische Universität Berlin: Ph.D. thesis, Technische Universität Berlin
[16] Gamrath G, Lübbecke ME (2010) Experiments with a generic Dantzig-Wolfe decomposition for integer programs. In: Festa P, Experimental algorithms: 9th international symposium SEA 2010 Ischia Island (eds). Springer, Berlin, pp 239-252
[17] Gange G, Berg J, Demirović E, Stuckey PJ (2020) Core-guided and core-boosted search for CP. In: Proceedings of the 7th international conference on the integration of constraint programming, artificial intelligence, and operations research. (to appear)
[18] Gleixner A, Bastubbe M, Eifler L, Gally T, Gamrath G, Gottwald RL, Hendel G, Hojny C, Koch T, Lübbecke ME, Maher SJ, Miltenberger M, Müller B, Pfetsch ME, Puchert C, Rehfeldt D, Schlösser F, Schubert C, Serrano F, Shinano Y, Viernickel JM, Walter M, Wegscheider F, Witt JT, Witzig J (2018) The SCIP Optimization Suite 6.0. ZIB-Report 18-26, Zuse Institute Berlin. http://nbn-resolving.de/urn:nbn:de:0297-zib-69361
[19] Hooker JN (2004) A hybrid method for planning and scheduling. In: Wallace M (ed) Principles and practice of constraint programming - CP 2004, lecture notes in computer science, vol 3258. Springer, Berlin, pp 305-316 · Zbl 1152.90445
[20] Hooker, JN, Planning and scheduling by logic-based Benders decomposition, Oper Res, 55, 3, 588-602 (2007) · Zbl 1167.90512 · doi:10.1287/opre.1060.0371
[21] Hooker, JN; Ottosson, G., Logic-based Benders decomposition, Math Program, 96, 1, 33-60 (2003) · Zbl 1023.90082 · doi:10.1007/s10107-003-0375-9
[22] Junker U, Karisch SE, Kohl N, Vaaben B, Fahle T, Sellmann M (1999) A framework for constraint programming based column generation. In: Jaffar J (ed) Principles and practice of constraint programming - CP’99: 5th international conference, CP’99, alexandria, VA, USA, October 11-14, 1999. Proceedings. Springer, pp 261-274 · Zbl 0983.90059
[23] Lam E (2017) Hybrid optimization of vehicle routing problems. Ph.D. thesis, University of Melbourne. http://hdl.handle.net/11343/220534
[24] Lam, E.; Van Hentenryck, P., A branch-and-price-and-check model for the vehicle routing problem with location congestion, Constraints, 21, 3, 394-412 (2016) · Zbl 1368.90115 · doi:10.1007/s10601-016-9241-2
[25] Lam E, Van Hentenryck P (2017) Branch-and-check with explanations for the vehicle routing problem with time windows. In: Beck JC (ed) Principles and practice of constraint programming: 23rd international conference, CP 2017, Melbourne, VIC, Australia, August 28 - September 1, 2017, Proceedings. Springer, Cham, pp 579-595
[26] Marques Silva JaP, Sakallah KA (1996) GRASP-a new search algorithm for satisfiability. In: Proceedings of the 1996 IEEE/ACM international conference on computer-aided design, ICCAD ’96. IEEE Computer Society, pp 220-227
[27] Nethercote N, Stuckey PJ, Becket R, Brand S, Duck GJ, Tack G (2007) Minizinc: towards a standard CP modelling language. In: Bessière C (ed) Principles and practice of constraint programming - CP 2007. Springer, Berlin, pp 529-543
[28] Ohrimenko, O.; Stuckey, PJ; Codish, M., Propagation via lazy clause generation, Constraints, 14, 3, 357-391 (2009) · Zbl 1192.68654 · doi:10.1007/s10601-008-9064-x
[29] Refalo P (2000) Linear formulation of constraint programming models and hybrid solvers. In: Dechter R (ed) Principles and practice of constraint programming - CP 2000. Springer, Berlin, pp 369-383 · Zbl 1044.68792
[30] Régin, JC, Cost-based arc consistency for global cardinality constraints, Constraints, 7, 3, 387-405 (2002) · Zbl 1028.68157 · doi:10.1023/A:1020506526052
[31] Schutt, A.; Feydy, T.; Stuckey, PJ; Wallace, MG, Explaining the cumulative propagator, Constraints, 16, 3, 250-282 (2010) · Zbl 1226.68099 · doi:10.1007/s10601-010-9103-2
[32] Shen K, Schimpf J (2005) Eplex: Harnessing mathematical programming solvers for constraint logic programming. In: Principles and practice of constraint programming: 11th international conference, CP2005, proceedings, LNCS, vol 3709. Springer, pp 622-636
[33] Steiger R, van Hoeve WJ, Szymanek R (2011) An efficient generic network flow constraint. In: Proceedings of the 2011 ACM symposium on applied computing. ACM, pp 893-900
[34] Taşkin ZC (2010) Benders decomposition. In: Wiley encyclopedia of operations research and management science. Wiley
[35] Thorsteinsson E (2001) Branch-and-check: a hybrid framework integrating mixed integer programming and constraint logic programming. In: Walsh T (ed) Principles and practice of constraint programming - CP. lecture notes in computer science, vol 2239. Springer, Berlin, pp 16-30 · Zbl 1067.68677
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.