Adding Penalty causes invalid solution

[pardeep632]

I am using java version of CVRP solver. below is the complete code:

public class CapacityConstranit {
    static {
        System.loadLibrary("jniortools");
    }
    static class DataModel {
        public final long[][] distanceMatrix = {
                {0, 40, 30, 50},
                {0, 0, 50, 30},
                {0, 50, 0, 40},
                {0, 30, 40, 0},
        };
        public final long[] demands = {0, 40, 30, 50};
        public final long[] vehicleCapacities = {25, 40, 60};
        public final int vehicleNumber = 3;
        public final int depot = 0;
    }
    public void solve() throws Exception {
        final DataModel data = new DataModel();
        RoutingIndexManager manager =
                new RoutingIndexManager(data.distanceMatrix.length, data.vehicleNumber, data.depot);
        RoutingModel routing = new RoutingModel(manager);
        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];
                });
        routing.setArcCostEvaluatorOfAllVehicles(transitCallbackIndex);
        final int demandCallbackIndex = routing.registerUnaryTransitCallback((long fromIndex) -> {
            // Convert from routing variable Index to user NodeIndex.
            int fromNode = manager.indexToNode(fromIndex);
            return data.demands[fromNode];
        });
        routing.addDimensionWithVehicleCapacity(demandCallbackIndex, 0, // null capacity slack
                data.vehicleCapacities, // vehicle maximum capacities
                true, // start cumul to zero
                "Capacity");

        // Allow to drop nodes.
        long penalty = 300;
        for (int i = 1; i < data.distanceMatrix.length; ++i) {
            routing.addDisjunction(new long[] {manager.nodeToIndex(i)}, penalty);
        }

        // Setting first solution heuristic.
        RoutingSearchParameters searchParameters =
                main.defaultRoutingSearchParameters()
                        .toBuilder()
                        .setFirstSolutionStrategy(FirstSolutionStrategy.Value.PATH_CHEAPEST_ARC)
                        .build();

        // Solve the problem.
        Assignment solution = routing.solveWithParameters(searchParameters);
        printSolution(data, routing, manager, solution);
    }

void printSolution(
            DataModel data, RoutingModel routing, RoutingIndexManager manager, Assignment solution) {
        // Inspect solution.
        long totalDistance = 0;
        long totalLoad = 0;
        for (int i = 0; i < data.vehicleNumber; ++i) {
            long index = routing.start(i);
            System.out.println("Route for Vehicle " + i + ":");
            long routeDistance = 0;
            long routeLoad = 0;
            String route = "";
            while (!routing.isEnd(index)) {
                long nodeIndex = manager.indexToNode(index);
                routeLoad += data.demands[(int) nodeIndex];
                route += nodeIndex + " Load(" + routeLoad + ") -> ";
                long previousIndex = index;
                index = solution.value(routing.nextVar(index));
                routeDistance += routing.getArcCostForVehicle(previousIndex, index, i);
            }
            route += manager.indexToNode(routing.end(i));
            System.out.println(route);
            System.out.println("Distance of the route: " + routeDistance + "m");
            totalDistance += routeDistance;
            totalLoad += routeLoad;
        }
        System.out.println("Total distance of all routes: " + totalDistance + "m");
        System.out.println("Total load of all routes: " + totalLoad);
    }
}

Case 1: I the program i have 3 locations to be served. As we see demands are {0, 40, 30, 50} and vehicle capacities are {25,40,60}.

As we see total capacity = 25+40+60 = 125 total demand = 0+40+30+50 = 120 The obvious cheapest path solution is : vehicle 1 -> location 1(load 40) , vehicle 2 -> location 2(load 30). Location 3 remains unserved as remaining capacity of 25 (vehicle 0) not able to serve location 3 (load 50).

Now before running the solver we know that our total capacity is more than total demand , Ideally we assume that all locations will be served. But the following program returns a null solution if i do not add the penalties. If i add penalties the solver works fine and returns the solution as mentioned above. So here i think penalties works for me .

Case 2 But if i modify the input data model a bit like just change the capacity of vehicle 0 from 25 to 30. So we have new capacities {30,40,60}. Now all three locations are serviceable. The obvious solution would be : vehicle 0 -> location 2(load 30) , vehicle 1 -> location 1(load 40) , vehicle 2 -> location 2(load 50).

But the solver gives: vehicle 2 -> location 2(load 30) , vehicle 1 -> location 1(load 40) And keeps the vehicle 0 unused.

And i have mentioned before in Case 1 that penalties are added to each location. So now if i comment the code for adding penalties for this case , then the solver starts giving the expected result. i.e it assigns all vehicles, each to one location.

Now the problem is that, adding penalties works if solvers finds no solution and adding penalty gives wrong solution when there exist a proper solution. And since before submitting to solver we do not know if the problem requires penalties to be added or not. So i am not able to decide if i should use penalties or not .

[lperron]

Why is this a wrong solution?

[pardeep632]

@Iperron In case 2 : there are two scenarios: a. penalty for each node is defined : Here the solver gives - vehicle 2 -> location 2(load 30) , vehicle 1 -> location 1(load 40) And keeps the vehicle 0 unused.

b. no penalty defined for any node: here the solver gives - vehicle 0 -> location 2(load 30) , vehicle 1 -> location 1(load 40) , vehicle 2 -> location 2(load 50).

so basically for same data input , solvers gives two solutions one of which is right (b) and one is wrong (a).

SO what i have understood so far is that , if penalties are defined for each node and solver does not need to drop any nodes , then solver will give wrong solution in some cases as shown above (a).

[pardeep632]

In short

if (total demand at all nodes > total capacity of all vehicles) {
     define penalties for all nodes
     call capacity solver 
     solver gives proper solution with some nodes left unserved
} else {
    total demand is less than total capacity of all vehicles
    so ideally there is no need of defining penalties for nodes
    call capacity solver 
    solver works for all data where  all nodes are serviceable .But it fails when all nodes are not serviceable like : demands are {0, 40, 30, 50} and vehicle capacities are {25,40,60}. total capacity exceeds total demand (125 > 120)
but still all nodes can not be served. So if i call solver with this input it gives null solution.

Now define penalties
use this input data: demands are {0, 40, 30, 50} and vehicle capacities are {25,40,60}. its same as above
call capacity solver.
it gives a proper solution i.e now it does not give null solutiion.

now since penalties are defined 
use this input data: demands are {0, 40, 30, 50} and vehicle capacities are {30,40,60}.
all nodes are serviceable.
call capacity solver
but solver fails it gives a path which serves only two nodes.

now again remove the penalties
use same input  data in the last example i.e : demands are {0, 40, 30, 50} and vehicle capacities are {30,40,60}.
all nodes are serviceable.
call capacity solver
now solver works and gives a path which covers all nodes.

from above three example , i can not decide when to use penalties and when not to use them

}