Class NetworkSimplex
java.lang.Object
org.jacop.constraints.netflow.simplex.NetworkSimplex
- Direct Known Subclasses:
Network
- Version:
- 4.10
-
Field Summary
Fields -
Constructor Summary
Constructors -
Method Summary
Modifier and TypeMethodDescriptionprotected void
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
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
void
TODO prove (or disprove) correctnessvoid
updateTree
(Arc leaving, Arc entering) TODO prove (or disprove) correctness (and efficiency)
-
Field Details
-
DEBUG
public static final boolean DEBUG- See Also:
-
DEBUG_ALL
public static final boolean DEBUG_ALL- See Also:
-
LARGE_COST
public static final int LARGE_COST- See Also:
-
TREE_ARC
public static final int TREE_ARC- See Also:
-
DELETED_ARC
public static final int DELETED_ARC- See Also:
-
root
-
nodes
-
lower
-
numArcs
public int numArcs -
blocking
-
pivotRule
-
infeasibleNodes
-
allArcs
-
-
Constructor Details
-
NetworkSimplex
-
-
Method Details
-
incrementDegree
-
decrementDegree
-
addArc
- Parameters:
arc
- the network arc being added
-
addArcWithFlow
-
removeArc
-
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
Performs a primal pivot.- Parameters:
entering
- a non-tree arc that violates optimality
-
augmentFlow
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
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
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
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
-
cost
public long cost(long cutoff) -
print
public void print()Debug
-