Automatic Core-Guided Reformulation via Constraint Explanation and Condition Learning

SAT and propagation solvers often underperform for optimisation models whose objective sums many single-variable terms. MaxSAT solvers avoid this by detecting and exploiting cores: subsets of these terms that cannot collectively take their lower bounds. Previous work has shown manual analysis of cores can help define model reformulations likely to speed up solving for many model instances. This paper presents a method to automate this process. For each selected core the method identifies the instance constraints that caused it; infers the model constraints and parameters that explain how these instance constraints were formed; and learns the conditions that made those model constraint instances generate cores, while others did not. It then uses this information to reformulate the objective. The empirical evaluation shows this method can produce useful reformulations. Importantly, the method can be useful in many other situations that require explaining a set of constraints.

Authors

• Kevin Leo Department of Data Science & AI (DSAI), Monash University, Australia
• Grame Gange Department of Data Science & AI (DSAI), Monash University, Australia
• Maria Garcia de la Banda Department of Data Science & AI (DSAI), Monash University, Australia ARC Training Centre in Optimisation Technologies, Integrated Methodologies, and Applications (OPTIMA), Australia
• Mark Wallace Monash University

Keywords

• CSO: Constraint Learning and Acquisition
• CSO: Constraint Optimization
• CSO: Constraint Programming
• CSO: Constraint Satisfaction
• CSO: Mixed Discrete/Continuous Optimization
• CSO: Satisfiability
• CSO: Solvers and Tools