JaCoP.constraints.netflow.simplex
Class NetworkSimplex

java.lang.Object
  JaCoP.constraints.netflow.simplex.NetworkSimplex

Direct Known Subclasses:

Network

public class NetworkSimplex
extends java.lang.Object

Version:

3.1

Author:

Robin Steiger and Radoslaw Szymanek

Field Summary

java.util.List<Arc>	allArcs
Arc	blocking
static boolean	DEBUG
static boolean	DEBUG_ALL
static int	DELETED_ARC
java.util.Set<Node>	infeasibleNodes
static int	LARGE_COST
Arc[]	lower
Node[]	nodes
int	numArcs
Node	root
static int	TREE_ARC

Constructor Summary

NetworkSimplex(java.util.List<Node> nodes, java.util.List<Arc> arcs)

Method Summary

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

Methods inherited from class java.lang.Object

equals, 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 Node root

nodes

public final Node[] nodes

lower

public final Arc[] lower

numArcs

public int numArcs

blocking

public Arc blocking

infeasibleNodes

public final java.util.Set<Node> infeasibleNodes

allArcs

public final java.util.List<Arc> allArcs

Constructor Detail

NetworkSimplex

public NetworkSimplex(java.util.List<Node> nodes,
                      java.util.List<Arc> arcs)

Method Detail

addArcWithFlow

public void addArcWithFlow(Arc arc)

removeArc

public void removeArc(Arc arc)

networkSimplex

public int networkSimplex(int maxPivots)

Parameters:

maxPivots -

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 -

sink -

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