Nutmeg: a MIP and CP Hybrid Solver Using Branch-and-Check

作     者：Lam, Edward Gange, Graeme Stuckey, Peter J. Van Hentenryck, Pascal Dekker, Jip J. 

作者机构：Department of Data Science and Artificial Intelligence Faculty of Information Technology Monash University Melbourne VIC Australia H. Milton Stewart School of Industrial and Systems Engineering Georgia Institute of Technology Atlanta GA United States 

出 版 物：《Operations Research Forum》 (SN Oper. Res. Forum)

年 卷 期：2020年第1卷第3期

页      面：1-27页

主　　题：Branch-and-check Conflict analysis Constraint programming Dual bound Hybridization Lazy clause generation Linear constraints Logic-based Benders decomposition Mixed integer programming Nogood 

摘      要：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. © 2020, Springer Nature Switzerland AG.