Ecole Nationale Supérieure de
Génie Mathématiques et
Modélisation
Introduction à Choco Solver
Optimisation combinatoire avec
Java
Demandé par:
Dr SANNI Moustapha
Présenté par :
SOGNOMBO Bernard
CLASSE : GMM3
Année académique : 2024-2025
1 Introduction à Choco Solver
• Choco Solver est une bibliothèque Java open-source.
• Utilisée pour résoudre des problèmes d’optimisation et de satisfaction de
contraintes (CSP).
• Applications : Planification de tâches, Optimisation de réseaux,Résolution
de puzzles ou jeux,Problèmes de transports ou d’allocation de ressources
etc.
2 Installation de Choco Solver (Maven)
Via Maven : ajoutez le dépôt et la dépendance Chovo Solver dans le
fichier pom.xml de votre projet.
<dependency>
<groupId>org.choco-solver</groupId>
<artifactId>choco-solver</artifactId>
<version>4.10.14</version>
</dependency>
3 Installation de Choco Solver (Gradle)
Via Gradle : ajoutez cette ligne dans le fichier build.gradle.
implementation ’org.choco-solver:choco-solver:4.10.14’
4 Installation manuelle (sans Maven/Gradle)
1. Téléchargement du jar:
• Rendez-vous sur le site officiel de Choco Solver ou le dépôt Maven
Central.
• Téléchargez le fichier JAR de la dernière version stable.
2. Ajout dans votre projet:
• Copiez le fichier .jar dans le dossier lib de votre projet (ou créez-le
si nécessaire).
• Configurez votre IDE pour inclure ce fichier JAR dans le classpath :
• Dans Eclipse : Clic droit sur le projet → Build Path → Configure
Build Path → Add External JARs.
• Dans IntelliJ : Ouvrez le projet → File → Project Structure →
Libraries → Add JARs or Directories.
2
5 Exemple : Problème des N Reines
Objectif : Placer N reines sur un échiquier N × N sans qu’elles ne s’attaquent.
Contraintes :
• Une reine par ligne et par colonne.
• Aucune reine sur la même diagonale.
6 Code Java : Problème des N Reines
import java.util.Scanner;
import org.chocosolver.solver.Model;
import org.chocosolver.solver.Solution;
import org.chocosolver.solver.variables.IntVar;
public class NQueens {
public static void main(String[] args) {
Scanner sc =new Scanner(System.in);
// Entrer le nombre de reines
System.out.println("Entrer la taille de l’échiquier: ");
int n = sc.nextInt(); // Taille de l’échiquier
Model model = new Model(n+"N Queens Problem");
3
// Variables représentant les positions des reines
IntVar[] queens=new IntVar[n];
for(int q=0;q<n;q++) {
queens[q] = model.intVar("Q_ " +q, 1, n);
}
// Contraintes
model.allDifferent(queens).post(); // Chaque reine est dans
une colonne différente
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j < n; j++) {
model.arithm(queens[i], "!=", queens[j],"+" , j -
i).post(); // Pas de diagonale montante
model.arithm(queens[i], "!=", queens[j] ,"-",
j-i).post(); // Pas de diagonale descendante
}
Solver solver =model.getSolver();
// Afficher les statistiques
solver.showStatistics();
// Stratégie de recherche par défaut
solver.setSearch(Search.domOverWDegRefSearch(queens));
// Toutes les solutions du problème
int solutionCount=0;
while (solver.solve()) {
solutionCount++;
System.out.println("Solution " + solutionCount + ": ");
for (int i = 0; i < n; i++) {
System.out.println("Reine_" + (i+1) + " en position :
" + queens[i].getValue());
}
System.out.println(); // Passe àla solution suivante
}
//Nombre de solutions
if(solutionCount==0) {
System.out.println("Pas de solution trouvée !");
}
else {
System.out.println("Nombre total de solutions : " +
solutionCount);
7 Exemple 2 : Problème d’emplacement d’entrepôt
Dans le problème d’emplacement d’entrepôt (WLP), une entreprise envisage
d’ouvrir des entrepôts à certains emplacements candidats afin d’approvisionner
ses magasins existants:
4
• Chaque entrepôt possible a le même coût d’entretien et une capacité désig-
nant le nombre maximum de magasins qu’il peut approvisionner.
• Chaque magasin doit être approvisionner par exactement un entrepôt ou-
vert. Le coût d’approvisionnement d’un magasin dépend de l’entrepôt
.
• L’objectif est de déterminer quels entrepôts ouvrir, et lesquels de ces en-
trepôts doivent aproviosionner les différents magasins,de telle sorte que la
somme des coûts d’entretien et d’approvisionnement soit minimisée.
Variables:
• Une variable booléenne openi par entrepôt i est nécessaire, défini true si
l’entrepôt correspondant est ouvert,f alse sinon ∀ i ∈ [1, 5]openi = {0, 1}
• Une variable entière supplierj par magasin j est nécessaire , il indique quel
entrepôt le fournit. ∀ j ∈ [1, 10], supplierj = [1, 5]
• Une variable entière costj par magasin j est également nécessaire , il stocke
le coût d’approvisionnement par un entrepôt (la portée est déduite de la
matrice P ). ∀j ∈ [1, 10], costj = [1, 96]‘
• Une variable entière totcost = [1, +∞[.
Contraintes:
• Si un entrepôt i approvisionne un magasin j alors l’entrepôt est ouvert:
∀j ∈ [1, 10], opensupplierj = 1. Ici supplierj définit l’index du tableau open
à évaluer à 1 . Il s’agit d’un élément codé avec une contrainte d’élément.
• si un entrepôt iapprovisionne un magasin j , cela est lié à un coût spé-
cifique: ∀ j ∈ [1, 10], Pj,supplierj = costj . Ici encore , une contrainte
d’élément est utilisée pour lier le fournisseur et la matrice des coûts d’approvisionnement
au coût d’approvisionnement d’un magasin.
• Le nombre maximum de magasins qu’un entrepôt peux approvisionner est
limité à Ki :
P10
∀ i ∈ [1, 5], j=1 (supplierj == i) = occi
∀ i ∈ [1, 5], occi ≤ Ki
∀ [1, 5], occi ≥ openi
La première contrainte compte le nombre d’occurrences de la valeur i dans le
tableau fournisseur et stocke le résultat dans la variable occi . Cette variable
est alors contrainte d’être inférieure ou égale à Ki , pour garantir que la capacité
est satisfaite mais aussi être supérieure ou égale à openi pour une meilleure
propagation.
5
• Il faut alors maintenir le coût de la mission , y compris le frais fixes et les
frais d’approvisionnement:
5
X 10
X
totcost = 30 × openi + costj
i=1 j=1
Objectif:
L’objectif n’est pas simplement de trouver une solution mais une solution qui
minimise totcost .
8 Conclusion
Choco solver est un outil puissant et flexible pour résourdre une large gamme
de problèmes d’optimisation et de satisfaction de contraintes, allant des défits
académiques aux applications industrielles.Grâce à sa conception modulaire et
à son intégration native avec java,il offre:
• Une facilité d’expression des contraintes complexes .
• Une efficacité dans la résolution grâce à des algorithmes optimisés.
• Une adaptabilité aux besoins spécifiques, comme le coloriage de graphes,la
planification,ou encore l’ordonnancement.
References
[1] Choco Solver: Documentation officielle.
Disponible sur https://choco-solver.org
[2] Cours Contraintes : Introduction à la programmation par Contraintes.
Auteur: Michel RUEHER , Date: 27 Novembre 2010
