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

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.


answered 02 Jun '10, 21:05

Paul%20Rubin's gravatar image

Paul Rubin ♦♦
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.


answered 03 Jun '10, 06:36

Matthew%20Saltzman's gravatar image

Matthew Salt... ♦
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/


answered 03 Jun '10, 16:25

Tallys%20Yunes's gravatar image

Tallys Yunes ♦
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



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



Asked: 02 Jun '10, 19:30

Seen: 1,776 times

Last updated: 03 Jun '10, 16:25

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