Philippe Codognet

ICAART Conference 2023 Invited Paper

Quantum Annealing for Constraint Satisfaction and Constrained Optimization

• Philippe Codognet

Even if the debate is still going on whether quantum supremacy has already been achieved or not, it is clear that quantum computing will have a profound impact on computer science in the next 10 to 20 years. In the domains of combinatorial optimization and problem solving, which are ubiquitous in AI, the use of quantum computers to solve concrete problems has started to raise tremendous interest, in both the gatebased paradigm with the Quantum Approximate Optimization Algorithm and in the adiabatic computing paradigm with Quantum Annealing (QA). QA is an alternative type of computation in which problems are encoded in quantum Hamiltonians (energy functions) and quantum dynamics is used to find solutions (ground states of minimal energy). QA can be seen as derived from simulated annealing, but taking advantage of the quantum tunneling effect to overcome energy barriers and therefore escape local minima during the computation. Quantum computers such as the D-Wave systems are implementing those ideas in hardware, as well as quantum-inspired devices based on classical electronics such as Fujitsu's Digital Annealing Unit. From a programming point of view, the use of QA computers for solving combinatorial problems is getting easier by the general adoption of the Quadratic Unconstrained Binary Optimization (QUBO) formalism. QUBO has become a standard input language for all "Ising Machines" developed by D-Wave, NTT, Fujitsu, Hitachi, Toshiba, Fixstars Amplify and NEC.

AAAI Conference 2015 Conference Paper

Solving Hard Stable Matching Problems via Local Search and Cooperative Parallelization

• Danny Munera
• Daniel Diaz
• Salvador Abreu
• Francesca Rossi
• Vijay Saraswat
• Philippe Codognet

Stable matching problems have several practical applications. If preference lists are truncated and contain ties, finding a stable matching with maximal size is computationally difficult. We address this problem using a local search technique, based on Adaptive Search and present experimental evidence that this approach is much more efficient than state-of-the-art exact and approximate methods. Moreover, parallel versions (particularly versions with communication) improve performance so much that very large and hard instances can be solved quickly.

SAT Conference 2012 Conference Paper

Towards Massively Parallel Local Search for SAT - (Poster Presentation)

• Alejandro Arbelaez
• Philippe Codognet

Abstract Parallel portfolio-based algorithms have become a standard methodology for building parallel algorithms for SAT. In this methodology, different algorithms (or the same one with different random seeds) compete to solve a given problem instance. Moreover, the portfolio is usually equipped with cooperation, this way algorithms exchange important knowledge acquired during the search to solve a given problem instance. Portfolio algorithms based on complete solvers exchange learned clauses which are incorporated within each search engine (e. g. ManySAT [1] and plingeling), while those based on incomplete solvers [2] exchange the best assignment for the variables found so far in order to properly craft a new assignment for the variables to restart from. These strategies range from a voting mechanism where each algorithm in the portfolio suggests a value for each variable to probabilistic constructions.

IJCAI Conference 2003 Conference Paper

Solving Finite Domain Constraint Hierarchies by Local Consistency and Tree Search

• Stefano Bistarelli
• Philippe Codognet
• H K C Hui
• J. H. M. Lee

We provide a reformulation of the constraint hierarchies (CHs) framework based on the notion of error indicators. Adapting the generalized view of local consistency in semiring-based constraint satisfaction problems (SCSPs), we define constraint hierarchy k-consistency (CH-k-C) and give a CH- 2-C enforcement algorithm. We demonstrate how the CH-2-C algorithm can be seamlessly integrated into the ordinary branch-and-bound algorithm to make it a finite domain CH solver. Experimentation confirms the efficiency and robustness of our proposed solver prototype. Unlike other finite domain CH solvers, our proposed method works for both local and global comparators. In addition, our solver can support arbitrary error functions.

AIJ Journal 2002 Journal Article

Abstracting soft constraints: Framework, properties, examples

• Stefano Bistarelli
• Philippe Codognet
• Francesca Rossi

Soft constraints are very flexible and expressive. However, they are also very complex to handle. For this reason, it may be reasonable in several cases to pass to an abstract version of a given soft constraint problem, and then to bring some useful information from the abstract problem to the concrete one. This will hopefully make the search for a solution, or for an optimal solution, of the concrete problem, faster. In this paper we propose an abstraction scheme for soft constraint problems and we study its main properties. We show that processing the abstracted version of a soft constraint problem can help us in finding good approximations of the optimal solutions, or also in obtaining information that can make the subsequent search for the best solution easier. We also show how the abstraction scheme can be used to devise new hybrid algorithms for solving soft constraint problems, and also to import constraint propagation algorithms from the abstract scenario to the concrete one. This may be useful when we don't have any (or any efficient) propagation algorithm in the concrete setting.

ECAI Conference 1994 Conference Paper

Abduction and Concurrent Logic Languages

• Christian Codognet
• Philippe Codognet