3

I need to solve a sparse linear programming problem, and I am looking for a library for the same.

Primary requirements:
The most important requirement is that it should be very fast. A randomised approximate solution is acceptable, if it is faster.

LP specifications:
The size of the problem is a function of 2 parameters : P and Q, with P << Q most of the times.
No. of variables ~ P + Q
No. of constraints ~ 2Q
The constraint matrix is sparse - it has only O(Q) non-zero entries.

Solutions tried
1) MATLAB : The linprog function of MATLAB is not particularly useful in our setting, as it takes very long to solve the LP.
2) GLPK : glpk_simplex is also not as fast as expected - for a problem with P=15, Q=15,000, I need to get an answer in at most 10 seconds, but glpk_simplex takes 20-25 minutes. glpk_interior runs out of memory for a problem of the above-mentioned size.

Can anyone suggest some efficient libraries? Please suggest both free and commercially available ones, that can be used to solve the problem exactly or approximately.

user2966082
  • 71
  • 5
  • 2
    Heh... "A randomized approximate solution is acceptable, if it is faster." Ok, 42 is the solution... Roughly random, and very approximate, given some arbitrary threshhold... – twalberg Nov 07 '13 at 19:11
  • 2
    [lpsolve](http://lpsolve.sourceforge.net/5.5/) is a very efficient (single threaded) open-source LP/MILP solver. On my 3 year old i7 laptop, it has solved *dense* problems with 1000 variables and 2000 constraints in less than 5 seconds. As far as commercial solvers go, I recommend you look at [Gurobi](http://www.gurobi.com/), which provides an efficient multi-threaded LP engine. – Anders Gustafsson Nov 07 '13 at 20:36

1 Answers1

2

Regarding other solver options, here are two SO questions that you should take a look at if you haven't checked them out already:

  1. SO Question on which solvers to use

  2. Java Solver Options

But the reason I am posting is that I have a couple of other suggestions for you, rather than going for the solver speed. (Something might work for Q ~ 15K in your problem, but if Q gets bigger, you will have to search for even faster solvers.)

Other suggestions to try

  1. Have you played around with the solver options in either MATLAB or GLPK? There are quite a number of things you could try: Setting iteration limit, or Timelimit (to 10000 milliseconds).

  2. Look into decomposing and relaxing your formulation. Typically, in these large LP's there is a nice underlying structure, but a few dense constraints play spoil-sport and those are the ones that give the solver trouble. If you can identify those, you can relax those, and maybe even throw it into the objective function with a multiplier.

    To make it a little more concrete, you consider Lagranian relaxations for 'troublesome constraints.' (As one reference to what I'm referring to see how problem 12.3 becomes 12.4 here after being relaxed. You can do the same for dense several constraints in your problem.

Hope this helps you move forward.

Community
  • 1
  • 1
Ram Narasimhan
  • 22,341
  • 5
  • 49
  • 55