Refactoring d'un composant logiciel (3/3)

Important : Consultez les modalités de rendu.

La stratégie alwaysReduce

Travail à faire : Nous allons maintenant construire une stratégie (alwaysReduce) qui consiste à réduire le problème à chaque étape. Contrairement aux autres stratégies, cette dernière est susceptible de modifier plusieurs domaines à chaque étape. Un travail de sauvegarde/restauration est donc nécessaire.
  • Prévoir une classe Backup qui se charge d'une sauvegarde et de l'opération de restauration associée.
  • Il faut sans doute modifier l'interface IStrategy pour prendre en compte cette spécificité (void backup() et void restore()).
  • Proposer une implémentation de cette stratégie et vérifier sur un problème que cette stratégie est bien plus efficace.
Travail à faire : Pour tirer partie de cette stratégie et de la réduction de la contrainte diff, vous pouvez tester la résolution du problème des N-Reines avec le code ci-dessous (92 solutions pour 8 reines).
public ISolver makeQueens(int n) {
    ISolver solver = new Solver();
    var queens = new Variable[n];
    // diagonals
    var diagonals1 = new Variable[n];
    var diagonals2 = new Variable[n];
    for (int i = 0; i < n; i++) {
        queens[i] = solver.newVar("R" + i, 1, n);
        diagonals1[i] = solver.expression(queens[i], "+", i);
        diagonals2[i] = solver.expression(queens[i], "-", i);
    }
    solver.addAllDiffRelation(queens);
    solver.addAllDiffRelation(diagonals1);
    solver.addAllDiffRelation(diagonals2);
    solver.alwaysReduceStrategy();
    solver.setVerbose(false);
    return solver;
}

Un problème d'optimisation

Cet exercice est optionnel mais très intéressant !

Nous allons maintenant changer le fonctionnement de notre solveur en ajoutant la minimisation de la valeur d'une variable. Par exemple, pour le problème ci-dessous, la plus petite valeur de COST est 330 pour X=70 et Y=30.

0 <= X, X <= 70,
0 <= Y, Y <= 70,
X + Y = 100,
COST = (3 * X) + (4 * Y)
Travail à faire : Nous allons traiter cette nouvelle fonctionnalité comme une nouvelle stratégie :
  • Préparer une classe OptimizationStrategy qui hérite de AlwaysReduceStrategy.
  • Cette stratégie va conserver la valeur courante minimale de la variable à minimiser (variable qu'elle doit donc connaître).
  • A chaque solution, cette valeur est éventuellement mise à jour.
  • A chaque réduction, cette stratégie va réduire le domaine de la variable pour ne pas autoriser des valeurs plus grandes que celles déjà trouvées. Ainsi, à chaque étape, nous améliorons notre objectif.
  • Amélioration : Comment faire pour ne plus renvoyer les solutions non-optimales ?
Travail à faire : Considérons le problème d'affectation ci-dessous. Nous avons des tâches à faire et des agents pour les faire. Chaque tâche est faite par un seul agent qui ne peut faire qu'au plus une tâche. Cette affectation entraîne un coût qui est détaillé dans le tableau ci-dessous.
           Agent 1   Agent 2   Agent 3   Agent 4
tâche 1 :    8         5         9         9
tâche 2 :    4         2         6         4
tâche 3 :    7         3         7         8
Problème : quelle est l'affection des tâches aux agents qui minimise le coût ? Aidez-vous de la méthode ci-dessous afin de construire un test unitaire qui va trouver la solution de ce problème.
public ISolver buildAssignmentProblem(int[][] costs) {
    var solver = new Solver();
    int nbTasks = costs.length;
    int nbAgents = costs[0].length;
    Variable[][] matrix = new Variable[nbTasks][nbAgents];
    
    // create nbTasks * nbAgents variables 0..1
    for (int t = 0; t < nbTasks; t++) {
        for (int a = 0; a < nbAgents; a++) {
            matrix[t][a] = solver.newVar("T" + t + "A" + a, 0, 1);
        }
    }
    
    // each task have one agent
    var zero = solver.newConstant(0);
    for (int t = 0; t < nbTasks; t++) {
        var sum = zero;
        for (int a = 0; a < nbAgents; a++) {
            sum = solver.expression(sum, "+", matrix[t][a]);
        }
        solver.addRelation(sum, "=", 1);
    }
    
    // each agent have at most one task
    for (int a = 0; a < nbAgents; a++) {
        var sum = zero;
        for (int t = 0; t < nbTasks; t++) {
            sum = solver.expression(sum, "+", matrix[t][a]);
        }
        solver.addRelation(sum, "<=", 1);
    }
    
    // compute cost
    var cost = zero;
    for (int t = 0; t < nbTasks; t++) {
        for (int a = 0; a < nbAgents; a++) {
            cost = solver.expression(cost, "+", matrix[t][a], "*", costs[t][a]);
        }
    }
    var varCost = solver.newVar("cost");
    solver.addRelation(cost, "=", varCost);
    solver.setVerbose(false);
        solver.alwaysReduceStrategy();
    // Code a adapter pour minimiser cost
    ....
    ....
    return solver;
}

Modalités de rendu via etulab

  • Le rendu de votre projet Solver est à faire pour le jeudi 23 octobre 2025 à 23h59. Il faudra que le dépôt git sur etulab soit à jour et que Jean-Luc Massat (identifiant massat) soit membre du projet avec des droits au moins égal à reporter.
  • L'ajout de membre se fait via manage / members dans le menu de votre projet sur etulab, puis en cliquant sur le bouton invite members.
  • Important : Vous devrez déclarer votre projet dans un questionnaire prévu sur Ametice.
  • Votre projet devra contenir à sa racine un fichier README.md contenant les informations sur ses membres et les emprunts réalisés. Le format du fichier devra être le suivant :
# Solver

## Membres du projet

- NOM Prénom du premier membre
- NOM Prénom du deuxième membre (si applicable)

## Description des emprunts

- Utilisation de ChatGPT pour les classes : `Main.java`, ...
- ...