This is the second day of my participation in Gwen Challenge

Contents summary

This chapter is the first introduction to OptaPlanner, a Demo similar to Java’s HelloWorld. For the “black on a red background” part of this article, keep this concept in mind and we’ll cover it in more detail in a later chapter.

OptaPlanner introduction

OptaPlanner is a lightweight, embeddable constraint satisfaction engine for solving planning problems that cleverly combines scores to compare each solution, with the highest score as the best solution. OptaPlanner itself supports a variety of algorithms, has high scalability and usability, a relatively active community environment abroad, and stable version iteration. There is no point in talking more. Here is the video introduction for you to understand OptaPlanner intuitively (the subtitles were translated by myself, please forgive me for being inaccurate).

OptaPlanner video introduction

What problems are you going to solve?

Today we are going to optimize a school schedule for high school students and teachers.

We will use the OptaPlanner algorithm to automatically assign courses to the corresponding classrooms and classrooms, and follow the rules of hard and soft constraints as follows: Hard constraints

  • One room can have up to one class at a time.
  • A teacher can teach up to one class at a time.
  • A student can take up to one class at a time.

Soft constraints

  • A teacher likes to teach every lesson in one room.
  • A teacher likes to teach consecutive lessons and doesn’t like gaps between lessons.

Mathematically, school scheduling is a NP-hard problem. Simply using an exhaustive algorithm to iterate over all possible combinations would take millions of years, even on a supercomputer, for a small data set. Fortunately, ai constraint solvers like OptaPlanner have advanced algorithms that can provide a near-optimal solution in a reasonable amount of time.

The preparatory work

JDK, MAVEN and editor:

  • JDK 8 or later
  • Maven 3.2 + or Gradle4 +
  • An IDE, such as IntelliJ IDEA, VSCode or Eclipse

Project creation and Maven configuration

To initialize an application with IDEA:

  • Spring Web (spring-boot-starter-web)

MAVEN configuration:


      
<project xmlns="http://maven.apache.org/POM/4.0.0" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="http://maven.apache.org/POM/4.0.0 http://maven.apache.org/xsd/maven-4.0.0.xsd">
    <modelVersion>4.0.0</modelVersion>
    <parent>
        <groupId>org.springframework.boot</groupId>
        <artifactId>spring-boot-starter-parent</artifactId>
        <version>{version-org-spring-framework-boot}</version>
    </parent>

    <groupId>com.example</groupId>
    <artifactId>constraint-solving-ai-optaplanner</artifactId>
    <version>0.1.0 from - the SNAPSHOT</version>
    <name>Constraint Solving AI with OptaPlanner</name>
    <description>A Spring Boot OptaPlanner example to generate a school timetable.</description>

    <properties>
        <java.version>1.8</java.version>
    </properties>

    <dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>
        <dependency>
            <groupId>org.optaplanner</groupId>
            <artifactId>optaplanner-spring-boot-starter</artifactId>
        </dependency>

        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
            <exclusions>
                <exclusion>
                    <groupId>org.junit.vintage</groupId>
                    <artifactId>junit-vintage-engine</artifactId>
                </exclusion>
            </exclusions>
        </dependency>
    </dependencies>

    <dependencyManagement>
        <dependencies>
            <dependency>
                <groupId>org.optaplanner</groupId>
                <artifactId>optaplanner-spring-boot-starter</artifactId>
                <version>{project-version}</version>
            </dependency>
        </dependencies>
    </dependencyManagement>

    <build>
        <plugins>
            <plugin>
                <groupId>org.springframework.boot</groupId>
                <artifactId>spring-boot-maven-plugin</artifactId>
            </plugin>
        </plugins>
    </build>
</project>
Copy the code

Business model the problem

Our goal is to assign each class to a time period and a room. So you need to create courses. The following class diagram:

Timeslot

Time class indicates the time period of class, for example, 10:30 to 11:30 on Monday or 13:30 to 14:30 on Tuesday. For simplicity, all time slots have the same length of time, with no time slots during lunch or other breaks. A time period has no date, because the high school curriculum only repeats once a week. Therefore, there is no need to add a date attribute.

public class Timeslot {

    private DayOfWeek dayOfWeek;
    private LocalTime startTime;
    private LocalTime endTime;

    private Timeslot(a) {}public Timeslot(DayOfWeek dayOfWeek, LocalTime startTime, LocalTime endTime) {
        this.dayOfWeek = dayOfWeek;
        this.startTime = startTime;
        this.endTime = endTime;
    }
    @Override
    public String toString(a) {
        return dayOfWeek + "" + startTime.toString();
    }
    / / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
    // Getters and setters
    / / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

    public DayOfWeek getDayOfWeek(a) {
        return dayOfWeek;
    }
    public LocalTime getStartTime(a) {
        return startTime;
    }
    public LocalTime getEndTime(a) {
        returnendTime; }}Copy the code

Because the Timeslot object does not change during the solution, a Timeslot is called a Problem Fact. Such classes do not require any OptaPlanner annotations. Note: The toString() method keeps the output short, so it’s easier to read OptaPlanner’s DEBUG or TRACE logs.

Room

The room represents the location of the lecture, for example, room A or room B. For simplicity, there are no capacity limits in any of the rooms and they can accommodate all classes.

public class Room {

    private String name;

    private Room(a) {}public Room(String name) {
        this.name = name;
    }
    @Override
    public String toString(a) {
        return name;
    }
    / / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
    // Getters and setters
    / / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

    public String getName(a) {
        returnname; }}Copy the code

Room objects don’t change during solution, so Room is also a Problem Fact.

Lesson

In a Lesson represented by the Lesson class, a teacher teaches a subject to a group of students, for example, math by A. Uring in grade 9 or chemistry by M.Curie in grade 10. If a subject is taught by the same teacher to the same group of students many times a week, there will be multiple instances of Lesson, which can only be distinguished by ID. For example, grade 9 students have six math classes a week. During the solution process, OptaPlanner changes the timeSlot and Room fields of the Lesson class to assign each Lesson to a time period and a room. Because OptaPlanner changed these fields, Lesson is a Planning Entity.

One coursetimeslot androomThe field is empty at initialization. OptaPlanner changes the values of these fields as it solves. These fields are calledPlanning Variable. In order for OptaPlanner to identify them,timeslot 和roomEach field requires one@PlanningVariableAnnotation. Their containing classesLesson, need a@PlanningEntityAnnotation.

@PlanningEntity
public class Lesson {

    private Long id;

    private String subject;
    private String teacher;
    private String studentGroup;

    @PlanningVariable(valueRangeProviderRefs = "timeslotRange")
    private Timeslot timeslot;

    @PlanningVariable(valueRangeProviderRefs = "roomRange")
    private Room room;

    private Lesson(a) {}public Lesson(Long id, String subject, String teacher, String studentGroup) {
        this.id = id;
        this.subject = subject;
        this.teacher = teacher;
        this.studentGroup = studentGroup;
    }

    @Override
    public String toString(a) {
        return subject + "(" + id + ")";
    }

    / / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
    // Getters and setters
    / / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *

    public Long getId(a) {
        return id;
    }

    public String getSubject(a) {
        return subject;
    }

    public String getTeacher(a) {
        return teacher;
    }

    public String getStudentGroup(a) {
        return studentGroup;
    }

    public Timeslot getTimeslot(a) {
        return timeslot;
    }

    public void setTimeslot(Timeslot timeslot) {
        this.timeslot = timeslot;
    }

    public Room getRoom(a) {
        return room;
    }

    public void setRoom(Room room) {
        this.room = room; }}Copy the code

Define constraints and calculate scores

The score represents the quality of a solution, and the higher the better. OptaPlanner looks for the optimal solution, that is, the solution with the highest score found in the time available, and it may be the optimal solution. Because this use case has hard and soft constraints, the HardSoftScore class is used to represent the score.

  • Hard constraints cannot be broken. For example, one room can have up to one class at a time.
  • Soft constraints should not be broken. For example, a teacher would prefer to teach in one room.

Hard constraints are weighted with other hard constraints. Soft constraints are also weighted. Compared with other soft constraints, hard constraints are always larger than soft constraints, regardless of their respective weights. The two are of different levels. Create a TimeTableConstraintProvider. Java classes to perform the incremental fraction calculations. It uses the ConstraintStream API of OptaPlanner, which is inspired by Java 8 Streams and SQL.

public class TimeTableConstraintProvider implements ConstraintProvider {

    @Override
    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {
        return new Constraint[]{
                // Hard constraints
                roomConflict(constraintFactory),
                teacherConflict(constraintFactory),
                studentGroupConflict(constraintFactory),
                // Soft constraints are only implemented in the "complete" implementation
        };
    }

    private Constraint roomConflict(ConstraintFactory constraintFactory) {
        // A room can hold up to one class at a time.

        // Select a course...
        return constraintFactory.from(Lesson.class)
                / /... And pair with another course......
                .join(Lesson.class,
                        / /... During the same period of time...
                        Joiners.equal(Lesson::getTimeslot),
                        / /... In the same room...
                        Joiners.equal(Lesson::getRoom),
                        / /... And this pair is unique (different ids, no reverse pair).
                        Joiners.lessThan(Lesson::getId))
                // Then punish each pair with a hard weight.
                .penalize("Room conflict", HardSoftScore.ONE_HARD);
    }

    private Constraint teacherConflict(ConstraintFactory constraintFactory) {
        // A teacher can teach up to one subject at a time.
        return constraintFactory.from(Lesson.class)
                .join(Lesson.class,
                        Joiners.equal(Lesson::getTimeslot),
                        Joiners.equal(Lesson::getTeacher),
                        Joiners.lessThan(Lesson::getId))
                .penalize("Teacher conflict", HardSoftScore.ONE_HARD);
    }

    private Constraint studentGroupConflict(ConstraintFactory constraintFactory) {
        // A student can have no more than one lesson at a time.
        return constraintFactory.from(Lesson.class)
                .join(Lesson.class,
                        Joiners.equal(Lesson::getTimeslot),
                        Joiners.equal(Lesson::getStudentGroup),
                        Joiners.lessThan(Lesson::getId))
                .penalize("Student group conflict", HardSoftScore.ONE_HARD); }}Copy the code

Create PlanningSolution class

Creating the TimeTable class wraps all Timeslot, Room, and Lesson instances of a single data set. Also, because it includes all courses, each course has a specific state of planning variables, so it is a planning solution, and it has a score. The Timeable class can be thought of as the entry point for OptaPlanner to manipulate data during the solving process. All constant data, variable modification, and fractional calculations are performed through this class. The scores are as follows:

  • If the course is still unassigned, then it is an uninitialized solution, for example, a score of-4init/0hard/0softThe solution to the problem.
  • If it breaks hard constraints, then it is an unworkable solution, for example, a score of-2hard/3softThe solution to the problem.
  • If it complies with all the hard constraints, then it is a viable solution, for example, a score of0hard/7softThe solution to the problem.
@PlanningSolution
public class TimeTable {

    @ValueRangeProvider(id = "timeslotRange")
    @ProblemFactCollectionProperty
    private List<Timeslot> timeslotList;
    @ValueRangeProvider(id = "roomRange")
    @ProblemFactCollectionProperty
    private List<Room> roomList;
    @PlanningEntityCollectionProperty
    private List<Lesson> lessonList;
    @PlanningScore
    private HardSoftScore score;

    private TimeTable(a) {}public TimeTable(List
       
         timeslotList, List
        
          roomList, List
         
           lessonList)
         
        
        {
        this.timeslotList = timeslotList;
        this.roomList = roomList;
        this.lessonList = lessonList;
    }
    / / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
    // Getters and setters
    / / * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * * *
    public List<Timeslot> getTimeslotList(a) {
        return timeslotList;
    }
    public List<Room> getRoomList(a) {
        return roomList;
    }
    public List<Lesson> getLessonList(a) {
        return lessonList;
    }
    public HardSoftScore getScore(a) {
        returnscore; }}Copy the code

The TimeTable class has an @PlanningSolution annotation, so OptaPlanner knows that this class contains all the input and output data. Specifically, this class is the input to the problem:

  • timeslotListfield
    • This is aProblem factsBecause they don’t change during the course of the problem.
  • RoomList field
    • This is aProblem factsBecause they don’t change during the course of the problem.
  • lessonListfield
  • This is aPlanning entitiesBecause they change as we go along.
  • lesson
    • timeslotandroom The value of the field is usually still empty, so it is not allocated. They arePlanning variables.
    • Other fields, such assubject.teacher ,studentGroup, are filled in. These fields areProblem Properties.

Of course, this class is also the output of the solution.

  • lessonListField, eachLessonInstances have non-empty TimesLot and Room room fields after resolution
  • scoreThe score field, which represents the quality of the output solution, for example,0hard/-5soft

Create the solution business class

Now let’s put everything together and create a REST service. But solving planning problems on REST threads can cause HTTP timeouts. Thus, the Spring Boot launcher injects an instance of SolverManager, which runs the solver in a separate thread pool and can solve multiple data sets in parallel.

@RestController
@RequestMapping("/timeTable")public class TimeTableController {

    @Autowired
    private SolverManager<TimeTable, UUID> solverManager;

    @PostMapping("/solve")
    public TimeTable solve(@RequestBody TimeTable problem) {
        UUID problemId = UUID.randomUUID();
        // Submit the problem and start solving
        SolverJob<TimeTable, UUID> solverJob = solverManager.solve(problemId, problem);
        TimeTable solution;
        try {
            // Wait for the solution to end
            solution = solverJob.getFinalBestSolution();
        } catch (InterruptedException | ExecutionException e) {
            throw new IllegalStateException("Solving failed.", e);
        }
        returnsolution; }}Copy the code

For simplicity, the implementation waits for the solver to complete, which still causes HTTP timeouts. The full implementation avoids HTTP timeouts more elegantly.

Set termination time

If there is no termination setting or termination event, the solver runs forever. To avoid this, limit the solution time to 5 seconds. This is short enough to avoid HTTP timeouts. Create the src/main/resources/application.properties file:

optaplanner.solver.termination.spent-limit=5s
Copy the code

Start the program

Use the SpringBoot Application class to start it.

@SpringBootApplication
public class TimeTableSpringBootApp {
    public static void main(String[] args) { SpringApplication.run(TimeTableSpringBootApp.class, args); }}Copy the code

Try to solve

After starting the service, we access it through PostMan. URL: http://localhost:8080/timeTable/solve to solve the JSON data:

{
        "timeslotList": [{"dayOfWeek": "MONDAY"."startTime": "08:30:00"."endTime": "09:30:00"
                },
                {
                        "dayOfWeek": "MONDAY"."startTime": "09:30:00"."endTime": "10:30:00"}]."roomList": [{"name": "Room A"
                },
                {
                        "name": "Room B"}]."lessonList": [{"id": 1."subject": "Math"."teacher": "A. Turing"."studentGroup": "9th grade"
                },
                {
                        "id": 2."subject": "Chemistry"."teacher": "M. Curie"."studentGroup": "9th grade"
                },
                {
                        "id": 3."subject": "French"."teacher": "M. Curie"."studentGroup": "10th grade"
                },
                {
                        "id": 4."subject": "History"."teacher": "I. Jones"."studentGroup": "10th grade"}}]Copy the code

After about 5 seconds, the service returns an output based on the termination time defined in application.properties.

Result output:

{
    "timeslotList": [{"dayOfWeek": "MONDAY"."startTime": "08:30:00"."endTime": "09:30:00"
        },
        {
            "dayOfWeek": "MONDAY"."startTime": "09:30:00"."endTime": "10:30:00"}]."roomList": [{"name": "Room A"
        },
        {
            "name": "Room B"}]."lessonList": [{"id": 1."subject": "Math"."teacher": "A. Turing"."studentGroup": "9th grade"."timeslot": {
                "dayOfWeek": "MONDAY"."startTime": "08:30:00"."endTime": "09:30:00"
            },
            "room": {
                "name": "Room A"}}, {"id": 2."subject": "Chemistry"."teacher": "M. Curie"."studentGroup": "9th grade"."timeslot": {
                "dayOfWeek": "MONDAY"."startTime": "09:30:00"."endTime": "10:30:00"
            },
            "room": {
                "name": "Room A"}}, {"id": 3."subject": "French"."teacher": "M. Curie"."studentGroup": "10th grade"."timeslot": {
                "dayOfWeek": "MONDAY"."startTime": "08:30:00"."endTime": "09:30:00"
            },
            "room": {
                "name": "Room B"}}, {"id": 4."subject": "History"."teacher": "I. Jones"."studentGroup": "10th grade"."timeslot": {
                "dayOfWeek": "MONDAY"."startTime": "09:30:00"."endTime": "10:30:00"
            },
            "room": {
                "name": "Room B"}}]."score": "0hard/0soft"
}
Copy the code

As you can see, the program assigns all four classes to one of two periods and one of two rooms. Notice also that it meets all the hard constraints. For example, the two classes at M. Curie’s are at different times. On the server side, the informational log shows what OptaPlanner did in those five seconds.

. Solving started: time spent (33), best score (-8init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).... Construction Heuristic phase (0) ended: time spent (73), best score (0hard/0soft), score calculation speed (459/sec), step total (4).... Local Search phase (1) ended: time spent (5000), best score (0hard/0soft), score calculation speed (28949/sec), step total (28398).... Solving ended: time spent (5000), best score (0hard/0soft), score calculation speed (28524/sec), phase total (2), environment mode (REPRODUCIBLE).
Copy the code

The log configuration

When we add constraints to ConstraintProvider, note the speed at which the score is computed in the information log and evaluate the performance impact after solving the same time.

. Solving ended: ... , score calculation speed (29455/sec), ...
Copy the code

To see how OptaPlanner solves problems internally, change logging in the application.properties file or with the -D system property.

logging.level.org.optaplanner=debug
Copy the code

Use the debug log to display each step:

. Solving started: time spent (67), best score (-20init/0hard/0soft), environment mode (REPRODUCIBLE), random (JDK with seed 0).... CH step (0), time spent (128), score (-18init/0hard/0soft), selected move count (15), picked move ([Math(101) {null -> Room A}, Math(101) {null -> MONDAY 08:30}]).... CH step (1), time spent (145), score (-16init/0hard/0soft), selected move count (15), picked move ([Physics(102) {null -> Room A}, Physics(102) {null -> MONDAY 09:30}])....Copy the code

conclusion

Give ourselves a thumbs up! We just developed a Spring application with OptaPlanner. This article code address: gitee.com/yqsoftware/…

homework

Through this article, we have been able to build a simple solution program, we mentioned in the article hard constraints/soft constraints, only the implementation of hard constraints, you can try to add soft constraints to it, for example: soft constraints: M. Curie likes afternoon classes.

conclusion

This time, you have been able to build a simple solution program. In the next chapter, I will study various examples to deepen my understanding of OptaPlanner. Finally, we will systematically study each deep application. Finally writing is not easy, trouble to give a small praise, pay attention to me, we learn together ~~~