Modélisation de problèmes par contraintes

Dans cette section, nous allons introduire les concepts fondamentaux de la modélisation de problèmes par contraintes.

Un problème $P = \langle V, D, C\rangle$ est généralement modélisé en définissant un ensemble de variables $V = {v_1, v_2, \ldots, v_n}$, où chaque variable $v_i$ peut prendre des valeurs dans un domaine fini $D_i$. Le domaine global $D$ est l’ensemble des domaines individuels, c’est-à-dire $D = D_1 \times D_2 \times \ldots \times D_n$. Les contraintes $C = {c_1, c_2, \ldots, c_m}$ sont des relations qui limitent les combinaisons de valeurs que les variables peuvent prendre simultanément. Chaque contrainte $c_j$ est définie sur un sous-ensemble de variables et spécifie les combinaisons de valeurs autorisées pour ces variables.

L’objectif de la résolution de problèmes par contraintes est de trouver une affectation des variables qui satisfait toutes les contraintes, ou d’optimiser une fonction objectif sous les contraintes données.

Prenons un exemple simple pour illustrer ces concepts.

Exemple : la conférence

Un chercheur a invité 4 conférenciers pour une école d’été sur 5 demi-journées.

chaque conférencier anime une seule demi-journée,
la conférence de Bob doit avoir lieu avant celle de Diane,
la conférence d’Alice doit être programmée immédiatement après celle de Colin,
une après-midi est réservée pour une activité sociale,
chaque conférencier a des disponibilités spécifiques.

---
config:
  logLevel: 'debug'
  theme: 'default'
  themeVariables:
    cScale0: rgba(134, 172, 65, 1)
    cScaleLabel0: '#ffffff'
    cScale1: rgba(52, 103, 92, 1)
    cScaleLabel1: '#ffffff'
    cScale2: rgba(125, 163, 161, 1)
    cScaleLabel2: '#ffffff'
---
timeline
    title Disponibilité des conférenciers
    section Mercredi
    Matin: Alice : Bob : Diane
    Après-midi: Alice : Bob : Colin : Diane
    section Jeudi
    Matin : Alice  : Colin : Diane
    Après-midi : Alice : Colin : Diane
    section Vendredi
    Matin : Alice : Colin

Solution (unique)

---
config:
  logLevel: 'debug'
  theme: 'default'
  themeVariables:
    cScale0: rgba(134, 172, 65, 1)
    cScaleLabel0: '#ffffff'
    cScale1: rgba(52, 103, 92, 1)
    cScaleLabel1: '#ffffff'
    cScale2: rgba(125, 163, 161, 1)
    cScaleLabel2: '#ffffff'
---
timeline
    title Planning de l'école d'été
    section Mercredi
    Matin: Bob
    Après-midi: Activité sociale
    section Jeudi
    Matin : Diane
    Après-midi : Colin
    section Vendredi
    Matin : Alice

Modélisation mathématique

Pour modéliser ce problème, nous devons définir les variables, leurs domaines et les contraintes associées.

Variables (et leur domaine)

Les variables déterminent une décision à prendre, elles répondent donc à une question.

Ici, une question pertinente peut être :

“Quel est le créneau horaire attribué à Alice ?”

Bien entendu, cette question se pose pour chaque conférencier. Dès lors, une manière naturelle de modéliser le problème est de définir une variable par conférencier représentant le créneau horaire qui lui est attribué. Le domaine de chaque variable correspond aux créneaux horaires auxquels le conférencier peut être affecté, prenant en compte les disponibilités de chaque conférencier. Notons que l’activité sociale est considérée comme un “conférencier” supplémentaire pour simplifier la modélisation.

Nous déclarons alors une variable $c_i$ pour chaque conférencier $i \in \lbrace Alice,Bob, Colin, Diane, ActSocial\rbrace$, représentant le créneau horaire auquel il est affecté :

$c_{Alice}$ : créneau d’Alice
$c_{Bob}$ : créneau de Bob
$c_{Colin}$ : créneau de Colin
$c_{Diane}$ : créneau de Diane
$c_{ActSocial}$ : créneau de l’activité sociale

En fonction des disponibilités des conférenciers, nous définissons les domaines suivants :

$dom(c_{Alice}) = [\![1, 5]\!]$
$dom(c_{Bob}) = [\![ 1, 2]\!]$
$dom(c_{Colin}) = [\![ 1, 5]\!]$
$dom(c_{Diane}) = [\![2, 4]\!]$
$dom(c_{ActSocial}) = \lbrace 2, 4\rbrace$

Les créneaux sont numérotés de 1 à 5, où 1 correspond au mercredi matin et 5 au vendredi matin. Remarquons que les domaines peuvent être définis avec des intervalles (comme Alice) ou des ensembles de valeurs spécifiques (comme l’activité sociale).

Ce choix de modélisation est sera nommé “modélisation par conférencier” par la suite.

Une autre modélisation possible

La question aurait pu être formulée différement:

“Qui va animer le mercredi matin ?”

Là encore, la question se pose pour chaque créneau horaire. Cela induirait une modélisation différente, avec une variable par créneau horaire représentant le conférencier affecté à ce créneau. Le domaine de chaque variable serait l’ensemble des conférenciers disponibles pour ce créneau.

Dans ce cas, nous aurions les variables suivantes :

$c_{Mm}$ : conférencier du mercredi matin
$c_{Ma}$ : conférencier du mercredi après-midi
$c_{Jm}$ : conférencier du jeudi matin
$c_{Ja}$ : conférencier du jeudi après-midi
$c_{Vm}$ : conférencier du vendredi matin

En notant Alice par 1, Bob par 2, Colin par 3, Diane par 4, et l’activité sociale par 5, les domaines seraient :

$dom(c_{Mm}) = \lbrace 1, 2, 4 \rbrace$
$dom(c_{Ma}) = [\![1, 5]\!]$
$dom(c_{Jm}) = \lbrace 1, 3, 4 \rbrace$
$dom(c_{Ja}) = \lbrace 1, 3, 4, 5 \rbrace$
$dom(c_{Vm}) = \lbrace 1, 3 \rbrace$

Ce choix de modélisation est sera nommé “modélisation par créneau” par la suite.

Contraintes

Les contraintes limitent les combinaisons de valeurs que les variables peuvent prendre simultanément. Bien entendu, les contraintes sont définies en fonction de la modélisation choisie.

Contraintes pour la modélisation par conférencier

Nous traduisons les exigences du problème en contraintes formelles :

Chaque conférencier doit présenter une seule fois, et l’activité sociale doit occuper un créneau unique : $$c_{Alice} \neq c_{Bob} \neq c_{Colin} \neq c_{Diane} \neq c_{social}$$
La conférence de Bob doit avoir lieu avant celle de Diane : $$c_{Bob} < c_{Diane}$$
La conférence d’Alice doit être programmée immédiatement après celle de Colin : $$c_{Alice} = c_{Colin} + 1$$

Contraintes pour la modélisation par créneau

Nous traduisons les exigences du problème en contraintes formelles :

Chaque conférencier doit présenter une seule fois, et l’activité sociale doit occuper un créneau unique : $$c_{Mm} \neq c_{Ma} \neq c_{Jm} \neq c_{Ja} \neq c_{Vm}$$
La conférence de Bob doit avoir lieu avant celle de Diane : $$\exists (x,y) \in \lbrace (Mm, Ma), (Mm, Jm), (Mm, Ja), (Mm, Vm), (Ma, Jm), (Ma, Ja), (Ma, Vm), (Jm, Ja), (Jm, Vm), (Ja, Vm) \rbrace, c_{x} = 2 \land c_{y} = 4$$
La conférence d’Alice doit être programmée immédiatement après celle de Colin : $$\exists (x,y) \in \lbrace (Mm, Ma), (Ma,Jm), (Jm, Ja), (Ja,Vm), (Ja, Vm) \rbrace, c_{x} = 3 \land c_{y} = 1$$

Remarques

A ce stade, nous avons proposé deux modélisations différentes du même problème, chacune avec ses propres variables, domaines et contraintes. Vous aurez peut-être remarqué que ces deux modèles sont liées : une solution dans un modèle peut être traduite en une solution dans l’autre modèle. En particulier, dans le premier modèle si Alice est affectée au créneau 5 (vendredi matin), alors dans le second modèle, la variable correspondant au vendredi matin doit être affectée à Alice. On parlera de dualité entre les deux modèles. L’espace des solutions est le même dans les deux cas.

Il existe souvent plusieurs façons de modéliser un même problème par contraintes. Nous en proposons deux ici pour illustrer ce point mais il en existe certainement d’autres. Cependant, vous aurez remarqué que certains modélisations sont plus naturelles, plus compactes, plus lisibles que d’autres. De plus, certaines modélisations peuvent être plus efficaces à résoudre que d’autres, parce qu’elles conduisent à des espaces de recherche plus petits ou à des contraintes plus efficaces.

Programmation avec Choco-solver

Selon le modèle choisi, le programme à écrire pour résoudre le problème diffère. Dans le premier cas, la transcription en code est relativement directe. La première contrainte, qui impose que chaque conférencier présente une seule fois, se traduit par une contrainte “AllDifferent”. C’est une contrainte globale. Sémantiquement parlant, elle est équivalente à une conjonction de contraintes binaires d’inégalité. Cependant, le filtrage obtenu en utilisant une contrainte globale est souvent plus fort, puisqu’elle dispose d’une vue d’ensemble du problème.

Remarque

L’une des difficultés de la modélisation par contraintes est de savoir quelles contraintes (globales ou non) existent et quand les utiliser à bon escient. Un point de départ utile est de consulter le catalogue de contraintes globales ou la documentation de Choco-solver.

Programme pour la modélisation par conférencier

Voici comment modéliser ce problème en utilisant Choco-solver en Java et Python.

import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.IntVar;

Model model = new Model();
IntVar alice = model.intVar("Alice", 1, 5);
IntVar bob = model.intVar("Bob", 1, 2);
IntVar colin = model.intVar("Colin", 1, 5);
IntVar diana = model.intVar("Diana", 2, 4);
IntVar socialEvent = model.intVar("SocialEvent", new int[]{2, 4});

// 1. chaque intervenant ne peut intervenir qu'une seule fois
model.allDifferent(alice, bob, colin, diana, socialEvent).post();
// 2. Bob intervient avant Diane
model.arithm(bob, "<", diana).post();
// 3. Alice intervient immédiatement après Colin
model.arithm(alice, "=", colin, "+", 1).post();

Solver solver = model.getSolver();
while (solver.solve()) {
    System.out.println("Alice: " + alice.getValue());
    System.out.println("Bob: " + bob.getValue());
    System.out.println("Colin: " + colin.getValue());
    System.out.println("Diana: " + diana.getValue());
    System.out.println("Social Event: " + socialEvent.getValue());
    System.out.println("-----");
}

from pychoco import *

# Création du modèle
model = Model("Conférence")

# Définition des variables
alice = model.intvar(1, 5, "Alice")
bob = model.intvar(1, 2, "Bob")
colin = model.intvar(1, 5, "Colin")
diane = model.intvar(2, 4, "Diane")
social_activity = model.intvar([2,4], ub=None, name="Activité sociale")

# Contraintes
# 1. chaque intervenant ne peut intervenir qu'une seule fois
model.all_different(alice, bob, colin, diane, social_activity).post()
# 2. Bob intervient avant Diane
model.arithm(bob, "<", diane).post()
# 3. Alice intervient immédiatement après Colin
model.arithm(alice, "=", colin, "+", 1).post()
# 4. une après-midi est réservée pour une activité sociale (créneau 1 ou 3)
# (déjà modélisé dans la variable social_activity)


solver = model.get_solver()
while solver.solve():
    print(f"Alice : {alice.get_value()}")
    print(f"Bob : {bob.get_value()}")
    print(f"Colin : {colin.get_value()}")
    print(f"Diane : {diane.get_value()}")
    print(f"Activité sociale : {social_activity.get_value()}")
    print("-----")

Programme pour la modélisation par créneau

Voici comment modéliser ce problème en utilisant Choco-solver en Java et Python.

import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solver;
import org.chocosolver.solver.variables.IntVar; 

Model model = new Model();
IntVar mm = model.intVar("MercrediMatin", new int[]{1,2,4});
IntVar ma = model.intVar("MercrediAprèsMidi", 1, 5);
IntVar jm = model.intVar("JeudiMatin", new int[]{1,3,4});
IntVar ja = model.intVar("JeudiAprèsMidi", new int[]{1,3,4,5});
IntVar vm = model.intVar("VendrediMatin", new int[]{1,3});  

// 1. chaque intervenant ne peut intervenir qu'une seule fois
model.allDifferent(mm, ma, jm, ja, vm).post();
// 2. Bob intervient avant Diane
model.or(
    model.and(model.arithm(mm, "=", 2), model.arithm(ma, "=", 4)),
    model.and(model.arithm(mm, "=", 2), model.arithm(jm, "=", 4)),
    model.and(model.arithm(mm, "=", 2), model.arithm(ja, "=", 4)),
    model.and(model.arithm(mm, "=", 2), model.arithm(vm, "=", 4)),
    model.and(model.arithm(ma, "=", 2), model.arithm(jm, "=", 4)),
    model.and(model.arithm(ma, "=", 2), model.arithm(ja, "=", 4)),
    model.and(model.arithm(ma, "=", 2), model.arithm(vm, "=", 4)),
    model.and(model.arithm(jm, "=", 2), model.arithm(ja, "=", 4)),
    model.and(model.arithm(jm, "=", 2), model.arithm(vm, "=", 4)),
    model.and(model.arithm(ja, "=", 2), model.arithm(vm, "=", 4))
).post();

// 3. Alice intervient immédiatement après Colin
model.or(
    model.and(model.arithm(mm, "=", 3), model.arithm(ma, "=", 1)),
    model.and(model.arithm(ma, "=", 3), model.arithm(jm, "=", 1)),
    model.and(model.arithm(jm, "=", 3), model.arithm(ja, "=", 1)),
    model.and(model.arithm(ja, "=", 3), model.arithm(vm, "=", 1))
).post();   

Solver solver = model.getSolver();
while (solver.solve()) {
    System.out.println("Mercredi Matin: " + mm.getValue());
    System.out.println("Mercredi Après-Midi: " + ma.getValue());
    System.out.println("Jeudi Matin: " + jm.getValue());
    System.out.println("Jeudi Après-Midi: " + ja.getValue());
    System.out.println("Vendredi Matin: " + vm.getValue());
    System.out.println("-----");
}

from pychoco import *   

# Création du modèle
model = Model("Conférence")
# Définition des variables
mm = model.intvar([1,2,4], ub=None, name="MercrediMatin")
ma = model.intvar(1, 5, "MercrediAprèsMidi")
jm = model.intvar([1,3,4], ub=None, name="JeudiMatin")
ja = model.intvar([1,3,4,5], ub=None, name="JeudiAprèsMidi")
vm = model.intvar([1,3], ub=None, name="VendrediMatin")

# Contraintes
# 1. chaque intervenant ne peut intervenir qu'une seule fois
model.all_different([mm, ma, jm, ja, vm]).post()
# 2. Bob intervient avant Diane
model.or_([
    model.and_([model.arithm(mm, "=", 2), model.arithm(ma, "=", 4)]),
    model.and_([model.arithm(mm, "=", 2), model.arithm(jm, "=", 4)]),
    model.and_([model.arithm(mm, "=", 2), model.arithm(ja, "=", 4)]),
    model.and_([model.arithm(mm, "=", 2), model.arithm(vm, "=", 4)]),
    model.and_([model.arithm(ma, "=", 2), model.arithm(jm, "=", 4)]),
    model.and_([model.arithm(ma, "=", 2), model.arithm(ja, "=", 4)]),
    model.and_([model.arithm(ma, "=", 2), model.arithm(vm, "=", 4)]),
    model.and_([model.arithm(jm, "=", 2), model.arithm(ja, "=", 4)]),
    model.and_([model.arithm(jm, "=", 2), model.arithm(vm, "=", 4)]),
    model.and_([model.arithm(ja, "=", 2), model.arithm(vm, "=", 4)])]
).post()
# 3. Alice intervient immédiatement après Colin
model.or_([
    model.and_([model.arithm(mm, "=", 3), model.arithm(ma, "=", 1)]),
    model.and_([model.arithm(ma, "=", 3), model.arithm(jm, "=", 1)]),
    model.and_([model.arithm(jm, "=", 3), model.arithm(ja, "=", 1)]),
    model.and_([model.arithm(ja, "=", 3), model.arithm(vm, "=", 1)])]
).post()

solver = model.get_solver()
while solver.solve():
    print(f"Mercredi Matin : {mm.get_value()}")
    print(f"Mercredi Après-Midi : {ma.get_value()}")
    print(f"Jeudi Matin : {jm.get_value()}")
    print(f"Jeudi Après-Midi : {ja.get_value()}")
    print(f"Vendredi Matin : {vm.get_value()}")
    print("-----")

Et les modèles booléens ?

Dans certains cas, il peut être avantageux de modéliser un problème en utilisant uniquement des variables booléennes (0/1). Les contraintes prennent alors la forme de clauses logiques (disjonctions de littéraux) ou de fonctions linéaires. La question se pose alors d’utiliser la satisfaisabilité booléenne (SAT) ou la programmation linéaire en nombres entiers (ILP) pour résoudre le problème.

Il est cependant parfois possible de transformer un ensemble de variables booléennes en une variable entière. Par exemple, si nous avons trois variables booléennes $b_1, b_2, b_3$ représentant respectivement si une tâche est assignée à un employé A, B ou C. Si cette tâche ne peut être assignée qu’à un seul employé, nous pouvons introduire une variable entière $e$ avec le domaine $dom(e) = \lbrace 1, 2, 3 \rbrace$, où chaque valeur correspond à un employé spécifique (1 pour A, 2 pour B, 3 pour C). Cela permet de réduire le nombre de variables, d’éliminer les contraintes d’exclusivité mutuelle entre les variables booléennes, et de simplifier la modélisation globale du problème.

Remarque

Il existe d’autres types de variables, comme les variables de type ensemble, qui peuvent être utilisées pour modéliser certains problèmes de manière plus naturelle. Cependant, les variables entières et booléennes restent les plus couramment utilisées en programmation par contraintes.

Conclusion

La première étape dans la résolution d’un problème par contraintes est de le modéliser correctement. Cela implique de définir les variables, leurs domaines et les contraintes qui régissent leurs interactions. Différentes modélisations peuvent exister pour un même problème, chacune ayant ses avantages et inconvénients. Le choix de la modélisation peut avoir un impact sur les contraintes utilisées, l’efficacité de la résolution et la lisibilité du modèle.

Il est souvent bénéfique d’explorer différentes modélisations pour trouver la plus adaptée au problème à résoudre.