JBoss.orgCommunity Documentation
The number of possible solutions for a planning problem can be mind blowing. For example:
The business wants the optimal solution, but they also have other requirements:
Scale out: Large production datasets must not crash and have good results too.
Optimize the right problem: The constraints must match the actual business needs.
Available time: The solution must be found in time, before it becomes useless to execute.
Reliability: Every dataset must have at least a decent result (better than a human planner).
Given these requirements, and despite the promises of some salesmen, it's usually impossible for anyone or anything to find the optimal solution. Therefore, Planner focuses on finding the best solution in available time. In realistic, independent competitions, Planner often comes out as the best reusable software.
The nature of NP-complete problems make scaling a prime concern. The result quality of a small dataset guarantees nothing about the result quality of a large dataset. Scaling problems cannot be mitigated by hardware purchases. Start testing with a production sized dataset as soon as possible. Don't asses quality on small datasets (unless production encounters such datasets). Instead, solve a production sized dataset and compare with the results of longer execution, different algorithms and - if available - the human planner.
If you want to learn more about metaheuristics, read the free book Essentials of Metaheuristics or Clever Algorithms.
Start with a quick configuration that involves little or no configuration and optimization code:
Next, implement planning entity difficulty comparison and turn it into:
Next, implement moves and add tabu search behind it:
And combine them with tabu search:
If you have time, continue experimenting even further. Blog about your experiments!
Here's a configuration that runs 3 phases in sequence:
<solver>
...
<constructionHeuristic>
... <!-- First phase: First Fit decreasing -->
</constructionHeuristic>
<localSearch>
... <!-- Second phase: Simulated annealing -->
</localSearch>
<localSearch>
... <!-- Third phase: Tabu search -->
</localSearch>
</solver>
<solver>
...
<termination><!-- Solver termination -->
<maximumSecondsSpend>90</maximumSecondsSpend>
</termination>
<localSearch>
<termination><!-- Phase termination -->
<maximumSecondsSpend>60</maximumSecondsSpend><!-- Give the next phase a chance to run too, before the Solver terminates -->
</termination>
...
</localSearch>
<localSearch>
...
</localSearch>
</solver>
Terminates when an amount of time has been reached:
<termination>
<maximumTimeMillisSpend>500</maximumTimeMillisSpend>
</termination>
<termination>
<maximumSecondsSpend>10</maximumSecondsSpend>
</termination>
<termination>
<maximumMinutesSpend>5</maximumMinutesSpend>
</termination>
<termination>
<maximumHoursSpend>1</maximumHoursSpend>
</termination>
<termination>
<scoreAttained>0</scoreAttained>
</termination>
For a planning problem with hard and soft constraints, it could look like this:
<termination>
<scoreAttained>0hard/-5000soft</scoreAttained>
</termination>
You can use this Termination
to terminate once it reaches a feasible solution.
Terminates when an amount of steps has been reached:
<termination>
<maximumStepCount>100</maximumStepCount>
</termination>
This Termination
can only be used for a SolverPhase
, not for the
Solver
itself.
Terminates when the best score hasn't improved in a number of steps:
<termination>
<maximumUnimprovedStepCount>100</maximumUnimprovedStepCount>
</termination>
This Termination
can only be used for a SolverPhase
, not for the
Solver
itself.
<termination>
<terminationCompositionStyle>OR</terminationCompositionStyle>
<maximumStepCount>100</maximumStepCount>
<scoreAttained>0</scoreAttained>
</termination>
<termination>
<terminationCompositionStyle>AND</terminationCompositionStyle>
<maximumUnimprovedStepCount>5</maximumUnimprovedStepCount>
<scoreAttained>-100</scoreAttained>
</termination>
Each time a new best solution is found, the Solver
fires a
BestSolutionChangedEvent
.
To listen to such events, add a SolverEventListener
to the
Solver
:
public interface Solver {
// ...
void addEventListener(SolverEventListener eventListener);
void removeEventListener(SolverEventListener eventListener);
}
Implement the CustomSolverPhaseCommand
interface:
public interface CustomSolverPhaseCommand {
void changeWorkingSolution(ScoreDirector scoreDirector);
}
public class ExaminationSolutionInitializer implements CustomSolverPhaseCommand {
public void changeWorkingSolution(ScoreDirector scoreDirector) {
Examination examination = (Examination) scoreDirector.getWorkingSolution();
for (Exam exam : examination.getExamList()) {
Score unscheduledScore = scoreDirector.calculateScore();
...
for (Period period : examination.getPeriodList()) {
scoreDirector.beforeVariableChanged(exam, "period");
exam.setPeriod(period)
scoreDirector.afterVariableChanged(exam, "period");
Score score = scoreDirector.calculateScore();
...
}
...
}
}
}
Do not change any of the planning facts in a CustomSolverPhaseCommand
. That will corrupt
the Solver
because any previous score or solution was for a different problem. If you want to
do that, see repeated planning and real-time planning instead.
And configure it like this:
<solver>
...
<customSolverPhase>
<customSolverPhaseCommandClass>org.optaplanner.examples.examination.solver.solution.initializer.ExaminationSolutionInitializer</customSolverPhaseCommandClass>
</customSolverPhase>
... <!-- Other phases -->
</solver>
It's possible to configure multiple customSolverPhaseCommandClass
instances, which will be
run in sequence.
If the changes of a CustomSolverPhaseCommand
don't result in a better score, the best
solution won't be changed (so effectively nothing will have changed for the next SolverPhase
or
CustomSolverPhaseCommand
). To force such changes anyway, use
forceUpdateBestSolution
:
<customSolverPhase>
<customSolverPhaseCommandClass>...MyUninitializer</customSolverPhaseCommandClass>
<forceUpdateBestSolution>true</forceUpdateBestSolution>
</customSolverPhase>
If the Solver
or SolverPhase
wants to terminate while a
CustomSolverPhaseCommand
is still running, it will wait to terminate until the
CustomSolverPhaseCommand
is done, however long that takes.