SEER: Supervised Learning to Control Energetic Reasoning
Artificial Intelligence
Summary
The authors look at a method called Constraint Programming, which helps solve problems by narrowing down possibilities using rules called propagators. Different problems might need different propagators that vary in speed and effectiveness, and choosing the right one is tricky. They suggest using Machine Learning to create a guide (an oracle) that decides when to use more powerful but slower propagators during solving. Their tests focus on a specific kind of propagator called Energetic Reasoning, showing their approach can predict well and offering ideas on what features help make those predictions. They also discuss challenges in building such a decision-making tool.
Authors
Sascha Van Cauwelaert, Michele Lombardi, Pierre Schaus
Abstract
One of the main strengths of Constraint Programming is the ability to reduce the search space via propagation. However, propagation is a double-edged sword, with more pruning power coming at the price of larger computation time. For each problem constraint, the best propagator depends on the specific instance and may change at search time. In the literature, Machine Learning (ML) techniques and activity-based heuristics have been applied respectively for choosing (statically) the propagators for a batch of problems and to adapt (dynamically) the propagation strength. We propose to merge those efforts by using an oracle function, obtained via ML, to decide whether to run complex propagators for a target constraint. A combination of design choices makes the approach flexible and easy to embed in state-of-the-art solvers. In this paper, we focus on investigating the feasibility of building an oracle for the Energetic Reasoning propagator. Our experiments show that high prediction accuracy can be obtained, provide suggestions for classification features, and highlight important issues to address when building such an oracle.