La programmation par contraintes avec Choco3 (Java)

LA PROGRAMMATION

PAR CONTRAINTES (PPC)

AVEC CHOCO3

ALINE FIGOUREUX

27 ans

Ingénieur Telecom Lille

Développeuse Java/Flex depuis 5 ans

Passionnée de déco et de bricolage

Membre des Duchess FR

[email protected] / @afigoureux

L A P R O G R A M M A T I O N P A R C O N T R A I N T E S A V E C

C H O C O 3 - A L I N E F I G O U R E U X 2

mailto:[email protected]

LES DUCHESS

• Groupe féminin de développement sur la

plateforme Java depuis 2010

• D’autres groupes dans le monde (Suisse, Belgique, Hollande..)

• Antennes à Paris, Lyon, Limoge, Marseille..

• Ouvert à TOUS



OBJECTIFS DES DUCHESS

• Donner plus de visibilité aux femmes de l’IT

• Aider et encourager celles qui ont des sujets à présenter

• Les encourager à se rencontrer pour coopérer sur des projets

• Etre présentes sur des events tels que Devoxx, Code story, DevFestWParis, JUGs, Google WomenTechMakers…

www.duchess-france.org

[email protected]

@duchessFR



http://www.duchess-france.org





LA PROGRAMMATION PAR

CONTRAINTES



Constraint Programming represents (…)

the Holy Grail of programming : the

user states the problem, the computer

solves it. (E. Freuder, Director of the Cork Constraint Computation Centre)



OBJECTIFS DE LA PPC

• Résoudre des problèmes très complexes ayant un

grand nombre de contraintes

• Offrir une autre façon de formuler et résoudre des

problèmes combinatoires

• Exemples d’applications :

Sudoku, carré magique, planification, emplois du

temps, séquençage de l’ADN, conception de circuits,

logistique, etc.



QU’EST CE QU’UN PROBLÈME ?

• Se modélise par un réseau de contraintes, soit :

• un ensemble de variables,

• un ensemble de domaines

• un ensemble de contraintes.

• A chaque variable est associé un domaine.



EN BREF UN PROBLÈME C’EST :

P est un triplé (X, D, C) avec :

•X={X1, X2, ..., Xn} – l’ensemble des variables

•D={D1, D2, ..., Dn} – l’ensemble des domaines finis

•C={C1, C2, ..., Ce} – l’ensemble des contraintes



QU’EST CE QU’UNE SOLUTION ?

• C’est l’affectation d’une valeur a chaque variable telle que les contraintes soient respectées (ou « pas de solution »)

• Exemple de Problème et de ses solutions :

• 3 variables x, y et z (entières).

• Leurs domaines Dx=[1,3], Dy=[1,3], Dz=[1,3].

• La contrainte x = y + z

• Les solutions sont (2,1,1), (3,1,2), (3,2,1).



AUTRE EXEMPLE : ORDONNANCEMENT SPORTIF

• n équipes, n-1 semaines, n/2 périodes

• chaque paire d’équipes joue exactement 1 fois

• chaque équipe joue un match chaque semaine

• chaque équipe joue au plus deux fois dans la même période


C H O C O 3 - A L I N E F I G O U R E U X

Semaine 1 Semaine 2 Semaine 3 Semaine 4 Semaine 5 Semaine 6 Semaine 7

Période 1 0 vs 1 0 vs 2 4 vs 7 3 vs 6 3 vs 7 1 vs 5 2 vs 4



Période 4 6 vs 7 4 vs 6 2 vs 5 1vs 2 0 vs 5 3 vs 4 1 vs 3

11

LA PPC PERMET DE :

Trouver une solution

Enumérer toutes les solutions

Trouver la solution optimale



LES SOLVEURS DE CONTRAINTES (LIBS JAVA)

Libres

• Choco

• Cream

• Google OR-tools

• JaCoP

• Jopt



Propriétaires

• Artelys Kalis

• ILOG CP

13

CHOCO



INTRODUCTION

• Libre (licence BSD)

• Projet français !

• Lisible et flexible (Conçu pour l’enseignement et la

recherche)

• Efficace et fiable (résout des problèmes concrets)

• Plus de 60 000 téléchargements à travers le monde depuis la

version 1.0 en 2003

• Code : Plus de 700 Classes (> 60 000 lignes)



L’HISTOIRE DE CHOCO

1999 - Première implémentation CLAIRE au sein du projet

OCRE (initiative nationale pour un solveur de contraintes

ouvert destiné a la recherche et a l’enseignement)

2003 - Choco 1.0 : Première implémentation Java

2008 - Choco 2.0 : Version user-oriented + séparation entre le

Modèle et le Solveur + ajout de nouvelles contraintes

2013 - Choco 3.0 : Refacto complète du code, easy-to-use,

meilleure maintenabilité



2013 : CHOCO3

Complètement différent de Choco2

Version stable actuelle : 3.1.1

Nouvelle version Choco-3.2.0 en Mars 2014 (oh wait..)

Utilisé notamment par :



APPLICATIONS DE CHOCO3 DANS L’INDUSTRIE

Entropy, Easyvirt, Hedera : Configuration de data center (placement de VM)

Vaberlin, GSD lab : Développement logiciel, génération de code

Safran, Dassault Aviation : Plannings de missions

KLS Optim, Optilogistic : Planning de chargement de camions et de palettes

Biotrial, Maif : Planning du personnel

Kosmos : Emplois du temps pour des lycées

PSA : Prototype de configuration de voiture online



EN BREF :



LES TYPES DE VARIABLES

Integer (IntVar)

Boolean (BoolVar)

Set (SetVar)

Graph (GraphVar)

Real (RealVar)



LES TYPES DE CONTRAINTES

Arithmétiques : =, !=, <, <=, >, >=

Globales:

AllDifferent Toutes les variables de la solution doivent être !=

GlobalCardinality Impose un nombre d’occurrences min et max pour chaque variable

Nvalue Le nombre de valeurs distinctes utilisées dans un ensemble de

variables doit être = à N

Scalar Le produit scalaire de l’ensemble des variables avec un autre

ensemble de valeurs doit être égal à un nombre donné.

Cumulative, Din, Occurrence, Element, Regular, Circuit, etc . . .

Exclusives: Tree, CostRegular, Ibex . .

Réifiées : and, or, not, implies, ifOnlyIf 80 contraintes disponibles en tout



CONTRAINTES SUR DES INTEGER

Contraintes basiques :

1. Arithmétiques :

Egalité (v1 == v2, v1 != v2);

Comparaison (v1 <= v2, v1 < v2);

Différence, combinaisons linéaires; produits de

variables, …

2. Expressions complexes

Sur les expressions : plus, minus, mult, …

Sur les variables : times, scalar, sum, …

3. Autres

max, min, abs , …



LES STRATÉGIES DE RECHERCHE

Permettent de définir une manière spécifique de

parcourir l'espace de recherche.

Différentes stratégies :

IntStrategyFactory.inputOrder_InDomainMin

IntStrategyFactory.inputOrder_InDomainMax

IntStrategyFactory.firstFail_InDomainMin

…



LES FACTORIES

VariableFactory

IntConstraintFactory, SetConstraintFactory et

GraphConstraintFactory…

IntStrategyFactory, SetStrategyFactory et

GraphStrategyFactory…



LE SOLVER

Le Solver est l’objet central qui doit être

créé en premier :

Solver solver = new Solver();

Rassemble toutes les informations



EXEMPLE TRIVIAL // 1. On crée le solver

Solver solver = new Solver(« mon super problème »);

// 2. On crée les variables à l’aide de la factory

IntVar x = VariableFactory.bounded("X", 0, 5, solver);

IntVar y = VariableFactory.bounded("Y", 0, 5, solver);

// 3. On crée une contrainte et on la poste dans le solver

solver.post(IntConstraintFactory.arithm(x, "+", y, "<", 5));

// 4. On définit la stratégie de recherche

solver.set(IntStrategyFactory.inputOrder_InDomainMin(new IntVar[]));

// 5. On lance le proccessus de résolution

solver.findSolution();



EXEMPLE DE CONTRAINTES BASIQUES SUR DES INT

Model prob = new Model();

IntDomainVar var1 = prob.makeEnumIntVar(“var1”, 2, 5);




Constraint c1 = prob.gt(var2,var1);

Constraint c2 = prob.leq(var1,var3);

IntExp var5Exp = prob.minus(var4, var1);

Constraint c3 = prob.neq(var5Exp,var3);

prob.post(c1); prob.post(c2); prob.post(c3);

[1..10]

[2..5]

[5..10]

[1..10] c1

c2 [-4..8]

c3

var1 var2

var3

var4

var5ex

p



EXEMPLE DU CARRÉ MAGIQUE

public class MagicSquare {

public static void main(String[] args) {

int n = 4;

System.out.println(

"Magic Square with n = " + n);

}

}



34

34 34

34

34

34 34

34

34 34

28

CARRÉ MAGIQUE : ON CRÉE LES VARIABLES

IntVar[] vars = new IntVar[n * n];

for (int i = 0; i < n; i++) {

for (int j = 0; j < n; j++) {

vars[i * n + j] = VariableFactory.bounded(

"C" + i + "_" + j, 1, n * n, solver );

}

}

IntVar sum = VariableFactory.bounded ( "S", 1, n * n * (n * n + 1) / 2,

solver );



n = 4

29

CARRÉ MAGIQUE : LES CONTRAINTES 1/2

// 1ère contrainte : Toutes les cases du carré doivent avoir

des valeurs différentes

for (int i = 0; i < n * n; i++) {

for (int j = 0; j < i; j++) {

solver.post( IntConstraintFactory.arithm( vars[i], “!=“,

vars[j] ) );

}

}



CARRÉ MAGIQUE : LES CONTRAINTES 2/2

// 2ème contrainte : La variable « Sum » est liée aux variables de chacune

des lignes et colonnes du carré

int[] coeffs = new int[n];

for (int i = 0; i < n; i++) {

coeffs[i] = 1;

}

for (int i = 0; i < n; i++) {

IntVar[] col = new IntVar[n];

IntVar[] row = new IntVar[n];

for (int j = 0; j < n; j++) {

col[j] = vars[i * n + j];

row[j] = vars[j * n + i];

}

solver.post( IntConstraintFactory.scalar( coeffs, row, sum ) );

solver.post( IntConstraintFactory.scalar( coeffs, col, sum ) );

}



On utilise un produit scalaire avec un

coefficient de 1 pour s’assurer que la

somme de chaque ligne et de chaque

colonne sera égale à la même valeur

31

CARRÉ MAGIQUE : SOLUTION

>java MagicSquare

Magic Square Problem with n = 4

Pb[17 vars, 129 constr.]

C0_0{16} C0_1{3} C0_2{2} C0_3{13}

C1_0{5} C1_1{10} C1_2{12} C1_3{8}

C2_0{9} C2_1{6} C2_2{7} C2_3{12}

C3_0{4} C3_1{15} C3_2{14} C3_3{1}

S{34}

-- solve => 1 solutions

-- 172[+0] millis.



LA FAMILLE SMITH



EXEMPLE DE MR ET MRS SMITH

La famille Smith et leurs 3 enfants veulent nous rendre

visite au Tours JUG mais ils n’ont pas tous les même

contraintes de temps :

Si Mr Smith vient, sa femme vient aussi

Au moins un des deux enfants Matt et John viendront

Mrs Smith ou Tim viendront, mais pas les deux

Tim et John viendront, ou aucun des deux

Si Matt vient, alors John et son père viendront aussi



MR ET MRS SMITH : LES VARIABLES

String[] x_names = {"Mr Smith","Mrs Smith", "Matt", "John", "Tim"};

BoolVar[] x = VariableFactory.boolArray("x", 5, solver);

BoolVar MrSmith = x[0];

BoolVar MrsSmith = x[1];

BoolVar Matt = x[2];

BoolVar John = x[3];

BoolVar Tim = x[4];



0 ne vient pas au Tours JUG

1 vient au Tours JUG

35

MR ET MRS SMITH : LES CONTRAINTES

// Si Mr Smith vient, sa femme vient aussi.

solver.post( IntConstraintFactory.arithm( MrSmith, “-", MrsSmith, "<=", 0 ) );

// Au moins un des deux enfants Matt et John viendront.

solver.post( IntConstraintFactory.arithm( Matt, "+", John, ">=", 1 ) );

// Mrs Smith ou Tim viendront, mais pas les deux.

solver.post( IntConstraintFactory.arithm( MrsSmith, "+", Tim, "=", 1 ) );

// Tim et John viendront, ou aucun des deux.

solver.post( IntConstraintFactory.arithm( Tim, "=", John ) );

// Si Matt vient, alors John et son père viendront aussi.

BoolVar JohnAndMrSmith = VariableFactory.bool( "JohnAndMrSmith", solver );

solver.post( IntConstraintFactory.times( John, MrSmith, JohnAndMrSmith ) );

solver.post( IntConstraintFactory.arithm( Matt, "-", JohnAndMrSmith, "<=", 0 ) );



MR ET MRS SMITH : DERNIERS DÉTAILS

// On sette la stratégie de recherche

solver.set(IntStrategyFactory.firstFail_InDomainMin(x));

// On lance le processus de résolution

solver.findSolution();



MR ET MRS SMITH : PRETTY OUT

if (solver.isFeasible()) {

int num_sol = 0;

do {

System.out.print(”Ceux qui viendront au Tours JUG sont : ");

for (int i = 0; i < n; i++) {

if (x[i].getValue() == 1) {

System.out.print(x_names[i] + " ");

}

}

num_sol++;

} while (solver.nextSolution() == Boolean.TRUE);

System.out.println(”Il y a " + num_sol + " solution(s).");

} else {

System.out.println(”Pas de solution.");

} L A P R O G R A M M A T I O N P A R C O N T R A I N T E S A V E C


MR ET MRS SMITH : UNE SEULE SOLUTION

MrSmith = 0

MrsSmith = 0

Matt = 0

John = 1

Tim = 1

“Ceux qui viendront au Tours JUG sont : John Tim

Il y a : 1 solution(s).”



github.com/chocoteam/choco3



BLOGS

Jean-Charles Regin/Pierre Schaus: "CP is fun"

http://cp-is-fun.blogspot.com/

Jacob Feldman: "CP Standardization Blog"

http://cpstandard.wordpress.com/

Helmut Simonis: "CP Applications Blog"

http://hsimonis.wordpress.com/

Hakan Kjellerstrand: My Constraint Programming Blog

http://www.hakank.org/constraint_programming_blog/















MERCI !



Technology

La programmation par contraintes avec Choco3 (Java)