operations_research::sat::RouteRelationsHelper Class Reference

Detailed Description

Helper to store the result of DetectDimensionsAndCumulExpressions() and also recover and store bounds on (node_expr[head] - node_expr[tail]) for each arc (tail -> head) assuming the arc is taken.

Definition at line 116 of file routing_cuts.h.

#include <routing_cuts.h>

Classes
struct	HeadMinusTailBounds

Public Member Functions
	RouteRelationsHelper ()=default
	Visible for testing.
int	num_dimensions () const
	Returns the number of "dimensions", such as time or vehicle load.
int	num_nodes () const
int	num_arcs () const
const AffineExpression &	GetNodeExpression (int node, int dimension) const
	Returns the expression associated with the given node and dimension.
const HeadMinusTailBounds &	GetArcRelation (int arc, int dimension) const
bool	HasShortestPathsInformation () const
bool	PathExists (int tail, int head) const
bool	PropagateLocalBoundsUsingShortestPaths (const IntegerTrail &integer_trail, int tail, int head, const absl::flat_hash_map< IntegerVariable, IntegerValue > &input, absl::flat_hash_map< IntegerVariable, IntegerValue > *output) const
IntegerValue	GetArcOffsetLowerBound (int arc, int dimension, bool negate_expressions) const
void	RemoveArcs (absl::Span< const int > sorted_arc_indices)

Static Public Member Functions
static std::unique_ptr< RouteRelationsHelper >	Create (int num_nodes, const std::vector< int > &tails, const std::vector< int > &heads, const std::vector< Literal > &literals, absl::Span< const AffineExpression > flat_node_dim_expressions, const BinaryRelationRepository &binary_relation_repository, Model *model)

Constructor & Destructor Documentation

RouteRelationsHelper()

operations_research::sat::RouteRelationsHelper::RouteRelationsHelper ( )

default

Visible for testing.

Member Function Documentation

Create()

std::unique_ptr< RouteRelationsHelper > operations_research::sat::RouteRelationsHelper::Create ( int num_nodes, const std::vector< int > & tails, const std::vector< int > & heads, const std::vector< Literal > & literals, absl::Span< const AffineExpression > flat_node_dim_expressions, const BinaryRelationRepository & binary_relation_repository, Model * model )

static

Creates a RouteRelationsHelper for the given RoutesConstraint and associated binary relations. The vector flat_node_dim_expressions should be the result of DetectDimensionsAndCumulExpressions(). If it is empty, this returns nullptr.

Otherwise this stores it and also computes the tightest bounds we can on (node_expr[head] - node_expr[tail]) for each arc, assuming the arc is taken (its literal is true).

Definition at line 1720 of file routing_cuts.cc.

GetArcOffsetLowerBound()

IntegerValue operations_research::sat::RouteRelationsHelper::GetArcOffsetLowerBound	(	int	arc,
		int	dimension,
		bool	negate_expressions ) const

Returns the level zero lower bound of the offset between the (optionally negated) expressions associated with the head and tail of the given arc, and the given dimension.

Todo

(user): If level zero bounds got tighter since we precomputed the relation, we might want to recompute it again.

Definition at line 1753 of file routing_cuts.cc.

GetArcRelation()

const HeadMinusTailBounds & operations_research::sat::RouteRelationsHelper::GetArcRelation ( int arc, int dimension ) const

inline

Definition at line 163 of file routing_cuts.h.

GetNodeExpression()

const AffineExpression & operations_research::sat::RouteRelationsHelper::GetNodeExpression ( int node, int dimension ) const

inline

Returns the expression associated with the given node and dimension.

Definition at line 147 of file routing_cuts.h.

HasShortestPathsInformation()

bool operations_research::sat::RouteRelationsHelper::HasShortestPathsInformation ( ) const

inline

Definition at line 170 of file routing_cuts.h.

num_arcs()

int operations_research::sat::RouteRelationsHelper::num_arcs ( ) const

inline

Definition at line 142 of file routing_cuts.h.

num_dimensions()

int operations_research::sat::RouteRelationsHelper::num_dimensions ( ) const

inline

Returns the number of "dimensions", such as time or vehicle load.

Definition at line 136 of file routing_cuts.h.

num_nodes()

int operations_research::sat::RouteRelationsHelper::num_nodes ( ) const

inline

Definition at line 138 of file routing_cuts.h.

PathExists()

bool operations_research::sat::RouteRelationsHelper::PathExists ( int tail, int head ) const

inline

If any of the bound is at the maximum, then there is no path between tail and head.

Definition at line 176 of file routing_cuts.h.

PropagateLocalBoundsUsingShortestPaths()

bool operations_research::sat::RouteRelationsHelper::PropagateLocalBoundsUsingShortestPaths ( const IntegerTrail & integer_trail, int tail, int head, const absl::flat_hash_map< IntegerVariable, IntegerValue > & input, absl::flat_hash_map< IntegerVariable, IntegerValue > * output ) const

inline

head_expr >= tail_lb + head_minus_tail_lb;

Definition at line 189 of file routing_cuts.h.

RemoveArcs()

void operations_research::sat::RouteRelationsHelper::RemoveArcs

(

absl::Span< const int >

sorted_arc_indices

)

Definition at line 1761 of file routing_cuts.cc.

---

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

• ortools/sat/routing_cuts.h
• ortools/sat/routing_cuts.cc