5

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)?

ə̷̶̸͇̘̜́̍͗̂̄︣͟
  • 5,412
  • 5
  • 22
  • 55
vkmv
  • 151
  • 1
  • Out of curiosity, what makes you don't try this with the commercial solvers? – A.Omidi Oct 14 '21 at 07:52
  • 1
    Good LP solvers usually can handle a model of this size without too much trouble. Make sure you have a machine with enough memory. – Erwin Kalvelagen Oct 14 '21 at 13:25
  • 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. – vkmv Oct 14 '21 at 16:14
  • 2
    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. – Samarth Oct 14 '21 at 17:00
  • You get a 30 day trial at mosek.com immediately. Also it is not that expensive. – ErlingMOSEK Oct 15 '21 at 17:02
  • I'd be curious to know where the bottlenecks are when you use HiGHS. If you're still interested in finding a good open source solver, get in touch (jajhall@ed.ac.uk) – SparseRunner Jan 07 '22 at 18:30

1 Answers1

4

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.

prubin
  • 39,078
  • 3
  • 37
  • 104