Answers to: Runtime of a Mathematical modelhttp://www.or-exchange.com/questions/411/runtime-of-a-mathematical-model<p>Has anyone tried to develop a method to predict run-time of a mathematical model given a solver like CPLEX?</p>enThu, 03 Jun 2010 16:25:01 -0400Answer by Tallys Yuneshttp://www.or-exchange.com/questions/411/runtime-of-a-mathematical-model/418<p>Take a look at this (very interesting) paper:</p>
<p>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.</p>
<p>It can be downloaded from Gerard's page at: <a href="http://integer.tepper.cmu.edu/" rel="nofollow">http://integer.tepper.cmu.edu/</a></p>Tallys YunesThu, 03 Jun 2010 16:25:01 -0400http://www.or-exchange.com/questions/411/runtime-of-a-mathematical-model/418Answer by Matthew Saltzmanhttp://www.or-exchange.com/questions/411/runtime-of-a-mathematical-model/417<p>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.)</p>
<p>For MIPS, I think there has been some work, but I don't think it's been broadly applicable or robust.</p>Matthew SaltzmanThu, 03 Jun 2010 06:36:03 -0400http://www.or-exchange.com/questions/411/runtime-of-a-mathematical-model/417Answer by Paul Rubinhttp://www.or-exchange.com/questions/411/runtime-of-a-mathematical-model/415<p>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).</p>
<p>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.</p>
<p>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.</p>Paul RubinWed, 02 Jun 2010 21:05:27 -0400http://www.or-exchange.com/questions/411/runtime-of-a-mathematical-model/415