#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)

int	ComputeMinOutgoingFlow (absl::Span< const int > subset)

int	ComputeTightMinOutgoingFlow (absl::Span< const int > subset)

Detailed Description

Helper to compute the minimum flow going out of a subset of nodes, for a given RoutesConstraint.

Definition at line 39 of file routing_cuts.h.

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 )

Definition at line 92 of file routing_cuts.cc.

Member Function Documentation

◆ 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.

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

Merge the bounds by variable and arc incoming to the last node of the path into bounds by variable, if possible, and check whether they are feasible or not.

If each arc which can reach the last node of the path enforces some lower bound for var, then the lower bound of var can be increased to the minimum of these arc-specific lower bounds (since at least one of these arcs must be selected to reach this node).

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.

lb(b.y) <= b.y <= ub(b.y) and lhs <= a.x + b.y <= rhs imply ceil((lhs - ub(b.y)) / a) <= x <= floor((rhs - lb(b.y)) / a)