This gem provides both an FFI interface to the lp_solve library and a simplified interface designed to pick from a set of choices to satisfy constraints (LPSelect).
lp_solve is a Mixed Integer Linear Programming (MILP) solver. It solves pure linear, (mixed) integer/binary, semi-cont and special ordered sets (SOS) models. lp_solve is written in ANSI C and can be compiled on many different platforms like Linux and WINDOWS.
The lp_solve library is included and dynamically loaded. The gem will look for the library in the lib/binaries folder, and searches for the first library it can load in this order:
liblpsolve55.dylib liblpsolve55.dylib-ppc liblpsolve55.dylib.x86-64 liblpsolve55.so liblpsolve55.so-ux64 lpsolve55.dll
You can download and compile the liblpsolve library from http://sourceforge.net/projects/lpsolve/
LPSelect is designed for selecting a set of things that satisfies as many constraints as possible. The lp_select_test.rb test is a contrived example showing how it can be used to select a fruit salad at the lowest cost that satisfies the most people. The price of each fruit is a weight and the objective is to minimize the cost (ie weight) of the selected fruits. Each person's choices is added as a constraint row.
Add this line to your application's Gemfile:
gem 'lp_select'
And then execute:
$ bundle
Or install it yourself as:
$ gem install lp_select
Current usage is focused on a handful of known problems to be solved, but it is easily extensible.
The lp_solve library uses 1 indexed arrays.
There is more example usage in the LPSelect library and tests
# Make a three row five column equation@lp=LPSolve::make_lp(3,5)# Set some column namesLPSolve::set_col_name(@lp,1,"fred")LPSolve::set_col_name(@lp,2,"bob")# Add a constraint and a row name, the API expects a 1 indexed arrayconstraint_vars=[0,0,1]FFI::MemoryPointer.new(:double,constraint_vars.size)do |p|
p.write_array_of_double(constraint_vars)LPSolve::add_constraint(@lp,p,LPSelect::EQ,1.0.to_f)endLPSolve::set_row_name(@lp,1,"onlyBob")# Set the objective function and minimize itconstraint_vars=[1.0,3.0]FFI::MemoryPointer.new(:double,constraint_vars.size)do |p|
p.write_array_of_double(constraint_vars)LPSolve::set_obj_fn(@lp,p)endLPSolve::set_minim(@lp)# Solve it and retreive the resultLPSolve::solve(@lp)@objective=LPSolve::get_objective(@lp)- Fork it
- Create your feature branch (
git checkout -b my-new-feature) - Commit your changes (
git commit -am 'Add some feature') - Push to the branch (
git push origin my-new-feature) - Create new Pull Request
- James Prior
- Jake Sower
- Mattias Ekberg