Learning Objective Boundaries for Constraint Optimization Problems
  Constraint Optimization Problems (COP) are often considered without
sufficient knowledge on the boundaries of the objective variable to optimize.
When available, tight boundaries are helpful to prune the search space or
estimate problem characteristics. Finding close boundaries, that correctly
under- and overestimate the optimum, is almost impossible without actually
solving the COP. This paper introduces Bion, a novel approach for boundary
estimation by learning from previously solved instances of the COP. Based on
supervised machine learning, Bion is problem-specific and solver-independent
and can be applied to any COP which is repeatedly solved with different data
inputs. An experimental evaluation over seven realistic COPs shows that an
estimation model can be trained to prune the objective variables' domains by
over 80%. By evaluating the estimated boundaries with various COP solvers, we
find that Bion improves the solving process for some problems, although the
effect of closer bounds is generally problem-dependent.
