Answers to: Solving large problem with free LP solvers (50+ million variables)http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables<p>I was wondering if any of the free solvers were powerful enough to solve a problem that has approximately 50M variables and 100+M constraints. It's a maximization and is entirely linear.</p>
<p>I was thinking of using Coin-OR's CLP solver on a relatively powerful workstation.</p>
<p>Will this yield a solution? If not, what is the rule of thumb for a free LP solver's maximum problem size? Would a commercial solver (e.g. cplex or gurobi) handle such a problem?</p>
<p><em>Note: I realize the answer depends on the problem type and solver, but I just wanted to ensure that I'm not off by multiple orders of magnitude before I actually start. The largest problems I could find references to (on a Google search) were less than 10M variables.</em></p>enTue, 28 Jan 2014 06:20:05 -0500Comment by jfpuget on Erling_MOSEK's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9166<p><a href="/users/143/erling">@Erling</a> Agreed</p>jfpugetTue, 28 Jan 2014 06:20:05 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9166Comment by Erling_MOSEK on Erling_MOSEK's answerhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9165<p><a href="/users/692/jfpuget">@jfpuget</a> I think we could use LPLIB collection of challenging large-scale LP test problems. Something that could test the limits but not be totally out of reach.</p>Erling_MOSEKTue, 28 Jan 2014 04:52:01 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9165Comment by jfpuget on Erling_MOSEK's answerhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9164<p>+vote for the suggestion to make the problem public, I'd be happy to run CPLEX on it as well!</p>jfpugetTue, 28 Jan 2014 04:15:07 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9164Answer by Erling_MOSEKhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables/9144<p>Most likely the dual problem will solve more efficiently than the primal since you have more rows than columns. Moreover, most likely an interior-point based algorithm works better than a simplex algorithm due to the size. The latter means that you most likely should use a commercial code. Since the public domain interior-point based codes for large scale LPs are not that good. [Please correct me if I wrong and biased.]</p>
<p>You will need a large computer in any case but how large will depend on the structure in your problem i.e. the sparsity pattern after presolve.</p>
<p>It would be fun if you would donate the problem to public domain so it can be used for test and benchmarking. I will be happy to try our code <a href="http://mosek.com">MOSEK</a> on it.</p>Erling_MOSEKMon, 27 Jan 2014 09:20:29 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables/9144Comment by Bo Jensen on Tim Y's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9143<p>BTW : In the previous mention case and also in many other huge problems, it tend to be the user who forget the model often already is an approximation to the real problem at hand i.e too much detail in the model.</p>Bo JensenMon, 27 Jan 2014 07:26:24 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9143Comment by Bo Jensen on Tim Y's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9142<p><a href="/users/340/ehsan">@Ehsan</a> In that case we agree, but for reducing memory using a partial pricing primal simplex with sections of the non basic variables written to disk is sufficient and will likely perform better if tailored correctly (I did implement such an idea long time ago).</p>Bo JensenMon, 27 Jan 2014 07:21:49 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9142Comment by Ehsan on Tim Y's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9141<p><a href="/users/62/bo-jensen">@Bo</a>: I agree. However, I think the main point of decomposition is to fit the problem into the machine, not just the CPU time. My own experience is with facility location problems, which are usually perfect for decomposition. Based on experience and reliable results from the literature, instances up to 100+M variables and constraints could be solved for basic FLPs. However, these simple FLPs could not be solved directly due to requiring a huge amount of memory. I think this is worth investigating before just putting the whole model into the solver at once.</p>EhsanMon, 27 Jan 2014 06:58:49 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9141Comment by Bo Jensen on Tim Y's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9139<p>Probably a better and faster advice, just pick the largest machine on amazon EC2 and try it out... Then you got your answer :-)</p>Bo JensenMon, 27 Jan 2014 06:00:23 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9139Comment by Bo Jensen on Tim Y's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9138<p><a href="/users/340/ehsan">@Ehsan</a> Have you had success with decomposition for huge LP's in terms of cutting down solving time ? From my experience it does not work very well, except for exceptional well suited structures (even if you ignore the tailing effect).</p>Bo JensenMon, 27 Jan 2014 05:53:23 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9138Comment by Ehsan on Tim Y's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9136<p>You could also try to exploit any specific structure in your model via decomposition techniques to decrease your CPU time significantly. Based on the number of variables and constraint, I bet there is something in there to constitute a nice and useful structure (e.g., planning periods or scenarios).</p>EhsanMon, 27 Jan 2014 05:49:06 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9136Comment by Bo Jensen on Tim Y's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9132<p>In absolute last resort and worst case, one can build a customized LP algorithm (fairly easy) which offload parts of the problem to disk. But that would require more than average optimizer knowledge.</p>Bo JensenMon, 27 Jan 2014 03:38:43 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9132Comment by Bo Jensen on Tim Y's questionhttp://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9131<p>Number of constraints or variables is a poor estimate even for LP performance. Since it's a LP I would think your biggest problem would be memory. One suggestion could be to build a smaller model on a standard desktop (if possible) increase the size and measure memory consumption to predict the memory consumption for the final model. Will give you an hint of machine size needed.</p>Bo JensenMon, 27 Jan 2014 03:37:16 -0500http://www.or-exchange.com/questions/9129/solving-large-problem-with-free-lp-solvers-50-million-variables#9131