5
$\begingroup$

I have an LP problem of the form $\min\ c^Tx$ subject to $Ax\leq b$ where $x$ consists of 30 million parameters and $A$ is a very very sparse matrix of size 30M by 30M (with only 3 ones per row). I tried solving this using scipy.linprog (Interior Point, HiGHS), cvxpy (ECOS, OSPQ) but none of them seem to really scale to this size. Is it currently possible to solve such large LP programs (using any freely available solvers or in the worst case even commercial ones)?

$\endgroup$
5
  • $\begingroup$ Out of curiosity, what makes you don't try this with the commercial solvers? $\endgroup$
    – A.Omidi
    Oct 14 at 7:52
  • 1
    $\begingroup$ Good LP solvers usually can handle a model of this size without too much trouble. Make sure you have a machine with enough memory. $\endgroup$ Oct 14 at 13:25
  • $\begingroup$ Commercial solvers are expensive for me to purchase for personal use because I am an ML researcher in the industry and what I am doing is part of a personal research project. I looked at Gurobi and asked them for an evaluation license. Hopefully I can get one. $\endgroup$
    – vkmv
    Oct 14 at 16:14
  • 2
    $\begingroup$ You might want to take a loot at the NEOS server that provides access to several commercial solvers free of charge, albeit with some restrictions on input file size and computational resources. However, I'm not sure whether it will work or not given the size of your problem. $\endgroup$
    – Samarth
    Oct 14 at 17:00
  • $\begingroup$ You get a 30 day trial at mosek.com immediately. Also it is not that expensive. $\endgroup$ Oct 15 at 17:02
4
$\begingroup$

If you can't find (or can't afford) a solver that will handle a problem with that many nonzero matrix coefficients, and if your problem has a structure that fits one of the following methods, you might try either Dantzig-Wolfe or Benders decomposition.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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