OptaPlanner : An AI constraint solver

OptaPlanner is an AI-based constraint solver which optimizes planning and scheduling problems. OptaPlanner is an open-source constraint solver which is developed and managed by RedHat. It was founded in 2006 by Geoffrey De Smet. It is written in Java Language. It solves problems such as Maintenance Scheduling, Vehicle Routing Problem, Employee Rostering, Task Assignment, School Timetabling, Job Shop Scheduling, Cloud Optimization, Conference Scheduling, Bin Packing etc. 

Lets understand this with an simple example.

Here we will create a simple Spring Boot project of time table sheduling for schoool to understand its functionality :

OptaPlanner integration in Spring Boot is very simple just add OptaPlanner Dependency.

<!-- https://mvnrepository.com/artifact/org.optaplanner/optaplanner-spring-boot-starter -->

<dependency>

    <groupId>org.optaplanner</groupId>

    <artifactId>optaplanner-spring-boot-starter</artifactId>

    <version>8.0.0.Final</version>

</dependency>

 

Now we need to create some Domain:

1. TimeSlot - This is a simple POJO.

public class Timeslot {



    private DayOfWeek dayOfWeek;

    private LocalTime startTime;

    private LocalTime endTime;    

    //Constructor

    //Getters and Setters

}

2. Room - This is a simple POJO

public class Room {

    private String name;

    private Room() {

    }

    public Room(String name) {

        this.name = name;

    }

    //Getter and Setter

}

3. Lesson - This is a Planning Entity which will be used during Solving the problem of Scheduling. @PlanningEntity annotation tells OptaPlanner That Lesson is a Entity and it has two planning variables timeslot and room. @PlanningVariable annotation tells OptaPlanner that this value could be changed during solving the problem.

@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;

    //Getter and Setters

}

4. TimeTable - It is a Planning solution which represents a problem and a possible solution of that problem. @PlanningSolution  annotation tells OptaPlanner that Time Table is a problem which is to be solved. It has Three Problem Facts timeslotList, roomList, lessonList whcih is basically the collection of all the properties which OptaPlanner can use to find the best solution.

It has score which specifies that the solution is feasible or not. It is calculated on the base of Hard and soft constraints defined in the solver. If any of the hard and soft constraint is broken it will be decreased by -1.

Hard constraints - These are the constraints which must not be broken. In our example a teacher can not teach two lessons at the same time. If solver assign it will be big problem because it is not possible.

Soft constraints - These are the constraints which can be broken to find the best solution. In our example a teacher does not like gaps between classes is a soft constraint.

@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;

    //Constructors

    //Getters and Setters

}

Solver - It is the most important part of the OptaPlanner. Here we define the constraints by which we will be solving the problem. In this we have defined only one constaint which is room conflict. It is not possible to have to classes at the same time in the same room. So if this constraint is broken during solving the problem it will be counted as one hard in the score.

public class TimeTableConstraintProvider implements ConstraintProvider {

    @Override

    public Constraint[] defineConstraints(ConstraintFactory constraintFactory) {

        return new Constraint[] {

                

                roomConflict(constraintFactory),

                //Other Constraints

        };

    }

    private Constraint roomConflict(ConstraintFactory constraintFactory) {

        

        return constraintFactory.from(Lesson.class)

                .join(Lesson.class,

                        Joiners.equal(Lesson::getTimeslot),

                        Joiners.equal(Lesson::getRoom),

                        Joiners.lessThan(Lesson::getId))

                .penalize("Room conflict", HardSoftScore.ONE_HARD);

    }

    // Other constraints defination

}

Lets understand the above code, Here in room conflict in first line we are taking a lesson and in second line line we are joining it with second lesson. then we are finding and checking time slot and room of both the lessons. If room and time slot is equal which means two classes have been assigned to a single room at the same time which is not possible. So, with the penalize method we are increasing one hard in the score.
 

Note : There are two methods for changing the score in solver penalize() and reward(). penalize() method is used to decrease the the score and reward() method is used to increase the score. The reward() method is used in those constraints which are good to be broken for example A teacher prefers to teach sequential lessons and dislikes gaps between lessons.

From the above demonstration we have understood the core concepts of OptaPlanner. It is a very good way to find best solution in less amount of time.