Learning Interpretable Error Functions for Combinatorial Optimization Problem Modeling
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.
Code (1)
Tasks
Combinatorial OptimizationvalidSimilar Papers 제목 키워드 기반
Active Value Querying to Minimize Additive Error in Subadditive Set Function Learning
Subadditive set functions play a pivotal role in computational economics (especially in combinatorial auctions), combinatorial optimization or artificial intelligence applications such as interpretable machine learning. …
Interpretable Machine LearningMaximizing Submodular or Monotone Approximately Submodular Functions by Multi-objective Evolutionary Algorithms
Evolutionary algorithms (EAs) are a kind of nature-inspired general-purpose optimization algorithm, and have shown empirically good performance in solving various real-word optimization problems. During the past two deca…
Combinatorial OptimizationEvolutionary AlgorithmsCombinatorial Bayesian Optimization with Random Mapping Functions to Convex Polytopes
Bayesian optimization is a popular method for solving the problem of global optimization of an expensive-to-evaluate black-box function. It relies on a probabilistic surrogate model of the objective function, upon which …
Bayesian Optimizationglobal-optimizationBayesian Optimization of Functions over Node Subsets in Graphs
We address the problem of optimizing over functions defined on node subsets in a graph. The optimization of such functions is often a non-trivial task given their combinatorial, black-box and expensive-to-evaluate nature…
Bayesian OptimizationCombinatorial OptimizationLearning for Robust Combinatorial Optimization: Algorithm and Application
Learning to optimize (L2O) has recently emerged as a promising approach to solving optimization problems by exploiting the strong prediction power of neural networks and offering lower runtime complexity than conventiona…
Combinatorial OptimizationEdge-computing