Thomas Schiex

AAAI Conference 2026 Conference Paper

Assignment Problems in Cost Function Networks

• Guidio Sewa
• David Allouche
• Simon de Givry
• George Katsirelos
• Pierre Montalbano
• Thomas Schiex

To efficiently solve exact discrete optimization problems, branch and bound algorithms require tight bounds. In constraint programming, for optimization, soft arc consistencies typically derive much stronger bounds than those offered by domain or bound consistencies applied to a cost variable. The reason is that soft local consistencies exchange marginal cost information between variables whereas domain consistencies rely only on shrinking domains, which is less informative. However, CP solvers equipped with soft arc consistencies have so far offered limited support for efficient processing of global constraints. In this work, we show how we can efficiently enforce soft local consistency over the AllDifferent constraint, relying on algorithms for the Linear Assignment Problem (LAP). We implement this propagator in toulbar2, the state-of-the-art weighted CP solver exploiting soft local consistencies for bounding. We show that, equipped with this new propagator, toulbar2 outperforms state-of-the-art domain consistency-based CP as well as integer programming solvers for the Quadratic Assignment Problem and shows better performance for miniCOP instances of the 2024 XCSP competition with AllDifferent constraints.

JAIR Journal 2026 Journal Article

Scaling Neuro-symbolic Problem Solving: Solver-Free Learning of Constraints and Objectives

• Marianne Defresne
• Romain Gambardella
• Sophie Barbe
• Thomas Schiex

Background: In the ongoing quest for hybridizing discrete reasoning with neural nets, there is an increasing interest in neural architectures that can learn how to solve discrete reasoning or optimisation problems from natural inputs, a task that Large Language Models seem to struggle with. Objectives: We introduce a differentiable neuro-symbolic architecture and a loss function dedicated to learning how to solve NP-hard reasoning problems. Methods: Our new probabilistic loss allows for learning both the constraints and the objective – possibly non-linear – of a combinatorial problem. Thus, it delivers a complete model that can be scrutinized and completed with side constraints. By pushing the combinatorial solver out of the training loop, our architecture also offers scalable training while exact inference gives access to maximum accuracy. Results: We empirically show that it can efficiently learn how to solve NP-hard reasoning problems from natural inputs. On three variants of the Sudoku benchmark – symbolic, visual, and many-solution –, our approach requires a fraction of data and training time of other hybrid methods. On a visual Min-Cut/Max-cut task, it optimizes the regret as well as a Decision-Focused-Learning regret-dedicated loss. Finally, it efficiently learns the energy optimisation formulation of the large real-world problem of designing proteins.

IJCAI Conference 2023 Conference Paper

Scalable Coupling of Deep Learning with Logical Reasoning

• Marianne Defresne
• Sophie Barbe
• Thomas Schiex

In the ongoing quest for hybridizing discrete reasoning with neural nets, there is an increasing interest in neural architectures that can learn how to solve discrete reasoning or optimization problems from natural inputs. In this paper, we introduce a scalable neural architecture and loss function dedicated to learning the constraints and criteria of NP-hard reasoning problems expressed as discrete Graphical Models. We empirically show our loss function is able to efficiently learn how to solve NP-hard reasoning problems from natural inputs as the symbolic, visual or many-solutions Sudoku problems as well as the energy optimization formulation of the protein design problem, providing data efficiency, interpretability, and a posteriori control over predictions.

ICML Conference 2022 Conference Paper

Efficient Low Rank Convex Bounds for Pairwise Discrete Graphical Models

• Valentin Durante
• George Katsirelos
• Thomas Schiex

In this paper, we extend a Burer-Monteiro style method to compute low rank Semi-Definite Programming (SDP) bounds for the MAP problem on discrete graphical models with an arbitrary number of states and arbitrary pairwise potentials. We consider both a penalized constraint approach and a dedicated Block Coordinate Descent (BCD) approach which avoids large penalty coefficients in the cost matrix. We show our algorithm is decreasing. Experiments show that the BCD approach compares favorably to the penalized approach and to usual linear bounds relying on convergent message passing approaches.

AIJ Journal 2016 Journal Article

Tractability-preserving transformations of global cost functions

• David Allouche
• Christian Bessiere
• Patrice Boizumault
• Simon de Givry
• Patricia Gutierrez
• Jimmy H.M. Lee
• Ka Lun Leung
• Samir Loudni

Graphical model processing is a central problem in artificial intelligence. The optimization of the combined cost of a network of local cost functions federates a variety of famous problems including CSP, SAT and Max-SAT but also optimization in stochastic variants such as Markov Random Fields and Bayesian networks. Exact solving methods for these problems typically include branch and bound and local inference-based bounds. In this paper we are interested in understanding when and how dynamic programming based optimization can be used to efficiently enforce soft local consistencies on Global Cost Functions, defined as parameterized families of cost functions of unbounded arity. Enforcing local consistencies in cost function networks is performed by applying so-called Equivalence Preserving Transformations (EPTs) to the cost functions. These EPTs may transform global cost functions and make them intractable to optimize. We identify as tractable projection-safe those global cost functions whose optimization is and remains tractable after applying the EPTs used for enforcing arc consistency. We also provide new classes of cost functions that are tractable projection-safe thanks to dynamic programming. We show that dynamic programming can either be directly used inside filtering algorithms, defining polynomially DAG-filterable cost functions, or emulated by arc consistency filtering on a Berge-acyclic network of bounded-arity cost functions, defining Berge-acyclic network-decomposable cost functions. We give examples of such cost functions and we provide a systematic way to define decompositions from existing decomposable global constraints. These two approaches to enforcing consistency in global cost functions are then embedded in a solver for extensive experiments that confirm the feasibility and efficiency of our proposal.

AIJ Journal 2014 Journal Article

Computational protein design as an optimization problem

• David Allouche
• Isabelle André
• Sophie Barbe
• Jessica Davies
• Simon de Givry
• George Katsirelos
• Barry O'Sullivan
• Steve Prestwich

Proteins are chains of simple molecules called amino acids. The three-dimensional shape of a protein and its amino acid composition define its biological function. Over millions of years, living organisms have evolved a large catalog of proteins. By exploring the space of possible amino acid sequences, protein engineering aims at similarly designing tailored proteins with specific desirable properties. In Computational Protein Design (CPD), the challenge of identifying a protein that performs a given task is defined as the combinatorial optimization of a complex energy function over amino acid sequences. In this paper, we introduce the CPD problem and some of the main approaches that have been used by structural biologists to solve it, with an emphasis on the exact method embodied in the dead-end elimination / A ⁎ algorithm ( DEE / A ⁎ ). The CPD problem is a specific form of binary Cost Function Network (CFN, aka Weighted CSP). We show how DEE algorithms can be incorporated and suitably modified to be maintained during search, at reasonable computational cost. We then evaluate the efficiency of CFN algorithms as implemented in our solver toulbar2, on a set of real CPD instances built in collaboration with structural biologists. The CPD problem can be easily reduced to 0/1 Linear Programming, 0/1 Quadratic Programming, 0/1 Quadratic Optimization, Weighted Partial MaxSAT and Graphical Model optimization problems. We compare toulbar2 with these different approaches using a variety of solvers. We observe tremendous differences in the difficulty that each approach has on these instances. Overall, the CFN approach shows the best efficiency on these problems, improving by several orders of magnitude against the exact DEE / A ⁎ approach. The introduction of dead-end elimination before or during search allows to further improve these results.

AAAI Conference 2012 Conference Paper

Filtering Decomposable Global Cost Functions

• David Allouche
• Christian Bessiere
• Patrice Boizumault
• Simon de Givry
• Patricia Gutierrez
• Samir Loudni
• Jean-Philippe Métivier
• Thomas Schiex

As (Lee and Leung 2012) have shown, weighted constraint satisfaction problems can benefit from the introduction of global cost functions, leading to a new Cost Function Programming paradigm. In this paper, we explore the possibility of decomposing global cost functions in such a way that enforcing soft local consistencies on the decomposition achieves the same level of consistency on the original global cost function. We give conditions under which directional and virtual arc consistency offer such guarantees. We conclude by experiments on decomposable cost functions showing that decompositions may be very useful to easily integrate efficient global cost functions in solvers.

IJCAI Conference 2011 Conference Paper

Pairwise Decomposition for Combinatorial Optimization in Graphical Models

• Aur
• eacute; lie Favier
• Simon de Givry
• Andr
• eacute; s Legarra
• Thomas Schiex

We propose a new additive decomposition of probability tables that preserves equivalence of the joint distribution while reducing the size of potentials, without extra variables. We formulate the Most Probable Explanation (MPE) problem in belief networks as a Weighted Constraint Satisfaction Problem (WCSP). Our pairwise decomposition allows to replace a cost function with smaller-arity functions. The resulting pairwise decomposed WCSP is then easier to solve using state-of-the-art WCSP techniques. Although testing pairwise decomposition is equivalent to testing pairwise independence in the original belief network, we show how to efficiently test and enforce it, even in the presence of hard constraints. Furthermore, we infer additional information from the resulting nonbinary cost functions by projecting and subtracting them on binary functions. We observed huge improvements by preprocessing with pairwise decomposition and project&subtract compared to the current state-of-the-art solvers on two difficult sets of benchmark.

IJCAI Conference 2009 Conference Paper

• Marti Sanchez
• David Allouche
• Simon de Givry
• Thomas Schiex

Optimization in graphical models is an important problem which has been studied in many AI frameworks such as weighted CSP, maximum satisfiability or probabilistic networks. By identifying conditionally independent subproblems, which are solved independently and whose optimum is cached, recent Branch and Bound algorithms offer better asymptotic time complexity. But the locality of bounds induced by decomposition often hampers the practical effects of this result because subproblems are often uselessly solved to optimality. Following the Russian Doll Search (RDS) algorithm, a possible approach to overcome this weakness is to (inductively) solve a relaxation of each subproblem to strengthen bounds. The algorithm obtained generalizes both RDS and treedecomposition based algorithms such as BTD or AND-OR Branch and Bound. We study its efficiency on different problems, closing a very hard frequency assignment instance which has been open for more than 10 years.

IJCAI Conference 2007 Conference Paper

• Martin C. Cooper
• Simon de Givry
• Thomas Schiex

The Valued (VCSP) framework is a generic optimization framework with a wide range of applications. Soft arc consistency operations transform a VCSP into an equivalent problem by shifting weights between cost functions. The principal aim is to produce a good lower bound on the cost of solutions, an essential ingredient of a branch and bound search. But soft AC is much more complex than traditional AC: there may be several closures (fixpoints) and finding the closure with a maximum lower bound has been shown to be NP-hard for integer costs. We introduce a relaxed variant of soft arc consistency using rational costs. In this case, an optimal closure can be found in polynomial time. Furthermore, for finite rational costs, the associated lower bound is shown to provide an optimal arc consistent reformulation of the initial problem. Preliminary experiments on random and structured problems are reported, showing the strength of the lower bound produced.

ECAI Conference 2006 Conference Paper

Decision with Uncertainties, Feasibilities, and Utilities: Towards a Unified Algebraic Framework

• Cédric Pralet
• Gérard Verfaillie
• Thomas Schiex

Several formalisms exist to express and solve decision problems. Each is designed to capture different kinds of knowledge: utilities expressing preferences, uncertainties on the environment, or feasibility constraints on the decisions, with a possible sequential aspect. Despite the fact that every framework relies on specific properties exploited by dedicated algorithms, these formalisms present interesting similarities. In this paper, we show that it is possible to capture these similarities in a generic algebraic framework for sequential decision making with uncertainties, feasibilities, and utilities. This framework subsumes several existing approaches, from constraint satisfaction problems to quantified boolean formulas, Bayesian networks or possibilistic Markov decision processes. We introduce this framework using a toy example, increasingly sophisticated by uncertainties, feasibilities and possible observations. This leads to a formal definition of the framework together with dedicated queries representing usual decision problems. Generic algorithms for solving the considered queries should allow to both factorize existing algorithmic works and allow for cross-fertilization between the subsumed formalisms.

UAI Conference 2006 Conference Paper

From Influence Diagrams to Multi-operator Cluster DAGs

• Cédric Pralet
• Thomas Schiex
• Gérard Verfaillie

There exist several architectures to solve influence diagrams using local computations, such as the Shenoy-Shafer, the HUGIN, or the Lazy Propagation architectures. They all extend usual variable elimination algorithms thanks to the use of so-called 'potentials'. In this paper, we introduce a new architecture, called the Multi-operator Cluster DAG architecture, which can produce decompositions with an improved constrained induced-width, and therefore induce potentially exponential gains. Its principle is to benefit from the composite nature of influence diagrams, instead of using uniform potentials, in order to better analyze the problem structure.

AIJ Journal 2004 Journal Article

Arc consistency for soft constraints

• Martin Cooper
• Thomas Schiex

The notion of arc consistency plays a central role in constraint satisfaction [R. Dechter, Constraint Processing, Morgan Kaufmann, San Mateo, CA, 2003]. It is known since the introduction of valued and semi-ring constraint networks in 1995 that the notion of local consistency can be extended to constraint optimisation problems defined by soft constraint frameworks based on an idempotent cost combination operator. This excludes non-idempotent operators such as + which define problems which are very important in practical applications such as Max-CSP, where the aim is to minimise the number of violated constraints. In this paper, we show that using a weak additional axiom satisfied by most existing soft constraints proposals, it is possible to define a notion of soft arc consistency that extends the classical notion of arc consistency and this even in the case of non-idempotent cost combination operators. A polynomial time algorithm for enforcing this soft arc consistency exists and its space and time complexities are identical to that of enforcing arc consistency in CSPs when the cost combination operator is strictly monotonic (for example Max-CSP). A directional version of arc consistency, first introduced by M. C. Cooper [Reduction operations in fuzzy or valued constraint satisfaction, Fuzzy Sets and Systems 134 (3) (2003) 311–342] is potentially even stronger than the non-directional version, since it allows non-local propagation of penalties. We demonstrate the utility of directional arc consistency by showing that it not only solves soft constraint problems on trees, but that it also implies a form of local optimality, which we call arc irreducibility.

AIJ Journal 2004 Journal Article

Solving weighted CSP by maintaining arc consistency

• Javier Larrosa
• Thomas Schiex

Recently, a general definition of arc consistency (AC) for soft constraint frameworks has been proposed by T. Schiex [Proc. CP-2000, Singapore, 2000, pp. 411–424]. In this paper we specialize this definition to weighted CSP and introduce two O(ed 3) enforcing algorithms. Then, we refine the definition and introduce a stronger form of arc consistency (AC∗) along with two O(n 2 d 2+ed 3) algorithms. As in the CSP case, an important application of AC is to combine it with search. We empirically demonstrate that a branch and bound algorithm that maintains either AC or AC∗ is a state-of-the-art general solver for weighted CSP. Our experiments cover binary Max-CSP and Max-SAT problems.

IJCAI Conference 2003 Conference Paper

In the quest of the best form of local consistency for Weighted CSP

• Javier Larrosa
• Thomas Schiex

The weighted CSP (WCSP) framework is a soft constraint framework with a wide range of applications. In this paper, we consider the problem of maintaining local consistency during search for solving WCSP. We first refine the notions of directional arc consistency (DAC) and full directional arc consistency (FDAC) introduced in [Cooper, 2003] for binary WCSP, define algorithms that enforce these properties and study their complexities. We then consider algorithms that maintain either arc consistency (AC), DAC or FDAC during search. The efficiency of these algorithms is empirically studied. It appears that despite its high theoretical cost, the strongest FDAC property is the best choice.

AIJ Journal 1999 Journal Article

Maintaining reversible DAC for Max-CSP

• Javier Larrosa
• Pedro Meseguer
• Thomas Schiex

We introduce an exact algorithm for maximizing the number of satisfied constraints in an overconstrained CSP (Max-CSP). The algorithm, which can also solve weighted CSP, probabilistic CSP and other similar problems, is based on directed arc-inconsistency counts (DAC). The usage of DAC increases the lower bound of branch and bound based algorithms for Max-CSP, improving their efficiency. Originally, DAC were defined following a static variable ordering. In this paper, we relax this condition, showing how DAC can be defined from a directed constraint graph. These new graph-based DAC can be effectively used for lower bound computation. Interestingly, any directed constraint graph of the considered problem is suitable for DAC computation, so the selected graph can change dynamically during search, aiming at optimizing the exploitation of directed arc-inconsistencies. In addition, directed arc-inconsistencies are maintained during search, propagating the effect of value pruning. With these new elements we present the PFC maintaining reversible DAC algorithm (PFC-MRDAC), a natural successor of PFC-DAC for Max-CSP. We provide experimental evidence for the superiority of PFC-MRDAC on random and real overconstrained CSP instances, including problems with weighted constraints.

AAAI Conference 1998 Conference Paper

Reversible DAC and Other Improvements for Solving Max-CSP

• Javier Larrosa
• Thomas Schiex

AAAI Conference 1996 Conference Paper

Lazy Arc Consistency

• Thomas Schiex
• Christine Gaspin

Arc consistency filtering is widely used in the framework of binary constraint satisfaction problems: with a low complexity, inconsistency may be detected,and domains are filtered. In this paper, we show that when detecting inconsistency is the objective, a systematic domain filtering is useless and a lazy approach is more adequate. Whereas usual arc consistency algorithms produce the maximum arc consistent sub-domain, when it exists, we propose a method, called LACY, which only looks for any arc consistent sub-domain. The algorithm is then extended to provide the additional service of locating one variable with a minimum domain cardinality in the maximum arc consistent sub-domain, without necessarily computing all domain sizes. Finally, we compare traditional AC enforcing and lazy AC enforcing using several benchmark problems, both randomly generated CSP and real life problems.

UAI Conference 1995 Conference Paper

A constraint satisfaction framework for decision under uncertainty

• Hélène Fargier
• Jérôme Lang
• Roger Martin-Clouaire
• Thomas Schiex

IJCAI Conference 1995 Conference Paper

Valued Constraint Satisfaction Problems: Hard and Easy Problems

• Thomas Schiex
• Helene Fargier
• Gtrard Verfaillie

In order to deal with over-constrained Constraint Satisfaction Problems, various extensions of the CSP framework have been considered by taking into account costs, uncertainties, preferences, priorities. .. Each extension uses a specific mathematical operator (+, max. ..) to aggregate constraint violations. In this paper, we consider a simple algebraic framework, related to Partial Constraint Satisfaction, which subsumes most of these proposals and use it to characterize existing proposals in terms of rationality and computational complexity. We exhibit simple relationships between these proposals, try to extend some traditional CSP algorithms and prove that some of these extensions may be computationally expensive.

UAI Conference 1994 Conference Paper

Penalty Logic and its Link with Dempster-Shafer Theory

• Florence Dupin de Saint-Cyr
• Jérôme Lang
• Thomas Schiex

Penalty logic, introduced by Pinkas, associates to each formula of a knowledge base the price to pay if this formula is violated. Penalties may be used as a criterion for selecting preferred consistent subsets in an inconsistent knowledge base, thus inducing a non-monotonic inference relation. A precise formalization and the main properties of penalty logic and of its associated non-monotonic inference relation are given in the first part. We also show that penalty logic and Dempster-Shafer theory are related, especially in the infinitesimal case.

ECAI Conference 1994 Conference Paper

Stubborness: A Possible Enhancement for Backjumping and Nogood Recording

• Thomas Schiex
• Gérard Verfaillie

UAI Conference 1992 Conference Paper

Possibilistic Constraint Satisfaction Problems or "How to Handle Soft Constraints? "

• Thomas Schiex

Many AI synthesis problems such as planning or scheduling may be modelized as constraint satisfaction problems (CSP). A CSP is typically defined as the problem of finding any consistent labeling for a fixed set of variables satisfying all given constraints between these variables. However, for many real tasks such as job-shop scheduling, time-table scheduling, design�, all these constraints have not the same significance and have not to be necessarily satisfied. A first distinction can be made between hard constraints, which every solution should satisfy and soft constraints, whose satisfaction has not to be certain. In this paper, we formalize the notion of possibilistic constraint satisfaction problems that allows the modeling of uncertainly satisfied constraints. We use a possibility distribution over labelings to represent respective possibilities of each labeling. Necessity-valued constraints allow a simple expression of the respective certainty degrees of each constraint. The main advantage of our approach is its integration in the CSP technical framework. Most classical techniques, such as Backtracking (BT), arcconsistency enforcing (AC) or Forward Checking have been extended to handle possibilistics CSP and are effectively implemented. The utility of our approach is demonstrated on a simple design problem.