COIN-OR::LEMON - Graph Library

Opened 9 years ago

Closed 9 years ago

#298 closed enhancement (fixed)

Small improvement for NetworkSimplex

Reported by: kpeter Owned by: kpeter
Priority: major Milestone: LEMON 1.2 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description


Attachments (7)

298-ns-impr-7408cac25b1e.patch (7.3 KB) - added by kpeter 9 years ago.
298-improvements-cab85bd7859b.patch (6.7 KB) - added by kpeter 9 years ago.
298-arcmixing-0a0cbbf56e23.patch (2.3 KB) - added by kpeter 9 years ago.
298-arcmixing-e2bdd1a988f3.patch (2.3 KB) - added by kpeter 9 years ago.
Slightly better version of [0a0cbbf56e23]
298-new-impr-64ba4ed66159.patch (1.5 KB) - added by kpeter 9 years ago.
A new small improvement
298-new-impr-5a74b94f19c5.patch (2.2 KB) - added by kpeter 9 years ago.
An extended version of the previous patch
298-new-impr-be48a648d28f.patch (1.9 KB) - added by kpeter 9 years ago.
Without changing the conversion

Download all attachments as: .zip

Change History (24)

Changed 9 years ago by kpeter

comment:1 Changed 9 years ago by kpeter

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

comment:2 Changed 9 years ago by kpeter

  • Status changed from new to assigned

comment:3 Changed 9 years ago by kpeter

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

comment:4 follow-up: Changed 9 years ago by kpeter

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.

comment:5 in reply to: ↑ 4 ; follow-up: Changed 9 years ago by alpar

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.

comment:6 in reply to: ↑ 5 ; follow-up: Changed 9 years ago by kpeter

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?

comment:7 in reply to: ↑ 6 Changed 9 years ago by alpar

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.

Changed 9 years ago by kpeter

Changed 9 years ago by kpeter

comment:8 Changed 9 years ago by kpeter

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.

Changed 9 years ago by kpeter

Slightly better version of [0a0cbbf56e23]

comment:9 Changed 9 years ago by kpeter

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

Changed 9 years ago by kpeter

A new small improvement

comment:10 follow-up: Changed 9 years ago by kpeter

[64ba4ed66159] is a new small improvement.

comment:11 in reply to: ↑ 10 ; follow-up: Changed 9 years ago by alpar

Replying to kpeter:

[64ba4ed66159] is a new small improvement.

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

comment:12 in reply to: ↑ 11 ; follow-up: Changed 9 years ago by 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.

Changed 9 years ago by kpeter

An extended version of the previous patch

comment:13 in reply to: ↑ 12 Changed 9 years ago by alpar

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.

comment:14 follow-up: Changed 9 years ago by kpeter

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

comment:15 in reply to: ↑ 14 ; follow-up: Changed 9 years ago by alpar

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.

Changed 9 years ago by kpeter

Without changing the conversion

comment:16 in reply to: ↑ 15 ; follow-up: Changed 9 years ago by kpeter

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:

comment:17 in reply to: ↑ 16 Changed 9 years ago by kpeter

  • Resolution set to fixed
  • Status changed from assigned to closed

They are in the main branch now.

Note: See TracTickets for help on using tickets.