Package org.jacop.constraints.netflow.simplex

Class NetworkSimplex

  • Direct Known Subclasses:
    Network
    public class NetworkSimplex
extends java.lang.Object
    Version:
    4.8

    • Constructor Detail

      • NetworkSimplex

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

    • Method Detail

      • incrementDegree

        private void incrementDegree​(Node node,
                             Arc myArc)

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