# Optimization in Graphical Models - NP-complete optimization and its applications

Thomas Schiex

<figure><img src="image_1.png" /></figure>

## To cite this version:

Thomas Schiex. Optimization in Graphical Models - NP-complete optimization and its applications. Assemblée générale de l'Association Française d'Intelligence Artificielle, Oct 2016, Paris, France. hal-02794159

HAL Id: hal-02794159

https://hal.inrae.fr/hal-02794159

Submitted on 5 Jun 2020

HAL is a multi-disciplinary open access archive for the deposit and dissemination of scientific research documents, whether they are published or not. The documents may come from teaching and research institutions in France or abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est destinée au dépôt et à la diffusion de documents scientifiques de niveau recherche, publiés ou non, émanant des établissements d'enseignement et de recherche français ou étrangers, des laboratoires publics ou privés.

<figure><img src="image_2.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# Optimization in Graphical Models

## NP-complete optimization and its applications

T. Schiex

Many co-workers and contributors, see bibliography

département
MA
TOULOUSE

INRA
SCIENCE & IMPACT

AFIA General assembly

EurAI Fellowship

October 2016
Spring of AI

* AI algorithms win chess championship, Deep Blue II, 1997.

* Computing power, RAM, search and a bit of ML (evaluation function)
# The second era of AI

## Spring of AI

* AI algorithms win chess championship, Deep Blue II, 1997.

* Computing power, RAM, search and a bit of ML (evaluation function)

## Now Go !

* 2016, AlphaGo wins over a world champion Go player.

* Computing power, RAM, Monte Carlo Tree Search, deep learning.
Spring of AI

* Al algorithms win chess championship, Deep Blue II, 1997.

* Computing power, RAM, search and a bit of ML (evaluation function)

Now Go !

* 2016, AlphaGo wins over a world champion Go player.

* Computing power, RAM, Monte Carlo Tree Search, deep learning.

New Spring of AI

* Mostly computing power, ML and data.

* Before that, NP-hard problem solving (CP, SAT, search) has been providing major contributions to AI, in its theory and applications.
## Inside AI and computer science

* Model Based Diagnosis, Planning,...

* Scheduling, Configuration, Resource Allocation,...

* Verification, Cryptography, Testing
## Inside AI and computer science

<figure><img src="image_3.png" /></figure>

* Model Based Diagnosis, Planning,...

<figure><img src="image_4.png" /></figure>

* Scheduling, Configuration, Resource Allocation,...

<figure><img src="image_5.png" /></figure>

* Verification, Cryptography, Testing

## SAT, CSP, CP, ASP: satisfiability/feasibility

Finding perfect solutions to perfectly defined problems
# The power of NP-hard problem solving

## Inside AI and computer science

* Model Based Diagnosis, Planning...

* Scheduling, Configuration, Resource Allocation,...

* Verification, Cryptography, Testing

## SAT, CSP, CP, ASP: satisfiability/feasibility

Finding perfect solutions to perfectly defined problems

The world is often more complex

ML gives us the capacity to build models of complex systems from data.
Early planning for GPS navigation

* A digital model of roads

* A shortest path algorithm for planning

* GPS navigation monitors plan execution
## Early planning for GPS navigation

* A digital model of roads

* A shortest path algorithm for planning

* GPS navigation monitors plan execution

* Static model of reality

* Exact and efficient algorithm to decide from this “exact” model
Modern planning for GPS navigation

* Data on travel time on each road, at all time

* Feeds a stochastic model of duration

* Planning by minimizing expected time

* GPS navigation monitors plan execution
Modern planning for GPS navigation

* Data on travel time on each road, at all time

* Feeds a stochastic model of duration

* Planning by minimizing expected time

* GPS navigation monitors plan execution

Data analytics: what do we need ?

* Massive data

* A family of (stochastic) models that can be learnt

* On which optimization algorithms may apply

* Minimum requirement: efficient/tight bounds.
Definition

1. Set $X = \{x_1, \dots, x_n\}$ of variables, each with a domain $D^i$

2. Set $\Phi$ of functions $\varphi_S$ involving variables of $S \subset X$ (scope).

3. A joint function on $X$, $\mathbf{x} \in D^X$:

$$F(\mathbf{x}) = \bigoplus_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}_S)$$
Definition

● Set $X = \{x_1, \dots, x_n\}$ of variables, each with a domain $D^i$

● Set $\Phi$ of functions $\varphi_S$ involving variables of $S \subset X$ (scope).

● A joint function on $X$, $\mathbf{x} \in D^X$:

$$F(\mathbf{x}) = \bigoplus_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}_S)$$

Why Graphical ?

● a vertex per variable

● an edge when 2 variables interact in a $\varphi_S \in \Phi$

● Allows to describe knowledge on a lot of variables concisely

● Usually hard to manipulate (NP-hard queries).
Constraint Network

❶ Variables and domains

❷ $\varphi_S$ are Boolean functions (constraints, $t \equiv 0 < 1 \equiv f$)

❸ Minimize joint function ($\oplus = \land = \max$)

$$F(\mathbf{x}) = \max_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}_S)$$
## Constraint Network

* Variables and domains

* $\varphi_S$ are Boolean functions (constraints, $t \equiv 0 < 1 \equiv f$)

* Minimize joint function ($\oplus = \land = \max$)

$$F(\mathbf{x}) = \max_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}_S)$$

## Graph coloring/RLFAP-feas

* A graph $G = (V, E)$ and $m$ colors.

* Can we color all vertices in such a way that no edge connects two vertices of the same color?

<figure><img src="image_6.png" /></figure>
Constraint Network

❶ Variables and domains

❷ $\varphi_S$ are Boolean functions (constraints, $t \equiv 0 < 1 \equiv f$)

❸ Minimize joint function ($\oplus = \land = \max$)

$$F(\mathbf{x}) = \max_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}_S)$$

Graph coloring/RLFAP-feas

❶ A graph $G = (V, E)$ and $m$ colors.

❷ Can we color all vertices in such a way that no edge connects two vertices of the same color ?

<figure><img src="image_7.png" /></figure>
Biology has very few general laws

Need to shift from perfect knowledge
processing to approximate/imperfect
knowledge processing
## Biology has very few general laws

Need to shift from perfect knowledge processing to approximate/imperfect knowledge processing

## Valued CSP

Shift from a conjunction of boolean functions to a more general combination of functions with a totally ordered co-domain (preferences, costs, priorities...)

T. Schiex, H. Fargier, and G. Verfaillie, "Valued Constraint Satisfaction Problems: hard and easy problems". In: Proc. of the 14th IJCAI. Montreal, Canada, Aug. 1995, pp. 631-637

S. Bistarelli, H. Fargier, U. Montanari, F. Rossi, et al. "Semiring-based CSPs and Valued CSPs: Frameworks, Properties and Comparison". In: Constraints 4 (1999), pp. 199-240
## Biology has very few general laws

Need to shift from perfect knowledge processing to approximate/imperfect knowledge processing

## Valued CSP

Shift from a conjunction of boolean functions to a more general combination of functions with a totally ordered co-domain (preferences, costs, priorities...)

<figure><img src="image_8.png" /></figure>

T. Schiex, H. Fargier, and G. Verfaillie, "Valued Constraint Satisfaction Problems: hard and easy problems". In: Proc. of the 14th IJCAI. Montreal, Canada, Aug. 1995, pp. 631-637

S. Bistarelli, H. Fargier, U. Montanari, F. Rossi, et al. "Semiring-based CSPs and Valued CSPs: Frameworks, Properties and Comparison". In: Constraints 4 (1999), pp. 199-240
Cost Function Networks - Weighted Constraint Networks - GAI models

* Variables and domains as usual

* Cost functions $\varphi_S : D^S \to \{0, \dots, k\}$ (k finite or not)

* Combined by bounded addition⁸

$$F(\mathbf{x}) = \sum_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}[S]) \quad \varphi_\emptyset : \text{lower bound}$$

A solution has cost $< k$. Optimal if minimum cost.
## Cost Function Networks - Weighted Constraint Networks - GAI models

* Variables and domains as usual

* Cost functions $\varphi_S : D^S \to \{0, \dots, k\}$ (k finite or not)

* Combined by bounded addition⁸

$$F(\mathbf{x}) = \sum_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}[S]) \quad \varphi_\emptyset : \text{lower bound}$$

A solution has cost $< k$. Optimal if minimum cost.

## Benefits

* Defines feasibility and cost homogeneously

* A constraint is a cost function with range $\{0, k\}$ only
Markov Random Fields, Bayesian Networks

* Random variables X with discrete domains

* joint probability distribution p(X) defined through the product of positive real-valued functions:

$$p(\mathbf{X} = \mathbf{x}) \propto \prod_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}_S)$$
## Markov Random Fields, Bayesian Networks

* Random variables X with discrete domains

* joint probability distribution p(X) defined through the product of positive real-valued functions:

$$p(\mathbf{X} = \mathbf{x}) \propto \prod_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}_S)$$

Massively used in 2/3D Image Analysis, Statistical Physics, NLP, planning/reasoning under uncertainty...
## Markov Random Fields, Bayesian Networks

* Random variables X with discrete domains

* joint probability distribution p(X) defined through the product of positive real-valued functions:

$$p(\mathbf{X} = \mathbf{x}) \propto \prod_{\varphi_S \in \Phi} \varphi_S(\mathbf{x}_S)$$

Massively used in 2/3D Image Analysis, Statistical Physics, NLP, planning/reasoning under uncertainty...

## Maximum a Posteriori MAP-MRF

MRF ≡ CFN up to a (– log) transform.
* No constraint or determinism: infinite k, finite costs

* $v_{ia}$: value a used for variable $x_i$.

* $p_{iajb}$: pair (a, b) used for $x_i$ and $x_j$

$$
\begin{array}{ll}
\text{Minimize} & \sum_{i,a} \varphi_i(a) \cdot v_{ia} + \\
& \sum_{\substack{\varphi_{ij} \in \Phi \\ a \in D^i, b \in D^j}} \varphi_{ij}(a, b) \cdot p_{iajb} \quad \text{subject to} \\
& \sum_{a \in D^i} v_{ia} = 1 \qquad \forall i \in \{1, \dots, n\} \\
& \sum_{b \in D^j} p_{iajb} = v_{ia} \qquad \forall \varphi_{ij} \in \Phi, \forall a \in D^i \\
& v_{ia}, p_{iajb} \in \{0, 1\}
\end{array}
$$

Continuous relaxation : the local polytope$^{45,25,54}$
## Exact approaches (beyond ILP)

* Dynamic programming (Variable and join-tree elimination,²,¹² resolution¹¹,⁴⁰,¹³)

* Tree search + fast, incremental approximate local reasoning (CP, SAT)

## Fast, approximate reasoning with some guarantees

* Arc Consistency in CSP/CP

* Message Passing (MRF/BN)

* Soft Arc Consistency in CFN
AC as Dynamic programming

* Imagine a CSP with a linear graph

* Assume we know which values of $D^i-1$ belongs to a solution on $x_1...x_{i-1}$

* We can extend this to $D^i$ for $x_1...x_i$

* Let $f_i = \min_{x_{i-1}} (\max(\varphi_{i-1}, \varphi_{i,i-1}))$

* Include $f_i$ in the problem

<figure><img src="image_9.png" /></figure>
AC as Dynamic programming

* Imagine a CSP with a linear graph

* Assume we know which values of $D^i-1$ belongs to a solution on $x_1...x_{i-1}$

* We can extend this to $D^i$ for $x_1...x_i$

* Let $f_i = \min_{x_{i-1}} (\max(\varphi_{i-1}, \varphi_{i,i-1}))$

* Include $f_i$ in the problem

<figure><img src="image_10.png" /></figure>
## AC as Dynamic programming

* Imagine a CSP with a linear graph

* Assume we know which values of $D^i-1$ belongs to a solution on $x_1...x_{i-1}$

* We can extend this to $D^i$ for $x_1...x_i$

* Let $f_i = \min_{x_{i-1}} (\max(\varphi_{i-1}, \varphi_{i,i-1}))$

* Include $f_i$ in the problem

<figure><img src="image_11.png" /></figure>

## Revise: Equivalence Preserving Transformation

The resulting problem is equivalent (same set of solutions)
Rooted tree CN

* Revise from leaves to root

* Root domain: values that belong to a solution

<figure><img src="image_12.png" /></figure>
## Tree CN

* Revise from leaves and back

* All domains: values that belong to a solution

* Resulting problem solved
backtrack-free¹⁹,¹⁸

<figure><img src="image_13.png" /></figure>
Arc consistency (Waltz 1972)

1 Linear time (tables)

2 Unique fixpoint (confluent)

3 Preserves equivalence

4 May detect infeasibility

5 Problem transformation
(incremental)

<figure><img src="image_14.png" /></figure>
MP - Dynamic Programming³⁵,²⁸

1. Assume that the optimum cost on $x_1 ... x_{i-1}$ is known for every value of $D^{i-1}$

2. We can extend this to $D^i$ for $x_1 ... x_i$

3. Let $f_i = \min_{x_{i-1}} (\varphi_{i-1} + \varphi_{i, i-1})$

4. Store $f_i$ as a message

<figure><img src="image_15.png" /></figure>
MP - Dynamic Programming³⁵,²⁸

1. Assume that the optimum cost on $x_1 ... x_{i-1}$ is known for every value of $D^{i-1}$

2. We can extend this to $D^i$ for $x_1 ... x_i$

3. Let $f_i = \min_{x_{i-1}} (\varphi_{i-1} + \varphi_{i, i-1})$

4. Store $f_i$ as a message

<figure><img src="image_16.png" /></figure>
MP - Dynamic Programming$^{35,28}$

1 Assume that the optimum cost on $x_1 ... x_{i-1}$ is known for every value of $D^{i-1}$

2 We can extend this to $D^i$ for $x_1 ... x_i$

3 Let $f_i = \min_{x_{i-1}} (\varphi_{i-1} + \varphi_{i,i-1})$

4 Store $f_i$ as a message

<figure><img src="image_17.png" /></figure>
MP - Dynamic Programming$^{35,28}$

1. Assume that the optimum cost on $x_1 ... x_{i-1}$ is known for every value of $D^{i-1}$

2. We can extend this to $D^i$ for $x_1 ... x_i$

3. Let $f_i = \min_{x_{i-1}} (\varphi_{i-1} + \varphi_{i,i-1})$

4. Store $f_i$ as a message

<figure><img src="image_18.png" /></figure>
MP - Dynamic Programming$^{35,28}$

1 Assume that the optimum cost on $x_1 ... x_{i-1}$ is known for every value of $D^{i-1}$

2 We can extend this to $D^i$ for $x_1 ... x_i$

3 Let $f_i = \min_{x_{i-1}} (\varphi_{i-1} + \varphi_{i,i-1})$

4 Store $f_i$ as a message

<figure><img src="image_19.png" /></figure>
MP - Dynamic Programming³⁵,²⁸

1. Assume that the optimum cost on $x_1 ... x_{i-1}$ is known for every value of $D^{i-1}$

2. We can extend this to $D^i$ for $x_1 ... x_i$

3. Let $f_i = \min_{x_{i-1}} (\varphi_{i-1} + \varphi_{i,i-1})$

4. Store $f_i$ as a message

<figure><img src="image_20.png" /></figure>

1. Solves Berge acyclic MRF/BN (acyclic Factor Graphs)

2. Does not converge on graphs (Loopy Belief Propagation)

3. Massively used to produce “good” solutions (turbo-decoding³⁹)

4. Not an equivalence preserving transformation!
Soft AC as Dynamic programming

1. use $\phi_{\emptyset}$ and $\phi_i(\cdot)$ to store optimum cost over $\{x_1, \dots, x_i\}$

2. Preserves equivalence by “cost shifting”^45,53,42

<figure><img src="image_21.png" /></figure>
Soft AC as Dynamic programming

1. use $\varphi_{\emptyset}$ and $\varphi_i(\cdot)$ to store optimum cost over $\{x_1, \dots, x_i\}$

2. Preserves equivalence by “cost shifting”^45,53,42

<figure><img src="image_22.png" /></figure>
Soft AC as Dynamic programming

1. use $\varphi_{\emptyset}$ and $\varphi_i(\cdot)$ to store optimum cost over $\{x_1, \dots, x_i\}$

2. Preserves equivalence by “cost shifting”^45,53,42

<figure><img src="image_23.png" /></figure>
Soft AC as Dynamic programming

1. use $\varphi_{\emptyset}$ and $\varphi_i(\cdot)$ to store optimum cost over $\{x_1, \dots, x_i\}$

2. Preserves equivalence by "cost shifting"$^{45,53,42}$

<figure><img src="image_24.png" /></figure>
Soft AC as Dynamic programming

1. use $\varphi_{\emptyset}$ and $\varphi_i(\cdot)$ to store optimum cost over $\{x_1, \dots, x_i\}$

2. Preserves equivalence by “cost shifting”^45,53,42

<figure><img src="image_25.png" /></figure>
Assume that initially $\phi_0 = 0, k = 4$

<figure><img src="image_26.png" /></figure>
Assume that initially $\phi_0 = 0, k = 4$

<figure><img src="image_27.png" /></figure>
Assume that initially $\phi_0 = 0, k = 4$

<figure><img src="image_28.png" /></figure>
Assume that initially $\phi_0 = 0, k = 4$

Shift 1 to left b

<figure><img src="image_29.png" /></figure>
Assume that initially $\varphi_{\emptyset} = 0, k = 4$

Shift 1 to left by b

<figure><img src="image_30.png" /></figure>

<figure><img src="image_31.png" /></figure>

Shift 1 from $\varphi_1$ to $\varphi_0$
Assume that initially $\varphi_{\emptyset} = 0, k = 4$

Shift 1 to left by b

<figure><img src="image_32.png" /></figure>

<figure><img src="image_33.png" /></figure>

Shift 1 from $\varphi_1$ to $\varphi_0$

$\varphi_{\emptyset} = 1$
Assume that initially $\varphi_{\emptyset} = 0, k = 4$

<figure><img src="image_34.png" /></figure>

↓ Shift 1 from $\varphi_1$ to $\varphi_\emptyset$

$$ \varphi_{\emptyset} = 1 $$

Preserves the joint function $F(\cdot)$ below $k$
* Solves tree structured problems, optimum in $\varphi\emptyset$

* Reformulation: incremental

* May loop indefinitely (graphs)

* No unique fixpoint (when it exists)

* Already used by Ukrainian school<sup>45,27,26,54</sup> and for a subclass of ILP.<sup>53</sup>

* Independently introduced in 2003 in ML as "reparametrizations"<sup>51</sup>

T. Schiex. "Arc consistency for soft constraints". In: Principles and Practice of Constraint Programming - CP 2000. Vol. 1894. LNCS. Singapore, Sept. 2000, pp. 411-424

M C. Cooper and T. Schiex. "Arc consistency for soft constraints". In: Artificial Intelligence 154:1-2 (2004), pp. 199-227
## Breaking the loops, strengthening $\varphi\emptyset$

* 2000: Arc consistency$^{42,29}$

* 2003: Full Directional AC$^{5,31,32}$

* 2005: Existential DAC$^{30}$

* 2008: Virtual AC$^{10,9}$

* 2007: Optimal Soft AC$^{7}$ (LP)
Breaking the loops, strengthening φØ

2000: Arc consistency<sup>42,29</sup>

2003: Full Directional AC<sup>5,31,32</sup>

2005: Existential DAC<sup>30</sup>

2008: Virtual AC<sup>10,9</sup>

2007: Optimal Soft AC<sup>7</sup> (LP)

* O(ed) space, equivalent to the CSP variants on CSP (except OSAC).

* Implemented in **toulbar2**, with many other bells & whistles
Optimal Soft Arc Consistency (finite costs, $k = \infty$)

LP variables, binary CFN with no constraint/determinism

* $u_i$: amount of cost shifted from $\varphi_i$ to $\varphi_\emptyset$

* $q_{ij}$: amount of cost shifted from $\varphi_{ij}$ to $a \in D^i$
LP variables, binary CFN with no constraint/determinism

● $u_i$: amount of cost shifted from $\varphi_i$ to $\varphi_\emptyset$

● $q_{ija}$: amount of cost shifted from $\varphi_{ij}$ to $a \in D^i$

OSAC$^{45,25,7,54,9}$

$$
\begin{array}{ll}
\text{Maximize} & \displaystyle\sum_{i=1}^{n} u_i \\
& \text{subject to} \\
& \varphi_i(a) - u_i + \sum_{(\varphi_{ij} \in \Phi)} q_{ija} \geq 0 \quad \forall i \in \{1, \dots, n\}, \forall a \in D^i \\
& \varphi_{ij}(a, b) - q_{ija} - q_{jib} \geq 0 \quad \forall \varphi_{ij} \in \Phi, \forall (a, b) \in D^{ij}
\end{array}
$$
## 01 LP Variables, for a binary CFN

* v<sub>ia</sub>: value a used for variable x<sub>i</sub>.

* p<sub>iajb</sub>: pair (a, b) used for x<sub>i</sub> and x<sub>j</sub>

## The MRF local polytope<sup>54</sup>

$$ \text{Minimize} \quad \sum_{i,a} c_i(a) \cdot x_{ia} + \sum_{\substack{c_{ij} \in C \\ a \in D^i, b \in D^i}} c_{ij}(a, b) \cdot y_{iajb} \quad \text{s.t} \\ \sum_{a \in D^i} x_{ia} = 1 \qquad \forall i \in \{1, \dots, n\} \quad (1) $$

$$ \sum_{b \in D^i} y_{iajb} - x_{ia} = 0 \qquad \forall c_{ij}/c_{ji} \in C, \forall a \in D^i \quad (2) $$
## 01 LP Variables, for a binary CFN

* v<sub>ia</sub>: value a used for variable x<sub>i</sub>.

* p<sub>iajb</sub>: pair (a, b) used for x<sub>i</sub> and x<sub>j</sub>

## The MRF local polytope<sup>54</sup>

$$ \text{Minimize} \quad \sum_{i,a} c_i(a) \cdot x_{ia} + \sum_{\substack{c_{ij} \in C \\ a \in D^i, b \in D^i}} c_{ij}(a, b) \cdot y_{iajb} \quad \text{s.t} \\ \sum_{a \in D^i} x_{ia} = 1 \qquad \forall i \in \{1, \dots, n\} \quad (1) $$

$$ \sum_{b \in D^i} y_{iajb} - x_{ia} = 0 \qquad \forall c_{ij}/c_{ji} \in C, \forall a \in D^i \quad (2) $$

OSAC is its dual: u<sub>i</sub> multiplier for (1) and q<sub>ija</sub> for (2).
<figure><img src="image_35.png" /></figure>

Soft convergent ACs find feasible (but non necessarily optimal) solutions of the dual.

<figure><img src="image_36.png" /></figure>

Optimal does not mean more efficient for tree search.
<figure><img src="image_37.png" /></figure>

Soft convergent ACs find feasible (but non necessarily optimal) solutions of the dual.

<figure><img src="image_38.png" /></figure>

Optimal does not mean more efficient for tree search.

2015: universality of the local polytope

Prusa and Werner³⁸ showed that any “normal” LP can be reduced to such a polytope in linear time (constructive proof).
<figure><img src="image_39.png" /></figure>

Soft convergent ACs find feasible (but non necessarily optimal) solutions of the dual.

<figure><img src="image_40.png" /></figure>

Optimal does not mean more efficient for tree search.

## 2015: universality of the local polytope

Prusa and Werner³⁸ showed that any “normal” LP can be reduced to such a polytope in linear time (constructive proof).

Could soft arc consistency (eg. VAC) speed-up LP?
CPLEX V12.4.0.0

Problem '3e4h.LP' read.
Root relaxation solution time = 811.28 sec.
...
MIP - Integer optimal solution: Objective = 150023297067
Solution time = 864.39 sec.
CPLEX V12.4.0.0

Problem '3e4h.LP' read.
Root relaxation solution time = 811.28 sec.
...
MIP - Integer optimal solution: Objective = 150023297067
Solution time = 864.39 sec.

tb2 and VAC

loading CFN file: 3e4h.wcsp
Lb after VAC: 150023297067
Preprocessing time: 9.13 seconds.
Optimum: 150023297067 in 129 backtracks, 129 nodes and 9.38 seconds.
Radio Link Frequency Assignment Problems

Assign frequencies to radio link in order to minimize interferences.

CELAR 06, n = 100, d = 44 - one core

1997: 26 days of a Sun UltraSparc 167 MHz.

2015: optimum found in 7", proved in 73" (2.1GHz CPU)

12.5 fold increase in frequency

* More than 30,000 times faster

* All min-interference instances closed. Most resisted ILP (fap.zib.de)
Design new enzymes for biofuels, drugs...cosmetics too

* graphical model capturing molecule stability based on atom-scale forces (electrostatics, solvation, torsion, Van der Waals...)

* Few variables (from 10 to few hundreds)

* Huge domains (typ. $d \approx 450$)

* Exact solvers: DEE/A\* (DEE\*<sup>14</sup>), ILP<sup>24</sup>

* By far the most used: simulated annealing (Rosetta<sup>21</sup>).

Seydou Traoré, David Allouche, Isabelle André, Simon de Givry, et al. "A new framework for computational protein design through cost function network optimization". In: Bioinformatics 29.17 (2013), pp. 2129-2136
<figure><img src="image_41.png" /></figure>

<figure><img src="image_42.png" /></figure>

David Allouche, Isabelle André, Sophie Barbe, Jessica Davies, et al. "Computational protein design as an optimization problem". In: Artificial Intelligence 212 (2014). pp. 59-79

Barry Hurley, Barry O'Sullivan, David Allouche, George Katsirelos, et al. "Multi-language evaluation of exact solvers in graphical model discrete optimization". In: Constraints 21.3 (2016). pp. 413-434
<figure><img src="image_43.png" /></figure>
<figure><img src="image_44.png" /></figure>

<figure><img src="image_45.png" /></figure>

David Simoncini, David Allouche, Simon de Givry, Celine Delmas, et al. "Guaranteed discrete energy optimization on large protein design problems". In: Journal of chemical theory and computation 11.12 (2015). pp. 5980-5989

Seydou Traoré, Kyle E Roberts, David Allouche, Bruce R Donald, et al. "Fast search algorithms for computational protein design". In: Journal of computational chemistry (2016)
## Genetic mapping with CarthaGene
GM learning and TSP optimization.

S. de Givry, M. Bouchez, P. Chabrier, D. Milan, et al. "CarthaGene: multipopulation integrated genetic and radiation hybrid mapping." In: Bioinformatics 21.8 (2005), pp. 1703-4

V. Laurent, E. Wajnberg, B. Mangin, T. Schiex, et al. "A composite genetic map of the parasitoid wasp Trichogramma brassicae based on RAPD markers." In: Genetics 150.1 (1998), pp. 275-82

## Gene finding with EuGene
Semi-CRF + optimization.

Tomato Genome Consortium et al. "The tomato genome sequence provides insights into fleshy fruit evolution." In: Nature 485.7400 (2012), pp. 635-641

C. Mathé, M. F. Sagot, T. Schiex, and P. Rouzé. "Current methods of gene prediction, their strengths and weaknesses." In: Nucleic Acids Res 30.19 (2002), pp. 4103-17

## RNA Gene finding: MilPat, Darn!
CSP/CFN + string algorithms

P. Thebault, S. de Givry, T. Schiex, and C. Gaspin. "Searching RNA motifs and their intermolecular contacts with constraint networks." In: Bioinformatics 22.17 (2006), pp. 2074-80

M Zytnicki, C. Gaspin, and T Schiex. "DARN! A soft constraint solver for RNA motif localization". In: Constraints 13.1 (2008), pp. 91-109

## MendelSoft: pedigree debugging
CFN for MPE on Bayesian nets

M Sanchez, S de Givry, and T Schiex. "Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques". In: Constraints 13.1 (2008), pp. 130-154

T. Faraut, S. de Givry, P. Chabrier, T. Derrien, et al. "A comparative genome approach to marker ordering." In: Bioinformatics 23.2 (2007), e50-6
## Genetic mapping with CarthaGene
GM learning and TSP optimization.

<figure><img src="image_46.png" /></figure>

## Gene finding with EuGene
Semi-CRF + optimization.

Tomato Genome Consortium et al. "The tomato genome sequence provides insights into fleshy fruit evolution". In: Nature 485.7400 (2012), pp. 635-641

C. Mathé, M. F. Sagot, T. Schiex, and P. Rouzé. "Current methods of gene prediction, their strengths and weaknesses." In: Nucleic Acids Res 30.19 (2002), pp. 4103-4117

## RNA Gene finding: MilPat, Darn!
CSP/CFN + string algorithms

P. Thebault, S. de Givry, T. Schiex, and C. Gaspin. "Searching RNA motifs and their intermolecular contacts with constraint networks." In: Bioinformatics 22.17 (2006), pp. 2074-2080

M Zytnicki, C. Gaspin, and T Schiex. "DARN! A soft constraint solver for RNA motif localization". In: Constraints 13.1 (2008), pp. 91-109

## MendelSoft: pedigree debugging
CFN for MPE on Bayesian nets

M Sanchez, S de Givry, and T Schiex. "Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques". In: Constraints 13.1 (2008), pp. 130-154

T. Faraut, S. de Givry, P. Chabrier, T. Derrien, et al. "A comparative genome approach to marker ordering". In: Bioinformatics 23.2 (2007), e50-6
<figure><img src="image_47.png" /></figure>

## Genetic mapping with CarthaGene
GM learning + TSP optimization.

S. de Givry, M. Bouchez, P. Chabrier, D. Milan, et al. "CarthaGene: multipopulation integrated genetic and radiation hybrid mapping." In: Bioinformatics 21.8 (2005), pp. 1703-1704

V. Laurent, E. Wajnberg, B. Mangin, T. Schiex, et al. "A composite genetic map of the parasitoid wasp Trichogramma brassicae based on RAPD markers." In: Genetics 150.1 (1998), pp. 275-82

## RNA Gene finding: MilPat, Darn!
CSP/CFN + string algorithms

P. Thebault, S. de Givry, T. Schiex, and C. Gaspin. "Searching RNA motifs and their intermolecular contacts with constraint networks." In: Bioinformatics 22.17 (2006), pp. 2074-2080

M Zytnicki, C. Gaspin, and T Schiex. "DARN! A soft constraint solver for RNA motif localization". In: Constraints 13.1 (2008), pp. 91-109

## Gene finding with EuGene
Semi-CRF + optimization.

<figure><img src="image_48.png" /></figure>

## MendelSoft: pedigree debugging
CFN for MPE on Bayesian nets

M Sanchez, S de Givry, and T Schiex. "Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques". In: Constraints 13.1 (2008), pp. 130-154

T. Faraut, S. de Givry, P. Chabrier, T. Derrien, et al. "A comparative genome approach to marker ordering." In: Bioinformatics 23.2 (2007), e50-6
<figure><img src="image_49.png" /></figure>

## Genetic mapping with CarthaGene
GM learning + TSP optimization.

S. de Givry, M. Bouchez, P. Chabrier, D. Milan, et al. "CarthaGene: multipopulation integrated genetic and radiation hybrid mapping." In: Bioinformatics 21.8 (2005), pp. 1703-4

V. Laurent, E. Wajnberg, B. Mangin, T. Schiex, et al. "A composite genetic map of the parasitoid wasp Trichogramma brassicae based on RAPD markers." In: Genetics 150.1 (1998), pp. 275-82

## Gene finding with EuGene
Semi-CRF + optimization.

Tomato Genome Consortium et al. "The tomato genome sequence provides insights into fleshy fruit evolution." In: Nature 485.7400 (2012), pp. 635-641

C. Mathé, M. F. Sagot, T. Schiex, and P. Rouzé. "Current methods of gene prediction, their strengths and weaknesses." In: Nucleic Acids Res 30.19 (2002), pp. 4103-17

## RNA Gene finding: MilPat, Darn!
CSP/CFN + string algorithms

<figure><img src="image_50.png" /></figure>

## MendelSoft: pedigree debugging
CFN for MPE on Bayesian nets

M. Sanchez, S. de Givry, and T. Schiex. "Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques." In: Constraints 13.1 (2008), pp. 130-154

T. Faraut, S. de Givry, P. Chabrier, T. Derrien, et al. "comparative genome approach to marker ordering." In: Bioinformatics 23.2 (2007), e50-6
## Genetic mapping with CarthaGene
GM learning and TSP optimization.

S. de Givry, M. Bouchez, P. Chabrier, D. Milan, et al. "CarthaGene: multipopulation integrated genetic and radiation hybrid mapping." In: Bioinformatics 21.8 (2005), pp. 1703-4

V. Laurent, E. Wajnberg, B. Mangin, T. Schiex, et al. "A composite genetic map of the parasitoid wasp Trichogramma brassicae based on RAPD markers." In: Genetics 150.1 (1998), pp. 275-82

## Gene finding with EuGene
Semi-CRF + optimization.

Tomato Genome Consortium et al. "The tomato genome sequence provides insights into fleshy fruit evolution." In: Nature 485.7400 (2012), pp. 635-641

C. Mathé, M. F. Sagot, T. Schiex, and P. Rouzé. "Current methods of gene prediction, their strengths and weaknesses." In: Nucleic Acids Res 30.19 (2002), pp. 4103-17

## RNA Gene finding: MilPat, Darn!
CSP/CFN + string algorithms

P. Thebault, S. de Givry, T. Schiex, and C. Gaspin. "Searching RNA motifs and their intermolecular contacts with constraint networks." In: Bioinformatics 22.17 (2006), pp. 2074-80

M Zytnicki, C. Gaspin, and T Schiex. "DARN! A soft constraint solver for RNA motif localization". In: Constraints 13.1 (2008), pp. 91-109

## MendelSoft: pedigree debugging
CFN for MPE on Bayesian nets

<figure><img src="image_51.png" /></figure>

<figure><img src="image_52.png" /></figure>
Graphical models with decision and stochastic variables

* MRF/BN: stochastic variables + probability distribution. Can be learnt (RBM for deep learning).

* CFN: decision variables + cost functions/utilities/feasibility distribution.
## Graphical models with decision and stochastic variables

* MRF/BN: stochastic variables + probability distribution. Can be learnt (RBM for deep learning).

* CFN: decision variables + cost functions/utilities/feasibility distribution.

## Mixed graphical models with decision and stochastic variables

* Influence diagrams²²

* Stochastic constraint programming⁵²

* Plausability-feasibility-utility networks³⁷

H. Fargier, J. Lang, R. Martin-Clouaire, and Thomas Schiex. "A constraint satisfaction framework for decision under uncertainty". In: Proc. of the 11th Int. Conf. on Uncertainty in Artificial Intelligence. Montréal, Canada, Aug. 1995

H. Fargier, J. Lang, and T. Schiex. "Mixed Constraint Satisfaction: a framework for decision problems under incomplete knowledge". In: Proc. of AAAI'96. Portland, OR: AAA Press, Aug. 1996

C Pralet, G Verfaillie, and T Schiex. "An algebraic graphical model for decision with uncertainties, feasibilities, and utilities". In: Journal of Artificial Intelligence Research 29 (2007), pp. 421-489
Beyond NP

* Marginal probability: weighted counting<sup>50</sup>

* Marginal MAP: maximize probability with unobservable variables.

* Maximize expected utility...

Clément Viricel, David Simoncini, Sophie Barbe, and Thomas Schiex. "Guaranteed Weighted Counting for Affinity Computation: Beyond Determinism and Structure". In: International Conference on Principles and Practice of Constraint Programming. Springer. 2016. pp. 733-750

C Pralet, T Schiex, and G Verfaillie. "From influence diagrams to multioperator cluster DAGs". In: Proc. of UAI'2006. Boston, MA, 2006
## Graphical models

Provide a strong and grounded basis for data analytics, from data to decision.
## Graphical models

Provide a strong and grounded basis for data analytics, from data to decision.

We need efficient anytime anyspace algorithms, with associated modelling languages and solvers.
Questions ?
[1] David Allouche, Isabelle André, Sophie Barbe, Jessica Davies, et al. "Computational protein design as an optimization problem". In: Artificial Intelligence 212 (2014), pp. 59-79.

[2] Umberto Bertelé and Francesco Brioschi. Nonserial Dynamic Programming. Academic Press, 1972.

[3] S. Bistarelli, H. Fargier, U. Montanari, F. Rossi, et al. "Semiring-based CSPs and Valued CSPs: Frameworks, Properties and Comparison". In: Constraints 4 (1999), pp. 199-240.

[4] B. Cabon, S. de Givry, L. Lobois, T. Schiex, et al. "Radio Link Frequency Assignment". In: Constraints Journal 4 (1999), pp. 79-89.

[5] Tomato Genome Consortium et al. "The tomato genome sequence provides insights into fleshy fruit evolution". In: Nature 485.7400 (2012), pp. 635-641.

[6] M. C. Cooper. "Reduction operations in fuzzy or valued constraint satisfaction". In: Fuzzy Sets and Systems 134.3 (2003), pp. 311-342.

[7] M. C. Cooper, S. de Givry, and T. Schiex. "Optimal soft arc consistency". In: Proc. of IJCAI'2007. Hyderabad, India, Jan. 2007, pp. 68-73.

[8] M. C. Cooper and T. Schiex. "Arc consistency for soft constraints". In: Artificial Intelligence 154.1-2 (2004), pp. 199-227.

[9] M. Cooper, S. de Givry, M. Sanchez, T. Schiex, et al. "Soft arc consistency revisited". In: Artificial Intelligence 174 (2010), pp. 449-478.
<figure><img src="image_53.png" /></figure>

[10] Martin C Cooper, Simon de Givry, Marti Sánchez, Thomas Schiex, et al. "Virtual Arc Consistency for Weighted CSP." In: AAAI. Vol. 8. 2008. pp. 253-258.

[11] Martin Davis and Hilary Putnam. "A computing procedure for quantification theory". In: Journal of the ACM (JACM) 7.3 (1960), pp. 201-215.

[12] Rina Dechter. "Bucket Elimination: A Unifying Framework for Reasoning". In: Artificial Intelligence 113.1-2 (1999), pp. 41-85.

[13] Rina Dechter and Irina Rish. "Directional resolution: The Davis-Putnam procedure, revisited". In: KR 94 (1994), pp. 134-145.

[14] J Desmet, M De Maeyer, B Hazes, and I Lasters. "The dead-end elimination theorem and its use in protein side-chain positioning". In: Nature 356.6369 (Apr. 1992), pp. 539-42. ISSN: 0028-0836.

[15] T. Faraut, S. de Givry, P. Chabrier, T. Derrien, et al. "A comparative genome approach to marker ordering". In: Bioinformatics 23.2 (2007), e50-6.

[16] H. Fargier, J. Lang, R. Martin-Clouaire, and Thomas Schiex. "A constraint satisfaction framework for decision under uncertainty". In: Proc. of the 11th Int. Conf. on Uncertainty in Artificial Intelligence. Montreal, Canada, Aug. 1995.

[17] H. Fargier, J. Lang, and T. Schiex. "Mixed Constraint Satisfaction: a framework for decision problems under incomplete knowledge". In: Proc. of AAAI'96. Portland, OR: AAAI Press, Aug. 1996.
[18] Eugene C. Freuder. "A sufficient Condition for Backtrack-Bounded Search". In: Journal of the ACM 32.14 (1985), pp. 755-761.

[19] Eugene C. Freuder. "A sufficient Condition for Backtrack-free Search". In: Journal of the ACM 29.1 (1982), pp. 24-32.

[20] S. de Givry, M. Bouchez, P. Chabrier, D. Milan, et al. "CarthaGene: multipopulation integrated genetic and radiation hybrid mapping". In: Bioinformatics 21.8 (2005), pp. 1703-4.

[21] Dominik Gront, Daniel W Kulp, Robert M Vernon, Charlie EM Strauss, et al. "Generalized fragment picking in Rosetta: design, protocols and applications". In: PloS one 6.8 (2011), e23294.

[22] Ronald A Howard and James E Matheson. "Influence diagrams". In: Decision Analysis 2.3 (2005), pp. 127-143.

[23] Barry Hurley, Barry O'Sullivan, David Allouche, George Katsirelos, et al. "Multi-language evaluation of exact solvers in graphical model discrete optimization". In: Constraints 21.3 (2016), pp. 413-434.

[24] Carleton L Kingsford, Bernard Chazelle, and Mona Singh. "Solving and analyzing side-chain positioning problems using linear and integer programming". In: Bioinformatics (Oxford, England) 21.7 (Apr. 2005), pp. 1028-36. ISSN: 1367-4803.

[25] A M C A. Koster. "Frequency assignment: Models and Algorithms". Available at www.zib.de/koster/thesis.html. PhD thesis. The Netherlands: University of Maastricht, Nov. 1999.
[26] VK Koval' and Mykhailo Ivanovich Schlesinger. "Two-dimensional programming in image analysis problems". In: Avtomatika i Telemekhanika 8 (1976), pp. 149-168.

[27] VA Kovalevsky and VK Koval. "A diffusion algorithm for decreasing energy of max-sum labeling problem". In: Glushkov Institute of Cybernetics, Kiev, USSR (1975).

[28] Frank R Kschischang, Brendan J Frey, and Hans-Andrea Loeliger. "Factor graphs and the sum-product algorithm". In: Information Theory, IEEE Transactions on 47.2 (2001), pp. 498-519.

[29] J. Larrosa. "On Arc and Node Consistency in weighted CSP". In: Proc. AAAI'02. Edmondton, (CA), 2002, pp. 48-53.

[30] J. Larrosa, S. de Givry, F. Heras, and M. Zytnicki. "Existential arc consistency: getting closer to full arc consistency in weighted CSPs". In: Proc. of the 19th IJCAI. Edinburgh, Scotland, Aug. 2005, pp. 84-89.

[31] J. Larrosa and T. Schiex. "In the quest of the best form of local consistency for Weighted CSP". In: Proc. of the 18th IJCAI. Acapulco, Mexico, Aug. 2003, pp. 239-244.

[32] Javier Larrosa and Thomas Schiex. "Solving weighted CSP by maintaining arc consistency". In: Artif. Intell. 159.1-2 (2004), pp. 1-26.

[33] V. Laurent, E. Wajnberg, B. Mangin, T. Schiex, et al. "A composite genetic map of the parasitoid wasp Trichogramma brassicae based on RAPD markers". In: Genetics 150.1 (1998), pp. 275-82.

[34] C. Mathé, M. F. Sagot, T. Schiex, and P. Rouzé. "Current methods of gene prediction, their strengths and weaknesses". In: Nucleic Acids Res 30.19 (2002), pp. 4103-17.
[35] Judea Pearl. Probabilistic Reasoning in Intelligent Systems, Networks of Plausible Inference. Palo Alto: Morgan Kaufmann, 1988.
[36] C Pralet, T Schiex, and G Verfaillie. "From influence diagrams to multioperator cluster DAGs". In: Proc. of UAI'2006. Boston, MA, 2006.
[37] C Pralet, G Verfaillie, and T Schiex. "An algebraic graphical model for decision with uncertainties, feasibilities, and utilities". In: Journal of Artificial Intelligence Research 29 (2007), pp. 421-489.
[38] Daniel Prusa and Tomas Werner. "Universality of the local marginal polytope". In: Pattern Analysis and Machine Intelligence, IEEE Transactions on 37.4 (2015), pp. 898-904.
[39] Thomas J Richardson and Rüdiger L Urbanke. "The capacity of low-density parity-check codes under message-passing decoding". In: Information Theory, IEEE Transactions on 47.2 (2001), pp. 599-618.
[40] J. Alan Robinson. "A machine-oriented logic based on the resolution principle". In: Journal of the ACM 12 (1965), pp. 23-44.
[41] M Sanchez, S de Givry, and T Schiex. "Mendelian error detection in complex pedigrees using weighted constraint satisfaction techniques". In: Constraints 13.1 (2008), pp. 130-154.
[42] T. Schiex. "Arc consistency for soft constraints". In: Principles and Practice of Constraint Programming - CP 2000. Vol. 1894. LNCS. Singapore, Sept. 2000, pp. 411-424.
[43] T. Schiex, H. Fargier, and G. Verfaillie. "Valued Constraint Satisfaction Problems: hard and easy problems". In: Proc. of the 14th IJCAI. Montréal, Canada, Aug. 1995, pp. 631-637.
[44] Thomas Schiex, Jean-Charles Régin, Chistine Gaspin, and Gérard Verfaillie. "Lazy Arc Consistency". In: Proc. of AAAI'96. Portland, OR: AAAI Press, Aug. 1996.

[45] M.I. Schlesinger. "Sintaksicheskiy analiz dvumernykh zritelnikh signalov v usloviyakh pomekh (Syntactic analysis of two-dimensional visual signals in noisy conditions)". In: Kibernetika 4 (1976), pp. 113-130.

[46] David Simoncini, David Allouche, Simon de Givry, Celine Delmas, et al. "Guaranteed discrete energy optimization on large protein design problems". In: Journal of chemical theory and computation 11.12 (2015), pp. 5980-5989.

[47] P. Thebault, S. de Givry, T. Schiex, and C. Gaspin. "Searching RNA motifs and their intermolecular contacts with constraint networks". In: Bioinformatics 22.17 (2006), pp. 2074-80.

[48] Seydou Traoré, David Allouche, Isabelle André, Simon de Givry, et al. "A new framework for computational protein design through cost function network optimization". In: Bioinformatics 29.17 (2013), pp. 2129-2136.

[49] Seydou Traoré, Kyle E Roberts, David Allouche, Bruce R Donald, et al. "Fast search algorithms for computational protein design". In: Journal of computational chemistry (2016).

[50] Clément Viricel, David Simoncini, Sophie Barbe, and Thomas Schiex. "Guaranteed Weighted Counting for Affinity Computation: Beyond Determinism and Structure". In: International Conference on Principles and Practice of Constraint Programming. Springer, 2016, pp. 733-750.
[51] Martin J Wainwright, Tommi S Jaakkola, and Alan S Willsky. "Tree-based reparameterization framework for analysis of sum-product and related algorithms". In: IEEE Transactions on information theory 49.5 (2003), pp. 1120-1146.

[52] Toby Walsh. "Stochastic constraint programming". In: ECAI. Vol. 2. 2002, pp. 111-115.

[53] Dag Wedelin. "An algorithm for large scale 0-1 integer programming with application to airline crew scheduling". In: Annals of operations research 57.1 (1995), pp. 283-301.

[54] T. Werner. "A Linear Programming Approach to Max-sum Problem: A Review." In: IEEE Trans. on Pattern Recognition and Machine Intelligence 29.7 (July 2007), pp. 1165-1179. URL: http://dx.doi.org/10.1109/TPAMI.2007.1036

[55] M Zytnicki, C Gaspin, and T Schiex. "DARN! A soft constraint solver for RNA motif localization". In: Constraints 13.1 (2008), pp. 91-109.