COIN-OR::LEMON - Graph Library

Changes between Initial Version and Version 3 of Ticket #391

09/01/10 07:08:16 (13 years ago)
Alpar Juttner

Replying to kpeter:

I attached two changesets. The first one [dca9eed2c375] contains various small modifications that slightly improve the performance of NS and also make some parts of the code more understandable.

The second one [f6f2a3139f64] improves the arc mixing method and enables it by default. There was a discussion about this question in #298 a year ago. Then, I argued for disabling arc mixing by default, but I recently managed to significantly improve its average performance and received another problem instance for which any reasonable mixing makes a huge improvement. Therefore, I changed my mind and suggest to use arc mixing by default.

The new mixing uses the same simple method but with a better factor which is fine tuned to cooperate well with the fastest pivot rules. It yields to significantly better average performance than either the previous version or the random permutation of the arcs. Applying this changeset, arc mixing is no longer worse than keeping the original arc order. I made comprehensive tests on various generated and real-life instances. The running time of the proposed variant was always within about 10 percent and on average, it was about the same efficient as not applying arc mixing.

I think, modifying the default parameter value does not break the API. Another possibility would be to also introduce the random permutation of arcs as an alternative method (though it turned out to be worse or equivalent to the proposed method on all instances). However, this would require the replacement of the bool parameter with an enum type. Would it be an acceptable change in the API? Would you like such an extension?


  • Ticket #391

    • Property Status changed from new to assigned
    • Property Cc magh@… added
  • Ticket #391 – Description

    initial v3  
     1In [f6f2a3139f64], I can see this:
     4+        int skip = int(std::sqrt(double(_arc_num * _arc_num) / _node_num));
     5+        int k = std::max(skip, 3);
     8Why not
     11const int skip = int(_arc_num/std::sqrt(_node_num));
     16Do I overlook something?