Satsuma.NetworkSimplex Class Reference

Finds a minimum cost feasible circulation using the network simplex method. More...

Inheritance diagram for Satsuma.NetworkSimplex:

Public Member Functions
void	Clear ()
	Reverts the solver to its initial state. More...
long	Flow (Arc arc)
	Returns the amount currently circulating on an arc. More...
	NetworkSimplex (IGraph graph, Func< Arc, long > lowerBound=null, Func< Arc, long > upperBound=null, Func< Node, long > supply=null, Func< Arc, double > cost=null)
	Hint: use named arguments when calling this constructor. More...
void	Run ()
	Runs the algorithm until the problem is found to be infeasible, an optimal solution is found, or the objective is found to be unbounded. More...
void	Step ()
	Performs an iteration in the simplex algorithm. More...

Properties
Func< Arc, double >	Cost [get, set]
	The cost of sending a unit of circulation through an arc. More...
IEnumerable< KeyValuePair< Arc, long > >	Forest [get]
	Returns those arcs which belong to the basic forest. More...
IGraph	Graph [get, set]
Func< Arc, long >	LowerBound [get, set]
	The lower bound for the circulation. More...
SimplexState	State [get, set]
	The current execution state of the simplex algorithm. More...
Func< Node, long >	Supply [get, set]
	The desired difference of outgoing and incoming flow for a node. More...
Func< Arc, long >	UpperBound [get, set]
	The upper bound for the circulation. More...
IEnumerable< Arc >	UpperBoundArcs [get]
	Returns those arcs which are saturated (the flow equals to the upper bound), but are not in the basic forest. More...

Detailed Description

Finds a minimum cost feasible circulation using the network simplex method.

Lower/upper bounds and supply must be integral, but cost can be double. Edges are treated as directed arcs, but this is not a real restriction if, for all edges, lower bound + upper bound = 0.

Definition at line 50 of file NetworkSimplex.cs.

Constructor & Destructor Documentation

Satsuma.NetworkSimplex.NetworkSimplex	(	IGraph	graph,
		Func< Arc, long >	lowerBound = null,
		Func< Arc, long >	upperBound = null,
		Func< Node, long >	supply = null,
		Func< Arc, double >	cost = null
	)

Hint: use named arguments when calling this constructor.

Definition at line 94 of file NetworkSimplex.cs.

Member Function Documentation

void Satsuma.NetworkSimplex.Clear

(

)

Reverts the solver to its initial state.

Implements Satsuma.IClearable.

Definition at line 139 of file NetworkSimplex.cs.

long Satsuma.NetworkSimplex.Flow

(

Arc

arc

)

Returns the amount currently circulating on an arc.

Definition at line 116 of file NetworkSimplex.cs.

void Satsuma.NetworkSimplex.Run

(

)

Runs the algorithm until the problem is found to be infeasible, an optimal solution is found, or the objective is found to be unbounded.

Definition at line 371 of file NetworkSimplex.cs.

void Satsuma.NetworkSimplex.Step

(

)

Performs an iteration in the simplex algorithm.

Modifies the State field according to what happened.

Definition at line 251 of file NetworkSimplex.cs.

Property Documentation

Func<Arc, double> Satsuma.NetworkSimplex.Cost

getset

The cost of sending a unit of circulation through an arc.

Must be finite. If null is supplied in the constructor, then the constant 1.0 function is taken.

Definition at line 68 of file NetworkSimplex.cs.

IEnumerable<KeyValuePair<Arc, long> > Satsuma.NetworkSimplex.Forest

get

Returns those arcs which belong to the basic forest.

Definition at line 127 of file NetworkSimplex.cs.

IGraph Satsuma.NetworkSimplex.Graph

getset

Definition at line 52 of file NetworkSimplex.cs.

Func<Arc, long> Satsuma.NetworkSimplex.LowerBound

getset

The lower bound for the circulation.

long.MinValue means negative infinity (unbounded). If null is supplied in the constructor, then the constant 0 function is taken.

Definition at line 56 of file NetworkSimplex.cs.

SimplexState Satsuma.NetworkSimplex.State

getset

The current execution state of the simplex algorithm.

Definition at line 91 of file NetworkSimplex.cs.

Func<Node, long> Satsuma.NetworkSimplex.Supply

getset

The desired difference of outgoing and incoming flow for a node.

Must be finite. The sum must be zero for each graph component. If null is supplied in the constructor, then the constant 0 function is taken.

Definition at line 65 of file NetworkSimplex.cs.

Func<Arc, long> Satsuma.NetworkSimplex.UpperBound

getset

The upper bound for the circulation.

Must be greater or equal to the lower bound. long.MaxValue means positive infinity (unbounded). If null is supplied in the constructor, then the constant long.MaxValue function is taken.

Definition at line 61 of file NetworkSimplex.cs.

IEnumerable<Arc> Satsuma.NetworkSimplex.UpperBoundArcs

get

Returns those arcs which are saturated (the flow equals to the upper bound), but are not in the basic forest.

Definition at line 136 of file NetworkSimplex.cs.

---

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

• src/NetworkSimplex.cs