7533
eng
reportzib
0
--
2019-12-02
--
Conflict-Free Learning for Mixed Integer Programming
Conflict learning plays an important role in solving mixed integer programs (MIPs) and is implemented in most major MIP solvers. A major step for MIP conflict learning is to aggregate the LP relaxation of an infeasible subproblem to a single globally valid constraint, the dual proof, that proves infeasibility within the local bounds. Among others, one way of learning is to add these constraints to the problem formulation for the remainder of the search.
We suggest to not restrict this procedure to infeasible subproblems, but to also use global proof constraints from subproblems that are not (yet) infeasible, but can be expected to be pruned soon. As a special case, we also consider learning from integer feasible LP solutions. First experiments of this conflict-free learning strategy show promising results on the MIPLIB2017 benchmark set.
1438-0064
urn:nbn:de:0297-zib-75338
10.1007/978-3-030-58942-4_34
Integration of AI and OR Techniques in Constraint Programming. CPAIOR 2020
Jakob Witzig
Jakob Witzig
Timo Berthold
ZIB-Report
19-59
eng
uncontrolled
mixed integer programming
eng
uncontrolled
conflict analysis
eng
uncontrolled
dual proof analysis
eng
uncontrolled
no-good learning
eng
uncontrolled
solution learning
Integer programming
Mixed integer programming
Mathematical Optimization
Mathematical Optimization Methods
Berthold, Timo
Witzig, Jakob
ASTfSCM
MIP-ZIBOPT
MODAL-SynLab
Siemens
BEAM-ME
MODAL-Gesamt
HPO-NAVI
https://opus4.kobv.de/opus4-zib/files/7533/ZR-19-59__witzig_berthold__conflict_free_learning_for_mip.pdf