operations_research::SimpleMinCostFlow Class Reference

#include <min_cost_flow.h>

Inheritance diagram for operations_research::SimpleMinCostFlow:

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

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

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 240 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 1020 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()

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 1040 of file min_cost_flow.cc.

Capacity()

FlowQuantity operations_research::SimpleMinCostFlow::Capacity

(

ArcIndex

arc

)

const

Definition at line 1192 of file min_cost_flow.cc.

Flow()

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 1180 of file min_cost_flow.cc.

Head()

ArcIndex operations_research::SimpleMinCostFlow::Head

(

ArcIndex

arc

)

const

Definition at line 1190 of file min_cost_flow.cc.

MaximumFlow()

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

ArcIndex operations_research::SimpleMinCostFlow::NumArcs

(

)

const

Definition at line 1186 of file min_cost_flow.cc.

NumNodes()

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 1184 of file min_cost_flow.cc.

operator=()

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

delete

OptimalCost()

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 1176 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 1035 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 332 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 276 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 285 of file min_cost_flow.h.

Supply()

FlowQuantity operations_research::SimpleMinCostFlow::Supply

(

NodeIndex

node

)

const

Definition at line 1200 of file min_cost_flow.cc.

Tail()

ArcIndex operations_research::SimpleMinCostFlow::Tail

(

ArcIndex

arc

)

const

Definition at line 1188 of file min_cost_flow.cc.

UnitCost()

CostValue operations_research::SimpleMinCostFlow::UnitCost

(

ArcIndex

arc

)

const

Definition at line 1196 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