Combinatorial Optimization and learning

The team explores 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

Clause learning based on explanations on global constraints for intelligent tree search

Learning for combinatorial optimization

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.

.

Time savings obtained by using 0-1 programming in a mahine learning algorithm depending of the desired true positive rate.  

Combinatorial optimization for learning

Recent works aim, 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.

 

Some ROC publications on optimization and learning