COIN-OR::LEMON - Graph Library

Opened 15 years ago

Closed 15 years ago

#298 closed enhancement (fixed)

Small improvement for NetworkSimplex

Reported by: Peter Kovacs Owned by: Peter Kovacs
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 Peter Kovacs 15 years ago.
298-improvements-cab85bd7859b.patch (6.7 KB) - added by Peter Kovacs 15 years ago.
298-arcmixing-0a0cbbf56e23.patch (2.3 KB) - added by Peter Kovacs 15 years ago.
298-arcmixing-e2bdd1a988f3.patch (2.3 KB) - added by Peter Kovacs 15 years ago.
Slightly better version of [0a0cbbf56e23]
298-new-impr-64ba4ed66159.patch (1.5 KB) - added by Peter Kovacs 15 years ago.
A new small improvement
298-new-impr-5a74b94f19c5.patch (2.2 KB) - added by Peter Kovacs 15 years ago.
An extended version of the previous patch
298-new-impr-be48a648d28f.patch (1.9 KB) - added by Peter Kovacs 15 years ago.
Without changing the conversion

Download all attachments as: .zip

Change History (24)

Changed 15 years ago by Peter Kovacs

comment:1 Changed 15 years ago by Peter Kovacs

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

comment:2 Changed 15 years ago by Peter Kovacs

Status: newassigned

comment:3 Changed 15 years ago by 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

comment:4 Changed 15 years ago by 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.

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

comment:6 in reply to:  5 ; Changed 15 years ago by 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?

comment:7 in reply to:  6 Changed 15 years ago by 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.

Changed 15 years ago by Peter Kovacs

Changed 15 years ago by Peter Kovacs

comment:8 Changed 15 years ago by 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.

Changed 15 years ago by Peter Kovacs

Slightly better version of [0a0cbbf56e23]

comment:9 Changed 15 years ago by 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.

Changed 15 years ago by Peter Kovacs

A new small improvement

comment:10 Changed 15 years ago by Peter Kovacs

[64ba4ed66159] is a new small improvement.

comment:11 in reply to:  10 ; Changed 15 years ago by 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.)

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

Changed 15 years ago by Peter Kovacs

An extended version of the previous patch

comment:13 in reply to:  12 Changed 15 years ago by 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.

comment:14 Changed 15 years ago by Peter Kovacs

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 ; Changed 15 years ago by 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.

Changed 15 years ago by Peter Kovacs

Without changing the conversion

comment:16 in reply to:  15 ; Changed 15 years ago by 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:

comment:17 in reply to:  16 Changed 15 years ago by Peter Kovacs

Resolution: fixed
Status: assignedclosed

They are in the main branch now.

Note: See TracTickets for help on using tickets.