5
$\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 3 \cdot 10^6$ rows and $\sim 1 \cdot 10^6$ 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 a Network problem. 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) 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$
  • 1
    $\begingroup$ Have you tried other solvers such as CPLEX or Gurobi? If by 3 M M constraints you mean $3 \times 10^{6}$ constraints, then your problem is in fact very large, and you'll probably need to use one of the better software packages to have any chance of solving this problem. $\endgroup$ – Brian Borchers Feb 16 '18 at 21:47
  • $\begingroup$ Haven't tried CPLEX or Gurobi yet. Trying to avoid buying. But, yes - $3 X 10^6$ constraints. My intuition is that the very sparse nature of $A$ should help. Each constraint looks like: $x_i + ax_j \geq b$. $\endgroup$ – EDZ Feb 16 '18 at 22:07
  • $\begingroup$ You may want to edit your question to use $3\cdot 10^6$ instead of $3MM$ mean. I stumbled about this as well. $\endgroup$ – Wolfgang Bangerth Feb 17 '18 at 2:14
  • $\begingroup$ Edited to be more explicit in size of the problem. Thanks! $\endgroup$ – EDZ Feb 17 '18 at 16:42
  • $\begingroup$ 1) can you describe what the problem is ? Quite a few reduce to LP in theory but have fast special-purpose algorithms, e.g. Constraint programming (python: kiwisolver). 2) Would you know of a smaller similar problem on the web ? Thanks $\endgroup$ – denis Jul 19 at 14:22
1
$\begingroup$

Have you tried any of the Coin-OR tools, like cbc or clp? They are pretty comparable to CPLEX for LP (not MIPs though), at least until a certain scale of the problem (your size should be solvable quickly using these). They claim to have support for Dantzig-Wolfe, although I haven't tried that.

$\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.