COIN-OR::LEMON - Graph Library

Opened 7 years ago

Closed 4 years ago

#422 closed defect (fixed)

CPLEX LP slow problem build-up

Reported by: Alpar Juttner Owned by: Peter Kovacs
Priority: major Milestone: LEMON 1.4 release
Component: core Version: hg main
Keywords: Cc:
Revision id:

Description

In an internal project we came across a situation when building-up an LP program was very slow compared to using CPLEX's native interface. The problem occurs on some special problems, only. The reasons are still unknown.

Attachments (3)

1ad592289f93.patch (2.2 KB) - added by Alpar Juttner 4 years ago.
results_before_patch.txt (922 bytes) - added by Peter Kovacs 4 years ago.
results_after_patch.txt (926 bytes) - added by Peter Kovacs 4 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 7 years ago by Alpar Juttner

It would be really helpful to see a reproducible example for this

comment:2 Changed 7 years ago by Alpar Juttner

I would greatly appreciate if someone could show me an example of this phenomenon. I believe it should not really depend on the actual LP but only on its size and probably on its density. And it doesn't even need to be a meaningful LP. Two pieces of code building up the same matrix

  • firstly using LEMON's interface
  • secondly using CPLEX's native interface

and showing significant build-up time would be a great help in identifying where LEMON is suboptimal.

Athos reported similar issue with COIN-OR, thus I consider it a major issue. (A similar example for COIN-OR would be welcome, too)

So, could anyone give some more info, please?

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

Replying to alpar:

and showing significant build-up time [...]

I mean significant build-up time difference.

comment:4 Changed 6 years ago by Alpar Juttner

Milestone: LEMON 1.3 releaseLEMON 1.4 release

Changed 4 years ago by Alpar Juttner

Attachment: 1ad592289f93.patch added

comment:5 Changed 4 years ago by Alpar Juttner

The [1ad592289f93] chgset in the attached patch probably solves the problem. It directly adds the row with CPXaddrows() (supplemented by CPXchgrngval() if need be). This approach is apparently much faster than the current implementation, which is comprised of a CPXnewrows() call followed by a CPXchgcoeflist().

Could anyone review and test this changeset?

comment:6 Changed 4 years ago by Peter Kovacs

I checked this patch on the particular LP problems for which we first noticed this issue. The results show that this patch perfectly solves the problem:

Instance Time before Time after
planar30-1 3.7s 0.20s
planar50-1 107s 0.96s
planar50-2 60s 0.65s
planar50-3 255s 1.17s

More detailed results file are also attached.

Changed 4 years ago by Peter Kovacs

Attachment: results_before_patch.txt added

Changed 4 years ago by Peter Kovacs

Attachment: results_after_patch.txt added

comment:7 Changed 4 years ago by Alpar Juttner

Resolution: fixed
Status: newclosed

Thanks for the evaluation. The patch is now in main branch, see [1ad592289f93].

Note: See TracTickets for help on using tickets.