Class NetworkSimplex
- java.lang.Object
-
- org.jacop.constraints.netflow.simplex.NetworkSimplex
-
- Direct Known Subclasses:
Network
public class NetworkSimplex extends java.lang.Object
- Version:
- 4.8
-
-
Field Summary
Fields Modifier and Type Field Description 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
protected PivotRule
pivotRule
Node
root
static int
TREE_ARC
-
Constructor Summary
Constructors Constructor Description NetworkSimplex(java.util.List<Node> nodes, java.util.List<Arc> arcs)
-
Method Summary
All Methods Instance Methods Concrete Methods Modifier and Type Method 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)
private void
decrementDegree(Node node)
boolean
dualPivot(Arc leaving)
private void
incrementDegree(Node node, Arc myArc)
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()
Debugvoid
removeArc(Arc arc)
void
treeSwap(Node a, Node b, Node c)
TODO prove (or disprove) correctnessvoid
updateTree(Arc leaving, Arc entering)
TODO prove (or disprove) correctness (and efficiency)
-
-
-
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
-
pivotRule
protected final PivotRule pivotRule
-
infeasibleNodes
public final java.util.Set<Node> infeasibleNodes
-
allArcs
public final java.util.List<Arc> allArcs
-
-
Method Detail
-
decrementDegree
private void decrementDegree(Node node)
-
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(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 flowto
- the sink of the flowdelta
- 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 treeentering
- the non-tree arc that enters the tree
-
treeSwap
public void treeSwap(Node a, Node b, Node c)
TODO prove (or disprove) correctnessTODO 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 ab
- the child nodec
- 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 nodesink
- sink nodebalance
- difference between in flow and out flow the flow to send from the source to the sinkmaxPivots
- 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
-
-