AddDisjunction function does not work like it supposed #1348
Comments
|
To repeat the forum posts here a little bit. The disjunctions by themselves aren't the problem. The problem comes when there is some sort of binary flip flop between one state and another. Here we want to choose one of two vehicles. The idea is a truck by itself, or a truck with a trailer---obviously you can't drive both. This is accomplished by the lines: for veh_pair in range(0, num_veh//2):
combo = veh_pair*2
single = veh_pair*2 + 1
index_combo = routing.End(combo)
index_single = routing.End(single)
end_time_combo = time_dimension.CumulVar(index_combo)
end_time_single = time_dimension.CumulVar(index_single)
combo_on = end_time_combo > 0
single_on = end_time_single > 0
solver.Add(combo_on * single_on == 0)This works, but only without disjunctions. So if the problem has more destinations than can be served by the vehicles, you need disjunctions to allow dropping of nodes. However, once you turn on disjunctions, the solver fails to find the correct solution. Attached code---disjunction_fail.zip---demonstrates the problem. See also my repo at https://github.com/jmarca/disjunction_tests. Running without disjunctions (the default) and with just 5 destinations, the solver does the right thing---uses two combo trucks, one with three visits, the other with two. Logging turned on to show the solver's progress. Run with disjunctions turned on, again with just 5 demand nodes, the solver fails. Instead of assigning all five as before, it decides to drop one node, no matter how large the penalty is. |
|
Any thoughts or comments on this? Is there something more I can do to clarify the issue? |
|
I can't speak for the original poster's bug, but my confirmation of it seems to be fixed. My possible solution is that I correctly added the "guided_local_search" flag, and it seems to be working now. Updated the python in my repo: https://github.com/jmarca/disjunction_tests/blob/master/disjunction_fail.py I have not tested all of the failing cases I found, but so far things seem to work. The fix: Previously I was using search_parameters.first_solution_strategy = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)Which is nonsense, but passes for some reason (I think because So, fixing that, search_parameters.first_solution_strategy = (
routing_enums_pb2.FirstSolutionStrategy.GLOBAL_CHEAPEST_ARC)
search_parameters.local_search_metaheuristic = (
routing_enums_pb2.LocalSearchMetaheuristic.GUIDED_LOCAL_SEARCH)
search_parameters.time_limit.seconds = 60 # timelimitAnd then the proper solution pops out |
lperron
added
Help Needed
|
Would it be possible to reopen this issue to update the documentation? I agree with @teemusanteri that the behavior of
The code below sets up a small CVRP with four customers and one vehicle of capacity 2. When I add a disjunction on To be clear, I do not suggest to change this behavior, as the functionality is great. However, it would be helpful to update the documentation to avoid confusion. Example code tested on ortools 9.10.4067 (simplified version of the CVRP example): """Capacited Vehicles Routing Problem (CVRP)."""
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["distance_matrix"] = [
# fmt: off
[0, 548, 776, 696, 582],
[548, 0, 684, 308, 194],
[776, 684, 0, 992, 878],
[696, 308, 992, 0, 114],
[582, 194, 878, 114, 0],
# fmt: on
]
data["demands"] = [0, 1, 1, 1, 1]
data["vehicle_capacities"] = [2]
data["num_vehicles"] = 1
data["depot"] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data["demands"][node_index]
plan_output += f" {node_index} Load({route_load}) -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
print(plan_output)
def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Add Capacity constraint.
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data["demands"][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data["vehicle_capacities"], # vehicle maximum capacities
True, # start cumul to zero
"Capacity",
)
### RELEVANT CODE ###
# add disjunction for all nodes with penalty 1
penalty = 1
max_cardinality = 4
routing.AddDisjunction([manager.NodeToIndex(node) for node in range(1, 5)], penalty, max_cardinality)
### RELEVANT CODE ###
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.time_limit.FromSeconds(1)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
print("Total penalty: {}".format(solution.ObjectiveValue()))
if __name__ == "__main__":
main() |
|
I agree the docs seem wrong.
From the C++ I see:
```cpp
IntVar* no_active_var = solver_->MakeBoolVar();
IntVar* number_active_vars = solver_->MakeIntVar(0, max_cardinality);
solver_->AddConstraint(
solver_->MakeSumEquality(disjunction_vars, number_active_vars));
solver_->AddConstraint(solver_->MakeIsDifferentCstCt(
number_active_vars, max_cardinality, no_active_var));
const int64_t penalty = disjunctions_[disjunction].value.penalty;
if (penalty < 0) {
no_active_var->SetMax(0);
return nullptr;
} else {
return solver_->MakeProd(no_active_var, penalty)->Var();
}
```
To me that looks like `no_active_var` is a 0/1 boolean that flags if the max cardinality is matched or not. So the penalty is multiplied by 1 or 0.
Regards,
James
…On Tue, May 21, 2024 at 07:39:49PM -0700, Kevin Dalmeijer wrote:
Would it be possible to reopen this issue to update the documentation? I agree with @teemusanteri that the behavior of `AddDisjunction()` does not match the documentation when `len(indices) > 1`. The [Python documentation](https://developers.google.com/optimization/reference/python/constraint_solver/pywrapcp#adddisjunction) and the [C++ documentation](https://github.com/google/or-tools/blob/stable/ortools/constraint_solver/routing.h#L889) both state:
> This is equivalent to adding the constraint: p + Sum(i)active[i] == max_cardinality where p is an integer variable, and the following cost to the cost function: p * penalty.
The code below sets up a small CVRP with four customers and one vehicle of capacity 2. When I add a disjunction on `[1, 2, 3, 4]` with `penalty=1` and `max_capacity=4`. I get the route `0 Load(0) -> 4 Load(1) -> 3 Load(2) -> 0 Load(2)` with penalty 1. However, based on the documentation I expected to see a penalty of 2, because `max_cardinality - Sum(i)active[i] = 2`.
To be clear, I do not suggest to change this behavior, as the functionality is great. However, it would be helpful to update the documentation to avoid confusion.
Example code tested on ortools 9.10.4067 (simplified version of the CVRP example):
```python
"""Capacited Vehicles Routing Problem (CVRP)."""
from ortools.constraint_solver import pywrapcp
def create_data_model():
"""Stores the data for the problem."""
data = {}
data["distance_matrix"] = [
# fmt: off
[0, 548, 776, 696, 582],
[548, 0, 684, 308, 194],
[776, 684, 0, 992, 878],
[696, 308, 992, 0, 114],
[582, 194, 878, 114, 0],
# fmt: on
]
data["demands"] = [0, 1, 1, 1, 1]
data["vehicle_capacities"] = [2]
data["num_vehicles"] = 1
data["depot"] = 0
return data
def print_solution(data, manager, routing, solution):
"""Prints solution on console."""
print(f"Objective: {solution.ObjectiveValue()}")
for vehicle_id in range(data["num_vehicles"]):
index = routing.Start(vehicle_id)
plan_output = f"Route for vehicle {vehicle_id}:\n"
route_distance = 0
route_load = 0
while not routing.IsEnd(index):
node_index = manager.IndexToNode(index)
route_load += data["demands"][node_index]
plan_output += f" {node_index} Load({route_load}) -> "
previous_index = index
index = solution.Value(routing.NextVar(index))
route_distance += routing.GetArcCostForVehicle(
previous_index, index, vehicle_id
)
plan_output += f" {manager.IndexToNode(index)} Load({route_load})\n"
print(plan_output)
def main():
"""Solve the CVRP problem."""
# Instantiate the data problem.
data = create_data_model()
# Create the routing index manager.
manager = pywrapcp.RoutingIndexManager(
len(data["distance_matrix"]), data["num_vehicles"], data["depot"]
)
# Create Routing Model.
routing = pywrapcp.RoutingModel(manager)
# Add Capacity constraint.
def demand_callback(from_index):
"""Returns the demand of the node."""
# Convert from routing variable Index to demands NodeIndex.
from_node = manager.IndexToNode(from_index)
return data["demands"][from_node]
demand_callback_index = routing.RegisterUnaryTransitCallback(demand_callback)
routing.AddDimensionWithVehicleCapacity(
demand_callback_index,
0, # null capacity slack
data["vehicle_capacities"], # vehicle maximum capacities
True, # start cumul to zero
"Capacity",
)
### RELEVANT CODE ###
# add disjunction for all nodes with penalty 1
penalty = 1
max_cardinality = 4
routing.AddDisjunction([manager.NodeToIndex(node) for node in range(1, 5)], penalty, max_cardinality)
### RELEVANT CODE ###
# Setting first solution heuristic.
search_parameters = pywrapcp.DefaultRoutingSearchParameters()
search_parameters.time_limit.FromSeconds(1)
# Solve the problem.
solution = routing.SolveWithParameters(search_parameters)
# Print solution on console.
if solution:
print_solution(data, manager, routing, solution)
print("Total penalty: {}".format(solution.ObjectiveValue()))
if __name__ == "__main__":
main()
```
--
Reply to this email directly or view it on GitHub:
#1348 (comment)
You are receiving this because you commented.
Message ID: ***@***.***>
--
James E. Marca
Activimetrics LLC
|
Mizux
added
the
Doc: Optimization Site
|
source of the ref doc: or-tools/ortools/constraint_solver/routing.h Lines 861 to 876 in c72e8bb and just to get syntax coloring of jmarca post (not working on email reply)... or-tools/ortools/constraint_solver/routing.cc Lines 1757 to 1771 in c72e8bb |
|
(I never noticed email replies do not support markdown. I'll keep that in mind in the future) |
Hi,
Adddisjunction does not work like it is documented.
See the forum topic:
https://groups.google.com/forum/m/?utm_medium=email&utm_source=footer#!msg/or-tools-discuss/703V05No26s/oQbpsPUCAgAJ
The text was updated successfully, but these errors were encountered: