Class NetworkSimplex

java.lang.Object
org.jacop.constraints.netflow.simplex.NetworkSimplex
Direct Known Subclasses:
Network

public class NetworkSimplex extends Object
Version:
4.10
  • Field Details

  • Constructor Details

    • NetworkSimplex

      public NetworkSimplex(List<Node> nodes, List<Arc> arcs)
  • Method Details

    • 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