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)?
$\begingroup$
$\endgroup$
6
-
$\begingroup$ Out of curiosity, what makes you don't try this with the commercial solvers? $\endgroup$– A.OmidiOct 14, 2021 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$– Erwin KalvelagenOct 14, 2021 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$– vkmvOct 14, 2021 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$– SamarthOct 14, 2021 at 17:00
-
$\begingroup$ You get a 30 day trial at mosek.com immediately. Also it is not that expensive. $\endgroup$– ErlingMOSEKOct 15, 2021 at 17:02
|
Show 1 more comment
1 Answer
$\begingroup$
$\endgroup$
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.
