COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#391 closed enhancement (done)

NetworkSimplex improvements

Reported by: Peter Kovacs Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.3 release
Component: core Version: hg main
Keywords: Cc: magh@…
Revision id:

Attachments (3)

391-1-dca9eed2c375.patch (16.3 KB) - added by Peter Kovacs 9 years ago.
391-2-f6f2a3139f64.patch (1.7 KB) - added by Peter Kovacs 9 years ago.
391-2-fb932bcfd803.patch (1.9 KB) - added by Peter Kovacs 9 years ago.

Download all attachments as: .zip

Change History (9)

comment:1 Changed 9 years ago by Peter Kovacs

Status: newassigned

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

Changed 9 years ago by Peter Kovacs

Attachment: 391-1-dca9eed2c375.patch added

Changed 9 years ago by Peter Kovacs

Attachment: 391-2-f6f2a3139f64.patch added

comment:2 Changed 9 years ago by Peter Kovacs

Cc: magh@… added

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?

comment:3 in reply to:  2 Changed 9 years ago by Alpar Juttner

Description: modified (diff)

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?

comment:4 Changed 9 years ago by Peter Kovacs

Description: modified (diff)

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?

comment:5 in reply to:  4 Changed 9 years ago by 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.

Changed 9 years ago by Peter Kovacs

Attachment: 391-2-fb932bcfd803.patch added

comment:6 Changed 9 years ago by Alpar Juttner

Resolution: done
Status: assignedclosed

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

Note: See TracTickets for help on using tickets.