Strong local consistency filtering for weighted constraint networks and other graphical models – FICOLOFO

Solving methods for cost functions netwoks are based on filtering algorithms or local consistency, similar to those of constraint programming but handling costs through processing problems maintaining equivalence. These algorithmic tools are extended to several global cost functions in the project.

New filtering methods, more powerful, more efficient. New global cost functions, capable of representing complex optimization problems. These results have been used to model and solve nurse rostering problems, crop allocation problems or protein design problems with an efficiency that can sometimes far exceed the efficiency of existing industrial tools (programming linear integer).

Continue to progress, improve the algorithmics of Cost Function Networks, offer additional global cost functions and a simpler more convenient way of modeling problems that out current flat WCSP format.

1. Mahuna Akplogan, Simon de Givry, Jean-Philippe Métivier, Gauthier Quesnel, Alexandre Joannon and Frédérick Garcia. Solving the Crop Allocation Problem using Hard and Soft Constraints. RAIRO - Operations Research / Volume 47 / Issue 02 / April 2013, pp 151-172.
1. D. Allouche, C. Bessiere , P. Boizumault , S. de Givry , P. Gutierrez , S. Loudni, JP. Metivier, T. Schiex. Filtering Decomposable Global Cost Functions. Proc. AAAI, 2012.
2. D. Allouche, A. Favier, S. de Givry, T. Schiex, M. Zytnicki, M. Fontaine, JP. Métivier, M. Sanchez, KL Leung. Combining exact WCSP techniques and VNS serach for solving MPE. Presentation invitee à UAI’2012, Los Angeles, USA (presentation du “PIC challenge).
1. M.C. Cooper and S. Zivny, Tractable Triangles and Cross-Free in Discrete Optimisation, JAIR, 2012. Volume 44, pages 445-490.
2. Traoré, Seydou ; Allouche, David ; André, Isabelle ; de Givry, Simon ; Katsirelos, George; Schiex, Thomas et Barbe, Sophie. A New Framework for Computational Protein Design through Cost Function Network Optimization. Bioinformatics, 2013.
3. Mathieu Fontaine, Samir Loudni et Patrice Boizumault. Exploiting Tree Decomposition for Guiding Neighborhoods Exploration for VNS. RAIRO - Operations Research / Volume 47 / Issue 02 / April 2013.
4. Soft Constraints for Pattern Mining. W. Ugarte, P. Boizumault, S. Loudni, B. Crémilleux, A. Lepailleur. Soumis à JIIS (Journal of Intelligent Information Systems).
5. Mining (Soft-) Skypatterns using Constraint Programming
W. Ugarte, P. Boizumault, S. Loudni, B. Crémilleux, A. Lepailleur
Soumis à Advances in Knowledge Discovery and Management Vol. 5 (AKDM-5).
1. Christian Bessiere, Patricia Gutierrez and Pedro Meseguer. Including Soft Global Constraints in DCOPs. Proc. of CP2012, Quebec city, Canada.
3. David Allouche, Seydou Traoré, Isabelle André, Simon de Givry, George Katsirelos, Sophie Barbe, Thomas Schiex.
Computational Protein Design as a Cost Function Network Optimization

Many combinatorial problems can be naturally modelled as a network of local interactions between discrete variables. In the simplest cases, the local interactions are simply compatibility/incompatibility relations and the network is a constraint network (CN). A fundamental property of such a network is its consistency (or feasibility): is it possible to find a value for each variable in the network in such a way that no incompatibility appears ? Answering this question defines the Constraint Satisfaction Problem (CSP).

This problem has been the object of intense research in the last 30 years and thee franch community is very weel represented at the international level. The dedicated techniques developed to solve CSP form the foundations of constraint programming languages such as IBM ILOG Solver, Cosytec CHIP, Cisco Eclipse... These tools have shown very good complementarity with mathematical programming techniques, for example in area such as resource scheduling and configuration... Many industrial size problems have been solved using this approach.

The ubiquitous and fundamental technique used inside these constraint solvers is the process of filtering by local consistency. This process consists in transforming a given constraint network in an equivalent network (having the same set of solutions) which is also more explicit and simple (characterized by specific properties). The most usual filtering techniques act at the level of single constraints and are known as filtering by arc consistency.

In 2000, these techniques have been extended to cost function networks (CFN, also called Weighted or Soft Constraint Networks). Cost function networks define an extension of pure constraint networks that allows to directly capture complex optimization problems mixing arbitrary constraints and cost functions (possibly non linear). In the last years, this technical advance has been combined with branch and bound, where it provides the required incremental lower bound. This approach has been sophisticated to the point where different hard combinatorial optimization problems, open for more than 15 years, have been solved to optimality. Cost function networks have also been used to solve very large problems in bioinformatics (genetics, molecular biology) adn aplied to large stochastic graphical models (bayesian nets and Markov random fields).

The aim of this project is to build on these recent successes by introducing stronger local consisyency filtering algorithms, capable of providing tighter lower bounds. The accumulated results in the field of constraint networks, more specifically on so-called "domain consistencies" and on "global constraints" (constraints with a semantics that allows for the definition of very time-efficient algorithms) will be instrumental in this process. This will require the extension of the year 2000 result on arc consistency to higher level of local consistency and to also take into acccount the precise semantics of significant "global cost functions". To guide these developments, we will rely on the complete set of benchmark problems accumulated in the "Cost function Library" completed with targeted applications: complex pedigreee diagnosis, maximum likelihood haplotyping (genetics), Nurse Rostering Prroblem instances as well as processing stochastic discrete graphical models derived from the genetics problems and from invasive speccies mapping problems modelled as Markov random fields. Beyond pure optimization problems, we will also use these techniques to give approximate computations with guarantees of the normalizing constant (Z) in these models, a difficult problem (#P-complete) central in the processing random Markov fields and more generally in reasoning under uncertainty.