Has anyone tried to develop a method to predict run-time of a mathematical model given a solver like CPLEX?

asked 02 Jun '10, 19:30

Venky's gravatar image

Venky
7681219
accept rate: 15%


For LPs, I think I once saw results that the "average" solution time for a model with m constraints and n variables was something like O(m^a n^b) where a might have been 2.5 and b 1.5 (but I saw this long, long ago, so don't quote me). The results were not specific to any particular software code or hardware platform, and I believe were for the simplex method (and definitely not interior point methods).

I'm skeptical that you'll find anything more specific. It's well know that run times for the same computer program applied to the same model on the same computer can vary wildly due to seemingly small things like changing the order in which the constraints are entered. Switching from one hardware platform to another (same software, same model) can cause changes because floating point arithmetic libraries vary from operating system to operating system. Hardware obviously makes a big difference. Parameter settings make a big difference.

There is one fairly reliable forecasting model for run time: if you're in a big hurry, it's going to take a long time.

link

answered 02 Jun '10, 21:05

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
14.6k412
accept rate: 19%

Thanks for your input. I am not in a hurry to forecast it. But i was research myself if there were any literature on forecasting run-time.

(03 Jun '10, 19:10) Venky

There's a section in Vanderbei's LP book on average simplex performance. There might be a brief bit in Chvatal's book as well. Interior-point methods are much more robust. with iterations commonly totaling in the 20-40 range for most problems. (I don't have a reference to hand for that, but Vanderbei might address it.)

For MIPS, I think there has been some work, but I don't think it's been broadly applicable or robust.

link

answered 03 Jun '10, 06:36

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
4.7k310
accept rate: 17%

hmmm.... I'll look into those books. thanks for the reference.

(03 Jun '10, 19:11) Venky

Take a look at this (very interesting) paper:

Early Estimates of the Size of Branch-and-Bound Trees by Gerard Cornuejols, Miroslav Karamanov and Yanjun Li. INFORMS Journal on Computing 18 (2006) 86-96.

It can be downloaded from Gerard's page at: http://integer.tepper.cmu.edu/

link

answered 03 Jun '10, 16:25

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
2.1k518
accept rate: 11%

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:

×191
×127

Asked: 02 Jun '10, 19:30

Seen: 1,612 times

Last updated: 03 Jun '10, 16:25

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