Stopping and restarting the solving process helps finding better solutions

user_7586818 0
Viewed 48

My colleague and I successfully implemented an exam scheduler based on OptaPlanner as our bachelor thesis. However, we noticed that the solver gets stuck during the local search phase for hours, and stopping/restarting the solving process helps find new solutions a lot. I think this behavior is due to how we handle new best solutions. In fact, we only save better solutions, as illustrated in the example graphic below. In the local search phase, we use "Step Counting Hill Climbing" with stepCountingHillClimbingSize = 400 and stepCountingHillClimbingSize = 1.

The dashed arrows indicate to which solution the new solution is compared. When the solving process is stopped at step 7 and restarted, the solution from step 5 is loaded. Whereas, if the solving process is not interrupted, the solution from step 7 becomes the reference solution. I think this process adds some randomness. How can I add this behaviour with OptaPlanner? Is this the same problem as described in OptaPlanner immediately produces better solution after terminating and restarting the solver?

enter image description here

solverConfig.xml

<?xml version="1.0" encoding="UTF-8" standalone="no"?>
<solver xmlns="https://www.optaplanner.org/xsd/solver">
    <!--TODO: enable for real production use - gives a small performance boost. See: https://docs.optaplanner.org/latest/optaplanner-docs/html_single/index.html#environmentModeProduction-->
    <!--<environmentMode>NON_REPRODUCIBLE</environmentMode>-->
    <moveThreadCount>AUTO</moveThreadCount>
    <solutionClass>ch.ost.examscheduler.solvers.opta.domain.ExamTimetable</solutionClass>
    <entityClass>ch.ost.examscheduler.solvers.opta.domain.Exam</entityClass>
    <scoreDirectorFactory>
        <constraintProviderClass>ch.ost.examscheduler.solvers.opta.solver.constraints.TimeTableConstraintProvider
        </constraintProviderClass>
        <constraintStreamImplType>DROOLS</constraintStreamImplType>
        <initializingScoreTrend>ONLY_DOWN/ONLY_DOWN</initializingScoreTrend>
    </scoreDirectorFactory>
    <constructionHeuristic>
        <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
    </constructionHeuristic>
    <localSearch>
        <unionMoveSelector>
            <cacheType>PHASE</cacheType>
            <changeMoveSelector>
                <filterClass>ch.ost.examscheduler.solvers.opta.solver.filters.AllRoomsUnassignedChangeMoveFilter
                </filterClass>
            </changeMoveSelector>
        </unionMoveSelector>
        <acceptor>
            <stepCountingHillClimbingSize>400</stepCountingHillClimbingSize>
        </acceptor>
        <forager>
            <acceptedCountLimit>1</acceptedCountLimit>
        </forager>
    </localSearch>
</solver>
optaplanner
1 Answers

Yea, we've seen this in some other use cases too. The default local search type, Late Acceptance can benefit from a restart in some use case. Such a restart is called reheating. We have an issue open to implement reheating.

It looks bad - but usually the gain of the reheat is a rounding error - and the result is still much better than what you'd fine elsewhere. But especially on small datasets, where other solvers might do better, it's a pain.

Meanwhile, a workaround (a manual reheat) is to configure the localSearch phase twice and put an unimproved time termination on the fist localSearch phase of 30 seconds or so. But what if it gets stuck twice?

user_4721090
Related