operations_research::CumulBoundsPropagator Class Reference

#include <routing_lp_scheduling.h>

Public Member Functions
	CumulBoundsPropagator (const RoutingDimension *dimension)
bool	PropagateCumulBounds (const std::function< int64_t(int64_t)> &next_accessor, int64_t cumul_offset, const std::vector< RoutingModel::RouteDimensionTravelInfo > *dimension_travel_info_per_route=nullptr)
int64_t	CumulMin (int index) const
int64_t	CumulMax (int index) const
const RoutingDimension &	dimension () const

Detailed Description

Classes to solve dimension cumul placement (aka scheduling) problems using linear programming. Utility class used in the core optimizer to tighten the cumul bounds as much as possible based on the model precedences.

Definition at line 57 of file routing_lp_scheduling.h.

Constructor & Destructor Documentation

CumulBoundsPropagator()

operations_research::CumulBoundsPropagator::CumulBoundsPropagator ( const RoutingDimension * dimension )

explicit

Definition at line 316 of file routing_lp_scheduling.cc.

Member Function Documentation

CumulMax()

int64_t operations_research::CumulBoundsPropagator::CumulMax ( int index ) const

inline

Definition at line 77 of file routing_lp_scheduling.h.

CumulMin()

int64_t operations_research::CumulBoundsPropagator::CumulMin ( int index ) const

inline

Definition at line 73 of file routing_lp_scheduling.h.

dimension()

const RoutingDimension & operations_research::CumulBoundsPropagator::dimension ( ) const

inline

Definition at line 84 of file routing_lp_scheduling.h.

PropagateCumulBounds()

bool operations_research::CumulBoundsPropagator::PropagateCumulBounds	(	const std::function< int64_t(int64_t)> &	next_accessor,
		int64_t	cumul_offset,
		const std::vector< RoutingModel::RouteDimensionTravelInfo > *	dimension_travel_info_per_route = nullptr )

Tightens the cumul bounds starting from the current cumul var min/max, and propagating the precedences resulting from the next_accessor, and the dimension's precedence rules. Returns false iff the precedences are infeasible with the given routes. Otherwise, the user can call CumulMin() and CumulMax() to retrieve the new bounds of an index.

Bellman-Ford-Tarjan algorithm.

The parent of this node is still in the queue, so no need to process node now, since it will be re-enqueued when its parent is processed.

Note

kint64min as a lower bound means no lower bound at all, so we don't use this value to propagate.

No update necessary for the head_node, continue to next children of node.

The new lower bound is infeasible, or a positive cycle was detected in the precedence graph by DisassembleSubtree().

Definition at line 492 of file routing_lp_scheduling.cc.

---

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

• ortools/constraint_solver/routing_lp_scheduling.h
• ortools/constraint_solver/routing_lp_scheduling.cc