COALA : COntraintes, ALgorithmes et Applications
Courriel : firstname.lastname@example.org
Telephone : 0491282740
Courriel : email@example.com
Telephone : 0491288937
Courriel : firstname.lastname@example.org
Courriel : email@example.com
Telephone : 0442939031
Courriel : firstname.lastname@example.org
Telephone : 0491288367
Courriel : email@example.com
Telephone : 0491288951
Courriel : firstname.lastname@example.org
Courriel : email@example.com
Other staff members
Our work aims to equip Artificial Intelligence reasoning systems with effective resolution tools, both in theory and in practice, and they can also have strong repercussions in many practical applications.
Our research focuses mainly on the algorithmic associated with solving the satisfiability problem in propositional logic (SAT problem), satisfaction of problem-solving constraints (CSP) and their extensions (eg. optimization).
This work consists of developing theoretical tools and methods for solving combinatorial problems, highlighting tractable classes (polynomial fragments), designing efficient solvers and applying them to real-life problems.
The theoretical foundations are based on graph theory and complexity theory.
We develop 3 major axes:
development of theoretical tools and solving methods for SAT, CSP and their extensions to optimization
related issues and transfer to industrial applications
conception and realization of solvers
We coordinate the national ANR Demograph project since 2017 (http://www.lsis.org/demograph/).
The team publishes in the main journals specialized in Artificial Intelligence and Constraint Programming (Artificial Intelligence Jal, Constraints, Annals of Mathematics and Artificial Intelligence and SAT Journal) as well as in the major conferences of these domains (IJCAI, AAAI, CP and ECAI ). .
As an illustration, the ahmaxsat solver who won 3 gold medals at the 2014 Max-SAT World Competition and an multi-objective optimal maritime route (industrial application).
Legende 1. Performance of the ahmaxsat solver developed by COALA. This solver won 3 gold medals at the Max-SAT World Cup at FloC 2014 in Vienna. (FloC 2014 is to date the most important scientific event organized around logic, including mathematics and computer science)
Legende 2. Plot of an optimal trajectory (weather and fuel consumption) between Le Havre and New York obtained by a system developed with the team in the perspective of an industrial collaboration for the routing of cargo ships.
Year of production
Article dans une revue
- Victor Chepoi, Arnaud Labourel, Sébastien Ratel. On density of subgraphs of halved cubes. European Journal of Combinatorics, Elsevier, 2018. ⟨hal-01959093⟩
- Jérémie Chalopin, Victor Chepoi, Hirai Hiroshi, Damian Osajda. Weakly modular graphs and nonpositive curvature. Memoirs of the American Mathematical Society, American Mathematical Society, In press. ⟨hal-01787197⟩
- Jérémie Chalopin, Victor Chepoi, Damian Osajda. On two conjectures of Maurer concerning basis graphs of matroids. Journal of Combinatorial Theory, Series B, Elsevier, 2015, 114, pp.1-32. ⟨10.1016/j.jctb.2015.03.004⟩. ⟨hal-02065778⟩
Communication dans un congrès
- Victor Chepoi, Feodor Dragan, Michel Habib, Yann Vaxès, Hend Alrasheed. Fast Approximation of Centrality and Distances in Hyperbolic Graphs. COCOA 2018 - 12th Annual International Conference on Combinatorial Optimization and Applications, Dec 2018, Atlanta, United States. pp.1-23. ⟨hal-01955263⟩
- Jérémie Chalopin, Victor Chepoi, Feodor Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast Approximation and Exact Computation of Negative Curvature Parameters of Graphs. 34th International Symposium on Computational Geometry (SoCG 2018), Jun 2018, Budapest, Hungary. pp.22, ⟨10.4230/LIPIcs.SoCG.2018.22⟩. ⟨hal-01836063⟩
- Jérémie Chalopin, Victor Chepoi. A Counterexample to Thiagarajan's Conjecture on Regular Event Structures. ICALP 2017, 2017, Warsaw, Poland. ⟨10.4230/LIPIcs.ICALP.2017.101⟩. ⟨hal-01787205⟩
Pré-publication, Document de travail
- Jérémie Chalopin, Victor Chepoi. 1-Safe Petri nets and special cube complexes: equivalence and applications. 2019. ⟨hal-01863455v2⟩
- Jérémie Chalopin, Victor Chepoi, Shay Moran, Manfred K. Warmuth. Unlabeled sample compression schemes and corner peelings for ample and maximum classes. 2019. ⟨hal-02065772⟩
- Jérémie Chalopin, Victor Chepoi, Feodor F. Dragan, Guillaume Ducoffe, Abdulhakeem Mohammed, et al.. Fast approximation and exact computation of negative curvature parameters of graphs. 2018. ⟨hal-01737445⟩