Small improvement for NetworkSimplex

[Peter Kovacs]

The attached patch contains some small changes that make the implementation slightly faster.

[Peter Kovacs]

Here are some benchmark results on the problem sets used for the GPCE paper.

On sparse networks (m = n*log_2(n)):

n         r1.1       [7408cac25b1e]
10000     0.189657   0.177591
20000     0.514086   0.455547
50000     2.52514    2.14604
100000    8.00875    7.17334
200000    27.79      23.358
500000    166.749    143.746
1000000   579.755    481.502

On dense networks (m = n*sqrt(n)):

n         r1.1       [7408cac25b1e]
5000      0.220552   0.151751
10000     0.712072   0.555311
20000     2.60351    1.91242
50000     12.4516    10.7151
100000    56.3111    40.4598

[Peter Kovacs]

The main difference in this patch is to store the edges in the original order instead of mixing them. For the problem instances generated with NETGEN the mixed order results in a less efficient algorithm (slower initialization and slower solving), as you can see above.

However note that there are some problems for which this "mixing" helps a lot. E.g. I tested large and relatively easy GEQ type instances for which it results in a 1,5 times faster algorithm. In spite of this I suggest applying this changeset.

[Alpar Juttner]

Replying to kpeter:

The main difference in this patch is to store the edges in the original order instead of mixing them.

Isn't it possible to allow the user to choose between using the original order and randomizing?

My concern is that we've learned that there are also some unlucky natural examples on which NS perform badly using the original edge order. (By "unlucky" I mean the example was generated in a natural way for a real life problem without deliberately obfuscating the order of the edges.)

The randomization of the edge order is a quite safe overcome of this problem.

For the problem instances generated with NETGEN the mixed order results in a less efficient algorithm (slower initialization and slower solving), as you can see above.

However note that there are some problems for which this "mixing" helps a lot. E.g. I tested large and relatively easy GEQ type instances for which it results in a 1,5 times faster algorithm. In spite of this I suggest applying this changeset.

[Peter Kovacs]

Replying to alpar:

Isn't it possible to allow the user to choose between using the original order and randomizing?

It is possible, of course. But first I thought that a general good decision can be made about it to keep the user interface simpler, but it can't.

The arcs are stored in the constructor, so the natural option would be a bool parameter for the constructor (with a default value, of course). What do you think about it? Would it be good?

[Alpar Juttner]

Replying to kpeter:

The arcs are stored in the constructor, so the natural option would be a bool parameter for the constructor (with a default value, of course). What do you think about it? Would it be good?

At least, I can't see anything better.

[Peter Kovacs]

I split the changes into two changesets: [cab85bd7859b] and [0a0cbbf56e23]. The later one adds an optional constructor parameter with which the arc mixing can be controlled. It is disabled by default.

[Peter Kovacs]

Slightly better version of [0a0cbbf56e23]

[Peter Kovacs]

[cab85bd7859b] makes the pivot rule implementations slightly faster and simpler, so this patch should be applied.

I also suggest [e2bdd1a988f3] to be applied, but the default option could be questionable.

[Peter Kovacs]

A new small improvement

[Peter Kovacs]

[64ba4ed66159] is a new small improvement.

[Alpar Juttner]

Replying to kpeter:

[64ba4ed66159] is a new small improvement.

What's the reason for changing the conversion? (The only code change in this patch.)

[Peter Kovacs]

Replying to alpar:

What's the reason for changing the conversion? (The only code change in this patch.)

Maybe it is nicer in C++ to explicitly specify the type of conversion, I don't know. However the doc change is important, since the removed sentences are wrong. Identically zero supply function does not only make sense when there are non-zero lower bounds, since negative costs are also supported.

[Peter Kovacs]

An extended version of the previous patch

[Alpar Juttner]

Replying to kpeter:

Replying to alpar:

What's the reason for changing the conversion? (The only code change in this patch.)

Maybe it is nicer in C++ to explicitly specify the type of conversion, I don't know. However the doc change is important, since the removed sentences are wrong. Identically zero supply function does not only make sense when there are non-zero lower bounds, since negative costs are also supported.

For me, it still doesn't make sense changing the conversion. In general I'm not a fan of the "maybe better/nicer" type changes is the repo.

[Peter Kovacs]

First of all, let's apply [cab85bd7859b]. After that, tell me which parts of [e2bdd1a988f3] and [5a74b94f19c5] do you accept.

[Alpar Juttner]

Replying to kpeter:

First of all, let's apply [cab85bd7859b]. After that, tell me which parts of [e2bdd1a988f3] and [5a74b94f19c5] do you accept.

My only - I admit, pedantic - concern is with the conversion. It is a maintenance issue.

I also slightly prefer the order randomization being the default choice (as it is more robust), but - as it can be set by the user - I do not insist on it. The question is if we tune for the benchmarks of for robustness.

[Peter Kovacs]

Without changing the conversion

[Peter Kovacs]

Replying to alpar:

My only - I admit, pedantic - concern is with the conversion. It is a maintenance issue.

[be48a648d28f] is a version without changing the conversion.

I also slightly prefer the order randomization being the default choice (as it is more robust), but - as it can be set by the user - I do not insist on it. The question is if we tune for the benchmarks of for robustness.

It is not clear which one is better, but I slightly prefer not to randomize the arcs as a default behavior.

So I suggest merging the following patches:

• [cab85bd7859b]
• [e2bdd1a988f3]
• [be48a648d28f]

[Peter Kovacs]

They are in the main branch now.