Combinatorial Optimization & Learning
We explore the relationship between combinatorial optimization and learning techniques in two complementary ways. On the one hand, we seek to integrate learning mechanisms within tree search for problem solving. On the other hand, in a dual way, other work aims at improving machine learning techniques by integrating combinatorial optimization methods.
Learning for combinatorial optimization
Clause learning based on explanations on global constraints for intelligent tree search
The team works on the integration of learning mechanisms within tree search for solving combinatorial optimization problems. These mechanisms can be implemented by simple, but effective conflict directed search algorithms where weights associated to variables are updated along the search. Recent work goes further by integrating explanations of failures caused by constraints in clause learning mechanisms inspired by the modern SAT solvers. These results improved the state of the art on a variety of scheduling problems.
Combinatorial optimization for learning
Time savings obtained by using 0-1 programming in a machine learning algorithm depending of the desired true positive rate.
This works aims, as a dual technique to the above-mentioned one, at improving machine learning techniques with the help of combinatorial optimization. A machine learning tool such as the soft cascade detector, has been significantly accelerated by modeling the minimization of the mean response time needed by the machine learning algorithm to perform a detection as an integer linear problem. A third association of machine learning and optimization/constraint satisfaction has been considered by the proposition of efficient algorithms that learn constraint satisfaction models.
