Learning Interpretable Error Functions for Combinatorial Optimization Problem Modeling
This addresses the modeling challenge in constraint programming for practitioners, though it is incremental as it builds on existing error function concepts.
The paper tackles the difficulty of manually designing error functions for constraints in combinatorial optimization by proposing a method to automatically learn interpretable error functions from validity predicates, achieving scalability to high dimensions and good performance over incomplete spaces in experiments on five constraints.
In Constraint Programming, constraints are usually represented as predicates allowing or forbidding combinations of values. However, some algorithms exploit a finer representation: error functions. Their usage comes with a price though: it makes problem modeling significantly harder. Here, we propose a method to automatically learn an error function corresponding to a constraint, given a function deciding if assignments are valid or not. This is, to the best of our knowledge, the first attempt to automatically learn error functions for hard constraints. Our method uses a variant of neural networks we named Interpretable Compositional Networks, allowing us to get interpretable results, unlike regular artificial neural networks. Experiments on 5 different constraints show that our system can learn functions that scale to high dimensions, and can learn fairly good functions over incomplete spaces.