search

google / or-tools

Google's Operations Research tools:
https://developers.google.com/optimization/
Apache License 2.0
11.27k stars 2.13k forks source link

(some?) search parameters ignored when starting with initial solution #4273

Closed huib closed 5 months ago

huib commented 5 months ago

What version of OR-Tools and what language are you using? Version: v9.10 (also observed with v9.9) Language: Java

Which solver are you using (e.g. CP-SAT, Routing Solver, GLOP, BOP, Gurobi) Routing Solver

What operating system (Linux, Windows, ...) and version? Linux: openSUSE Leap

What did you do? Run the following code (based on this example, modified search parameters based on this example)

import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.*;
import com.google.protobuf.Duration;

import java.util.logging.Logger;

/** Minimal VRP. */
public class ORToolsMWE {
    private static final Logger logger = Logger.getLogger(ORToolsMWE.class.getName());

    static class DataModel {
        public final long[][] distanceMatrix = {
                {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662},
                {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210},
                {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754},
                {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358},
                {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244},
                {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708},
                {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480},
                {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856},
                {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514},
                {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468},
                {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354},
                {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844},
                {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730},
                {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536},
                {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194},
                {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798},
                {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0},
        };
        public final long[][] initialRoutes = {
                {8, 16, 14, 13, 12, 11},
                {3, 4, 9, 10},
                {15, 1},
                {7, 5, 2, 6},
        };
        public final int vehicleNumber = 4;
        public final int depot = 0;
    }

    /// @brief Print the solution.
    static void printSolution(
            DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
        // Solution cost.
        logger.info("Objective : " + solution.objectiveValue());
        // Inspect solution.
        long maxRouteDistance = 0;
        for (int i = 0; i < data.vehicleNumber; ++i) {
            long index = routing.start(i);
            logger.info("Route for Vehicle " + i + ":");
            long routeDistance = 0;
            String route = "";
            while (!routing.isEnd(index)) {
                route += manager.indexToNode(index) + " -> ";
                long previousIndex = index;
                index = solution.value(routing.nextVar(index));
                routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
            }
            logger.info(route + manager.indexToNode(index));
            logger.info("Distance of the route: " + routeDistance + "m");
            maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
        }
        logger.info("Maximum of the route distances: " + maxRouteDistance + "m");
    }

    public static void main(String[] args) throws Exception {
        Loader.loadNativeLibraries();
        // Instantiate the data problem.
        final DataModel data = new DataModel();

        // Create Routing Index Manager
        RoutingIndexManager manager =
                new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);

        // Create Routing Model.
        RoutingModel routing = new RoutingModel(manager);

        // Create and register a transit callback.
        final int transitCallbackIndex =
                routing.registerTransitCallback((long fromIndex, long toIndex) -> {
                    // Convert from routing variable Index to user NodeIndex.
                    int fromNode = manager.indexToNode(fromIndex);
                    int toNode = manager.indexToNode(toIndex);
                    return data.distanceMatrix[fromNode][toNode];
                });

        // Define cost of each arc.
        routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

        // Add Distance constraint.
        routing.addDimension(transitCallbackIndex, 0, 3000,
                true, // start cumul to zero
                "Distance");
        RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
        distanceDimension.setGlobalSpanCostCoefficient(100);

        Assignment initialSolution = routing.readAssignmentFromRoutes(data.initialRoutes, true);
        logger.info("Initial solution:");
        printSolution(data, routing, manager, initialSolution);

        // Setting first solution heuristic.
        //RoutingSearchParameters searchParameters = main.defaultRoutingSearchParameters();
        RoutingSearchParameters searchParameters =
                main.defaultRoutingSearchParameters()
                        .toBuilder()
                        .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
                        .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
                        .setTimeLimit(Duration.newBuilder().setSeconds(5).build())
                        .build();

        // Solve the problem.
        Assignment solution = routing.solveFromAssignmentWithParameters(
                initialSolution, searchParameters);

        // Print solution on console.
        logger.info("Solution after search:");
        printSolution(data, routing, manager, solution);
    }
}

What did you expect to see The solver runs for approximately 5 seconds.

What did you see instead? The solver runs for less than 1 second.

Edit lines 97-99 to:

        Assignment initialSolution = null; //routing.readAssignmentFromRoutes(data.initialRoutes, true);
//        logger.info("Initial solution:");
//        printSolution(data, routing, manager, initialSolution);

and observe that now the solver does run for 5 seconds as expected.

lperron commented 5 months ago

run closeWithParameters() then just solveFromAssignment()

Mizux commented 5 months ago

IIRC routing.readAssignmentFromRoutes will close the model aka will fix some search parameters to default values.

ref: https://github.com/google/or-tools/blob/b09c17227f0d633b3641e23ede0f2bda52aa7f3c/ortools/constraint_solver/routing.cc#L3814-L3817

huib commented 5 months ago

Thanks for the suggestions. I tried it, and it has an effect. Though, not the one I expected or desired. But eventually I figured it out.

I tried calling routing.closeWithParameters(searchParameters) before reading the initial solution, and after reading the initial solution calling routing.solve(initialSolution). Now the solving process doesn't terminate (I let it run for 8+ minutes while the timeout was set to 5 seconds). Maybe it was set to guided local search, but the timelimit wasn't included? Including or excluding the call to readAssignmentFromRoutes doesn't change this behaviour.

If I use both routing.closeWithParameters(searchParameters) and routing.solveFromAssignmentWithParameters(initialSolution, searchParameters) all works as expected. Including or excluding the call to readAssignmentFromRoutes doesn't change this behaviour.

I see here that some parameters need to be set upon closing the model, and seeing the results of my experiments, some parameters need to be set when calling solve(). I'm not sure which parameters should be set when closing the model and which when starting the solve, but it's easier to just give all parameters in both places anyway.

I see now that the Python and C++ examples (complete code) here indeed specify the search parameters before reading the initial solution as well as when calling solve. The Java and C# examples do not.

For completeness, here's the working code now:

import com.google.ortools.Loader;
import com.google.ortools.constraintsolver.*;
import com.google.protobuf.Duration;

import java.util.logging.Logger;

/** Minimal VRP. */
public class ORToolsMWE {
    private static final Logger logger = Logger.getLogger(ORToolsMWE.class.getName());

    static class DataModel {
        public final long[][] distanceMatrix = {
                {0, 548, 776, 696, 582, 274, 502, 194, 308, 194, 536, 502, 388, 354, 468, 776, 662},
                {548, 0, 684, 308, 194, 502, 730, 354, 696, 742, 1084, 594, 480, 674, 1016, 868, 1210},
                {776, 684, 0, 992, 878, 502, 274, 810, 468, 742, 400, 1278, 1164, 1130, 788, 1552, 754},
                {696, 308, 992, 0, 114, 650, 878, 502, 844, 890, 1232, 514, 628, 822, 1164, 560, 1358},
                {582, 194, 878, 114, 0, 536, 764, 388, 730, 776, 1118, 400, 514, 708, 1050, 674, 1244},
                {274, 502, 502, 650, 536, 0, 228, 308, 194, 240, 582, 776, 662, 628, 514, 1050, 708},
                {502, 730, 274, 878, 764, 228, 0, 536, 194, 468, 354, 1004, 890, 856, 514, 1278, 480},
                {194, 354, 810, 502, 388, 308, 536, 0, 342, 388, 730, 468, 354, 320, 662, 742, 856},
                {308, 696, 468, 844, 730, 194, 194, 342, 0, 274, 388, 810, 696, 662, 320, 1084, 514},
                {194, 742, 742, 890, 776, 240, 468, 388, 274, 0, 342, 536, 422, 388, 274, 810, 468},
                {536, 1084, 400, 1232, 1118, 582, 354, 730, 388, 342, 0, 878, 764, 730, 388, 1152, 354},
                {502, 594, 1278, 514, 400, 776, 1004, 468, 810, 536, 878, 0, 114, 308, 650, 274, 844},
                {388, 480, 1164, 628, 514, 662, 890, 354, 696, 422, 764, 114, 0, 194, 536, 388, 730},
                {354, 674, 1130, 822, 708, 628, 856, 320, 662, 388, 730, 308, 194, 0, 342, 422, 536},
                {468, 1016, 788, 1164, 1050, 514, 514, 662, 320, 274, 388, 650, 536, 342, 0, 764, 194},
                {776, 868, 1552, 560, 674, 1050, 1278, 742, 1084, 810, 1152, 274, 388, 422, 764, 0, 798},
                {662, 1210, 754, 1358, 1244, 708, 480, 856, 514, 468, 354, 844, 730, 536, 194, 798, 0},
        };
        public final long[][] initialRoutes = {
                {8, 16, 14, 13, 12, 11},
                {3, 4, 9, 10},
                {15, 1},
                {7, 5, 2, 6},
        };
        public final int vehicleNumber = 4;
        public final int depot = 0;
    }

    /// @brief Print the solution.
    static void printSolution(
            DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
        // Solution cost.
        logger.info("Objective : " + solution.objectiveValue());
        // Inspect solution.
        long maxRouteDistance = 0;
        for (int i = 0; i < data.vehicleNumber; ++i) {
            long index = routing.start(i);
            logger.info("Route for Vehicle " + i + ":");
            long routeDistance = 0;
            String route = "";
            while (!routing.isEnd(index)) {
                route += manager.indexToNode(index) + " -> ";
                long previousIndex = index;
                index = solution.value(routing.nextVar(index));
                routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
            }
            logger.info(route + manager.indexToNode(index));
            logger.info("Distance of the route: " + routeDistance + "m");
            maxRouteDistance = Math.max(routeDistance, maxRouteDistance);
        }
        logger.info("Maximum of the route distances: " + maxRouteDistance + "m");
    }

    public static void main(String[] args) throws Exception {
        Loader.loadNativeLibraries();
        // Instantiate the data problem.
        final DataModel data = new DataModel();

        // Create Routing Index Manager
        RoutingIndexManager manager =
                new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);

        // Create Routing Model.
        RoutingModel routing = new RoutingModel(manager);

        // Create and register a transit callback.
        final int transitCallbackIndex =
                routing.registerTransitCallback((long fromIndex, long toIndex) -> {
                    // Convert from routing variable Index to user NodeIndex.
                    int fromNode = manager.indexToNode(fromIndex);
                    int toNode = manager.indexToNode(toIndex);
                    return data.distanceMatrix[fromNode][toNode];
                });

        // Define cost of each arc.
        routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);

        // Add Distance constraint.
        routing.addDimension(transitCallbackIndex, 0, 3000,
                true, // start cumul to zero
                "Distance");
        RoutingDimension distanceDimension = routing.getMutableDimension("Distance");
        distanceDimension.setGlobalSpanCostCoefficient(100);

        RoutingSearchParameters searchParameters =
                main.defaultRoutingSearchParameters()
                        .toBuilder()
                        .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
                        .setLocalSearchMetaheuristic(LocalSearchMetaheuristic.Value.GUIDED_LOCAL_SEARCH)
                        .setTimeLimit(Duration.newBuilder().setSeconds(5).build())
                        .build();

        routing.closeModelWithParameters(searchParameters);

        Assignment initialSolution = routing.readAssignmentFromRoutes(data.initialRoutes, true);
        logger.info("Initial solution:");
        printSolution(data, routing, manager, initialSolution);

        // Solve the problem.
        Assignment solution = routing.solveFromAssignmentWithParameters(
                initialSolution, searchParameters);

        // Print solution on console.
        logger.info("Solution after search:");
        printSolution(data, routing, manager, solution);
    }
}
Mizux commented 5 months ago

IIRC some search parameter are reset to default some others no...

did few tests long time ago but forget to write down an exhaustive list of how each parameters behave against closing model et "resolve" from an initial solution

Mizux commented 5 months ago

https://github.com/google/or-tools/blob/b09c17227f0d633b3641e23ede0f2bda52aa7f3c/ortools/constraint_solver/samples/vrp_initial_routes.py#L139-L157