#include <routing_filters.h>

Classes
struct	ExtendedInterval

struct	Interval

Public Member Functions
	DimensionChecker (const PathState *path_state, std::vector< Interval > path_capacity, std::vector< int > path_class, std::vector< std::function< Interval(int64_t, int64_t)> > demand_per_path_class, std::vector< Interval > node_capacity, int min_range_size_for_riq=kOptimalMinRangeSizeForRIQ)

bool	Check () const

void	Commit ()

Static Public Attributes
static constexpr int	kOptimalMinRangeSizeForRIQ = 4

Detailed Description

This checker enforces dimension requirements. A dimension requires that there is some valuation of cumul and demand such that for all paths:

cumul[A] is in interval node_capacity[A]
if arc A -> B is on a path of path_class p, then cumul[A] + demand[p](A, B) = cumul[B].
if A is on a path of class p, then cumul[A] must be inside interval path_capacity[path].

Definition at line 472 of file routing_filters.h.

Constructor & Destructor Documentation

◆ DimensionChecker()

operations_research::DimensionChecker::DimensionChecker	(	const PathState *	path_state,
		std::vector< Interval >	path_capacity,
		std::vector< int >	path_class,
		std::vector< std::function< Interval(int64_t, int64_t)> >	demand_per_path_class,
		std::vector< Interval >	node_capacity,
		int	min_range_size_for_riq = kOptimalMinRangeSizeForRIQ )

Todo: (user): the addition of kMinRangeSizeForRIQ slowed down Check(). See if using a template parameter makes it faster.

Definition at line 3907 of file routing_filters.cc.

Member Function Documentation

◆ Check()

bool operations_research::DimensionChecker::Check ( ) const

Given the change made in PathState, checks that the dimension constraint is still feasible.

Loop invariant: except for the first chain, cumul represents the cumul state of the last node of the previous chain, and it is nonempty.

Bring cumul state from last node of previous chain to first node of current chain.

Bring cumul state from first node to last node of the current chain.

Use a RIQ if the chain size is large enough; the optimal size was found with the associated benchmark in tests, in particular BM_DimensionChecker<ChangeSparsity::kSparse, *>.

Definition at line 3932 of file routing_filters.cc.

◆ Commit()

void operations_research::DimensionChecker::Commit ( )

Commits to the changes made in PathState, must be called before PathState::Commit().

Definition at line 3993 of file routing_filters.cc.

Member Data Documentation

◆ kOptimalMinRangeSizeForRIQ

int operations_research::DimensionChecker::kOptimalMinRangeSizeForRIQ = 4

staticconstexpr

Definition at line 504 of file routing_filters.h.

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

ortools/constraint_solver/routing_filters.h
ortools/constraint_solver/routing_filters.cc

Classes

Public Member Functions

Static Public Attributes