Hi Guys, I am working on a LP relaxation of a large scale industrial problem ( over half a million variables and several tenths of thousands constraints ), using coin-or clp. Do you think that it is worth investing time in tests with a different open source solver such as glpk or maybe commercial cplex or express-mp ? I know that the question is very general, more specifically I might ask if you know of cases when commercial solvers can be say order of magnitude faster when solving pure linear problems ? and as for open source solvers can such great disproportion in efficiency be observed in some cases ?

Best regards Luke

asked 10 Jul '10, 17:59

Luke's gravatar image

Luke
41112
accept rate: 0%


You should take a look at Hans Mittelmann's benchmarks, specifically the serial and parallel LP sections (and the large network LP benchmarks if your model has an underlying network structure). You'll see order of magnitude differences in some cases, but good luck finding a consistent winner -- it seems to be rather problem-specific. Interestingly (at least to me), CLP seems to beat both CPLEX's and Gurobi's simplex solvers on some problems (though frequently their barrier solvers seem to beat CLP on the same problems -- perhaps signaling massive degeneracy?).

link

answered 10 Jul '10, 19:17

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Hi

For large problems like yours it is our (http://www.mosek.com) experience that interior-point methods (aka barrier methods) are usually faster than simplex methods. To my knowledge only the commercial code offer good interior codes.

You are willing to make your problem available then we can run a benchmark for you.

Best Regards

Erling (CEO at MOSEK)

link

answered 15 Jul '10, 05:24

Erling's gravatar image

Erling
4404
accept rate: 0%

1

Hi Erling, Are you guys going to have discounts for the readers of this forum?

(15 Jul '10, 08:51) Alek Ronolsfson

You can see our prices and discount policy at http://www.mosek.com/sales/.

(15 Jul '10, 12:49) Erling

It is definitely worth a try to use an interior point based solver on your problem type. I have personally seen problem types where the difference between state of the art simplex and interior point implementations was staggering (simplex based methods (Clp, Cplex simplex) taking on the order of hours, whereas all interior-point based methods (Cplex barrier, Mosek) finishing within minutes). This obviously depends on the problem type and for some problems the reverse holds true. Therefore, try both.

link

answered 15 Jul '10, 08:10

Sebastian's gravatar image

Sebastian
311
accept rate: 0%

Regarding the large scale problem where interior point is much faster than simplex. I have often found that you can substantial speedup the simplex solution times by knowing about the problem structure ex. a certain types of variable should be preferred to some other types of variables in entering or leaving the basis. But this is very problem specific and only for experts to figure out. On the contrary the interior point requires no dirty tricks it runs nicely with default settings, which makes it the preferred algorithm for such problems. Actually the simplex is born under a lucky star, since it's run time complexity in practice "in most cases" is far from the theoretical complexity, but there are bad cases were you see the worst case performance. Understanding and improving the simplex algorithm on these instance is interesting future research..

link

answered 15 Jul '10, 09:59

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Please note the problem selection in the benchmark is somewhat biased towards complicated LP problems i.e most of them is either not numerical stable or has structure which can be exploited. So in my opinion this might over estimate the difference between a "not so good" and "good" LP solver. If you want to be sure of good performance, then you should purchase one of the best commercial packages, but you might find that some open source solver provide acceptable performance on your problem structure.

link

answered 12 Jul '10, 06:37

Bo%20Jensen's gravatar image

Bo Jensen ♦
5.0k2919
accept rate: 14%

Hi, Thanks for your response. I've just found this very same benchmark page and wanted to post the link here :)

link

answered 10 Jul '10, 19:21

Luke's gravatar image

Luke
41112
accept rate: 0%

Your answer
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×127
×46

Asked: 10 Jul '10, 17:59

Seen: 11,833 times

Last updated: 15 Jul '10, 09:59

OR-Exchange! Your site for questions, answers, and announcements about operations research.