Solver is too slow

Question

I am still using the OptaPlanner to optimize a chained planning problem which is similar to the VehicleRoutingExample. My planning entities have a planning variable which is another planning entity. The scores are HardSoftScores, which are calculated with an IncrementalScore.

At the moment I have the problem that the time the solver needs is still too long to find an acceptable solution.

I want to optimize a problem with a fixed number of workers, who have to process a fixed number of orders with several time windows.

The orders are my chained entities and the workers are used as anchors for the chains. I am calculating the start and end points of time for the orders by a listener. Another listener is saving the anchor of each chain in every entity (because it needs to much time to go through a chain which could be longer than 1000 entities….)

My aim is to solve a problem with something about 3000 entities at the moment the solver needs more than 2 hours to get an acceptable solution. For a smaller problem with 400 entities it needs nearly 5min which is too long too. 10 min for the bigger problem 10min would be okay, for the small one 1min.

I have already worked with the benchmarker to find the best solver config…

Does anybody see some possibilities to make my solver faster?

P.S.: Is der an opportunity to use multithreadning?, or does the optaplanner already use it?

Answer 1

Take a look at nearby selection in 6.2.0.CR2 (and CR1 too).

It's only partially documented yet... And not for all move types yet (just change and swap moves)... Be patient. But it's insanely better once you get to 2K entities and more. Without it, it's even worse than the worst ones on this graph:

Here's a quick and dirty copy and paste of one of my local benchmarks:

<#list [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 5000] as linearDistributionSizeMaximum>
  <solverBenchmark>
    <name>LA Nearby LinDist max${linearDistributionSizeMaximum}</name>
    <solver>
        <constructionHeuristic>
            <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
        </constructionHeuristic>
        <localSearch>
            <unionMoveSelector>
                <changeMoveSelector>
                    <entitySelector id="entitySelector1"/>
                    <valueSelector>
                        <nearbySelection>
                            <originEntitySelector mimicSelectorRef="entitySelector1"/>
                            <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
                            <linearDistributionSizeMaximum>${linearDistributionSizeMaximum}</linearDistributionSizeMaximum>
                        </nearbySelection>
                    </valueSelector>
                </changeMoveSelector>
                <swapMoveSelector>
                    <entitySelector id="entitySelector2"/>
                    <secondaryEntitySelector>
                        <nearbySelection>
                            <originEntitySelector mimicSelectorRef="entitySelector2"/>
                            <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
                            <linearDistributionSizeMaximum>${linearDistributionSizeMaximum}</linearDistributionSizeMaximum>
                        </nearbySelection>
                    </secondaryEntitySelector>
                </swapMoveSelector>
            </unionMoveSelector>
            <acceptor>
                <lateAcceptanceSize>200</lateAcceptanceSize>
            </acceptor>
            <forager>
                <acceptedCountLimit>1</acceptedCountLimit>
            </forager>
        </localSearch>
    </solver>
  </solverBenchmark>
</#list>
<#list [10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 150, 200, 5000] as parabolicDistributionSizeMaximum>
  <solverBenchmark>
    <name>LA Nearby ParDist max${parabolicDistributionSizeMaximum}</name>
    <solver>
        <constructionHeuristic>
            <constructionHeuristicType>FIRST_FIT_DECREASING</constructionHeuristicType>
        </constructionHeuristic>
        <localSearch>
            <unionMoveSelector>
                <changeMoveSelector>
                    <entitySelector id="entitySelector1"/>
                    <valueSelector>
                        <nearbySelection>
                            <originEntitySelector mimicSelectorRef="entitySelector1"/>
                            <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
                            <parabolicDistributionSizeMaximum>${parabolicDistributionSizeMaximum}</parabolicDistributionSizeMaximum>
                        </nearbySelection>
                    </valueSelector>
                </changeMoveSelector>
                <swapMoveSelector>
                    <entitySelector id="entitySelector2"/>
                    <secondaryEntitySelector>
                        <nearbySelection>
                            <originEntitySelector mimicSelectorRef="entitySelector2"/>
                            <nearbyDistanceMeterClass>org.optaplanner.examples.vehiclerouting.domain.solver.nearby.CustomerNearbyDistanceMeter</nearbyDistanceMeterClass>
                            <parabolicDistributionSizeMaximum>${parabolicDistributionSizeMaximum}</parabolicDistributionSizeMaximum>
                        </nearbySelection>
                    </secondaryEntitySelector>
                </swapMoveSelector>
            </unionMoveSelector>
            <acceptor>
                <lateAcceptanceSize>200</lateAcceptanceSize>
            </acceptor>
            <forager>
                <acceptedCountLimit>1</acceptedCountLimit>
            </forager>
        </localSearch>
    </solver>
  </solverBenchmark>
</#list>