#include <min_cost_flow.h>

Inheritance diagram for operations_research::SimpleMinCostFlow:

Public Types
typedef int32_t	NodeIndex

typedef int32_t	ArcIndex

typedef int64_t	FlowQuantity

typedef int64_t	CostValue

Public Types inherited from operations_research::MinCostFlowBase
enum	Status { NOT_SOLVED , OPTIMAL , FEASIBLE , INFEASIBLE , UNBALANCED , BAD_RESULT , BAD_COST_RANGE , BAD_CAPACITY_RANGE }

Public Member Functions
	SimpleMinCostFlow (NodeIndex reserve_num_nodes=0, ArcIndex reserve_num_arcs=0)

	SimpleMinCostFlow (const SimpleMinCostFlow &)=delete
	This type is neither copyable nor movable.

SimpleMinCostFlow &	operator= (const SimpleMinCostFlow &)=delete

ArcIndex	AddArcWithCapacityAndUnitCost (NodeIndex tail, NodeIndex head, FlowQuantity capacity, CostValue unit_cost)

void	SetArcCapacity (ArcIndex arc, FlowQuantity capacity)

void	SetNodeSupply (NodeIndex node, FlowQuantity supply)

Status	Solve ()

Status	SolveMaxFlowWithMinCost ()

CostValue	OptimalCost () const

FlowQuantity	MaximumFlow () const

FlowQuantity	Flow (ArcIndex arc) const

NodeIndex	NumNodes () const

ArcIndex	NumArcs () const

NodeIndex	Tail (ArcIndex arc) const

NodeIndex	Head (ArcIndex arc) const

FlowQuantity	Capacity (ArcIndex arc) const

FlowQuantity	Supply (NodeIndex node) const

CostValue	UnitCost (ArcIndex arc) const

void	SetPriceScaling (bool value)

Detailed Description

A simple and efficient min-cost flow interface. This is as fast as GenericMinCostFlow<ReverseArcStaticGraph>, which is the fastest, but is uses more memory in order to hide the somewhat involved construction of the static graph.

Todo: (user): If the need arises, extend this interface to support warm start and incrementality between solves. Note that this is already supported by the GenericMinCostFlow<> interface.

Definition at line 258 of file min_cost_flow.h.

Member Typedef Documentation

◆ ArcIndex

typedef int32_t operations_research::SimpleMinCostFlow::ArcIndex

Definition at line 261 of file min_cost_flow.h.

◆ CostValue

typedef int64_t operations_research::SimpleMinCostFlow::CostValue

Definition at line 263 of file min_cost_flow.h.

◆ FlowQuantity

typedef int64_t operations_research::SimpleMinCostFlow::FlowQuantity

Definition at line 262 of file min_cost_flow.h.

◆ NodeIndex

typedef int32_t operations_research::SimpleMinCostFlow::NodeIndex

Definition at line 260 of file min_cost_flow.h.

Constructor & Destructor Documentation

◆ SimpleMinCostFlow() [1/2]

operations_research::SimpleMinCostFlow::SimpleMinCostFlow	(	NodeIndex	reserve_num_nodes = 0,
		ArcIndex	reserve_num_arcs = 0 )

explicit

By default, the constructor takes no size. New node indices are created lazily by AddArcWithCapacityAndUnitCost() or SetNodeSupply() such that the set of valid nodes will always be [0, NumNodes()).

You may pre-reserve the internal data structures with a given expected number of nodes and arcs, to potentially gain performance.

Definition at line 1014 of file min_cost_flow.cc.

◆ SimpleMinCostFlow() [2/2]

operations_research::SimpleMinCostFlow::SimpleMinCostFlow ( const SimpleMinCostFlow & )

delete

This type is neither copyable nor movable.

Member Function Documentation

◆ AddArcWithCapacityAndUnitCost()

SimpleMinCostFlow::ArcIndex operations_research::SimpleMinCostFlow::AddArcWithCapacityAndUnitCost	(	NodeIndex	tail,
		NodeIndex	head,
		FlowQuantity	capacity,
		CostValue	unit_cost )

Adds a directed arc from tail to head to the underlying graph with a given capacity and cost per unit of flow.

Node indices and the capacity must be non-negative (>= 0).
The unit cost can take any integer value (even negative).
Self-looping and duplicate arcs are supported.
After the method finishes, NumArcs() == the returned ArcIndex + 1.

Definition at line 1034 of file min_cost_flow.cc.

◆ Capacity()

SimpleMinCostFlow::FlowQuantity operations_research::SimpleMinCostFlow::Capacity ( ArcIndex arc ) const

Definition at line 1203 of file min_cost_flow.cc.

◆ Flow()

SimpleMinCostFlow::FlowQuantity operations_research::SimpleMinCostFlow::Flow ( ArcIndex arc ) const

Returns the flow on arc, this only make sense for a successful Solve().

Note: It is possible that there is more than one optimal solution. The algorithm is deterministic so it will always return the same solution for a given problem. However, there is no guarantee of this from one code version to the next (but the code does not change often).

Definition at line 1182 of file min_cost_flow.cc.

◆ Head()

SimpleMinCostFlow::ArcIndex operations_research::SimpleMinCostFlow::Head ( ArcIndex arc ) const

Definition at line 1199 of file min_cost_flow.cc.

◆ MaximumFlow()

SimpleMinCostFlow::FlowQuantity operations_research::SimpleMinCostFlow::MaximumFlow ( ) const

Returns the total flow of the minimum-cost flow found by the algorithm when the returned Status is OPTIMAL.

Definition at line 1178 of file min_cost_flow.cc.

◆ NumArcs()

SimpleMinCostFlow::ArcIndex operations_research::SimpleMinCostFlow::NumArcs ( ) const

Definition at line 1191 of file min_cost_flow.cc.

◆ NumNodes()

SimpleMinCostFlow::SimpleMinCostFlow::NodeIndex operations_research::SimpleMinCostFlow::NumNodes ( ) const

Accessors for the user given data. The implementation will crash if "arc" is not in [0, NumArcs()) or "node" is not in [0, NumNodes()).

Definition at line 1186 of file min_cost_flow.cc.

◆ operator=()

SimpleMinCostFlow & operations_research::SimpleMinCostFlow::operator= ( const SimpleMinCostFlow & )

delete

◆ OptimalCost()

SimpleMinCostFlow::CostValue operations_research::SimpleMinCostFlow::OptimalCost ( ) const

Returns the cost of the minimum-cost flow found by the algorithm when the returned Status is OPTIMAL.

Definition at line 1174 of file min_cost_flow.cc.

◆ SetArcCapacity()

void operations_research::SimpleMinCostFlow::SetArcCapacity	(	ArcIndex	arc,
		FlowQuantity	capacity )

Modifies the capacity of the given arc. The arc index must be non-negative (>= 0); it must be an index returned by a previous call to AddArcWithCapacityAndUnitCost().

Definition at line 1046 of file min_cost_flow.cc.

◆ SetNodeSupply()

void operations_research::SimpleMinCostFlow::SetNodeSupply	(	NodeIndex	node,
		FlowQuantity	supply )

Sets the supply of the given node. The node index must be non-negative (>= 0). Nodes implicitly created will have a default supply set to 0. A demand is modeled as a negative supply.

Definition at line 1029 of file min_cost_flow.cc.

◆ SetPriceScaling()

void operations_research::SimpleMinCostFlow::SetPriceScaling ( bool value )

inline

Advanced usage. The default is true.

Without cost scaling, the algorithm will return a 1-optimal solution to the given problem. The solution will be an optimal solution to a perturbed problem where some of the arc unit costs are changed by at most 1.

If the cost are initially integer and we scale them by (num_nodes + 1), then we can show that such 1-optimal solution is actually optimal. This is what happen by default or when SetPriceScaling(true) is called.

However, if your cost were originally double, you don't really care to solve optimally a problem where the weights are approximated in the first place. It is better to multiply your double by a scaling_factor (prefer a power of 2) so that the maximum rounded arc unit cost is under kint64max / (num_nodes + 1) to prevent any overflow. You can then solve without any cost scaling. The final result will be the optimal to a problem were the unit cost of some arc as been changed by at most 1 / scaling_factor.

Definition at line 360 of file min_cost_flow.h.

◆ Solve()

Status operations_research::SimpleMinCostFlow::Solve ( )

inline

Solves the problem, and returns the problem status. This function requires that the sum of all node supply minus node demand is zero and that the graph has enough capacity to send all supplies and serve all demands. Otherwise, it will return INFEASIBLE.

Definition at line 304 of file min_cost_flow.h.

◆ SolveMaxFlowWithMinCost()

Status operations_research::SimpleMinCostFlow::SolveMaxFlowWithMinCost ( )

inline

Same as Solve(), but does not have the restriction that the supply must match the demand or that the graph has enough capacity to serve all the demand or use all the supply. This will compute a maximum-flow with minimum cost. The value of the maximum-flow will be given by MaximumFlow().

Definition at line 313 of file min_cost_flow.h.

◆ Supply()

SimpleMinCostFlow::FlowQuantity operations_research::SimpleMinCostFlow::Supply ( NodeIndex node ) const

Definition at line 1212 of file min_cost_flow.cc.

◆ Tail()

SimpleMinCostFlow::ArcIndex operations_research::SimpleMinCostFlow::Tail ( ArcIndex arc ) const

Definition at line 1195 of file min_cost_flow.cc.

◆ UnitCost()

SimpleMinCostFlow::CostValue operations_research::SimpleMinCostFlow::UnitCost ( ArcIndex arc ) const

Definition at line 1208 of file min_cost_flow.cc.

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

ortools/graph/min_cost_flow.h
ortools/graph/min_cost_flow.cc

Public Types

Public Member Functions

Detailed Description

Member Typedef Documentation

◆ ArcIndex

◆ CostValue

◆ FlowQuantity

◆ NodeIndex

Constructor & Destructor Documentation

◆ SimpleMinCostFlow() [1/2]

◆ SimpleMinCostFlow() [2/2]

Member Function Documentation

◆ AddArcWithCapacityAndUnitCost()

◆ Capacity()

◆ Flow()

◆ Head()

◆ MaximumFlow()

◆ NumArcs()

◆ NumNodes()

◆ operator=()

◆ OptimalCost()

◆ SetArcCapacity()

◆ SetNodeSupply()

◆ SetPriceScaling()

◆ Solve()

◆ SolveMaxFlowWithMinCost()

◆ Supply()

◆ Tail()

◆ UnitCost()