3

I'm writing some code in C++, and it turns out I need to solve an optimization problem which may be formulated using m variables and n linear constraints (i.e. constraint i is of the form \sum_j a_{i,j} x_j >= b_i ; although if you don't know what linear programming is you can probably not answer this question).

I need the solution to be fast - at least in expectation (hopefully no more than one pass over most constraints) - and I'm willing to pay in distance from the optimum for that.

Is there a library for this 'niche' of linear programming? If not, what would be generally fast linear programming libraries?

Requirements:

  • Libre license
  • Code available
  • Works on Linux
  • Works on x86_64
  • Fast
  • Gratis

Desired features:

  • Really fast
  • Can trade off accuracy for speed
  • Multi-platform
  • C++ rather than C
  • Modern C++ rather than C++98/03
  • Well-documented
  • If C++ is indeed not an absolute requirement, you can also look at open source Java Solvers, such as OptaPlanner and Choco, fwiw. – Geoffrey De Smet Jul 17 at 7:50
0

I'm looking into COIN-OR's CLP. It's a C++ FOSS LP solver; beyond that I can't say much for now.

0

There are two aspects to discuss here:

  1. The algorithm.
  2. The implementation of (1) in a suitable language.

The algorithm is what determines the runtime and accuracy of the method. If you are willing to sacrifice accuracy, you would choose a method like IP over Simplex (this is an example for illustrative purposes).

As for the implementation - seeing how these sort of problems are usually solved by matrix operations, you can use the classic go-to library for these things - BLAS. Another possibility is the GLPK package. If you want a demonstration of how to use the latter, take a look at Octave's source code. Perhaps Octave's documentation on the topic might also be useful.

BTW, another way to make the tradeoff, regardless of the specific technique, is performing the computation in a reduced-precision datatype, e.g. float32 and not float64.

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.