Has anyone tried to develop a method to predict run-time of a mathematical model given a solver like CPLEX?
Operations Research Exchange!
|
3
|
|
|
|
|
4
|
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. |
|||
|
OR-Exchange! Your site for questions and answers about operations research.
|
2
|
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/ |
||
|
|
|
2
|
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. |
|||
|
