NetworkSimplex improvements

[Peter Kovacs]

I work on various improvements for NS. I will attach some changesets to this ticket soon.

[Peter Kovacs]

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?

[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?

[Peter Kovacs]

Alpar added this comment (but to the description of the ticket):

In [f6f2a3139f64], I can see this:

  int skip = int(std::sqrt(double(_arc_num * _arc_num) / _node_num));
  int k = std::max(skip, 3);

Why not

  const int skip = int(_arc_num/std::sqrt(_node_num));

?

Do I overlook something?