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

[matthew henry]

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
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lemon.cs.elte.hu/pipermail/lemon-user/attachments/20150522/e3dc7018/attachment-0001.html>