Learning Objective Boundaries for Constraint Optimization Problems
This work addresses a domain-specific challenge for practitioners in optimization, offering an incremental improvement by learning boundaries to potentially enhance solver efficiency.
The paper tackles the problem of estimating objective variable boundaries in Constraint Optimization Problems (COP) without solving them, introducing Bion, a supervised learning approach that prunes objective domains by over 80% based on training from solved instances.
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.