org.jacop.constraints.netflow.simplex

Class NetworkSimplex

java.lang.Object

org.jacop.constraints.netflow.simplex.NetworkSimplex

Direct Known Subclasses:

Network

public class NetworkSimplex
extends Object

Version:

4.9

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<org.jacop.constraints.netflow.simplex.Node>	infeasibleNodes
static int	LARGE_COST
Arc[]	lower
org.jacop.constraints.netflow.simplex.Node[]	nodes
int	numArcs
protected PivotRule	pivotRule
org.jacop.constraints.netflow.simplex.Node	root
static int	TREE_ARC

Constructor Summary

Constructors

Constructor and Description
NetworkSimplex(List<org.jacop.constraints.netflow.simplex.Node> nodes, List<Arc> arcs)

Method Summary

Modifier and Type	Method and Description
protected void	addArc(Arc arc)
void	addArcWithFlow(Arc arc)
int	augmentFlow(org.jacop.constraints.netflow.simplex.Node from, org.jacop.constraints.netflow.simplex.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(org.jacop.constraints.netflow.simplex.Node source, org.jacop.constraints.netflow.simplex.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(org.jacop.constraints.netflow.simplex.Node a, org.jacop.constraints.netflow.simplex.Node b, org.jacop.constraints.netflow.simplex.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

See Also:

Constant Field Values

DEBUG_ALL

public static final boolean DEBUG_ALL

See Also:

Constant Field Values

LARGE_COST

public static final int LARGE_COST

See Also:

Constant Field Values

TREE_ARC

public static final int TREE_ARC

See Also:

Constant Field Values

DELETED_ARC

public static final int DELETED_ARC

See Also:

Constant Field Values

root

public final org.jacop.constraints.netflow.simplex.Node root

nodes

public final org.jacop.constraints.netflow.simplex.Node[] nodes

lower

public final Arc[] lower

numArcs

public int numArcs

blocking

public Arc blocking

pivotRule

protected final PivotRule pivotRule

infeasibleNodes

public final Set<org.jacop.constraints.netflow.simplex.Node> infeasibleNodes

allArcs

public final List<Arc> allArcs

Constructor Detail

NetworkSimplex

public NetworkSimplex(List<org.jacop.constraints.netflow.simplex.Node> nodes,
                      List<Arc> arcs)

Method Detail

addArc

protected void addArc(Arc arc)

Parameters:

arc - the network arc being added

addArcWithFlow

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(org.jacop.constraints.netflow.simplex.Node from,
                       org.jacop.constraints.netflow.simplex.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(org.jacop.constraints.netflow.simplex.Node a,
                     org.jacop.constraints.netflow.simplex.Node b,
                     org.jacop.constraints.netflow.simplex.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(org.jacop.constraints.netflow.simplex.Node source,
                          org.jacop.constraints.netflow.simplex.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