23
$\begingroup$

I have found a PowerPoint presentation in which the presentor Hall claims instances could be of the size of 108 in variables and constraints to be solved today. I assume that he meant sparse problems. Bixby claims that since CPLEX 5 the problem size scales proportionally with the time needed. Is there actually evidence for this? Which problems are hard nuts to crack? What actual time is necessary to solve a problem with certain characteristics in general?

Improve this question
$\endgroup$
1
  • 1
    $\begingroup$ Apparently integer linear programming is NP hard, (at least as hard as the hardest problems in complexity class NP) so worst case is exponential time in input size and you can start your trip to the locker room -- but special cases may of course be cheaper. Compare with SAT Solving. There must be a paper about real-valued instances too. $\endgroup$
    – David Tonhofer
    Jul 3, 2019 at 16:50

4 Answers 4

Reset to default
27
$\begingroup$

For sure Julian Hall meant sparse problems.

It is possible to solve huge sparse LP problems. If they have sufficiently nice structure your can solve problems with up 231 constraints or variables.

For instance we solve some huge problems in this GitHub tutorial in a moderate amount of time.

Saying some about the solution time based of some simple statistics of the problem is in my opinion impossible. You have to run it.

However, here is an example where glop (a simplex solver sponsored by Google) did not finish in 40 days. Although this problem is not huge.

Usually I find interior-point methods are better than simplex algorithm for large problems. It is also true the time per simplex iteration is almost constant independent of the problem dimension for many practical LPs. But there are exceptions and the number of iterations can be huge for degenerate problems.

Well, this based on experience with developing Mosek.

Improve this answer
$\endgroup$
1
  • 1
    $\begingroup$ Completely agree. In the end, sparsity and structure are the two things that drive solution time in my experience. For example: if I tell you to minimize the sum of $10^{10}$ continuous variables bound between 0 and 1 (technically $2\cdot 10^{10}$ constraints), the answer is obvious (everything is 0). Equally for very dense problems you’ll have a hard time even for “moderately” sized problems. $\endgroup$
    – Richard
    Jul 1, 2019 at 20:06
19
$\begingroup$

Hans Mittelmann maintains a well-respected website with benchmarks for optimization software.

For LP problems, both simplex and barrier methods are compared. The first instance on the barrier page is L1_sixm1000obs, with 3,082,940 constraints, 1,426,256 variables, and 14,262,560 non-zero elements in the constraint matrix. This problem is solved within the hour by the MOSEK solver.

Do note that due to an incident (see site) the performance of solvers CPLEX, Gurobi, and XPRESS are not included in the current benchmarks, but can in part be found in the archives.

Based on this information, the claim that significantly larger LP problems can be solved by state-of-the-art solvers is not unbelievable to me.

Improve this answer
$\endgroup$
17
$\begingroup$

A couple years ago, I solved an integer program with more than 11,000,000 variables as part of a Kaggle competition. To solve the IP, the MIP solver first solved the LP relaxation, which took about 45 minutes.

Recently, my PhD student Hamid solved an LP with 65 million variables, 65 million constraints, and 325 million nonzeros. It took 5 days to solve with barrier and required roughly 60 GB RAM. That's getting close to the 108 number you quote.

Improve this answer
$\endgroup$
11
$\begingroup$

The instances I referred to are stochastic LPs (for unit commitment problems)1.

We developed a parallel simplex solver exploiting the block structure and used a special hot start procedure. The biggest solved had 500,000,000 variables and constraints, but took only 41000 iterations. So, highly specialised problems and solution method, and far from reality!

In general, Bixby's correct regarding problems exhibiting hyper-sparsity. The cost per iteration is $\mathcal O(1)$, so the $\mathcal O(m+n)$ iteration count means that the solution time scales linearly with problem size. Many practical problems are hyper-sparse, but by no means all, and particularly so for benchmark instances. Mittelmann's 11 recent changes of problem means that there are fewer hyper-sparse problems. Witness the fact that most solvers are less uncompetitive relative to Clp as a result.

If you're solving a single LP with no information about the solution, then IPM will generally be faster - simplex is better for some hyper-sparse problems and oddities like the QAPs (following the Idiot crash).

Reference

[1] Lubin, M., Hall, J. A. J., Petra, C. G., Anitescu, M. (2013). Parallel distributed-memory simplex for large-scale stochastic LP problems. Computational Optimization and Applications. 55(3), 571-596, 2013. DOI: 10.1007/s10589-013-9542-y

Improve this answer
$\endgroup$
1

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

Not the answer you're looking for? Browse other questions tagged or ask your own question.