Combinatorial Decision, Optimization and Knowledge Compilation

Certain natural processes can be modelled by simple algorithms. For example, the evolution of a bacteria or virus by successive mutations can be viewed as a hill-climbing algorithm in a fitness landscape. A local maximum of fitness corresponds to a stable state in which evolution stagnates. In collaboration with researchers from Royal Holloway, London and Monash University, and Australia, we are investigating the theoretical conditions on the interactions between genes which guarantee a rapid (polynomial-time) convergence to a stable state.

The CSP constraint satisfaction problem is a generic combinatorial problem with diverse applications in Artificial Intelligence, Operations Research and Bio-informatics. This is the case for line drawings that pose problems of visual interpretation[9]. Inviolable constraints make it possible to detect the impossibility of objects corresponding to certain plots, while these same constraints associated with preferences for planar surfaces and right angles make it possible to reconstruct the shape of this object from the drawing. The time to solve the problem increases exponentially as its size increases. We have developed several algorithms (open source software ToulBar2 in collaboration with INRA) to solve these large optimization problems[6]. It has a natural generalisation to optimisation in the form of valued CSP (also known as cost function networks). Efficient constraint solvers use reduction operations, such as variable and value elimination, to mitigate the high computational complexity of constraint satisfaction or constrained optimisation. We are actively working on novel reduction operations for the (valued) CSP.

Since the (valued) CSP is NP-hard, it is natural to look for polytime-solvable subproblems (such as max-closed constraints encountered in the stable marriage problem or submodular cost functions encountered in min-cut max-flow problems). In continuous collaboration with researchers from the University of Oxford over a long period, we have investigated the possible characterisation of all tractable subproblems of the (valued) CSP. Although this characterisation was recently completed for languages of (valued) constraints, there still remain many open questions, especially concerning so-called hybrid tractable classes [1], [3].

If combinatorial problems are fully resolved online, it is extremely difficult to ensure system responsiveness. The so-called “information compilation” techniques propose to pre-treat the static part of the problem offline. We will then “compile” the model of the system to be diagnosed or the vehicle to be configured. One of the key points of the theoretical research carried out with CRIL, GREYC and ONERA, is the study of languages in which the model will be compact and will allow an effective response to requests [8], [2], [11], [12].

On a practical level, our collaborations with industrial teams (Renault, Cameleon) aim to integrate structures compiled within configurators for online sales or logistics planning and management systems.

Projets en cours

References

  • [1] David Cohen, Martin Cooper, Paidi Creed, Peter Jeavons, Stanislav Zivny. An Algebraic Theory of Complexity for Discrete Optimization. In : SIAM Journal on Computing, Society for Industrial and Applied Mathematics (SIAM), USA, Vol. 42 N. 5, pp. 1915-1939, 2013.(pdf)
  • [2] Hélène Fargier, Marquis Pierre, Alexandre Niveau, Nicolas Schmidt. A Knowledge Compilation Map for Ordered Real-Valued Decision Diagrams. In : AAAI Conference on Artificial Intelligence, AAAI Press, p. 1049-1055, juillet 2014.(pdf)
  • [3] Martin Cooper, Stanislav Zivny. Hybrid tractability of valued constraint problems. In : Artificial Intelligence, Elsevier, Vol. 175 N. 9-10, pp. 1555-1569, 2011.(pdf)
  • [4] Jean Marc Astesana, Laurent Cosserat, Hélène Fargier. Constraint-based vehicle configuration : a case study. In : International Conference on Tools with Artificial Intelligence (ICTAI 2010), IEEE Computer Society, pp. 0-1, October 2010.(pdf)
  • [5] Martin Cooper, Peter Jeavons, Andras Salamon. Generalizing constraint satisfaction on trees: hybrid tractability and variable elimination. In : Artificial Intelligence, Elsevier, Vol. 174, pp. 570-584, 2010.(pdf)
  • [6] Martin Cooper, Simon De Givry, Marti Sanchez, Thomas Schiex, Matthias Zytnicki, Tomas Werner. Soft arc consistency revisited. In : Artificial Intelligence, Elsevier, Vol. 174, pp. 449-478, 2010.(pdf)
  • [7] Meghyn Bienvenu, Hélène Fargier, Pierre Marquis. Knowledge Compilation in the Modal Logic S5 . In : Conference on Artificial Intelligence (AAAI 2010), AAAI Press, pp. 261-266, July 2010. (pdf)
  • [8] Hélène Fargier, Pierre Marquis. Disjunctive closures for knowledge compilation . In : Artificial Intelligence, Elsevier, Vol. 216, p. 129-162, août 2014.(pdf)
  • [9] Martin Cooper. Line Drawing Interpretation, Springer, 2008.
  • [10] Martin Cooper, Achref El Mouelhi, Cyril Terrioux, Bruno Zanuttini. On Broken Triangles. In : International Conference on Principles and Practice of Constraint Programming (CP 2014), Springer, pp. 9-24, 2014 (Best Paper).(pdf)
  • [11] Hélène Fargier, Frédéric Maris, Vincent Roger. Temporal Constraint Satisfaction Problems and Difference Decision Diagrams: A Compilation Map. Dans / In : IEEE International Conference on Tools with Artificial Intelligence, IEEE : Institute of Electrical and Electronics Engineers, p. 429-436, novembre / november 2015.(pdf)
  • [12] Christian Bessière, Hélène Fargier, Christophe Lecoutre. Computing and restoring global inverse consistency in interactive constraint satisfaction. Dans / In : Artificial Intelligence, Elsevier, Vol. 241, p. 153-169, octobre / october 2016.(pdf)