2
$\begingroup$

I have the following LP problem:

$$ \min \limits_{\varepsilon, x_{1}, \ldots, x_{n}}f(\varepsilon, x_{1}, \ldots, x_{n}) = \varepsilon \;\;\;\;\; \mathrm{s.t.} \;\;C x \geq 0, \;\; x_{i}^{0} - \varepsilon \leq x_{i} \leq x_{i}^{0} + \varepsilon $$

where $C$ is $m \times n$ matrix, and $x$ and $x^{0}$ are vectors of dimension $n$.

$C$ is a very sparse matrix, each of its rows contains only $4$ non-zero values.

The typical case is $m = 15000$ and $n = 5000$.

Can anybody advise any LP-solver that can provide the best performance for this problem?

Improve this question
$\endgroup$
1
  • $\begingroup$ Python is not hard to learn. I would suggest Gurobi using the Python interface. $\endgroup$
    – Sergio Parreiras
    Jun 11, 2014 at 13:48

2 Answers 2

Reset to default
4
$\begingroup$

The best performance solvers are probably Gurobi or CPLEX; last I checked, Gurobi is slightly faster, but both are competitive. These two commercial solvers are roughly ten times faster than the best open-source solvers.

That said, as AC_MOSEK points out, your problem is small enough that essentially any functioning LP solver based on sparse data structures (i.e., most of them) will work. Instead of locking your implementation into a specific solver, if you can, I suggest implementing your problem in an optimization framework like GAMS or AMPL, or using an LP-specific modeling framework such as PuLP or Coopr. These frameworks are geared towards making it easy for you to input your problem in a solver-independent, math-like format, so you can experiment with different formulations and solvers rapidly. Then, after settling on a formulation and solver combination that works best for you, you can implement it in a lower-level language for speed for that formulation and specific solver.

Improve this answer
$\endgroup$
6
  • $\begingroup$ Thanks, @GeoffOxberry, do you mean that it's possible to give different solvers to optimization frameworks, i. e. without big modification in the program itself? Is it possible to do it using Matlab? If there is no difference for me, what framework is better? $\endgroup$
    – Ilya Palachev
    Apr 2, 2014 at 4:45
  • $\begingroup$ Yes, it is possible to give different solvers to optimization frameworks without extensive modifications (maybe one to two lines). It might be possible to do using MATLAB, but you would likely need to buy that capability (TOMLAB might have an LP modeling framework). If you know Python, PuLP is lightweight and easy to learn; Coopr is more powerful, but takes more time to learn. If you don't know Python, I would use GAMS. You can download a free copy for small problems, and submit large problems through the NEOS server. $\endgroup$
    – Geoff Oxberry
    Apr 2, 2014 at 21:12
  • $\begingroup$ The problem is that I don't exactly know what formulation to use. Because LP problem may be used just for finding first approximation for the QP problem: $\min ||h - h^{0}||^{2}_{2} \;\; s. t. Q h \geq 0$. So I have doubt that LP-based frameworks can help with this. The current idea is to use some LP solver to find first approximation and then give it as input to Ipopt algorithm, using Eigen as an angine for matrix multiplcation, needed for Ipopt. Also I have heard that algorithm PDCOcan solve it in 1 sec $\endgroup$
    – Ilya Palachev
    Apr 3, 2014 at 7:42
  • $\begingroup$ GAMS and AMPL are modeling languages designed for general-purpose optimization, not specifically for LPs, so these frameworks would still be of use to you. If you intend to use a QP formulation, Gurobi and CPLEX also have QP solvers, and these would also be better than open-source alternatives. Eigen is not a dependency of IPOPT; BLAS and LAPACK libraries are. Using optimized BLAS and LAPACK libraries (vendor-specific, GotoBLAS/OpenBLAS, ATLAS), plus a linear solver such as HSL (or MUMPS, you should experiment with both, if possible) would be better courses of action. $\endgroup$
    – Geoff Oxberry
    Apr 3, 2014 at 18:29
  • $\begingroup$ Thanks, @GeoffOxberry, and have you ever heard anything about PDCO method? $\endgroup$
    – Ilya Palachev
    Apr 4, 2014 at 5:12
1
$\begingroup$

Your problem seems fairly easy, I would say that any reasonable LP solver should solve it in seconds. So it might be more a choice related to API's, price, licensing. Try out MOSEK, CPLEX or GUROBI among the commercial ones, or CLP from the coin-or project. You can find a list on Wikipedia

http://en.wikipedia.org/wiki/Linear_programming

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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