Un guide d'OptaPlanner

1. Présentation d'OptaPlanner

Dans ce didacticiel, nous examinons un solveur de satisfaction de contraintes Java appelé OptaPlanner.

OptaPlanner résout les problèmes de planification en utilisant une suite d'algorithmes avec une configuration minimale.

Bien qu'une compréhension des algorithmes puisse fournir des détails utiles, le cadre effectuant le travail acharné pour nous.

2. Dépendance de Maven

Tout d'abord, nous allons ajouter une dépendance Maven pour OptaPlanner:

 org.optaplanner optaplanner-core 7.9.0.Final  

Nous localisons la version la plus récente d'OptaPlanner à partir du référentiel Maven Central.

3. Classe de problème / solution

Pour résoudre un problème, nous avons certainement besoin d'un exemple spécifique.

L'horaire des conférences est un exemple approprié en raison de la difficulté d'équilibrer les ressources telles que les salles, le temps et les enseignants.

3.1. Cours

CourseSchedule contient une combinaison de nos variables de problème et d'entités de planification, c'est donc la classe de solution. En conséquence, nous utilisons plusieurs annotations pour le configurer.

Examinons de plus près chacun séparément:

@PlanningSolution public class CourseSchedule { private List roomList; private List periodList; private List lectureList; private HardSoftScore score;

L' annotation PlanningSolution indique à OptaPlanner que cette classe contient les données pour englober une solution.

OptaPlanner attend ces composants minimaux: l'entité de planification, les faits du problème et un score.

3.2. Conférence

Lecture, un POJO, ressemble à:

@PlanningEntity public class Lecture { public Integer roomNumber; public Integer period; public String teacher; @PlanningVariable( valueRangeProviderRefs = {"availablePeriods"}) public Integer getPeriod() { return period; } @PlanningVariable( valueRangeProviderRefs = {"availableRooms"}) public Integer getRoomNumber() { return roomNumber; } }

Nous utilisons la classe Lecture comme entité de planification, nous ajoutons donc une autre annotation sur le getter dans CourseSchedule :

@PlanningEntityCollectionProperty public List getLectureList() { return lectureList; }

Notre entité de planification contient les contraintes qui sont définies.

L' annotation PlanningVariable et les annotations valueRangeProviderRef lient les contraintes aux faits du problème.

Ces valeurs de contrainte seront notées ultérieurement dans toutes les entités de planification.

3.3. Faits sur le problème

Les variables roomNumber et period agissent comme des contraintes de la même manière.

OptaPlanner note les solutions en fonction de la logique utilisant ces variables. Nous ajoutons des annotations aux deux méthodes getter :

@ValueRangeProvider(id = "availableRooms") @ProblemFactCollectionProperty public List getRoomList() { return roomList; } @ValueRangeProvider(id = "availablePeriods") @ProblemFactCollectionProperty public List getPeriodList() { return periodList; } 

Ces listes sont toutes les valeurs possibles utilisées dans les champs Lecture .

OptaPlanner les remplit dans toutes les solutions de l'espace de recherche.

Enfin, il définit ensuite un score pour chacune des solutions, nous avons donc besoin d'un champ pour stocker le score:

@PlanningScore public HardSoftScore getScore() { return score; }

Sans score, OptaPlanner ne peut pas trouver la solution optimale d'où l'importance soulignée plus tôt.

4. Notation

Contrairement à ce que nous avons examiné jusqu'à présent, la classe de notation nécessite plus de code personnalisé.

En effet, le calculateur de score est spécifique au problème et au modèle de domaine.

4.1. Java personnalisé

Nous utilisons un simple calcul de score pour résoudre ce problème (même si cela ne semble pas être le cas):

public class ScoreCalculator implements EasyScoreCalculator { @Override public Score calculateScore(CourseSchedule courseSchedule) { int hardScore = 0; int softScore = 0; Set occupiedRooms = new HashSet(); for(Lecture lecture : courseSchedule.getLectureList()) { String roomInUse = lecture.getPeriod() .toString() + ":" + lecture.getRoomNumber().toString(); if(occupiedRooms.contains(roomInUse)){ hardScore += -1; } else { occupiedRooms.add(roomInUse); } } return HardSoftScore.valueOf(hardScore, softScore); } }

Si nous examinons de plus près le code ci-dessus, les parties importantes deviennent plus claires. Nous calculons un score dans la boucle car la liste contient des combinaisons spécifiques non uniques de pièces et de périodes.

Le HashSet est utilisé pour enregistrer une clé unique (chaîne) afin que nous puissions pénaliser les conférences en double dans la même salle et période.

En conséquence, nous recevons des ensembles uniques de chambres et de périodes.

4.2. Bave

Les fichiers Drools nous donnent un moyen rapide de modifier les règles d'application aux fichiers. Bien que la syntaxe puisse parfois prêter à confusion, le fichier Drools peut être un moyen de gérer la logique en dehors des classes compilées.

Notre règle pour empêcher les entrées nulles ressemble à ceci:

global HardSoftScoreHolder scoreHolder; rule "noNullRoomPeriod" when Lecture( roomNumber == null ); Lecture( period == null ); then scoreHolder.addHardConstraintMatch(kcontext, -1); end

5. Configuration du solveur

Un autre fichier de configuration nécessaire, nous avons besoin d'un fichier XML pour configurer le solveur.

5.1. Fichier de configuration XML

    org.baeldung.optaplanner.ScoreCalculator    10   

En raison de nos annotations dans la classe CourseSchedule , nous utilisons l' élément scanAnnotatedClasses ici pour analyser les fichiers sur le chemin de classe .

Le contenu de l'élément scoreDirectorFactory définit notre classe ScoreCalculator pour contenir notre logique de notation.

Lorsque nous voulons utiliser un fichier Drools, nous remplaçons le contenu de l'élément par:

courseScheduleScoreRules.drl

Our final setting is the termination element. Rather than search endlessly for an optimized solution that may never exist, this setting will stop the search after a time limit.

Ten seconds is more than enough for most problems.

6. Testing

We configured our solution, solver and problem classes. Let's test it!

6.1. Setting up Our Test

First, we do some setup:

SolverFactory solverFactory = SolverFactory .createFromXmlResource("courseScheduleSolverConfiguration.xml"); solver = solverFactory.buildSolver(); unsolvedCourseSchedule = new CourseSchedule();

Second, we populate data into the planning entity collection and problem fact List objects.

6.2. Test Execution and Verification

Finally, we test it by calling solve.

CourseSchedule solvedCourseSchedule = solver.solve(unsolvedCourseSchedule); assertNotNull(solvedCourseSchedule.getScore()); assertEquals(-4, solvedCourseSchedule.getScore().getHardScore());

We check that the solvedCourseSchedule has a score which tells us that we have the “optimal” solution.

For a bonus, we create a print method that will display our optimized solution:

public void printCourseSchedule() { lectureList.stream() .map(c -> "Lecture in Room " + c.getRoomNumber().toString() + " during Period " + c.getPeriod().toString()) .forEach(k -> logger.info(k)); }

This method displays:

Lecture in Room 1 during Period 1 Lecture in Room 2 during Period 1 Lecture in Room 1 during Period 2 Lecture in Room 2 during Period 2 Lecture in Room 1 during Period 3 Lecture in Room 2 during Period 3 Lecture in Room 1 during Period 1 Lecture in Room 1 during Period 1 Lecture in Room 1 during Period 1 Lecture in Room 1 during Period 1

Notice how the last three entries are repeating. This happens because there is no optimal solution to our problem. We chose three periods, two classrooms and ten lectures.

There are only six possible lectures due to these fixed resources. At the very least this answer shows the user that there are not enough rooms or periods to contain all the lectures.

7. Extra Features

Our example for OptaPlanner we created was a simple one, however, the framework has added features for more diverse use cases. We may want to implement or alter our algorithm for optimization and then specify the framework to use it.

Due to recent improvements in Java's multi-threading capabilities, OptaPlanner also gives developers the ability to use multiple implementations of multi-threading such as fork and join, incremental solving and multitenancy.

Reportez-vous à la documentation pour plus d'informations.

8. Conclusion

Le framework OptaPlanner fournit aux développeurs un outil puissant pour résoudre les problèmes de satisfaction des contraintes tels que la planification et l'allocation des ressources.

OptaPlanner offre une utilisation minimale des ressources JVM ainsi qu'une intégration avec Jakarta EE. L'auteur continue de prendre en charge le framework, et Red Hat l'a ajouté dans le cadre de sa suite de gestion des règles métier.

Comme toujours, le code peut être trouvé sur Github.