[Lemon-user] Network Simplex Initialisation (based on Bonneel's network_simplex_simple.h)

[Kovács Péter]

Hi Matthew,

I did not know about Bonneel's version of our code, but I'm glad to see 
such use cases as well.

Your approach for utilizing an initial flow is interesting, but I think 
some problems may arise and this implementation seems to be incorrect 
for me.

Let me note some issues without completeness:
   * The invariant of the network simplex algorithm requires that for 
each arc outside the current spanning tree, the flow value must be 
either at the lower bound or at the upper bound. If 
delta>initialValues_[i][j], then your code decreases the delta value and 
performs a non-saturating flow augmentation. It means that if delta>0, 
none of the arcs along the considered cycle will meet the above 
conditions, so none of them can be selected to be the leaving arc 
without violating the invariant.
   * If delta==initialValues_[i][j], then your code explicitly 
overwrites the change variable to false, but the leaving arc may not be 
same as the entering arc (if another arc is also saturated).
   * Are you sure that delta<initialValues_[i][j] case cannot occur?


 > I have tried initialising it to the optimal solution, and I still get
 > iterations in the while loop of the execution (i.e.
 > pivot.findEnteringArc() is true and change is true) and I can't quite
 > figure out why.

There can be different reasons for this:
   * maybe the "guided" iterations were performed incorrectly (see above)
   * or you observed so-called degenerate iterations in the while loop

Degeneracy is a well-known phenomenon in simplex methods. It is possible 
that a pivot step actually finds a cycle of zero residual capacity (i.e. 
delta == 0), and hence the flow cost cannot be decreased, only the 
spanning tree is modi
ed. You can easily check this by checking the 
value of the delta variable in these iterations. If you encounter 
positive delta values in the while loop, then something is surely wrong 
(either the flow was not optimal or the algorithm is incorrect).


Anyway, why is it important for you to start the algorithm with initial 
flow values? Merely for efficiency reasons? Maybe the algorithm is 
efficient enough without such guidance. Have you tried it?


If it is really important to consider the initial flow values, let me 
suggest an entirely different approach. You can transform the input of 
the algorithm, rather than the algorithm itself, which is an easier and 
safer way. For each arc e=(i,j) having d=initialValues_[i][j] > 0,
   * decrease the capacity of e with d
   * add a reverse arc e'=(j,i) to the graph with capacity d and cost 
equal to -cost[i][j]
Furthermore (assuming that the initial flow was feasible), set the 
supply/demand values to zero for each node.

If you find an optimal flow x in this modified graph and sum it with 
your initial flow, then you will get an optimal flow in the original 
graph. (The flow value for an arc e in the original graph should be set 
to initialValue[e] + x[e] - x[e'].)


I hope these thoughts help.


Best regards,
Péter




> Hello,
>
> I am basing myself on the network_simplex_simple.h code written by N.
> Bonneel (http://liris.cnrs.fr/~nbonneel/FastTransport/).
>
> I am developing an algorithm where I would need to initialise the
> network with already known flows.
> I want to input a 2D array of size (number of sources x number of sinks)
> and the network simplex to begin the algorithm with the flows in my 2D
> array.
>
> First, is there something similar already coded?
>
> If not, I gave it a try and here is what I did :
>
> My idea was to let the algorithm initialise the artificial arcs with the
> root, and before it runs the main execution loop, I do iterations where
> I set the entering arc and the amount by which the flow changes.
>
> initialValues_[i][j] : 2D array with initial flows with n0_ sources and
> n1_ sinks
>
> // EDIT IN THE START() FUNCTION
>
> template <typename PivotRuleImpl>
>          ProblemType start() {
>
> // BEGIN EDIT
>
>              // Initialisation by user sets the entering arc and the
> quantity by which the flow changes.
>              // The rest is handled by already existing functions.
>
>              if(my_initialise_bool){
>                for(int i = 0; i < n0_; i++) {
>                  for(int j = 0; j < n1_; j++) {
>                  if(initialValues_[i][j]>0){
>
> in_arc=findArc(_graph.nodeFromId(i),_graph.nodeFromId(j+n0_));
>                    // sanity check :  i = _node_id(_source[in_arc]) and
> j = _node_id(_target[in_arc]) --> returns true! yay! :)
>                    findJoinNode();
>                    bool change = findLeavingArc();
>                    if (delta >= LEMON_MAX) return UNBOUNDED;
>
>                    // if the amount of flow I want to initialise with is
> lower the total possible amount, then change = false
>                    if(delta>initialValues_[i][j]){
>                      change = false;
>                    } else {
>                      change = true;
>                    }
>
>                    // set delta = amount of flow I want to initialise with
>                    delta = (double)initialValues_[i][j];
>
>                    changeFlow(change);
>                    if (change) {
>                        updateTreeStructure();
>                        updatePotential();
>                    }
>                  }
>                  }
>                }
>              }
>
> // END EDIT
>
>              PivotRuleImpl pivot(*this);
>
>              if (!initialPivots()) return UNBOUNDED;
>
>              // Execute the Network Simplex algorithm
>              while (pivot.findEnteringArc()) {
>                  findJoinNode();
>                  bool change = findLeavingArc();
>                  if (delta >= LEMON_MAX) return UNBOUNDED;
>                  changeFlow(change);
>                  if (change) {
>                      updateTreeStructure();
>                      updatePotential();
>                  }   [...]
>
>
> After my "edit", I get that the artificial arcs have 0 flow (which is
> normal).
>
> I have tried initialising it to the optimal solution, and I still get
> iterations in the while loop of the execution (i.e.
> pivot.findEnteringArc() is true and change is true) and I can't quite
> figure out why.
>
> If anyone knows the solution or has any appropriate direction of
> inquiry, it would be much appreciated!
>
> Cheers,
>
> Matthew
>
>
> _______________________________________________
> Lemon-user mailing list
> Lemon-user at lemon.cs.elte.hu
> http://lemon.cs.elte.hu/mailman/listinfo/lemon-user
>