Google OR-Tools v9.14
a fast and portable software suite for combinatorial optimization
Loading...
Searching...
No Matches
operations_research::SimpleMinCostFlow Class Reference

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.

#include <min_cost_flow.h>

Inheritance diagram for operations_research::SimpleMinCostFlow:
operations_research::MinCostFlowBase

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)

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

◆ Capacity()

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

Definition at line 1205 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 1184 of file min_cost_flow.cc.

◆ Head()

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

Definition at line 1201 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 1180 of file min_cost_flow.cc.

◆ NumArcs()

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

Definition at line 1193 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 1188 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 1176 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 1048 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 1031 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 1214 of file min_cost_flow.cc.

◆ Tail()

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

Definition at line 1197 of file min_cost_flow.cc.

◆ UnitCost()

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

Definition at line 1210 of file min_cost_flow.cc.

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