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?

[Peter Kovacs]

Replying to alpar:

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?

No, you're absolutely right. Your version is not only simpler, but is safer, too, since _arc_num * _arc_num could cause int overflow.

Anyway, I muddled this changeset somehow. I made experiments with various versions of arc mixing, but not this one was the latest version. I found a simpler and at least as good version, which is now attached.

Notes:

• Note that the "how" of the arc mixing is almost ad-hoc in a sense that in theory, none of the solutions is better than the other, since nothing is known about the original arc order. However, some methods are typically better than other ones over quite different kinds of input instances.
• The main reason for changing the default option to true is that there are problem instances for which it greatly improves the running time (by a factor of 3), but we did not meet with such a huge difference in the other direction.

[Alpar Juttner]

[dca9eed2c375] and [fb932bcfd803] has been pushed to the main branch.