This is the 8th day of my participation in Gwen Challenge

Contents summary

Over the last few chapters we’ve looked at some of the key concepts of OptaPlanner and how to create a planning problem solver class, so today we’ll look at how to use OptaPlanner to solve problems.

Solver interface

Solver interface

public interface Solver<Solution_> {

    Solution_ solve(Solution_ problem); . }Copy the code

A Solver instance Solver can solve only one instance of a programming problem at a time. It’s built by a SolverFactory, and you don’t need to implement it yourself. Except for those methods that are explicitly documented as thread-safe in Javadoc, a Solver can only be accessed from one thread.

The solve() method occupies the current thread. This can cause HTTP timeouts for REST services and require additional code to resolve multiple data sets in parallel. To avoid these problems, SolverManager can be used instead.

Problem solving

Solving a problem is fairly easy:

  • A solver built from a solver configuration
  • One that represents an instance of a planning problem@PlanningSolution

As long as the programming problem is supplied as a parameter to the solve() method, it returns the best solution found.

NQueens problem = ... ; NQueens bestSolution = solver.solve(problem);Copy the code

For example, out of n queens, the solve() method returns an instance of NQueens, each assigned to a row.

The best solution to the mystery of the Four Queens

The solve approach can take a long time (depending on the size of the problem and the configuration of the solver). The solver intelligently accesses the search space for possible solutions and remembers the best solution it encountered during the solution. Depends on many factors (including problem size, how much time the solver has, solver configuration……) The optimal solution may or may not be an optimal solution.

The solution instance that calls the method solve(solution) is changed by Solver, but do not assume that it is the best solution, because the problem size, solution configuration, constraint rule writing, and so on, may not be an optimal solution.

Environment configuration

The environment schema, which allows detection of common errors in the implementation, can be set in the XML file of the solver configuration:

<solver xmlns="https://www.optaplanner.org/xsd/solver" xmlns:xsi="http://www.w3.org/2001/XMLSchema-instance"
    xsi:schemaLocation="https://www.optaplanner.org/xsd/solver https://www.optaplanner.org/xsd/solver/solver.xsd">
  <environmentMode>FAST_ASSERT</environmentMode>.</solver>
Copy the code

A solver has a single random instance. Some solvers are configured to use random instances more than others. For example, simulated annealing relies heavily on random numbers, while tabu search only relies on it to deal with the problem of identical scores. The environment mode affects the seed of the random instance. Supports the following configurations:

FULL_ASSERT

The FULL_ASSERT mode turns on all assertions (such as asserting that incremental score calculations for each Move have not been broken) in order to quickly fail in the event of errors in Move implementation, constraints, the engine itself, and so on. This pattern is repeatable (see repeatable pattern). It is also intrusive because it calls the calculateScore() method more frequently than non-assertion mode. FULL_ASSERT mode is very slow (because it does not rely on incremental score calculations).

NON_INTRUSIVE_FULL_ASSERT

NON_INTRUSIVE_FULL_ASSERT turns on several assertions to quickly fail in the event of errors in the Move implementation, constraints, the engine itself, and so on. This pattern is repeatable (see repeatable pattern). It is non-invasive because it does not call method calculateScore() more frequently than non-assertion mode. The NON_INTRUSIVE_FULL_ASSERT mode is turtle speed (because it does not rely on incremental score calculations).

FAST_ASSERT

The FAST_ASSERT mode turns on most assertions (such as asserting that a undoMove score is the same as before the move) in order to quickly fail if something goes wrong with the move implementation, constraints, the engine itself, and so on. This pattern is repeatable (see repeatable pattern). It is also intrusive because it calls the method calculateScore() more frequently than non-assertion mode. The FAST_ASSERT mode is also slow. It is recommended to write a test case that does a short run on your programming problem in FAST_ASSERT mode.

REPRODUCIBLE (default)

Reproducible mode is the default mode because it is recommended during development. In this mode, two runs from the same OptaPlanner execute the same code in the same order. The two runs will have the same result at each step, unless the comments below change. This makes it possible to reproduce the bug consistently. It also allows you to fairly benchmark certain refactorings, such as performance optimizations for fractional constraints, across different runs. This configuration is very useful, we need to reproduce the last solution results during debugging and development to find problems.

Despite reproducible patterns, the application may not reproduce completely because: Use an unordered HashSet (or another set with inconsistent order between JVM runs) as a collection of planned entities or planned values (but not normal problem facts), especially in solution implementations, and be careful to replace it with LinkedHashSet. Combine algorithms that rely on time gradients (most obviously simulated annealing) with terminations that take time. The amount of CPU time allocated varies enough to affect the time gradient. B: Use Late Acceptance instead of Simulated rolling. Or use step terminations instead of time-consuming terminations. (It’s not common.)

Repeatable patterns may be slightly slower than non-repeatable patterns. If your production environment could use some help from repeatability, use this pattern in production.

In practice, this pattern uses the default, fixed random seed if no seed is specified, and it also disables some concurrency optimizations.

NON_REPRODUCIBLE

Non-recurring patterns may be slightly faster than live ones. Avoid it during development because it makes debugging and fixing bugs a pain. If your production environment doesn’t care about repeatability, use this pattern in production. In practice, the pattern does not use fixed random seeds if no seeds are specified.

The level of logging

We can adjust the level of the log to see what the solver does at each step, which is very helpful for debugging the problem.

  • Error: Logs errors, except those performedRuntimeExceptionError thrown to calling code.
    • OptaPlanner fails quickly if an error occurs: it throws oneRuntimeExceptionAnd provide detailed information to the calling code. It does not record it as an error to avoid duplicate logging information. Unless the calling code explicitly catches and eats itRuntimeExceptionOtherwise the thread defaultsExceptionHandlerIt will be logged as an error. At the same time, the code is terminated.
  • Warn: Logs suspicious conditions.
  • Info: Records each stage of the resolver itself.
  • Debug: Records each step in each phase.
  • Trace: Records each action at each step of each stage.
    • At the Trace level, performance degrades dramatically: it’s typically four times slower. However, it can be invaluable for discovering bottlenecks during development.

For example, set it to debug level to see when the phase ends and the pace of the steps:

INFO  Solving started: time spent (3), best score (-4init/0).random (JDK with seed 0).
DEBUG     CH step (0), time spent (5).score (-3init/0), selected move count (1), picked move (Queen-2 {null -> Row-0}).
DEBUG     CH step (1), time spent (7).score (-2init/0), selected move count (3), picked move (Queen-1 {null -> Row-2}).
DEBUG     CH step (2), time spent (10).score (-1init/0), selected move count (4), picked move (Queen-3 {null -> Row-3}).
DEBUG     CH step (3), time spent (12).score (-1), selected move count (4), picked move (Queen-0 {null -> Row-1}).
INFO  Construction Heuristic phase (0) ended: time spent (12), best score (-1), score calculation speed (9000/sec), step total (4).
DEBUG     LS step (0), time spent (19).score (-1),     best score (-1), accepted/selected move count (12/12), picked move (Queen-1 {Row-2 -> Row-3}).
DEBUG     LS step (1), time spent (24).score (0), new best score (0), accepted/selected move count (9/12), picked move (Queen-3 {Row-3 -> Row-2}).
INFO  Local Search phase (1) ended: time spent (24), best score (0), score calculation speed (4000/sec), step total (2).
INFO  Solving ended: time spent (24), best score (0), score calculation speed (7000/sec), phase total (2), environment mode (REPRODUCIBLE).
Copy the code

All time values are in milliseconds, and everything is logged to SLF4J.

Configure the log level for the org.optaPlanner package in the logback.xml file.

<configuration>

  <logger name="org.optaplanner" level="debug"/>

  ...
</configuration>
Copy the code

SolverManager use

SolverManager is a facade for one or more Solver instances to simplify the resolution of planning problems in REST and other enterprise services. With the Solver. Solve (…). The method is different.

SolverManager.solve(…) Return now: It arranges the problem for asynchronous solution without blocking the calling thread. This avoids the timeouts of HTTP and other technologies.

SolverManager.solve(…) Multiple planning problems in the same domain can be solved in parallel.

Internally, SolverManager manages a call to solver.solve (…) Solver thread pool, and a consumer thread pool that handles best solution change events.

In Spring Boot, instances of SolverManager are automatically injected into the code. Otherwise, use create(…) Method to create an instance of SolverManager.

SolverConfig solverConfig = SolverConfig.createFromXmlResource("... /cloudBalancingSolverConfig.xml");
SolverManager<CloudBalance, UUID> solverManager = SolverManager.create(solverConfig, new SolverManagerConfig());
Copy the code

Submitted to SolverManager. Solve (…). Each problem for a method requires a unique problemId. Future calls to getSolverStatus(problemId) or terminateEarly(problemId) will use the problemId to distinguish planning problems. ProblemId must be an immutable class, such as Long, String, or java.util.uuid.

The SolverManagerConfig class has a parallelSolverCount property that controls how many solvers are run in parallel. For example, if set to 4, four problems are resolved immediately when five problems are submitted, and the fifth problem starts at the end of another problem. If these problems are solved for 5 minutes each, the fifth problem takes 10 minutes to complete. By default, parallelSolverCount is set to AUTO, which solves half the CPU core, independent of the solver’s moveThreadCount.

To go after the best solution, after the expiration of the solver is normal, using SolverJob. GetFinalBestSolution ().

CloudBalance problem1 = ... ; UUID problemId = UUID.randomUUID();// Returns immediatelySolverJob<CloudBalance, UUID> solverJob = solverManager.solve(problemId, problem1); . CloudBalance solution1;try {
    // Returns only after solving terminates
    solution1 = solverJob.getFinalBestSolution();
} catch (InterruptedException | ExecutionException e) {
    throw. ; }Copy the code

Bulk solution

To solve multiple datasets in parallel (constrained by parallelSolverCount), a call to solve() is required for each dataset.

public class TimeTableService {

    private SolverManager<TimeTable, Long> solverManager;

    // Return immediately and call it for each dataset
    public void solveBatch(Long timeTableId) {
        solverManager.solve(timeTableId,
                // called once, when the solution starts
                this::findById,
                // call once, when the solution is finished
                this::save);
    }

    public TimeTable findById(Long timeTableId) {... }public void save(TimeTable timeTable) {...}

}
Copy the code

Solution monitoring

When the solver runs, the end user is waiting for the solution, and the user may have to wait for minutes or hours to receive a result. To show the user that everything is going well, you can show progress by showing the best solution and the best score achieved so far.

To handle the best solution in the middle, you can use solveAndListen().

public class TimeTableService {

    private SolverManager<TimeTable, Long> solverManager;

    // Return immediately
    public void solveLive(Long timeTableId) {
        solverManager.solveAndListen(timeTableId,
                // called once, when the solution starts
                this::findById,
                // called multiple times, each change to the best solution is called
                this::save);
    }

    public TimeTable findById(Long timeTableId) {... }public void save(TimeTable timeTable) {... }public void stopSolving(Long timeTableId) { solverManager.terminateEarly(timeTableId); }}Copy the code

If satisfied with the best solution is in the middle, and don’t want to wait for a better solution, call SolverManager. TerminateEarly (problemId) end.

conclusion

This chapter mainly studied the use of Solver. It is recommended to use SolverManager in the subsequent use. This section on environment configuration is somewhat difficult to understand and will be explained separately later.

homework

You can use today’s SolverManger in the previous examples to get the hang of it.

conclusion

In the next chapter, we will study the most important part, the writing of constraint scoring rules, and it is relatively complex.

Creation is not easy, unauthorized reprint is prohibited. Like/like/follow my post if it helps you ❤❤❤❤❤❤