Predictive Machine Learning of Objective Boundaries for Solving COPs
  Solving Constraint Optimization Problems (COPs) can be dramatically
simplified by boundary estimation, that is, providing tight boundaries of cost
functions. By feeding a supervised Machine Learning (ML) model with data
composed of known boundaries and extracted features of COPs, it is possible to
train the model to estimate boundaries of a new COP instance. In this paper, we
first give an overview of the existing body of knowledge on ML for Constraint
Programming (CP) which learns from problem instances. Second, we introduce a
boundary estimation framework that is applied as a tool to support a CP solver.
Within this framework, different ML models are discussed and evaluated
regarding their suitability for boundary estimation, and countermeasures to
avoid unfeasible estimations that avoid the solver to find an optimal solution
are shown. Third, we present an experimental study with distinct CP solvers on
seven COPs. Our results show that near-optimal boundaries can be learned for
these COPs with only little overhead. These estimated boundaries reduce the
objective domain size by 60-88% and can help the solver to find near-optimal
solutions early during search.
