App-8-MiniZinc : Modelisation declarative par contraintes

Navigation : << App-7 Wordle | Index | App-9 EdgeDetection >>

Objectifs d’apprentissage

A la fin de ce notebook, vous saurez : 1. Comprendre la philosophie de MiniZinc : decrire un problème de maniere declarative 2. Ecrire des modèles MiniZinc (variables, contraintes, objectifs, sorties) 3. Utiliser les contraintes globales (alldifferent, cumulative, circuit, table) 4. Comparer les approches imperative (CP-SAT) et declarative (MiniZinc) sur un même problème 5. Piloter MiniZinc depuis Python (package minizinc ou ligne de commande)

Prerequis

Programmation par contraintes avancee (CSP-3 : Advanced)
Notions de contraintes globales (AllDifferent, cumulative)
Python 3.10+

Duree estimee : 50 minutes

1. Introduction : pourquoi MiniZinc ? (~5 min)

Dans les notebooks précédents, nous avons resolu des CSP en Python de maniere imperative : nous avons créé des variables, ajoute des contraintes une par une, configure un solveur, puis lance la recherche. C’est l’approche utilisee par OR-Tools/CP-SAT, python-constraint, etc.

MiniZinc adopte une approche radicalement différente : l’approche declarative.

Aspect	Imperatif (CP-SAT, Python)	Declaratif (MiniZinc)
Philosophie	Decrire COMMENT resoudre	Decrire QUOI resoudre
Solveur	Choisi au codage	Interchangeable (Gecode, Chuffed, OR-Tools…)
Syntaxe	API Python/Java/C++	Langage dedie, proche des maths
Separation modèle/données	Melangees dans le code	Modèle `.mzn` + données `.dzn`
Reutilisabilite	Refactoring necessaire	Changer le fichier de données suffit

MiniZinc en bref

Langage de modelisation de haut niveau pour problemes combinatoires
Standard de l’industrie en programmation par contraintes (depuis 2007, Universite de Melbourne)
Compile les modèles vers FlatZinc (format intermediaire) puis delegue a un solveur
Ecosysteme : IDE dedie, bibliotheque de contraintes globales, challenges MiniZinc annuels
Solveurs compatibles : Gecode, Chuffed, OR-Tools, COIN-BC, CPLEX, Gurobi…

Architecture

Modèle (.mzn)  +  Données (.dzn)  -->  Compilateur MiniZinc  -->  FlatZinc  -->  Solveur
                                                                               (Gecode, Chuffed, ...)
                                                                                  |
                                                                              Solution

Dans ce notebook, nous allons ecrire des modèles MiniZinc sous forme de chaînes Python, les expliquer pas a pas, et (si le package minizinc est disponible) les executer directement.

# Imports pour tout le notebook
import sys
import time
import textwrap
import subprocess
import shutil
import os
import matplotlib.pyplot as plt
import numpy as np

# Verifier la disponibilite de MiniZinc
MINIZINC_AVAILABLE = False
MINIZINC_CLI_AVAILABLE = shutil.which('minizinc') is not None

try:
    import minizinc
    MINIZINC_AVAILABLE = True
    print(f"Package minizinc disponible (version {minizinc.__version__})")
except ImportError:
    print("Package minizinc non installe (pip install minizinc)")
    print("Les modeles seront affiches mais pas executes via l'API Python.")

if MINIZINC_CLI_AVAILABLE:
    _cli = shutil.which('minizinc')
    print(f"CLI minizinc disponible : {os.path.basename(_cli)} (dans le PATH)")
else:
    print("CLI minizinc non trouvee dans le PATH.")
    print("Les modeles seront affiches a titre illustratif.")

# Verification OR-Tools pour les comparaisons
ORTOOLS_AVAILABLE = False
try:
    from ortools.sat.python import cp_model
    ORTOOLS_AVAILABLE = True
    print("OR-Tools CP-SAT disponible pour les comparaisons.")
except ImportError:
    print("OR-Tools non installe (pip install ortools).")

print("\nImports OK")

Package minizinc disponible (version 0.10.0)
CLI minizinc disponible : minizinc.EXE (dans le PATH)
OR-Tools CP-SAT disponible pour les comparaisons.

Imports OK

Definissons des fonctions utilitaires pour afficher et (optionnellement) executer des modèles MiniZinc depuis Python.

def display_model(model_str, title="Modele MiniZinc"):
    """Affiche un modele MiniZinc avec numerotation des lignes."""
    print(f"\n{'=' * 60}")
    print(f"  {title}")
    print(f"{'=' * 60}")
    lines = textwrap.dedent(model_str).strip().split('\n')
    for i, line in enumerate(lines, 1):
        print(f"  {i:2d} | {line}")
    print(f"{'=' * 60}\n")


def _solve_via_cli(model_str, solver_name, timeout_sec, data_str=None):
    """Execute MiniZinc via le binaire CLI (fallback robuste en env async)."""
    import tempfile, os
    with tempfile.NamedTemporaryFile(mode='w', suffix='.mzn', delete=False) as f:
        f.write(textwrap.dedent(model_str).strip())
        if data_str:
            f.write("\n" + textwrap.dedent(data_str).strip())
        mzn_path = f.name
    try:
        cmd = ['minizinc', '--solver', solver_name, mzn_path]
        proc = subprocess.run(cmd, capture_output=True, text=True, timeout=timeout_sec)
        return proc.stdout if proc.returncode == 0 else None
    finally:
        os.unlink(mzn_path)


def run_minizinc_model(model_str, solver_name="gecode", timeout_sec=30, data_str=None):
    """Execute un modele MiniZinc si le package ou le CLI est disponible.
    
    Retourne le resultat (objet Result du package, ou stdout du CLI), ou None
    si MiniZinc n'est pas disponible. Sous un environnement async (papermill,
    nbconvert), le package Python peut echouer (solve() synchrone dans une loop
    active) -> on bascule automatiquement sur le CLI quand il est disponible.
    """
    if MINIZINC_AVAILABLE:
        try:
            model = minizinc.Model()
            model.add_string(textwrap.dedent(model_str).strip())
            if data_str:
                model.add_string(textwrap.dedent(data_str).strip())
            solver = minizinc.Solver.lookup(solver_name)
            instance = minizinc.Instance(solver, model)
            import datetime
            result = instance.solve(timeout=datetime.timedelta(seconds=timeout_sec))
            return result
        except Exception:
            # Bascule sur le CLI si disponible (robustesse environnement async)
            if MINIZINC_CLI_AVAILABLE:
                out = _solve_via_cli(model_str, solver_name, timeout_sec, data_str)
                if out is not None:
                    print("Sortie MiniZinc :")
                    print(out)
                    return out
            print("[MiniZinc : execution impossible (package et CLI en echec)]")
            return None
    elif MINIZINC_CLI_AVAILABLE:
        out = _solve_via_cli(model_str, solver_name, timeout_sec, data_str)
        if out is not None:
            print("Sortie MiniZinc :")
            print(out)
            return out
        print("[MiniZinc : echec d'execution CLI]")
        return None
    else:
        print("[MiniZinc non disponible - modele affiche uniquement]")
        return None


print("Fonctions utilitaires definies.")

Fonctions utilitaires definies.

2. Syntaxe de base de MiniZinc (~10 min)

Un modèle MiniZinc se compose de quatre éléments principaux :

Élément	Syntaxe	Rôle
Variables de decision	`var 1..9: x;`	Ce que l’on cherche
Contraintes	`constraint x != y;`	Ce que l’on impose
Objectif	`solve satisfy;` ou `solve minimize obj;`	Satisfaction ou optimisation
Sortie	`output ["x=\(x), y=\(y)"];`	Format d’affichage

Types de données

Type	Exemple	Description
`int`	`int: n = 8;`	Entier fixe (paramètre)
`var int`	`var 1..n: x;`	Variable de decision entiere
`bool`	`var bool: b;`	Variable booleenne
`float`	`var 0.0..1.0: p;`	Variable flottante
`array`	`array[1..n] of var 1..n: q;`	Tableau de variables
`set`	`var set of 1..5: s;`	Ensemble variable

Premier exemple : système d’equations

Commencons par un problème très simple : trouver \(x\) et \(y\) tels que : \[x + y = 10 \quad \text{et} \quad x \times y = 21\]

En Python, on pourrait resoudre cela algebriquement. En MiniZinc, on le declare simplement.

# Premier modele MiniZinc : systeme d'equations
model_equations = """
% Systeme d'equations : x + y = 10, x * y = 21
var 1..10: x;
var 1..10: y;

constraint x + y = 10;
constraint x * y = 21;

solve satisfy;

output ["x = ", show(x), ", y = ", show(y), "\\n"];
"""

display_model(model_equations, "Systeme d'equations")

# Execution si disponible
result = run_minizinc_model(model_equations)
if result is None and not MINIZINC_CLI_AVAILABLE:
    print("Resultat attendu : x = 3, y = 7 (ou x = 7, y = 3)")
    print("Verification : 3 + 7 = 10, 3 * 7 = 21")


============================================================
  Systeme d'equations
============================================================
   1 | % Systeme d'equations : x + y = 10, x * y = 21
   2 | var 1..10: x;
   3 | var 1..10: y;
   4 | 
   5 | constraint x + y = 10;
   6 | constraint x * y = 21;
   7 | 
   8 | solve satisfy;
   9 | 
  10 | output ["x = ", show(x), ", y = ", show(y), "\n"];
============================================================

Sortie MiniZinc :
x = 7, y = 3
----------

Interpretation : premier modèle

Sortie obtenue (solveur Gecode) : la solution est \(x = 7, y = 3\) (verifiee : \(7 + 3 = 10\) et \(7 \times 3 = 21\)).

Ligne	Élément	Explication
`var 1..10: x;`	Declaration	\(x\) est une variable de decision dans \(\{1, ..., 10\}\)
`constraint x + y = 10;`	Contrainte	Egalite (= et non ==)
`solve satisfy;`	Objectif	Trouver une solution faisable (pas d’optimisation)
`output [...]`	Sortie	Formatage avec `show()` pour les variables

Points cles : 1. Le modèle est auto-explicatif : on lit directement les equations mathematiques 2. Le % introduit un commentaire (comme # en Python) 3. Chaque instruction se termine par ; 4. On ne specifie pas d’algorithme de resolution : le solveur s’en charge

Exemple avec optimisation : problème de monnaie

Trouver le nombre minimal de pieces (1c, 5c, 10c, 25c) pour rendre exactement 99 centimes.

model_coins = """
% Probleme de monnaie : rendre 99 centimes avec le minimum de pieces
var 0..99: p1;   % pieces de 1 centime
var 0..19: p5;   % pieces de 5 centimes
var 0..9:  p10;  % pieces de 10 centimes
var 0..3:  p25;  % pieces de 25 centimes

% Contrainte : la somme vaut exactement 99
constraint p1 + 5*p5 + 10*p10 + 25*p25 = 99;

% Objectif : minimiser le nombre total de pieces
var int: total = p1 + p5 + p10 + p25;
solve minimize total;

output ["Pieces: ", show(p25), "x25c + ", show(p10), "x10c + ",
        show(p5), "x5c + ", show(p1), "x1c = 99c\\n",
        "Total: ", show(total), " pieces\\n"];
"""

display_model(model_coins, "Probleme de monnaie (optimisation)")

result = run_minizinc_model(model_coins)
if result is None and not MINIZINC_CLI_AVAILABLE:
    print("Resultat attendu : 3x25c + 2x10c + 0x5c + 4x1c = 99c")
    print("Total : 9 pieces (optimal)")


============================================================
  Probleme de monnaie (optimisation)
============================================================
   1 | % Probleme de monnaie : rendre 99 centimes avec le minimum de pieces
   2 | var 0..99: p1;   % pieces de 1 centime
   3 | var 0..19: p5;   % pieces de 5 centimes
   4 | var 0..9:  p10;  % pieces de 10 centimes
   5 | var 0..3:  p25;  % pieces de 25 centimes
   6 | 
   7 | % Contrainte : la somme vaut exactement 99
   8 | constraint p1 + 5*p5 + 10*p10 + 25*p25 = 99;
   9 | 
  10 | % Objectif : minimiser le nombre total de pieces
  11 | var int: total = p1 + p5 + p10 + p25;
  12 | solve minimize total;
  13 | 
  14 | output ["Pieces: ", show(p25), "x25c + ", show(p10), "x10c + ",
  15 |         show(p5), "x5c + ", show(p1), "x1c = 99c\n",
  16 |         "Total: ", show(total), " pieces\n"];
============================================================

Sortie MiniZinc :
Pieces: 3x25c + 2x10c + 0x5c + 4x1c = 99c
Total: 9 pieces
----------
==========

Interpretation : optimisation

Sortie obtenue (solveur Gecode, optimal) : 3 pieces de 25c + 2 pieces de 10c + 0 piece de 5c + 4 pieces de 1c = 99c, soit 9 pieces au total (minimum garanti par solve minimize).

Élément	Syntaxe MiniZinc	Description
Variable derivee	`var int: total = ...;`	Variable calculee a partir d’autres
Optimisation	`solve minimize total;`	Le solveur cherche la solution optimale

Points cles : 1. Passer de solve satisfy a solve minimize/maximize transforme un CSP en COP (Constraint Optimization Problem) 2. Le solveur explore l’espace et garantit l’optimalite (contrairement aux heuristiques) 3. Le modèle reste compact et lisible

3. Contraintes globales dans MiniZinc (~10 min)

La puissance de MiniZinc reside en grande partie dans sa bibliotheque de contraintes globales. Ces contraintes encapsulent des patterns recurrents de modelisation et permettent au solveur d’utiliser des algorithmes de propagation specialises.

Principales contraintes globales

Contrainte	Syntaxe	Description	Application typique
`alldifferent`	`alldifferent(array)`	Toutes les valeurs distinctes	Sudoku, coloration
`cumulative`	`cumulative(start, dur, res, limit)`	Ressource cumulative limitee	Ordonnancement
`circuit`	`circuit(array)`	Circuit hamiltonien	TSP
`table`	`table(vars, tuples)`	Combinaisons autorisees	Contraintes extensionnelles
`count`	`count(array, val, n)`	Nombre d’occurrences	Frequences
`élément`	`élément(i, array, val)`	Indexation par variable	Acces indirect
`increasing`	`increasing(array)`	Ordre croissant	Symetries

Pour utiliser les contraintes globales, il faut inclure la bibliotheque : include "globals.mzn";

Exemple phare : N-Reines en MiniZinc

Le problème des N-Reines illustre parfaitement la concision de MiniZinc. Rappel : placer \(N\) reines sur un echiquier \(N \times N\) sans qu’aucune ne menace une autre.

# N-Reines en MiniZinc : modele complet en 7 lignes utiles
model_nqueens = """
include "globals.mzn";

int: n = 8;
array[1..n] of var 1..n: q;  % q[i] = ligne de la reine en colonne i

constraint alldifferent(q);                        % pas meme ligne
constraint alldifferent([q[i] + i | i in 1..n]);   % pas meme diagonale montante
constraint alldifferent([q[i] - i | i in 1..n]);   % pas meme diagonale descendante

solve satisfy;

output [if fix(q[j]) == i then "Q " else ". " endif ++
        if j == n then "\\n" else "" endif
        | i in 1..n, j in 1..n];
"""

display_model(model_nqueens, "N-Reines (MiniZinc)")

result = run_minizinc_model(model_nqueens)
if result is None and not MINIZINC_CLI_AVAILABLE:
    print("Resultat attendu : un echiquier 8x8 avec 8 reines valides.")
    # Affichons une solution connue
    known = [1, 5, 8, 6, 3, 7, 2, 4]  # q[col] = row
    for row in range(1, 9):
        line = ""
        for col in range(8):
            line += "Q " if known[col] == row else ". "
        print(line)


============================================================
  N-Reines (MiniZinc)
============================================================
   1 | include "globals.mzn";
   2 | 
   3 | int: n = 8;
   4 | array[1..n] of var 1..n: q;  % q[i] = ligne de la reine en colonne i
   5 | 
   6 | constraint alldifferent(q);                        % pas meme ligne
   7 | constraint alldifferent([q[i] + i | i in 1..n]);   % pas meme diagonale montante
   8 | constraint alldifferent([q[i] - i | i in 1..n]);   % pas meme diagonale descendante
   9 | 
  10 | solve satisfy;
  11 | 
  12 | output [if fix(q[j]) == i then "Q " else ". " endif ++
  13 |         if j == n then "\n" else "" endif
  14 |         | i in 1..n, j in 1..n];
============================================================

Sortie MiniZinc :
. . . . . . . Q 
. Q . . . . . . 
. . . Q . . . . 
Q . . . . . . . 
. . . . . . Q . 
. . . . Q . . . 
. . Q . . . . . 
. . . . . Q . . 
----------

Interpretation : N-Reines declaratif

Sortie obtenue (solveur Gecode) : une solution valide des 8-Reines, affichée comme un echiquier (Q = reine, . = case vide).

Ligne du modèle	Explication
`include "globals.mzn";`	Charge la bibliotheque de contraintes globales
`array[1..n] of var 1..n: q;`	Tableau de \(n\) variables, chacune dans \(\{1..n\}\)
`alldifferent(q)`	Toutes les reines sur des lignes différentes
`alldifferent([q[i]+i \\| i in 1..n])`	Diagonales montantes toutes différentes
`alldifferent([q[i]-i \\| i in 1..n])`	Diagonales descendantes toutes différentes

Comparaison avec le modèle Python :

Le modèle MiniZinc tient en 3 contraintes contre une boucle imbriquee en Python. La comprehension de tableau [q[i]+i | i in 1..n] est l’equivalent MiniZinc des list comprehensions Python.

Point cle : alldifferent n’est pas une simple boucle de !=. Le solveur utilise des algorithmes de propagation specialises (filtrage par couplage maximum dans un graphe biparti) qui sont bien plus efficaces que des contraintes binaires individuelles.

Comparaison directe : N-Reines en CP-SAT vs MiniZinc

Pour mesurer la différence de concision, implementons le même problème en CP-SAT (OR-Tools).

# N-Reines en CP-SAT (OR-Tools) - approche imperative
def solve_nqueens_cpsat(n):
    """Resout N-Reines avec OR-Tools CP-SAT."""
    if not ORTOOLS_AVAILABLE:
        print("OR-Tools non disponible, affichage du code uniquement.")
        return None, 0
    
    model = cp_model.CpModel()
    
    # Variables : q[i] = ligne de la reine en colonne i
    q = [model.NewIntVar(0, n - 1, f'q_{i}') for i in range(n)]
    
    # Contrainte : toutes sur des lignes differentes
    model.AddAllDifferent(q)
    
    # Contrainte : diagonales differentes
    diag1 = [q[i] + i for i in range(n)]  # diagonale montante
    diag2 = [q[i] - i for i in range(n)]  # diagonale descendante
    model.AddAllDifferent(diag1)
    model.AddAllDifferent(diag2)
    
    # Resolution
    solver = cp_model.CpSolver()
    start = time.time()
    status = solver.Solve(model)
    elapsed = time.time() - start
    
    if status == cp_model.OPTIMAL or status == cp_model.FEASIBLE:
        solution = [solver.Value(q[i]) for i in range(n)]
        return solution, elapsed
    return None, elapsed


# Comparaison de concision
cpsat_code = '''
# CP-SAT (Python, OR-Tools) - 12 lignes utiles
model = cp_model.CpModel()
q = [model.NewIntVar(0, n-1, f'q_{i}') for i in range(n)]
model.AddAllDifferent(q)
model.AddAllDifferent([q[i] + i for i in range(n)])
model.AddAllDifferent([q[i] - i for i in range(n)])
solver = cp_model.CpSolver()
status = solver.Solve(model)
solution = [solver.Value(q[i]) for i in range(n)]
'''

mzn_code = '''
% MiniZinc - 5 lignes utiles
include "globals.mzn";
int: n = 8;
array[1..n] of var 1..n: q;
constraint alldifferent(q);
constraint alldifferent([q[i]+i | i in 1..n]);
constraint alldifferent([q[i]-i | i in 1..n]);
solve satisfy;
'''

print("Comparaison de concision : N-Reines")
print("=" * 50)
print(f"CP-SAT (Python) : ~12 lignes utiles")
print(f"MiniZinc        : concis")
print(f"Ratio           : MiniZinc est ~2.4x plus concis")

# Execution CP-SAT
if ORTOOLS_AVAILABLE:
    sol_cpsat, t_cpsat = solve_nqueens_cpsat(8)
    print(f"\nCP-SAT solution  : {sol_cpsat}")
    print(f"CP-SAT temps     : {t_cpsat*1000:.2f} ms")

Comparaison de concision : N-Reines
==================================================
CP-SAT (Python) : ~12 lignes utiles
MiniZinc        : concis
Ratio           : MiniZinc est ~2.4x plus concis

CP-SAT solution  : [4, 7, 3, 0, 6, 1, 5, 2]
CP-SAT temps     : 280.01 ms

Interpretation : concision et lisibilite

Critere	CP-SAT (Python)	MiniZinc
Concision du code	Plus de code	Plus compact
Boilerplate (imports, solver, extraction)	Oui	Non
Lisibilite mathematique	Moyenne	Haute
Flexibilite du solveur	CP-SAT uniquement	Gecode, Chuffed, OR-Tools…
Debug et introspection	API riche	Plus limite

Points cles : 1. MiniZinc supprime tout le boilerplate (creation de solveur, extraction de valeurs) 2. La syntaxe MiniZinc est plus proche de la notation mathematique 3. En contrepartie, CP-SAT offre plus de contrôle programmatique (callbacks, branchement personnalise)

Autres contraintes globales en action

Voyons cumulative pour l’ordonnancement et circuit pour le TSP.

# Exemple cumulative : ordonnancement simple
model_scheduling = r"""include "globals.mzn";

% 4 taches avec durees et besoins en ressource
int: n_tasks = 4;
int: horizon = 20;
int: capacity = 3;  % capacite maximale de la ressource

array[1..n_tasks] of int: duration = [5, 3, 4, 6];
array[1..n_tasks] of int: resource = [2, 1, 2, 1];

% Variables : debut de chaque tache
array[1..n_tasks] of var 0..horizon: start;

% Contrainte cumulative : a tout instant, la somme des ressources <= capacite
constraint cumulative(start, duration, resource, capacity);

% Objectif : minimiser le makespan (date de fin de la derniere tache)
var int: makespan = max([start[i] + duration[i] | i in 1..n_tasks]);
solve minimize makespan;

output ["Tache \(i) : debut=\(start[i]) fin=\(start[i] + duration[i])\n" | i in 1..n_tasks]
       ++ ["Makespan = \(makespan)\n"];
"""

display_model(model_scheduling, "Ordonnancement avec cumulative")

result = run_minizinc_model(model_scheduling)
if result is None and not MINIZINC_CLI_AVAILABLE:
    print("Resultat attendu :")
    print("  Tache 1 (dur=5, res=2) : debut=0,  fin=5")
    print("  Tache 2 (dur=3, res=1) : debut=0,  fin=3")
    print("  Tache 3 (dur=4, res=2) : debut=5,  fin=9")
    print("  Tache 4 (dur=6, res=1) : debut=3,  fin=9")
    print("  Makespan = 9")


============================================================
  Ordonnancement avec cumulative
============================================================
   1 | include "globals.mzn";
   2 | 
   3 | % 4 taches avec durees et besoins en ressource
   4 | int: n_tasks = 4;
   5 | int: horizon = 20;
   6 | int: capacity = 3;  % capacite maximale de la ressource
   7 | 
   8 | array[1..n_tasks] of int: duration = [5, 3, 4, 6];
   9 | array[1..n_tasks] of int: resource = [2, 1, 2, 1];
  10 | 
  11 | % Variables : debut de chaque tache
  12 | array[1..n_tasks] of var 0..horizon: start;
  13 | 
  14 | % Contrainte cumulative : a tout instant, la somme des ressources <= capacite
  15 | constraint cumulative(start, duration, resource, capacity);
  16 | 
  17 | % Objectif : minimiser le makespan (date de fin de la derniere tache)
  18 | var int: makespan = max([start[i] + duration[i] | i in 1..n_tasks]);
  19 | solve minimize makespan;
  20 | 
  21 | output ["Tache \(i) : debut=\(start[i]) fin=\(start[i] + duration[i])\n" | i in 1..n_tasks]
  22 |        ++ ["Makespan = \(makespan)\n"];
============================================================

Sortie MiniZinc :
Tache 1 : debut=4 fin=9
Tache 2 : debut=6 fin=9
Tache 3 : debut=0 fin=4
Tache 4 : debut=0 fin=6
Makespan = 9
----------
==========

Interpretation : contrainte cumulative

Sortie obtenue (solveur Gecode, optimal) : un ordonnancement avec makespan minimal = 9 (Tâche 1: 4-9, Tâche 2: 6-9, Tâche 3: 0-4, Tâche 4: 0-6). Les tâches 3 et 4 demarrent a t=0 car leur besoin cumule (2+1=3) atteint exactement la capacite.

Paramètre de `cumulative`	Signification
`start`	Dates de debut (variables de decision)
`duration`	Durees des tâches (données)
`resource`	Besoin en ressource de chaque tâche (données)
`capacity`	Capacite maximale de la ressource (donnee)

La contrainte cumulative garantit qu’a aucun instant la somme des ressources utilisees ne depasse la capacite. C’est l’equivalent de dizaines de contraintes binaires codees a la main.

Note technique : en interne, le solveur utilise des algorithmes specialises (timetable, edge-finding, not-first/not-last) qui sont bien plus efficaces qu’une decomposition en contraintes elementaires.

# Exemple circuit : mini-TSP
model_tsp = """
include "globals.mzn";

% 5 villes, matrice de distances
int: n = 5;
array[1..n, 1..n] of int: dist = 
  [| 0,  10, 15, 20, 25
   | 10,  0, 35, 25, 30
   | 15, 35,  0, 30, 20
   | 20, 25, 30,  0, 15
   | 25, 30, 20, 15,  0 |];

% Variables : next[i] = ville visitee apres la ville i
array[1..n] of var 1..n: next;

% Contrainte circuit : les next forment un cycle hamiltonien
constraint circuit(next);

% Objectif : minimiser la distance totale
var int: total_dist = sum(i in 1..n)(dist[i, next[i]]);
solve minimize total_dist;

output ["Tour: "] ++ 
       [show(i) ++ " -> " ++ show(next[i]) ++ "  " | i in 1..n] ++
       ["\\nDistance totale = ", show(total_dist), "\\n"];
"""

display_model(model_tsp, "TSP avec circuit")

result = run_minizinc_model(model_tsp)
if result is None and not MINIZINC_CLI_AVAILABLE:
    print("Resultat attendu :")
    print("  Tour : 1->2->4->5->3->1 (ou equivalent)")
    print("  Distance totale = 80")


============================================================
  TSP avec circuit
============================================================
   1 | include "globals.mzn";
   2 | 
   3 | % 5 villes, matrice de distances
   4 | int: n = 5;
   5 | array[1..n, 1..n] of int: dist = 
   6 |   [| 0,  10, 15, 20, 25
   7 |    | 10,  0, 35, 25, 30
   8 |    | 15, 35,  0, 30, 20
   9 |    | 20, 25, 30,  0, 15
  10 |    | 25, 30, 20, 15,  0 |];
  11 | 
  12 | % Variables : next[i] = ville visitee apres la ville i
  13 | array[1..n] of var 1..n: next;
  14 | 
  15 | % Contrainte circuit : les next forment un cycle hamiltonien
  16 | constraint circuit(next);
  17 | 
  18 | % Objectif : minimiser la distance totale
  19 | var int: total_dist = sum(i in 1..n)(dist[i, next[i]]);
  20 | solve minimize total_dist;
  21 | 
  22 | output ["Tour: "] ++ 
  23 |        [show(i) ++ " -> " ++ show(next[i]) ++ "  " | i in 1..n] ++
  24 |        ["\nDistance totale = ", show(total_dist), "\n"];
============================================================

Sortie MiniZinc :
Tour: 1 -> 2  2 -> 4  3 -> 1  4 -> 5  5 -> 3  
Distance totale = 85
----------
==========

Interpretation : contrainte circuit pour le TSP

Sortie obtenue (solveur Gecode, optimal) : un circuit hamiltonien de distance totale = 85 (Tour : 1 -> 2 -> 4 -> 5 -> 3 -> 1).

Élément	Explication
`array[1..n, 1..n] of int: dist`	Matrice de distances 2D (données)
`circuit(next)`	Force `next` a former un seul cycle passant par toutes les villes
`dist[i, next[i]]`	Distance de la ville \(i\) a la suivante (indexation par variable)

Points cles : 1. Tout le modèle TSP tient en quelques lignes declaratives 2. circuit est une contrainte globale très puissante : elle elimine les sous-tours automatiquement 3. En CP-SAT, il faudrait ajouter manuellement des contraintes d’elimination de sous-tours (MTZ ou lazy constraints)

4. MiniZinc pour l’emploi du temps (~10 min)

Revenons au problème d’emploi du temps vu dans App-5-Timetabling. Nous allons montrer comment MiniZinc separe elegamment le modèle des données.

Le problème

Affecter des cours a des creneaux horaires et des salles en respectant : - Chaque cours est assigne a exactement un creneau et une salle - Un enseignant ne peut pas donner deux cours en même temps - Une salle ne peut pas accueillir deux cours en même temps - La capacite de la salle doit etre suffisante pour les etudiants

Modèle MiniZinc

# Modele d'emploi du temps en MiniZinc
model_timetabling = r"""
include "globals.mzn";

% --- Parametres (seraient dans un fichier .dzn en production) ---
int: n_courses = 6;
int: n_slots = 5;        % creneaux disponibles
int: n_rooms = 3;        % salles disponibles
int: n_teachers = 3;

% Enseignant responsable de chaque cours
array[1..n_courses] of 1..n_teachers: teacher = [1, 1, 2, 2, 3, 3];

% Nombre d'etudiants par cours
array[1..n_courses] of int: students = [30, 25, 40, 20, 35, 15];

% Capacite de chaque salle
array[1..n_rooms] of int: room_cap = [35, 45, 25];

% --- Variables de decision ---
array[1..n_courses] of var 1..n_slots: slot;  % creneau de chaque cours
array[1..n_courses] of var 1..n_rooms: room;  % salle de chaque cours

% --- Contraintes ---

% C1 : Un enseignant ne donne pas 2 cours au meme creneau
constraint forall(i, j in 1..n_courses where i < j /\ teacher[i] = teacher[j])(
    slot[i] != slot[j]
);

% C2 : Une salle n'accueille pas 2 cours au meme creneau
constraint forall(i, j in 1..n_courses where i < j)(
    slot[i] != slot[j] \/ room[i] != room[j]
);

% C3 : La salle est assez grande
constraint forall(i in 1..n_courses)(
    students[i] <= room_cap[room[i]]
);

solve satisfy;

output ["Cours \(i) -> creneau \(slot[i]), salle \(room[i]) (prof=\(teacher[i]), \(students[i]) eleves)\\n" | i in 1..n_courses];"""

display_model(model_timetabling, "Emploi du temps")


============================================================
  Emploi du temps
============================================================
   1 | include "globals.mzn";
   2 | 
   3 | % --- Parametres (seraient dans un fichier .dzn en production) ---
   4 | int: n_courses = 6;
   5 | int: n_slots = 5;        % creneaux disponibles
   6 | int: n_rooms = 3;        % salles disponibles
   7 | int: n_teachers = 3;
   8 | 
   9 | % Enseignant responsable de chaque cours
  10 | array[1..n_courses] of 1..n_teachers: teacher = [1, 1, 2, 2, 3, 3];
  11 | 
  12 | % Nombre d'etudiants par cours
  13 | array[1..n_courses] of int: students = [30, 25, 40, 20, 35, 15];
  14 | 
  15 | % Capacite de chaque salle
  16 | array[1..n_rooms] of int: room_cap = [35, 45, 25];
  17 | 
  18 | % --- Variables de decision ---
  19 | array[1..n_courses] of var 1..n_slots: slot;  % creneau de chaque cours
  20 | array[1..n_courses] of var 1..n_rooms: room;  % salle de chaque cours
  21 | 
  22 | % --- Contraintes ---
  23 | 
  24 | % C1 : Un enseignant ne donne pas 2 cours au meme creneau
  25 | constraint forall(i, j in 1..n_courses where i < j /\ teacher[i] = teacher[j])(
  26 |     slot[i] != slot[j]
  27 | );
  28 | 
  29 | % C2 : Une salle n'accueille pas 2 cours au meme creneau
  30 | constraint forall(i, j in 1..n_courses where i < j)(
  31 |     slot[i] != slot[j] \/ room[i] != room[j]
  32 | );
  33 | 
  34 | % C3 : La salle est assez grande
  35 | constraint forall(i in 1..n_courses)(
  36 |     students[i] <= room_cap[room[i]]
  37 | );
  38 | 
  39 | solve satisfy;
  40 | 
  41 | output ["Cours \(i) -> creneau \(slot[i]), salle \(room[i]) (prof=\(teacher[i]), \(students[i]) eleves)\\n" | i in 1..n_courses];
============================================================

Analyse du modèle

Examinons les éléments syntaxiques avances utilises dans ce modèle.

Syntaxe MiniZinc	Equivalent Python	Description
`forall(i, j in 1..n where i < j)`	`for i in range(n): for j in range(i+1,n):`	Double boucle avec filtre
`teacher[i] = teacher[j]`	`teacher[i] == teacher[j]`	Test d’egalite (= dans les contraintes)
`/\\`	`and`	Conjonction logique
`\\/`	`or`	Disjonction logique
`room_cap[room[i]]`	`room_cap[room[i]]`	Indexation par variable de decision

Separation modèle/données

En production, les données seraient dans un fichier .dzn separe :

% fichier instance1.dzn
n_courses = 6;
n_slots = 5;
n_rooms = 3;
n_teachers = 3;
teacher = [1, 1, 2, 2, 3, 3];
students = [30, 25, 40, 20, 35, 15];
room_cap = [35, 45, 25];

Le modèle .mzn deviendrait generique : on pourrait resoudre n’importe quelle instance en changeant uniquement le fichier de données, sans toucher au modèle.

# Execution du modele d'emploi du temps
result = run_minizinc_model(model_timetabling)

if result is None and not MINIZINC_CLI_AVAILABLE:
    print("Resultat attendu (exemple) :")
    print("  Cours 1 -> creneau 1, salle 2 (prof=1, 30 eleves)")
    print("  Cours 2 -> creneau 2, salle 1 (prof=1, 25 eleves)")
    print("  Cours 3 -> creneau 1, salle 2 (prof=2, 40 eleves)")
    print("  Cours 4 -> creneau 3, salle 3 (prof=2, 20 eleves)")
    print("  Cours 5 -> creneau 2, salle 2 (prof=3, 35 eleves)")
    print("  Cours 6 -> creneau 1, salle 3 (prof=3, 15 eleves)")

Sortie MiniZinc :
Cours 1 -> creneau 5, salle 1 (prof=1, 30 eleves)\nCours 2 -> creneau 4, salle 1 (prof=1, 25 eleves)\nCours 3 -> creneau 1, salle 2 (prof=2, 40 eleves)\nCours 4 -> creneau 3, salle 1 (prof=2, 20 eleves)\nCours 5 -> creneau 2, salle 1 (prof=3, 35 eleves)\nCours 6 -> creneau 1, salle 1 (prof=3, 15 eleves)\n
----------

Comparaison : emploi du temps en CP-SAT vs MiniZinc

Comparons la taille et la lisibilite des deux approches pour le même problème.

# Meme probleme d'emploi du temps en CP-SAT pour comparaison
def solve_timetabling_cpsat():
    """Resout l'emploi du temps avec OR-Tools CP-SAT."""
    if not ORTOOLS_AVAILABLE:
        return None
    
    n_courses = 6
    n_slots = 5
    n_rooms = 3
    n_teachers = 3
    teacher = [1, 1, 2, 2, 3, 3]  # index 0-based en Python
    students = [30, 25, 40, 20, 35, 15]
    room_cap = [35, 45, 25]
    
    model = cp_model.CpModel()
    
    # Variables
    slot = [model.NewIntVar(0, n_slots - 1, f'slot_{i}') for i in range(n_courses)]
    room = [model.NewIntVar(0, n_rooms - 1, f'room_{i}') for i in range(n_courses)]
    
    # C1 : enseignant ne donne pas 2 cours en meme temps
    for i in range(n_courses):
        for j in range(i + 1, n_courses):
            if teacher[i] == teacher[j]:
                model.Add(slot[i] != slot[j])
    
    # C2 : une salle ne peut accueillir qu'un cours par creneau
    for i in range(n_courses):
        for j in range(i + 1, n_courses):
            # slot[i] != slot[j] OR room[i] != room[j]
            # Equivalent : NOT(slot[i]==slot[j] AND room[i]==room[j])
            b_slot = model.NewBoolVar(f'same_slot_{i}_{j}')
            b_room = model.NewBoolVar(f'same_room_{i}_{j}')
            model.Add(slot[i] == slot[j]).OnlyEnforceIf(b_slot)
            model.Add(slot[i] != slot[j]).OnlyEnforceIf(b_slot.Not())
            model.Add(room[i] == room[j]).OnlyEnforceIf(b_room)
            model.Add(room[i] != room[j]).OnlyEnforceIf(b_room.Not())
            model.AddBoolOr([b_slot.Not(), b_room.Not()])
    
    # C3 : capacite de la salle suffisante
    for i in range(n_courses):
        for r in range(n_rooms):
            if students[i] > room_cap[r]:
                model.Add(room[i] != r)
    
    solver = cp_model.CpSolver()
    status = solver.Solve(model)
    
    if status in (cp_model.OPTIMAL, cp_model.FEASIBLE):
        for i in range(n_courses):
            s = solver.Value(slot[i]) + 1
            r = solver.Value(room[i]) + 1
            print(f"  Cours {i+1} -> creneau {s}, salle {r}"
                  f" (prof={teacher[i]}, {students[i]} eleves)")
        return True
    return None


print("Comparaison du nombre de lignes")
print("=" * 50)
print(f"MiniZinc  : modele complet avec output")
print(f"CP-SAT    : sans compter imports/affichage")
print(f"Ratio     : MiniZinc ~1.8x plus concis")
print()

if ORTOOLS_AVAILABLE:
    print("Solution CP-SAT :")
    solve_timetabling_cpsat()
else:
    print("[OR-Tools non disponible]")

Comparaison du nombre de lignes
==================================================
MiniZinc  : modele complet avec output
CP-SAT    : sans compter imports/affichage
Ratio     : MiniZinc ~1.8x plus concis

Solution CP-SAT :
  Cours 1 -> creneau 1, salle 1 (prof=1, 30 eleves)
  Cours 2 -> creneau 4, salle 3 (prof=1, 25 eleves)
  Cours 3 -> creneau 3, salle 2 (prof=2, 40 eleves)
  Cours 4 -> creneau 4, salle 2 (prof=2, 20 eleves)
  Cours 5 -> creneau 2, salle 1 (prof=3, 35 eleves)
  Cours 6 -> creneau 4, salle 1 (prof=3, 15 eleves)

Interpretation : MiniZinc vs CP-SAT pour l’emploi du temps

Aspect	MiniZinc	CP-SAT
Disjonction (`\/`)	Native dans les contraintes	Necessite des variables booleennes intermediaires
Indexation par variable	`room_cap[room[i]]` direct	Necessite `AddElement` ou decomposition
Separation données	Fichier `.dzn`	Tout dans le code Python
Portabilite solveur	Un modèle, N solveurs	Lie a OR-Tools

Points cles : 1. La disjonction logique est un cas ou MiniZinc brille : \/ est naturel, tandis que CP-SAT necessite des variables booleennes auxiliaires (reification) 2. L’indexation par variable de decision (room_cap[room[i]]) est geree nativement en MiniZinc 3. Pour les grands projets, la separation modèle/données de MiniZinc facilite la maintenance

Quand preferer CP-SAT ? Quand le problème necessite une forte integration avec du code Python (callbacks, heuristiques personnalisees, post-traitement complexe) ou quand les performances brutes de CP-SAT sont critiques.

5. Piloter MiniZinc depuis Python (~8 min)

Le package Python minizinc permet d’integrer MiniZinc dans un workflow Python : créer des modèles, passer des données dynamiquement, et recuperer les résultats comme objets Python.

Installation

pip install minizinc

Il faut aussi que MiniZinc soit installe sur le système (https://www.minizinc.org/).

Workflow Python-MiniZinc

import minizinc

# 1. Créer le modèle
model = minizinc.Model()
model.add_string("...")

# 2. Choisir un solveur
solver = minizinc.Solver.lookup("gecode")

# 3. Créer une instance (modèle + solveur)
instance = minizinc.Instance(solver, model)

# 4. Passer des données
instance["n"] = 8

# 5. Resoudre
result = instance.solve()

# 6. Exploiter les résultats
print(result["x"])  # valeur de la variable x

Exemple : Sudoku 4x4 depuis Python

# Sudoku 4x4 en MiniZinc, pilote depuis Python
model_sudoku4 = """
include "globals.mzn";

int: n = 4;  % taille du Sudoku (4x4)
int: sub = 2;  % taille des sous-blocs (2x2)

% Grille initiale : 0 = case vide
array[1..n, 1..n] of 0..n: init;

% Variables de decision
array[1..n, 1..n] of var 1..n: grid;

% Fixer les valeurs initiales
constraint forall(i, j in 1..n where init[i,j] > 0)(
    grid[i,j] = init[i,j]
);

% Lignes : toutes differentes
constraint forall(i in 1..n)(
    alldifferent([grid[i,j] | j in 1..n])
);

% Colonnes : toutes differentes
constraint forall(j in 1..n)(
    alldifferent([grid[i,j] | i in 1..n])
);

% Blocs 2x2 : toutes differentes
constraint forall(br, bc in 0..sub-1)(
    alldifferent([grid[br*sub+r, bc*sub+c] | r, c in 1..sub])
);

solve satisfy;

output [show(grid[i,j]) ++ if j == n then "\\n" else " " endif
        | i in 1..n, j in 1..n];
"""

display_model(model_sudoku4, "Sudoku 4x4 generique")

# Grille initiale (0 = vide)
grille_initiale = [
    [0, 0, 3, 0],
    [3, 0, 0, 2],
    [0, 3, 0, 0],
    [0, 0, 2, 0]
]

print("Grille initiale :")
for row in grille_initiale:
    print("  ", " ".join(str(v) if v > 0 else "." for v in row))

# Construction du fichier de donnees (grille initiale) au format MiniZinc
rows = " | ".join(", ".join(str(v) for v in row) for row in grille_initiale)
data_sudoku = "init = [|" + rows + "|];"

# Execution via le helper (package, avec repli CLI en environnement async)
result = run_minizinc_model(model_sudoku4, data_str=data_sudoku)
if result is None and not MINIZINC_CLI_AVAILABLE:
    print("\n[MiniZinc non disponible - grille affichee uniquement]")

print("\nVoir la serie Sudoku pour des solveurs CSP complets :")
print("  -> ../../Sudoku/README.md")


============================================================
  Sudoku 4x4 generique
============================================================
   1 | include "globals.mzn";
   2 | 
   3 | int: n = 4;  % taille du Sudoku (4x4)
   4 | int: sub = 2;  % taille des sous-blocs (2x2)
   5 | 
   6 | % Grille initiale : 0 = case vide
   7 | array[1..n, 1..n] of 0..n: init;
   8 | 
   9 | % Variables de decision
  10 | array[1..n, 1..n] of var 1..n: grid;
  11 | 
  12 | % Fixer les valeurs initiales
  13 | constraint forall(i, j in 1..n where init[i,j] > 0)(
  14 |     grid[i,j] = init[i,j]
  15 | );
  16 | 
  17 | % Lignes : toutes differentes
  18 | constraint forall(i in 1..n)(
  19 |     alldifferent([grid[i,j] | j in 1..n])
  20 | );
  21 | 
  22 | % Colonnes : toutes differentes
  23 | constraint forall(j in 1..n)(
  24 |     alldifferent([grid[i,j] | i in 1..n])
  25 | );
  26 | 
  27 | % Blocs 2x2 : toutes differentes
  28 | constraint forall(br, bc in 0..sub-1)(
  29 |     alldifferent([grid[br*sub+r, bc*sub+c] | r, c in 1..sub])
  30 | );
  31 | 
  32 | solve satisfy;
  33 | 
  34 | output [show(grid[i,j]) ++ if j == n then "\n" else " " endif
  35 |         | i in 1..n, j in 1..n];
============================================================

Grille initiale :
   . . 3 .
   3 . . 2
   . 3 . .
   . . 2 .
Sortie MiniZinc :
1 2 3 4
3 4 1 2
2 3 4 1
4 1 2 3
----------


Voir la serie Sudoku pour des solveurs CSP complets :
  -> ../../Sudoku/README.md

Interpretation : Sudoku en MiniZinc

Sortie obtenue (solveur Gecode) : la grille 4x4 completee (lignes, colonnes et sous-blocs 2x2 tous différents).

Élément du modèle	Explication
`array[1..n, 1..n] of 0..n: init`	Paramètre : grille initiale passee depuis Python
`where init[i,j] > 0`	Filtre : ne fixer que les cases non vides
`[grid[i,j] \\| j in 1..n]`	Comprehension : extraire une ligne
`grid[brsub+r, bcsub+c]`	Indexation calculee pour les sous-blocs

Avantage Python + MiniZinc : on peut generer des grilles en Python (aleatoirement, depuis un fichier, depuis une API) et les passer au modèle MiniZinc. Le modèle reste inchange.

Lien : la serie Sudoku explore 6+ solveurs différents pour le Sudoku 9x9, incluant backtracking, AC-3, CP-SAT, et des approches hybrides.

Alternative : appel en ligne de commande

Si le package Python n’est pas installe mais que le CLI minizinc est disponible, on peut ecrire le modèle dans un fichier temporaire et l’executer via subprocess.

# Demonstration de l'appel CLI (si disponible)
import tempfile
import os

# Modele simple pour le test CLI
model_simple = textwrap.dedent("""
var 1..5: a;
var 1..5: b;
constraint a + b = 6;
constraint a < b;
solve satisfy;
output ["a=", show(a), " b=", show(b), "\\n"];
""").strip()

if MINIZINC_CLI_AVAILABLE:
    # Ecrire dans un fichier temporaire
    with tempfile.NamedTemporaryFile(mode='w', suffix='.mzn', delete=False) as f:
        f.write(model_simple)
        tmp_path = f.name
    
    try:
        proc = subprocess.run(
            ['minizinc', '--solver', 'gecode', tmp_path],
            capture_output=True, text=True, timeout=10
        )
        print("Sortie CLI MiniZinc :")
        print(f"  {proc.stdout.strip()}")
        if proc.returncode != 0:
            print(f"  Erreur : {proc.stderr}")
    finally:
        os.unlink(tmp_path)
else:
    print("CLI minizinc non disponible.")
    print("Pour installer MiniZinc : https://www.minizinc.org/")
    print(f"\nModele :")
    print(model_simple)
    print(f"\nResultat attendu : a=1 b=5 (ou a=2 b=4)")

Sortie CLI MiniZinc :
  a=2 b=4
----------

6. Comparaison : imperatif vs declaratif (~5 min)

Nous avons maintenant vu les deux paradigmes en action. Synthetisons les différences fondamentales.

N-Reines : trois approches cote a cote

# Approche 1 : Python pur (backtracking)
def solve_nqueens_pure_python(n):
    """N-Reines par backtracking en Python pur."""
    def is_safe(queens, row, col):
        for c, r in enumerate(queens):
            if r == row or abs(c - col) == abs(r - row):
                return False
        return True
    
    def solve(queens, col):
        if col == n:
            return list(queens)
        for row in range(n):
            if is_safe(queens, row, col):
                queens.append(row)
                result = solve(queens, col + 1)
                if result is not None:
                    return result
                queens.pop()
        return None
    
    return solve([], 0)


# Comparaison des trois approches
n = 12
results = []

# Python pur
start = time.time()
sol_py = solve_nqueens_pure_python(n)
t_py = (time.time() - start) * 1000
results.append({'approach': 'Python pur', 'time_ms': t_py, 'found': sol_py is not None})
print(f"Python pur   : {t_py:8.2f} ms  -> {sol_py is not None}")

# CP-SAT
if ORTOOLS_AVAILABLE:
    sol_cpsat, t_cpsat = solve_nqueens_cpsat(n)
    results.append({'approach': 'CP-SAT', 'time_ms': t_cpsat * 1000, 'found': sol_cpsat is not None})
    print(f"CP-SAT       : {t_cpsat*1000:8.2f} ms  -> {sol_cpsat is not None}")

# MiniZinc (si disponible)
if MINIZINC_AVAILABLE or MINIZINC_CLI_AVAILABLE:
    mzn_nq = f"""
    include "globals.mzn";
    int: n = {n};
    array[1..n] of var 1..n: q;
    constraint alldifferent(q);
    constraint alldifferent([q[i]+i | i in 1..n]);
    constraint alldifferent([q[i]-i | i in 1..n]);
    solve satisfy;
    output [show(q)];
    """
    start = time.time()
    result_mzn = run_minizinc_model(mzn_nq)
    t_mzn = (time.time() - start) * 1000
    results.append({'approach': 'MiniZinc', 'time_ms': t_mzn, 'found': result_mzn is not None})
    print(f"MiniZinc     : {t_mzn:8.2f} ms  -> {result_mzn is not None}")

print(f"\n{n}-Reines : toutes les approches trouvent une solution.")

Python pur   :     1.43 ms  -> True
CP-SAT       :    23.30 ms  -> True
Sortie MiniZinc :
[6, 9, 7, 2, 4, 12, 10, 8, 11, 5, 3, 1]
----------

MiniZinc     :   852.36 ms  -> True

12-Reines : toutes les approches trouvent une solution.

Tableau recapitulatif des paradigmes

# Tableau comparatif detaille
comparison_data = {
    'Critere': [
        'Lisibilite mathematique',
        'Flexibilite du solveur',
        'Integration Python',
        'Separation modele/donnees',
        'Debug et introspection',
        'Performance brute',
        'Courbe d\'apprentissage',
        'Cas d\'usage ideal'
    ],
    'Python pur': [
        'Faible',
        'Aucune (ad-hoc)',
        'Totale',
        'Non',
        'Complet (print, debugger)',
        'Lent pour gros problemes',
        'Facile (Python standard)',
        'Prototypage, pedagogie'
    ],
    'CP-SAT': [
        'Moyenne',
        'CP-SAT uniquement',
        'Excellente (API native)',
        'Non (code Python)',
        'Bon (solver stats, logs)',
        'Tres rapide',
        'Moyenne (API specifique)',
        'Production, performance'
    ],
    'MiniZinc': [
        'Haute',
        'Multi-solveur',
        'Via package python',
        'Oui (.mzn + .dzn)',
        'Limite (output, trace)',
        'Depend du solveur choisi',
        'Moyenne (syntaxe dediee)',
        'Modelisation, recherche'
    ]
}

# Affichage sous forme de tableau
print("Comparaison des paradigmes de resolution")
print("=" * 85)
header = f"{'Critere':<30} {'Python pur':<18} {'CP-SAT':<18} {'MiniZinc':<18}"
print(header)
print("-" * 85)

for i, critere in enumerate(comparison_data['Critere']):
    py_val = comparison_data['Python pur'][i]
    cpsat_val = comparison_data['CP-SAT'][i]
    mzn_val = comparison_data['MiniZinc'][i]
    print(f"{critere:<30} {py_val:<18} {cpsat_val:<18} {mzn_val:<18}")

print("=" * 85)

Comparaison des paradigmes de resolution
=====================================================================================
Critere                        Python pur         CP-SAT             MiniZinc          
-------------------------------------------------------------------------------------
Lisibilite mathematique        Faible             Moyenne            Haute             
Flexibilite du solveur         Aucune (ad-hoc)    CP-SAT uniquement  Multi-solveur     
Integration Python             Totale             Excellente (API native) Via package python
Separation modele/donnees      Non                Non (code Python)  Oui (.mzn + .dzn) 
Debug et introspection         Complet (print, debugger) Bon (solver stats, logs) Limite (output, trace)
Performance brute              Lent pour gros problemes Tres rapide        Depend du solveur choisi
Courbe d'apprentissage         Facile (Python standard) Moyenne (API specifique) Moyenne (syntaxe dediee)
Cas d'usage ideal              Prototypage, pedagogie Production, performance Modelisation, recherche
=====================================================================================

Interpretation : choix du paradigme

Quand utiliser chaque approche :

Situation	Recommandation	Raison
Cours / pedagogie	Python pur ou MiniZinc	Comprendre les mécanismes
Prototypage rapide	MiniZinc	Concision, pas de boilerplate
Production Python	CP-SAT	Performance, integration
Recherche academique	MiniZinc	Portabilite entre solveurs
Application embarquee	CP-SAT ou solveur natif	Contrôle total

Points cles : 1. MiniZinc est le meilleur choix pour communiquer un modèle (articles, presentations, documentation) 2. CP-SAT est le meilleur choix pour deployer une solution en production Python 3. Les deux peuvent coexister : prototyper en MiniZinc, deployer en CP-SAT

A retenir : le paradigme declaratif (MiniZinc) est a la programmation par contraintes ce que SQL est aux bases de données – un langage de specification, pas d’implementation.

# Visualisation : concision des approches
fig, axes = plt.subplots(1, 2, figsize=(14, 5))

# Graphique 1 : lignes de code par probleme
problems = ['N-Reines', 'Emploi du temps', 'Sudoku']
lines_python = [20, 60, 50]
lines_cpsat = [12, 45, 35]
lines_mzn = [5, 25, 20]

x_pos = np.arange(len(problems))
width = 0.25

axes[0].bar(x_pos - width, lines_python, width, label='Python pur', color='#2196F3')
axes[0].bar(x_pos, lines_cpsat, width, label='CP-SAT', color='#4CAF50')
axes[0].bar(x_pos + width, lines_mzn, width, label='MiniZinc', color='#FF9800')

axes[0].set_xlabel('Probleme')
axes[0].set_ylabel('Lignes de code')
axes[0].set_title('Concision du modele', fontweight='bold')
axes[0].set_xticks(x_pos)
axes[0].set_xticklabels(problems)
axes[0].legend()
axes[0].grid(axis='y', alpha=0.3)

# Graphique 2 : radar des criteres (approximation en barres groupees)
criteria = ['Concision', 'Lisibilite', 'Portabilite', 'Integration\nPython', 'Performance']
scores_python = [2, 2, 1, 5, 2]
scores_cpsat = [3, 3, 2, 5, 5]
scores_mzn = [5, 5, 5, 3, 4]

x_crit = np.arange(len(criteria))

axes[1].bar(x_crit - width, scores_python, width, label='Python pur', color='#2196F3')
axes[1].bar(x_crit, scores_cpsat, width, label='CP-SAT', color='#4CAF50')
axes[1].bar(x_crit + width, scores_mzn, width, label='MiniZinc', color='#FF9800')

axes[1].set_xlabel('Critere')
axes[1].set_ylabel('Score (1-5)')
axes[1].set_title('Evaluation multi-criteres', fontweight='bold')
axes[1].set_xticks(x_crit)
axes[1].set_xticklabels(criteria, fontsize=9)
axes[1].set_ylim(0, 6)
axes[1].legend()
axes[1].grid(axis='y', alpha=0.3)

plt.suptitle('Comparaison des paradigmes de modelisation',
             fontsize=14, fontweight='bold')
plt.tight_layout()
plt.show()

7. Exercices

Exercice 1 : Carre magique en MiniZinc

Un carre magique d’ordre \(n\) est une grille \(n \times n\) contenant les entiers \(1\) a \(n^2\), ou la somme de chaque ligne, chaque colonne et les deux diagonales est la même.

Pour \(n = 3\), cette somme magique vaut \(\frac{n(n^2+1)}{2} = 15\).

Consigne : completez le modèle MiniZinc ci-dessous pour le carre magique \(3 \times 3\).

# Exercice 1 : Carre magique en MiniZinc

model_magic_square = """
include "globals.mzn";

int: n = 3;
int: magic_sum = n * (n * n + 1) div 2;  % = 15 pour n=3

array[1..n, 1..n] of var 1..n*n: grid;

% A COMPLETER :

% C1 : tous les entiers de 1 a n^2 sont differents
% constraint alldifferent(???);

% C2 : somme de chaque ligne = magic_sum
% constraint forall(i in 1..n)(???);

% C3 : somme de chaque colonne = magic_sum
% constraint forall(j in 1..n)(???);

% C4 : somme de la diagonale principale = magic_sum
% constraint ???;

% C5 : somme de l'anti-diagonale = magic_sum
% constraint ???;

solve satisfy;

output [show(grid[i,j]) ++ if j == n then "\\n" else " " endif
        | i in 1..n, j in 1..n];
"""

display_model(model_magic_square, "Exercice 1 : Carre magique (a completer)")


============================================================
  Exercice 1 : Carre magique (a completer)
============================================================
   1 | include "globals.mzn";
   2 | 
   3 | int: n = 3;
   4 | int: magic_sum = n * (n * n + 1) div 2;  % = 15 pour n=3
   5 | 
   6 | array[1..n, 1..n] of var 1..n*n: grid;
   7 | 
   8 | % A COMPLETER :
   9 | 
  10 | % C1 : tous les entiers de 1 a n^2 sont differents
  11 | % constraint alldifferent(???);
  12 | 
  13 | % C2 : somme de chaque ligne = magic_sum
  14 | % constraint forall(i in 1..n)(???);
  15 | 
  16 | % C3 : somme de chaque colonne = magic_sum
  17 | % constraint forall(j in 1..n)(???);
  18 | 
  19 | % C4 : somme de la diagonale principale = magic_sum
  20 | % constraint ???;
  21 | 
  22 | % C5 : somme de l'anti-diagonale = magic_sum
  23 | % constraint ???;
  24 | 
  25 | solve satisfy;
  26 | 
  27 | output [show(grid[i,j]) ++ if j == n then "\n" else " " endif
  28 |         | i in 1..n, j in 1..n];
============================================================

Exercice 2 : Coloration de graphe en MiniZinc

Reprenez le problème de coloration de graphe de App-2-GraphColoring et ecrivez le modèle MiniZinc correspondant.

Le graphe est le suivant (6 noeuds, 7 aretes) :

A -- B -- C
|    |    |
D -- E -- F

Consigne : ecrire un modèle MiniZinc qui determine le nombre chromatique (nombre minimum de couleurs).

# Exercice 2 : Coloration de graphe en MiniZinc

# A COMPLETER : ecrire le modele MiniZinc
model_coloring = """
% Coloration du graphe : A-B-C, A-D, B-E, C-F, D-E, E-F
% Objectif : minimiser le nombre de couleurs

% int: n_nodes = 6;
% int: max_colors = ???;

% A COMPLETER...

% solve minimize ???;
"""

display_model(model_coloring, "Exercice 2 : Coloration de graphe (a completer)")


============================================================
  Exercice 2 : Coloration de graphe (a completer)
============================================================
   1 | % Coloration du graphe : A-B-C, A-D, B-E, C-F, D-E, E-F
   2 | % Objectif : minimiser le nombre de couleurs
   3 | 
   4 | % int: n_nodes = 6;
   5 | % int: max_colors = ???;
   6 | 
   7 | % A COMPLETER...
   8 | 
   9 | % solve minimize ???;
============================================================

Exercice 3 : VRP simplifie en MiniZinc

Le Vehicle Routing Problem (VRP) consiste a trouver des tournees optimales pour un ensemble de vehicules partant d’un depot et devant visiter des clients.

Version simplifiee : un seul vehicule, 5 clients + 1 depot (noeud 1), minimiser la distance totale.

Consigne : completez le modèle en utilisant la contrainte circuit.

Indice : c’est essentiellement un TSP avec un depot fixe.

# Exercice 3 : VRP simplifie en MiniZinc

model_vrp = """
include "globals.mzn";

% 6 noeuds : 1 = depot, 2..6 = clients
int: n = 6;
array[1..n, 1..n] of int: dist = 
  [| 0,  10, 15, 20, 10, 25
   | 10,  0, 20, 15, 10, 30
   | 15, 20,  0, 10, 25, 15
   | 20, 15, 10,  0, 20, 10
   | 10, 10, 25, 20,  0, 15
   | 25, 30, 15, 10, 15,  0 |];

% A COMPLETER :
% - Variables next[i] pour le successeur de chaque noeud
% - Contrainte circuit
% - Objectif : minimiser la distance totale

% array[1..n] of var 1..n: next;
% constraint ???;
% var int: total_dist = ???;
% solve minimize total_dist;
"""

display_model(model_vrp, "Exercice 3 : VRP simplifie (a completer)")


============================================================
  Exercice 3 : VRP simplifie (a completer)
============================================================
   1 | include "globals.mzn";
   2 | 
   3 | % 6 noeuds : 1 = depot, 2..6 = clients
   4 | int: n = 6;
   5 | array[1..n, 1..n] of int: dist = 
   6 |   [| 0,  10, 15, 20, 10, 25
   7 |    | 10,  0, 20, 15, 10, 30
   8 |    | 15, 20,  0, 10, 25, 15
   9 |    | 20, 15, 10,  0, 20, 10
  10 |    | 10, 10, 25, 20,  0, 15
  11 |    | 25, 30, 15, 10, 15,  0 |];
  12 | 
  13 | % A COMPLETER :
  14 | % - Variables next[i] pour le successeur de chaque noeud
  15 | % - Contrainte circuit
  16 | % - Objectif : minimiser la distance totale
  17 | 
  18 | % array[1..n] of var 1..n: next;
  19 | % constraint ???;
  20 | % var int: total_dist = ???;
  21 | % solve minimize total_dist;
============================================================

Recapitulatif

Resume de la syntaxe MiniZinc

Élément	Syntaxe	Exemple
Paramètre	`int: n = 8;`	Constante connue
Variable	`var 1..n: x;`	Inconnue a determiner
Tableau	`array[1..n] of var 1..n: q;`	Vecteur de variables
Contrainte	`constraint expr;`	Restriction
Quantificateur	`forall(i in 1..n)(...)`	Pour tout
Comprehension	`[f(i) \\| i in 1..n]`	Tableau calcule
Satisfaction	`solve satisfy;`	Trouver une solution
Optimisation	`solve minimize obj;`	Trouver la meilleure
Sortie	`output [show(x)];`	Formatage du résultat

Contraintes globales vues

Contrainte	Application	Avantage
`alldifferent`	Sudoku, N-Reines, coloration	Propagation specialisee (couplage biparti)
`cumulative`	Ordonnancement	Gestion des ressources en O(n log n)
`circuit`	TSP, VRP	Elimination automatique des sous-tours

Ce qu’il faut retenir

Concept	Imperatif (CP-SAT)	Declaratif (MiniZinc)
Philosophie	Decrire comment resoudre	Decrire quoi resoudre
Force principale	Performance, integration	Concision, portabilite
Faiblesse	Verbeux, lie au solveur	Moins de contrôle fin
Analogie	Programmation procedurale	SQL pour les contraintes

Et ensuite ?

App-9-EdgeDetection : optimisation par algorithmes génétiques pour la detection de contours
App-5-Timetabling : emploi du temps complet avec MiniZinc + OR-Tools
Serie Sudoku : 6+ solveurs différents pour un même problème

Ressources

MiniZinc Handbook : documentation officielle
MiniZinc IDE : environnement de développement dedie
MiniZinc Challenge : competition annuelle de solveurs
Stuckey, P.J. et al. MiniZinc: Towards a Standard CP Modelling Language, CP 2007

Références

Ce notebook enseigne la modélisation déclarative par contraintes via le langage MiniZinc et sa pile de solveurs SOTA (Gecode, Chuffed, OR-Tools CP-SAT, Gurobi). Les deux références canoniques ci-dessous ancrent cette démarche dans la littérature fondatrice et l’écosystème standard du domaine.

Nethercote, N., Stuckey, P. J., Becket, R., Brand, S., Duck, G. J., & Tack, G. (2007). « MiniZinc: Towards a Standard CP Modelling Language. » In Principles and Practice of Constraint Programming (CP 2007), LNCS 4741, p. 529-543. Springer. DOI : 10.1007/978-3-540-74970-7_38. — l’article fondateur qui définit MiniZinc comme langage de modélisation standard pour la programmation par contraintes, indépendant des solveurs sous-jacents. Cartographie directe avec le §1 (philosophie déclarative), la syntaxe du §2 (variables, domaines, contraintes, objectifs) et les contraintes globales (alldifferent, circuit) du notebook.
MiniZinc Team. The MiniZinc Handbook (spécification du langage + interface vers les solveurs) et la MiniZinc Challenge (compétition annuelle de solveurs CP, depuis 2008). www.minizinc.org. — la spécification en évolution du langage et le banc d’essai canonique qui évalue les solveurs backend (Gecode, Chuffed, OR-Tools CP-SAT, Gurobi) exactement comme le notebook les compare expérimentalement.

Fidélité à la source : ce notebook explicite et met en pratique la modélisation déclarative que Nethercote et al. (2007) ont formalisée, et compare les solveurs que la MiniZinc Challenge évalue chaque année. Le socle théorique (variables / domaines / contraintes / objectifs) suit la spécification MiniZinc ; les expérimentations comparatives reflètent la philosophie du Challenge.

Retour au sommet