Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::sat::MinOutgoingFlowHelper Class Reference

Detailed Description

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.

Constructor & Destructor Documentation

◆ MinOutgoingFlowHelper()

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 )
Warning
The underlying tails/heads/literals might be resized from one call to the next of one of the functions here, so be careful.

Definition at line 116 of file routing_cuts.cc.

◆ ~MinOutgoingFlowHelper()

operations_research::sat::MinOutgoingFlowHelper::~MinOutgoingFlowHelper ( )

Definition at line 139 of file routing_cuts.cc.

Member Function Documentation

◆ CannotBeFirst()

absl::Span< const int > operations_research::sat::MinOutgoingFlowHelper::CannotBeFirst ( ) const
inline

Definition at line 470 of file routing_cuts.h.

◆ CannotBeLast()

absl::Span< const int > operations_research::sat::MinOutgoingFlowHelper::CannotBeLast ( ) const
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.

◆ ComputeDimensionBasedMinOutgoingFlow()

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.

◆ ComputeMinOutgoingFlow()

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.

Todo
(user): use has_incoming_arcs_from_outside_[] to be more precise.

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.

◆ ComputeTightMinOutgoingFlow()

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()).

Todo
(user): use has_incoming_arcs_from_outside_[] to skip some nodes.

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.

◆ ReportDpSkip()

void operations_research::sat::MinOutgoingFlowHelper::ReportDpSkip ( )
inline

Just for stats reporting.

Definition at line 473 of file routing_cuts.h.

◆ SubsetMightBeServedWithKRoutes()

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

  • Start at this special_node if use_forward_direction = true
  • End at this special_node if use_forward_direction = false

If the RouteRelationsHelper is non null, then we will use "shortest path" bounds instead of recomputing them from the binary relation of the model.

Todo
(user): the complexity also depends on the longest route and improves if routes fail quickly. Give a better estimate?

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.

Todo
(user): Maybe we should abstract that in a better way.

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.

Note
unlike the other algorithm here, we keep the collective bounds of all the nodes so far, so this is likely in O(longest_route * num_dimensions) which can take quite a lot of space.

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.


The documentation for this class was generated from the following files: