A planning entity is a JavaBean (POJO) that changes during solving, for example a Queen that changes to another row. A planning problem has multiple planning entities, for example for a single n queens problem, each Queen is a planning entity. But there's usually only 1 planning entity class, for example the Queen class.

A planning entity class needs to be annotated with the @PlanningEntity annotation.

Each planning entity class has 1 or more planning variables. It usually also has 1 or more defining properties. For example in n queens, a Queen is defined by its Column and has a planning variable Row. This means that a Queen's column never changes during solving, while its row does change.

@PlanningEntity

public class Queen {


    private Column column;


    // Planning variables: changes during planning, between score calculations.

    private Row row;


    // ... getters and setters

}

A planning entity class can have multiple planning variables. For example, a Lecture is defined by its Course and its index in that course (because 1 course has multiple lectures). Each Lecture needs to be scheduled into a Period and a Room so it has 2 planning variables (period and room). For example: the course Mathematics has 8 lectures per week, of which the first lecture is Monday morning at 08:00 in room 212.

@PlanningEntity

public class Lecture {


    private Course course;

    private int lectureIndexInCourse;


    // Planning variables: changes during planning, between score calculations.

    private Period period;

    private Room room;


    // ...

}

The solver configuration also needs to be made aware of each planning entity class:

<solver>

  ...

  <entityClass>org.optaplanner.examples.nqueens.domain.Queen</entityClass>

  ...

</solver>

Some uses cases have multiple planning entity classes. For example: route freight and trains into railway network arcs, where each freight can use multiple trains over its journey and each train can carry multiple freights per arc. Having multiple planning entity classes directly raises the implementation complexity of your use case.

Some optimization algorithms work more efficiently if they have an estimation of which planning entities are more difficult to plan. For example: in bin packing bigger items are harder to fit, in course scheduling lectures with more students are more difficult to schedule and in n queens the middle queens are more difficult to fit on the board.

Therefore, you can set a difficultyComparatorClass to the @PlanningEntity annotation:

@PlanningEntity(difficultyComparatorClass = CloudProcessDifficultyComparator.class)

public class CloudProcess {

    // ...

}

public class CloudProcessDifficultyComparator implements Comparator<CloudProcess> {


    public int compare(CloudProcess a, CloudProcess b) {

        return new CompareToBuilder()

                .append(a.getRequiredMultiplicand(), b.getRequiredMultiplicand())

                .append(a.getId(), b.getId())

                .toComparison();

    }


}

Alternatively, you can also set a difficultyWeightFactoryClass to the @PlanningEntity annotation, so you have access to the rest of the problem facts from the Solution too:

@PlanningEntity(difficultyWeightFactoryClass = QueenDifficultyWeightFactory.class)

public class Queen {

    // ...

}

See sorted selection for more information.

None of the current planning variable state should be used to compare planning entity difficult. During Construction Heuristics, those variables are likely to be null anyway. For example, a Queen's row variable should not be used.

A planning variable is a property (including getter and setter) on a planning entity. It points to a planning value, which changes during planning. For example, a Queen's row property is a planning variable. Note that even though a Queen's row property changes to another Row during planning, no Row instance itself is changed.

A planning variable getter needs to be annotated with the @PlanningVariable annotation, which needs a non-empty valueRangeProviderRefs property.

@PlanningEntity

public class Queen {


    private Row row;


    // ...


    @PlanningVariable(valueRangeProviderRefs = {"rowRange"})

    public Row getRow() {

        return row;

    }


    public void setRow(Row row) {

        this.row = row;

    }


}

The valueRangeProviderRefs property defines what are the possible planning values for this planning variable. It references 1 or more @ValueRangeProvider id's.

By default, an initialized planning variable cannot be null, so an initialized solution will never use null for any of its planning variables. In an over-constrained use case, this can be contra productive. For example: in task assignment with too many tasks for the workforce, we would rather leave low priority tasks unassigned instead of assigning them to an overloaded worker.

To allow an initialized planning variable to be null, set nullable to true:

    @PlanningVariable(..., nullable = true)

    public Worker getWorker() {

        return worker;

    }

Repeated planning (especially real-time planning) does not mix well with a nullable planning variable: every time the Solver starts or a problem fact change is made, the construction heuristics will try to initialize all the null variables again, which can be a huge waste of time. One way to deal with this, is to change when a planning entity should be reinitialized with an reinitializeVariableEntityFilter:

    @PlanningVariable(..., nullable = true, reinitializeVariableEntityFilter = ReinitializeTaskFilter.class)

    public Worker getWorker() {

        return worker;

    }

A planning variable is considered initialized if its value is not null or if the variable is nullable. So a nullable variable is always considered initialized, even when a custom reinitializeVariableEntityFilter triggers a reinitialization during construction heuristics.

A planning entity is initialized if all of its planning variables are initialized.

A Solution is initialized if all of its planning entities are initialized.

A planning value is a possible value for a planning variable. Usually, a planning value is a problem fact, but it can also be any object, for example a double. It can even be another planning entity or even a interface implemented by both a planning entity and a problem fact.

A planning value range is the set of possible planning values for a planning variable. This set can be a countable (for example row 1, 2, 3 or 4) or uncountable (for example any double between 0.0 and 1.0).

Some optimization algorithms work more efficiently if they have an estimation of which planning values are stronger, which means they are more likely to satisfy a planning entity. For example: in bin packing bigger containers are more likely to fit an item and in course scheduling bigger rooms are less likely to break the student capacity constraint.

Therefore, you can set a strengthComparatorClass to the @PlanningVariable annotation:

    @PlanningVariable(..., strengthComparatorClass = CloudComputerStrengthComparator.class)

    public CloudComputer getComputer() {

        // ...

    }

public class CloudComputerStrengthComparator implements Comparator<CloudComputer> {


    public int compare(CloudComputer a, CloudComputer b) {

        return new CompareToBuilder()

                .append(a.getMultiplicand(), b.getMultiplicand())

                .append(b.getCost(), a.getCost()) // Descending (but this is debatable)

                .append(a.getId(), b.getId())

                .toComparison();

    }


}

Alternatively, you can also set a strengthWeightFactoryClass to the @PlanningVariable annotation, so you have access to the rest of the problem facts from the solution too:

    @PlanningVariable(..., strengthWeightFactoryClass = RowStrengthWeightFactory.class)

    public Row getRow() {

        // ...

    }

See sorted selection for more information.

None of the current planning variable state in any of the planning entities should be used to compare planning values. During construction heuristics, those variables are likely to be null anyway. For example, none of the row variables of any Queen may be used to determine the strength of a Row.

Some use cases, such as TSP and Vehicle Routing, require chaining. This means the planning entities point to each other and form a chain. By modeling the problem as a set of chains (instead of a set of trees/loops), the search space is heavily reduced.

A planning variable that is chained either:

Here are some example of valid and invalid chains:

Every initialized planning entity is part of an open-ended chain that begins from an anchor. A valid model means that:

The optimization algorithms and build-in Move's do chain correction to guarantee that the model stays valid:

For example, in TSP the anchor is a Domicile (in vehicle routing it is Vehicle):

public class Domicile ... implements Standstill {


    ...


    public City getCity() {...}


}

The anchor (which is a problem fact) and the planning entity implement a common interface, for example TSP's Standstill:

public interface Standstill {


    City getCity();


}

That interface is the return type of the planning variable. Furthermore, the planning variable is chained. For example TSP's Visit (in vehicle routing it is Customer):

@PlanningEntity

public class Visit ... implements Standstill {


    ...


    public City getCity() {...}


    @PlanningVariable(graphType = PlanningVariableGraphType.CHAINED, valueRangeProviderRefs = {"domicileRange", "visitRange"})

    public Standstill getPreviousStandstill() {

        return previousStandstill;

    }


    public void setPreviousStandstill(Standstill previousStandstill) {

        this.previousStandstill = previousStandstill;

    }


}

Notice how 2 value range providers are usually combined:

2 variables are bi-directional if their instances always point to each other (unless they point to null). So if A references B, then B references A.

To map a bi-directional relationship between 2 planning variables, annotate the master side as a normal (= genuine) planning variable:

@PlanningEntity

public class Customer ... {


    @PlanningVariable(graphType = PlanningVariableGraphType.CHAINED, ...)

    public Standstill getPreviousStandstill() {

        return previousStandstill;

    }


    public void setPreviousStandstill(Standstill previousStandstill) {...}


}

And then annotate the other side as a @InverseRelationShadowVariable annotation.

@PlanningEntity

public interface Standstill {


    @InverseRelationShadowVariable(sourceVariableName = "previousStandstill")

    Customer getNextCustomer();

    void setNextCustomer(Customer nextCustomer);


}

The sourceVariableName property is the name of the planning variable on the return type of the getter.

The @InverseRelationShadowVariable variable is a form of a shadow variable: Planner uses a build-in VariableListener to update its state.

A shadow variable is a variables who's correct value can be deduced from the state of the genuine planning variables. Even though such a variable violates the principle of normalization by definition, in some use cases it can be very practical to use a shadow variable, especially to express the constraints more naturally. For example in vehicle routing with time windows: the arrival time at a customer for a vehicle can be calculated based on the previously visited customers of that vehicle (and the known travel times between 2 locations).

As the customers for a vehicle change, the arrival time is automatically adjusted. For more information, see the vehicle routing domain model.

To use custom VariableListener, implement the interface and annotate it on the shadow variable(s) that needs to change.

    @PlanningVariable(...)

    public Standstill getPreviousStandstill() {

        return previousStandstill;

    }


    @CustomShadowVariable(variableListenerClass = VehicleUpdatingVariableListener.class,

            sources = {@CustomShadowVariable.Source(variableName = "previousStandstill")})

    public Vehicle getVehicle() {

        return vehicle;

    }

The variableName is the variable that triggers changes in the shadow variable(s).

For example, the VehicleUpdatingVariableListener assures that every Customer in a chain has the same Vehicle, namely the chain's anchor.

public class VehicleUpdatingVariableListener implements VariableListener<Customer> {


    public void afterEntityAdded(ScoreDirector scoreDirector, Customer customer) {

        updateVehicle(scoreDirector, customer);

    }


    public void afterVariableChanged(ScoreDirector scoreDirector, Customer customer) {

        updateVehicle(scoreDirector, customer);

    }


    ...


    protected void updateVehicle(ScoreDirector scoreDirector, Customer sourceCustomer) {

        Standstill previousStandstill = sourceCustomer.getPreviousStandstill();

        Vehicle vehicle = previousStandstill == null ? null : previousStandstill.getVehicle();

        Customer shadowCustomer = sourceCustomer;

        while (shadowCustomer != null && shadowCustomer.getVehicle() != vehicle) {

            scoreDirector.beforeVariableChanged(shadowCustomer, "vehicle");

            shadowCustomer.setVehicle(vehicle);

            scoreDirector.afterVariableChanged(shadowCustomer, "vehicle");

            shadowCustomer = shadowCustomer.getNextCustomer();

        }

    }


}

From a score calculation perspective, a shadow variable is like any other planning variable. From an optimization perspective, Planner effectively only optimizes the genuine variables (and mostly ignores the shadow variables): it just assures that when a genuine variable changes, any dependent shadow variables are changed accordingly.

A dataset for a planning problem needs to be wrapped in a class for the Solver to solve. You must implement this class. For example in n queens, this in the NQueens class which contains a Column list, a Row list and a Queen list.

A planning problem is actually a unsolved planning solution or - stated differently - an uninitialized Solution. Therefor, that wrapping class must implement the Solution interface. For example in n queens, that NQueens class implements Solution, yet every Queen in a fresh NQueens class is not yet assigned to a Row (their row property is null). So it's not a feasible solution. It's not even a possible solution. It's an uninitialized solution.

You need to present the problem as a Solution instance to the Solver. So you need to have a class that implements the Solution interface:

public interface Solution<S extends Score> {


    S getScore();

    void setScore(S score);


    Collection<? extends Object> getProblemFacts();


}

For example, an NQueens instance holds a list of all columns, all rows and all Queen instances:

public class NQueens implements Solution<SimpleScore> {


    private int n;


    // Problem facts

    private List<Column> columnList;

    private List<Row> rowList;


    // Planning entities

    private List<Queen> queenList;


    // ...

}

A Solution requires a score property. The score property is null if the Solution is uninitialized or if the score has not yet been (re)calculated. The score property is usually typed to the specific Score implementation you use. For example, NQueens uses a SimpleScore:

public class NQueens implements Solution<SimpleScore> {


    private SimpleScore score;


    public SimpleScore getScore() {

        return score;

    }


    public void setScore(SimpleScore score) {

        this.score = score;

    }


    // ...

}

Most use cases use a HardSoftScore instead:

public class CourseSchedule implements Solution<HardSoftScore> {


    private HardSoftScore score;


    public HardSoftScore getScore() {

        return score;

    }


    public void setScore(HardSoftScore score) {

        this.score = score;

    }


    // ...

}

See the Score calculation section for more information on the Score implementations.

The method is only used if Drools is used for score calculation. Other score directors do not use it.

All objects returned by the getProblemFacts() method will be asserted into the Drools working memory, so the score rules can access them. For example, NQueens just returns all Column and Row instances.

    public Collection<? extends Object> getProblemFacts() {

        List<Object> facts = new ArrayList<Object>();

        facts.addAll(columnList);

        facts.addAll(rowList);

        // Do not add the planning entity's (queenList) because that will be done automatically

        return facts;

    }

All planning entities are automatically inserted into the Drools working memory. Do not add them in the method getProblemFacts().

The method getProblemFacts() is not called much: at most only once per solver phase per solver thread.

A cached problem fact is a problem fact that doesn't exist in the real domain model, but is calculated before the Solver really starts solving. The method getProblemFacts() has the chance to enrich the domain model with such cached problem facts, which can lead to simpler and faster score constraints.

For example in examination, a cached problem fact TopicConflict is created for every 2 Topic's which share at least 1 Student.

    public Collection<? extends Object> getProblemFacts() {

        List<Object> facts = new ArrayList<Object>();

        // ...

        facts.addAll(calculateTopicConflictList());

        // ...

        return facts;

    }


    private List<TopicConflict> calculateTopicConflictList() {

        List<TopicConflict> topicConflictList = new ArrayList<TopicConflict>();

        for (Topic leftTopic : topicList) {

            for (Topic rightTopic : topicList) {

                if (leftTopic.getId() < rightTopic.getId()) {

                    int studentSize = 0;

                    for (Student student : leftTopic.getStudentList()) {

                        if (rightTopic.getStudentList().contains(student)) {

                            studentSize++;

                        }

                    }

                    if (studentSize > 0) {

                        topicConflictList.add(new TopicConflict(leftTopic, rightTopic, studentSize));

                    }

                }

            }

        }

        return topicConflictList;

    }

Any score constraint that needs to check if no 2 exams have a topic which share a student are being scheduled close together (depending on the constraint: at the same time, in a row or in the same day), can simply use the TopicConflict instance as a problem fact, instead of having to combine every 2 Student instances.

Most (if not all) optimization algorithms clone the solution each time they encounter a new best solution (so they can recall it later) or to work with multiple solutions in parallel.

A planning clone of a Solution must fulfill these requirements:

Implementing a planning clone method is hard, therefore you don't need to implement it.

@DeepPlanningClone

public class SeatDesignationDependency {

    private SeatDesignation leftSeatDesignation; // planning entity

    private SeatDesignation rightSeatDesignation; // planning entity

    ...

}

public interface PlanningCloneable<T> {


    T planningClone();


}

public class NQueens implements Solution<...>, PlanningCloneable<NQueens> {

    ...


    /**

     * Clone will only deep copy the {@link #queenList}.

     */

    public NQueens planningClone() {

        NQueens clone = new NQueens();

        clone.id = id;

        clone.n = n;

        clone.columnList = columnList;

        clone.rowList = rowList;

        List<Queen> clonedQueenList = new ArrayList<Queen>(queenList.size());

        for (Queen queen : queenList) {

            clonedQueenList.add(queen.planningClone());

        }

        clone.queenList = clonedQueenList;

        clone.score = score;

        return clone;

    }

}

Build a Solution instance to represent your planning problem, so you can set it on the Solver as the planning problem to solve. For example in n queens, an NQueens instance is created with the required Column and Row instances and every Queen set to a different column and every row set to null.

    private NQueens createNQueens(int n) {

        NQueens nQueens = new NQueens();

        nQueens.setId(0L);

        nQueens.setN(n);

        nQueens.setColumnList(createColumnList(nQueens));

        nQueens.setRowList(createRowList(nQueens));

        nQueens.setQueenList(createQueenList(nQueens));

        return nQueens;

    }


    private List<Queen> createQueenList(NQueens nQueens) {

        int n = nQueens.getN();

        List<Queen> queenList = new ArrayList<Queen>(n);

        long id = 0;

        for (Column column : nQueens.getColumnList()) {

            Queen queen = new Queen();

            queen.setId(id);

            id++;

            queen.setColumn(column);

            // Notice that we leave the PlanningVariable properties on null

            queenList.add(queen);

        }

        return queenList;

    }

Figure 4.1. Uninitialized solution for the 4 queens puzzle

        private void createLectureList(CourseSchedule schedule) {

            List<Course> courseList = schedule.getCourseList();

            List<Lecture> lectureList = new ArrayList<Lecture>(courseList.size());

            for (Course course : courseList) {

                for (int i = 0; i < course.getLectureSize(); i++) {

                    Lecture lecture = new Lecture();

                    lecture.setCourse(course);

                    lecture.setLectureIndexInCourse(i);

                    // Notice that we leave the PlanningVariable properties (period and room) on null

                    lectureList.add(lecture);

                }

            }

            schedule.setLectureList(lectureList);

        }

The FULL_ASSERT mode turns on all assertions (such as assert that the incremental score calculation is uncorrupted for each move) to fail-fast on a bug in a Move implementation, a score rule, the rule engine itself, ...

This mode is reproducible (see the reproducible mode). It is also intrusive because it calls the method calculateScore() more frequently than a non assert mode.

The FULL_ASSERT mode is horribly slow (because it doesn't rely on delta based score calculation).

The NON_INTRUSIVE_FULL_ASSERT turns on several assertions to fail-fast on a bug in a Move implementation, a score rule, the rule engine itself, ...

This mode is reproducible (see the reproducible mode). It is non-intrusive because it does not call the method calculateScore() more frequently than a non assert mode.

The NON_INTRUSIVE_FULL_ASSERT mode is horribly slow (because it doesn't rely on delta based score calculation).

The FAST_ASSERT mode turns on most assertions (such as assert that an undo Move's score is the same as before the Move) to fail-fast on a bug in a Move implementation, a score rule, the rule engine itself, ...

This mode is reproducible (see the reproducible mode). It is also intrusive because it calls the method calculateScore() more frequently than a non assert mode.

The FAST_ASSERT mode is slow.

It's recommended to write a test case which does a short run of your planning problem with the FAST_ASSERT mode on.

The reproducible mode is the default mode because it is recommended during development. In this mode, 2 runs in the same OptaPlanner version will execute the same code in the same order. Those 2 runs will have the same result at every step, except if the note below applies. This enables you to reproduce bugs consistently. It also allows you to benchmark certain refactorings (such as a score constraint performance optimization) fairly across runs.

The reproducible mode is slightly slower than the production mode. If your production environment requires reproducibility, use this mode in production too.

In practice, this mode uses the default, fixed random seed if no seed is specified, and it also disables certain concurrency optimizations (such as work stealing).

The production mode is the fastest, but it is not reproducible. It is recommended for a production environment, unless reproducibility is required.

In pratice, this mode uses no fixed random seed if no seed is specified.