Can I run a custom phase generating an initial solution several times to generate a pool of starting solutions?

user_381281 0
Viewed 63

I’m using Optaplanner 8.15.0 to solve a variant of the redistricting problem: Geographic areas with an expected revenue are assembled to sales districts that must be contiguous and should be balanced and compact.

The initial solution is generated by a custom phase using a greedy heuristic. Afterwards a local search hill climbing phase makes big and obvious improvements to that using custom moves. Only then, the “real” optimization starts with a tabu search.

The configuration of the first two phases:

<customPhase>
    <customPhaseCommandClass>project.solver.SeedGrowthInitialSolution</customPhaseCommandClass>
</customPhase>
<localSearch>
    <localSearchType>HILL_CLIMBING</localSearchType>
    <moveListFactory>
        <moveListFactoryClass>project.move.SplitAndJoinMoveFactory</moveListFactoryClass>
    </moveListFactory>
    <termination>
        <unimprovedSecondsSpentLimit>60</unimprovedSecondsSpentLimit>
    </termination>
</localSearch>

It turned out that the quality (=score) of the overall solution depends very much on the quality of the initial solution after the second phase. I.e. the tabu search will improve the solution substantially, but it’s not able to “fix” a bad initial solution.

Is there a way to run the first two phases repeatedly to generate several candidate solutions and then continue with the best of them?

My current workaround is to start several instances manually, watch the logs for the achieved scores after the first two phases and restart all instances where the initial scores are not promising.

optaplanner heuristics
1 Answers

The answer is no, when the problem is specified like this. However, we could maybe change the problem statement a bit. If you run multiple independent solvers and, at the end, pick the best result, you can then pass that to a new solver which will start from there. This would be a variant of multi-bet solving. It is not supported out of the box, but would be relatively easy to code yourself, using either the Solver or SolverManager APIs.

That said, your entire approach is very unconventional. Custom construction heuristic is understandable, as are custom moves. But the fact that you feel the need to separate the moves into different phases makes me curious. Have you benchmarked this to be the best possible approach?

I would think that using the default local search (late acceptance), with your custom moves and our generic moves all thrown into the mix, would yield decent results already. If that fails to happen, then generally either your constraints need to be faster, or the solver needs to run for longer. For large problems, multi-threaded solving can help, too.

user_67940630
Related