 |
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
|
Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
|
Helper to compute the minimum flow going out of a subset of nodes, for a given RoutesConstraint.
Definition at line 408 of file routing_cuts.h.
#include <routing_cuts.h>
Public Member Functions | |
| MinOutgoingFlowHelper (int num_nodes, const std::vector< int > &tails, const std::vector< int > &heads, const std::vector< Literal > &literals, Model *model) | |
| ~MinOutgoingFlowHelper () | |
| int | ComputeDimensionBasedMinOutgoingFlow (absl::Span< const int > subset, const RouteRelationsHelper &helper, BestBoundHelper *best_bound) |
| int | ComputeMinOutgoingFlow (absl::Span< const int > subset) |
| int | ComputeTightMinOutgoingFlow (absl::Span< const int > subset) |
| bool | SubsetMightBeServedWithKRoutes (int k, absl::Span< const int > subset, RouteRelationsHelper *helper=nullptr, LinearConstraintManager *manager=nullptr, int special_node=-1, bool use_forward_direction=true) |
| absl::Span< const int > | CannotBeLast () const |
| absl::Span< const int > | CannotBeFirst () const |
| void | ReportDpSkip () |
| Just for stats reporting. | |
| operations_research::sat::MinOutgoingFlowHelper::MinOutgoingFlowHelper | ( | int | num_nodes, |
| const std::vector< int > & | tails, | ||
| const std::vector< int > & | heads, | ||
| const std::vector< Literal > & | literals, | ||
| Model * | model ) |
Definition at line 116 of file routing_cuts.cc.
| operations_research::sat::MinOutgoingFlowHelper::~MinOutgoingFlowHelper | ( | ) |
Definition at line 139 of file routing_cuts.cc.
|
inline |
Definition at line 470 of file routing_cuts.h.
|
inline |
Advanced. If non-empty, and one of the functions above proved that a subset needs at least k vehicles to serve it, then these vector list the nodes that cannot be first (resp. last) in one of the solution with k routes. If a node is listed here, it means we will need at least k + 1 routes to serve the subset and enter (resp. leave) from that node.
This can be used to either reduce the size of the subset and still need k vehicles, or generate stronger cuts.
Definition at line 469 of file routing_cuts.h.
| int operations_research::sat::MinOutgoingFlowHelper::ComputeDimensionBasedMinOutgoingFlow | ( | absl::Span< const int > | subset, |
| const RouteRelationsHelper & | helper, | ||
| BestBoundHelper * | best_bound ) |
Returns the minimum flow going out of subset, based on a generalization of the CVRP "rounded capacity inequalities", by using the given helper, if possible. The complexity is O((subset.size() + num_arcs()) * num_dimensions()).
Definition at line 202 of file routing_cuts.cc.
| int operations_research::sat::MinOutgoingFlowHelper::ComputeMinOutgoingFlow | ( | absl::Span< const int > | subset | ) |
Returns the minimum flow going out of subset, based on a conservative estimate of the maximum number of nodes of a feasible path inside this subset. subset must not be empty and must not contain the depot (node 0). Paths are approximated by their length and their last node, and can thus contain cycles. The complexity is O(subset.size() ^ 3).
Conservatively assume that each subset node is reachable from outside.
Maximum number of nodes of a feasible path inside the subset.
If this arc cannot be taken skip.
This is the first arc that reach this node.
Combine information with previous one.
The maximum number of distinct paths of length longest_path_length.
Reset the temporary data structures for the next call.
Definition at line 603 of file routing_cuts.cc.
| int operations_research::sat::MinOutgoingFlowHelper::ComputeTightMinOutgoingFlow | ( | absl::Span< const int > | subset | ) |
Same as above, but uses less conservative estimates (paths are approximated by their set of nodes and their last node – hence they can't contain cycles). The complexity is O(2 ^ subset.size()).
We remove it from the hash_map since this entry should no longer be used as we create path of increasing length.
We have found a feasible path, update the path length statistics...
... and try to extend the path with each arc going out of its last node.
If this arc cannot be taken skip.
We have a feasible path to a new state.
We found another way to reach this state, only keep common best bounds.
Definition at line 710 of file routing_cuts.cc.
|
inline |
Just for stats reporting.
Definition at line 473 of file routing_cuts.h.
| bool operations_research::sat::MinOutgoingFlowHelper::SubsetMightBeServedWithKRoutes | ( | int | k, |
| absl::Span< const int > | subset, | ||
| RouteRelationsHelper * | helper = nullptr, | ||
| LinearConstraintManager * | manager = nullptr, | ||
| int | special_node = -1, | ||
| bool | use_forward_direction = true ) |
Returns false if the given subset CANNOT be served by k routes. Returns true if we have a route or we don't know for sure (if we abort). The parameter k must be positive.
Even more costly algo in O(n!/k!*k^(n-k)) that answers the question exactly given the available enforced linear1 and linear2 constraints. However it can stop as soon as one solution is found.
If special_node is non-negative, we will only look for routes that
If the RouteRelationsHelper is non null, then we will use "shortest path" bounds instead of recomputing them from the binary relation of the model.
If we have a "special node" from which we must start, make sure it is always first. This simplifies the code a bit, and we don't care about the order of nodes in subset.
Make the span point to the new order.
We need a special graph here to handle both options.
Bit i is set iif node subset[i] is in one of the current routes.
The last nodes of each of the k routes. If the hamming weight is less that k, then at least one route is still empty.
Valid lower bounds for this state.
By "dimensions", we mean the number of variables appearing in binary relation controlled by an arc literal. See for instance RouteRelationsHelper that also uses a similar definition.
Hopefully the DFS order limit the number of entry to O(n^2 * k), so still somewhat reasonable for small values.
The sum of the reduced costs of all the literals selected to form the route(s) encoded by this state. If this becomes too large we know that this state can never be used to get to a better solution than the current best one and is thus "infeasible" for the problem of finding a better solution.
This is also correlated to the work done, and we abort if we starts to do too much work on one instance.
We just do a DFS from the initial state.
If a state has an unique arc to enter/leave it, we can update it further.
We always start with the first node in this case.
If there is a unique way to enter (resp. leave) that subset, we can start with tighter bounds!
The number of routes is the hamming weight of from_state.last_nodes_set.
We start by choosing the first k starts (in increasing order). For that we only add after the maximum position already chosen.
All "initial-state" start with empty hash-map that correspond to the level zero bounds.
We have k routes, extend one of the last nodes.
Use reduced costs to exclude solutions that cannot improve our current best solution.
We start from the old bounds and update them.
One of the last node has no arc to outside, this is not possible.
Add the constraints implied by each last node that has an unique way to leave the subset.
We explored everything, no way to serve this with only k routes!
Definition at line 789 of file routing_cuts.cc.
1.14.0