4
$\begingroup$

I'm having an issue solving an LP of the form:

$$\min z = c^Tx$$ $$\text{s.t.}$$ $$Ax \geq b$$ $$x\geq p$$ $1 \leq a_{ij} \ll b_i$, $p \leq 0$, and $c \geq 0$

The specific problems I'm running into with the ortools GLOP solver are:

  1. The LP takes an insanely long time to solve on a distributed system where each worker has $\geq 30$ cores and roughly $240$ GB of memory. To me seems a little too long. I've solved instances of TSP in less time on smaller machines that did more computations (with CPLEX / Gurobi via AMPL). Furthermore, lasso regression is reducible to simplex and can run on similarly sized data in a fraction of a fraction of the time. Latency is extremely important and I'd love to get this cooking in less than $45$–$60$ minutes.

  2. I've checked and double checked the formulation generated, and the output (after $\sim 6$ hours) is that the problem is infeasible by returning a solution of $x = 0$. Obviously, this can't be the case since if we take $x = b$, we have a basic feasible solution, which implies the existence of an optimal solution.

About the data:

$A$ has $\sim 3MM$ rows and $\sim1MM$ columns. However, $A$ is also very sparse with no more than $2$ $nonzero$ entries per row.

Unfortunately, I'm new to the Google's ortools and am having difficulty finding documentation on the specific objects and methods in the $python$ API.

My guesses as to where issues can be arising and possible solutions are:

  1. If the solver is using two phase simplex or "Big M" to find an initial BFS. I want to know if I can speed up the process by providing an initial BFS to the GLOP solver (e.g. $x = b$) to speed things up?

  2. If there's not an issue in $(1)$, then the problem must be too hard (doubtful). But, a better formulation may help. Sparsity of $A$ suggests I may be able to look at this as an MCNF problem and apply network simplex. Anyone have any experience with this?

  3. Can I go a step further by using something like Dantzig Wolfe decomposition to separate the "easy" constraints ($x \geq p$) from the hard ones? Related, but I'm wondering if I can also lift the easy constraints into the objective. Any experience with this?

  4. (Related to 3) but not sure if column generation works here, but can it? Does anyone have any experience with it for problems of this nature? My intuition is that I can look at x as a set of patterns since x's are tightly coupled and belong to independent variable sets.

$$$$

Most importantly, if you've worked with Google's ortools before, can you point me to traditional API docs (not examples) for $python$? And, if you can, can you share what your experience has been as well as common gotchas and helpful performance improvement tips?

Last, I'd love to use an open source solver like ortools rather than pay for something more expensive for this application. If you know of another open source solution that exists, please share in the comments. Anything that has a decent Java, Scala, or python API would be awesome. Extra points for distributed solutions. Extra Extra points for something that leverages Apache Spark's distributed environment.

Thanks a lot!

$\endgroup$

closed as off-topic by Mostafa Ayaz, hardmath, Saad, George Law, Mohammad Riazi-Kermani Feb 17 '18 at 3:30

This question appears to be off-topic. The users who voted to close gave this specific reason:

  • "This question is not about mathematics, within the scope defined in the help center." – Mostafa Ayaz, hardmath, Saad, George Law
If this question can be reworded to fit the rules in the help center, please edit the question.

  • $\begingroup$ N.B. Would a question like this be more suited to math overflow or stack overflow? Avoided math overflow because it doesn't "feel" like a research question, and avoided stack overflow because it's more general than a code question. $\endgroup$ – EDZ Feb 16 '18 at 19:44
  • 1
    $\begingroup$ You don't need to type $a<<b;$ you can type $a\ll b,$ which is the right notation for that occasion. Also notice the use of \text{} in my edit to this question. $\qquad$ $\endgroup$ – Michael Hardy Feb 16 '18 at 19:45
  • $\begingroup$ Thanks. Somewhat new to MathJax. Appreciate it! $\endgroup$ – EDZ Feb 16 '18 at 19:46
  • $\begingroup$ This Question, with its emphasis on "traditional API docs... for python" and "an open source solver like ortools", takes it outside the ambit of Math.SE. While StackOverflow is a not unreasonable suggestion, I'd point you to the SciComp.SE site here. $\endgroup$ – hardmath Feb 16 '18 at 19:56
  • 1
    $\begingroup$ Given the sparsity of $A$, I would guess it should be possible to solve this problem in a few minutes without using distributed computing. But it's essentially that the solver exploits the sparsity. Have you tried using Mosek? Also, does the solution need to be highly accurate or is it ok if you only have a few digits of accuracy? If you don't need high accuracy then you could consider using a first-order method. $\endgroup$ – littleO Feb 16 '18 at 20:08