org.jacop.constraints.netflow.simplex

## Class NetworkSimplex

• Direct Known Subclasses:
Network

```public class NetworkSimplex
extends Object```
Version:
4.6
Author:
Robin Steiger and Radoslaw Szymanek
• ### Field Summary

Fields
Modifier and Type Field and Description
`List<Arc>` `allArcs`
`Arc` `blocking`
`static boolean` `DEBUG`
`static boolean` `DEBUG_ALL`
`static int` `DELETED_ARC`
`Set<Node>` `infeasibleNodes`
`static int` `LARGE_COST`
`Arc[]` `lower`
`Node[]` `nodes`
`int` `numArcs`
`protected PivotRule` `pivotRule`
`Node` `root`
`static int` `TREE_ARC`
• ### Constructor Summary

Constructors
Constructor and Description
```NetworkSimplex(List<Node> nodes, List<Arc> arcs)```
• ### Method Summary

All Methods
Modifier and Type Method and Description
`protected void` `addArc(Arc arc)`
`void` `addArcWithFlow(Arc arc)`
`int` ```augmentFlow(Node from, Node to, int delta)```
Augments the flow between two nodes by the maximum amount along the unique tree path that connects these nodes.
`long` `cost(long cutoff)`
`boolean` `dualPivot(Arc leaving)`
`int` `networkSimplex(int maxPivots)`
`int` ```parametricStep(Node source, Node sink, int balance, int maxPivots)```
Given an optimal flow that satisfies all feasibility constraints except mass balance on two nodes, the parametric simplex algorithm tries to achieve feasibility while keeping the solution optimal.
`void` `primalStep(Arc entering)`
Performs a primal pivot.
`void` `print()`
Debug
`void` `removeArc(Arc arc)`
`void` ```treeSwap(Node a, Node b, Node c)```
TODO prove (or disprove) correctness
`void` ```updateTree(Arc leaving, Arc entering)```
TODO prove (or disprove) correctness (and efficiency)
• ### Methods inherited from class java.lang.Object

`clone, equals, finalize, getClass, hashCode, notify, notifyAll, toString, wait, wait, wait`
• ### Field Detail

• #### DEBUG

`public static final boolean DEBUG`
Constant Field Values
• #### DEBUG_ALL

`public static final boolean DEBUG_ALL`
Constant Field Values
• #### LARGE_COST

`public static final int LARGE_COST`
Constant Field Values
• #### TREE_ARC

`public static final int TREE_ARC`
Constant Field Values
• #### DELETED_ARC

`public static final int DELETED_ARC`
Constant Field Values
• #### root

`public final Node root`
• #### nodes

`public final Node[] nodes`
• #### lower

`public final Arc[] lower`
• #### numArcs

`public int numArcs`
• #### blocking

`public Arc blocking`
• #### pivotRule

`protected final PivotRule pivotRule`
• #### infeasibleNodes

`public final Set<Node> infeasibleNodes`
• #### allArcs

`public final List<Arc> allArcs`
• ### Constructor Detail

• #### NetworkSimplex

```public NetworkSimplex(List<Node> nodes,
List<Arc> arcs)```
• ### Method Detail

`protected void addArc(Arc arc)`
Parameters:
`arc` - the network arc being added

`public void addArcWithFlow(Arc arc)`
• #### removeArc

`public void removeArc(Arc arc)`
• #### networkSimplex

`public int networkSimplex(int maxPivots)`
Parameters:
`maxPivots` - max value of the pivot
Returns:
the number of pivots performed until optimality was reached, or -1 if the maximum number of pivots was reached.
• #### primalStep

`public void primalStep(Arc entering)`
Performs a primal pivot.
Parameters:
`entering` - a non-tree arc that violates optimality
• #### augmentFlow

```public int augmentFlow(Node from,
Node to,
int delta)```
Augments the flow between two nodes by the maximum amount along the unique tree path that connects these nodes.
Parameters:
`from` - the source of the flow
`to` - the sink of the flow
`delta` - an upper limit on the flow to send
Returns:
the actual flow that was sent. the blocking arc is 'returned' in the instance field 'blocking'.
• #### updateTree

```public void updateTree(Arc leaving,
Arc entering)```
TODO prove (or disprove) correctness (and efficiency)

Both arcs must form a cycle in the tree and point in the same direction on that cycle.

Parameters:
`leaving` - the tree arc that leaves the tree
`entering` - the non-tree arc that enters the tree
• #### treeSwap

```public void treeSwap(Node a,
Node b,
Node c)```
TODO prove (or disprove) correctness

TODO can be 'inlined' in updateTree (but that would decrease readability)

Changes the parent of a node and updates the thread data structure (This operation invalidates the depth values in the subtree)

Runs in O(T2) amortized time over all treeSwaps performed by an updateTree operation where T2 is the size of the subtree that is being reversed.

Parameters:
`a` - the old parent of a
`b` - the child node
`c` - the new parent of a
• #### parametricStep

```public int parametricStep(Node source,
Node sink,
int balance,
int maxPivots)```
Given an optimal flow that satisfies all feasibility constraints except mass balance on two nodes, the parametric simplex algorithm tries to achieve feasibility while keeping the solution optimal.

TODO do more tests TODO test whether non-feasibility can actually be detected due to the fact that we have 'artificial' arcs going to the root.

Parameters:
`source` - source node
`sink` - sink node
`balance` - difference between in flow and out flow the flow to send from the source to the sink
`maxPivots` - limits the number of dual pivots
Returns:
the number of pivots on success, -1 if the pivot limit was reached, -2 if the problem is infeasible
• #### dualPivot

`public boolean dualPivot(Arc leaving)`
• #### cost

`public long cost(long cutoff)`
• #### print

`public void print()`
Debug