COIN-OR::LEMON - Graph Library

Opened 7 years ago

Closed 3 years ago

#422 closed defect (fixed)

CPLEX LP slow problem build-up

Reported by: alpar Owned by: kpeter
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 4 years ago.
results_before_patch.txt (922 bytes) - added by kpeter 4 years ago.
results_after_patch.txt (926 bytes) - added by kpeter 4 years ago.

Download all attachments as: .zip

Change History (10)

comment:1 Changed 6 years ago by alpar

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

comment:2 follow-up: Changed 6 years ago by alpar

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 6 years ago by alpar

Replying to alpar:

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

I mean significant build-up time difference.

comment:4 Changed 5 years ago by alpar

  • Milestone changed from LEMON 1.3 release to LEMON 1.4 release

Changed 4 years ago by alpar

comment:5 Changed 4 years ago by alpar

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 kpeter

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 kpeter

Changed 4 years ago by kpeter

comment:7 Changed 3 years ago by alpar

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

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

Note: See TracTickets for help on using tickets.