Table of Contents generated with DocToc
Rulp is an easy to use Ruby DSL for generating linear programming and mixed integer programming problem descriptions in the LP file format.
The [.lp] file format can be read and executed by most LP solvers including coin-Cbc, Scip, GLPK, CPLEX and Gurobi.
Rulp will execute and parse the results generated by Cbc, Scip, fscip(ug) and GLPK.
Rulp is inspired by the ruby wrapper for the GLPK toolkit and the python LP library "Pulp".
# maximize
# z = 10 * x + 6 * y + 4 * z
#
# subject to
# p: x + y + z <= 100
# q: 10 * x + 4 * y + 5 * z <= 600
# r: 2 * x + 2 * y + 6 * z <= 300
#
# where all variables are non-negative integers
# x >= 0, y >= 0, z >= 0
#
given[
X_i >= 0,
Y_i >= 0,
Z_i >= 0
]
result = Rulp::Max( 10 * X_i + 6 * Y_i + 4 * Z_i ) [
X_i + Y_i + Z_i <= 100,
10 * X_i + 4 * Y_i + 5 * Z_i <= 600,
2 * X_i + 2 * Y_i + 6 * Z_i <= 300
].solve
##
# 'result' is the result of the objective function.
# You can retrieve the values of variables by using the 'value' method
# E.g
# X_i.value == 32
# Y_i.value == 67
# Z_i.value == 0
##To use Rulp as a complete solver toolkit you will need one of either Glpsol(GLPK), Scip or Coin-Cbc installed. Here are some sample instructions of how you install each of these solvers. Be sure to read the license terms for each of these solvers before using them.
####Scip:
Go to install directory
cd /usr/local
Download Scip source (Be sure to visit the SCIP website and check the license terms first.)
curl -O http://scip.zib.de/download/release/scipoptsuite-3.1.1.tgz
Extract Scip source
gunzip -c scipoptsuite-3.1.1.tgz | tar xvf -
Scip relies on a number of libraries including ZLIB, GMP and READLINE. Please read the INSTALL directory in the application directory for help on getting these installed.
Build Scip
cd scipoptsuite-3.1.1
make
Add scip bin directory to your path E.g
echo '\nexport PATH="$PATH:/usr/local/scipoptsuite-3.1.1/scip-3.1.1/bin"' >> ~/.bash_profile
Or
echo '\nexport PATH="$PATH:/usr/local/scipoptsuite-3.1.1/scip-3.1.1/bin"' >> ~/.zshrc
You should now have scip installed.
To run scip using multiple cores you will need to use the UG library for scip. This is bundled in the scipoptsuite directory. To install this simply run
make ug
From the base directory and then add the fscip binary to your path. E.g
echo '\nexport PATH="$PATH:/usr/local/scipoptsuite-3.1.1/ug-0.7.5/bin"' >> ~/.bash_profile
Or
echo '\nexport PATH="$PATH:/usr/local/scipoptsuite-3.1.1/ug-0.7.5/bin"' >> ~/.zshrc
####Coin Cbc:
Navigate to install location
cd /usr/local
Follow CBC installation instructions
svn co https://projects.coin-or.org/svn/Cbc/stable/2.8 coin-Cbc
cd coin-Cbc
./configure -C #Optionally add --enable-cbc-parallel here to enable multiple threads for cbc
make
make install
Add Coin-cbc to path
E.g
echo '\nexport PATH="$PATH:/usr/local/coin-Cbc/bin"' >> ~/.bash_profile
Or
echo '\nexport PATH="$PATH:/usr/local/coin-Cbc/bin"' >> ~/.zshrc
You should now have coin-Cbc installed.
####GLPK: Download the latest version of GLPK from http://www.gnu.org/software/glpk/#downloading
From the download directory
tar -xzf glpk-4.55.tar.gz
cd glpk-4.55
./configure --prefix=/usr/local
make
sudo make install
At this point, you should have GLPK installed. Verify it:
which glpsol
=> /usr/local/bin/glpsol
# Rulp variables are initialized as soon as they are needed so there is no
# need to initialize them.
# They follow a naming convention that defines their type.
# A variable is declared as a constant with one of three different suffixes.
# 'f' or '_f' indicates a general variable (No constraints)
# 'i' or '_i' indicates a integer variable
# 'b' or '_b' indicates a binary/boolean variable
An_Integer_i
=> #<IV:0x007ffc4b651b80 @name="An_Integer">
Generalf
=> #<LV:0x007ffc4b651b80 @name="General">
Bool_Val_b
=> #<BV:0x007ffc4b67b6b0 @name="Bool_Val">
# In some cases it is implausible to generate a unique name for every possible variable
# as an LP problem description may contain many hundreds of variables.
# To handle these scenarios variable definitions can
# accept index parameters to create large ranges of unique variables.
# Examples of how indexed variables can be declared are as follows:
Item_i(4,5)
#<IV:0x007ffc4b3ea518 @name="Item4_5">
Item_i("store_3", "table_2")
#<IV:0x007ffc4b3a3cd0 @name="Itemstore_3_table_2">
[*0..10].map(&Unit_f)
=> [#<LV:0x007ffc4cc25768 @name="Unit0">,
#<LV:0x007ffc4cc24cf0 @name="Unit1">,
#<LV:0x007ffc4cc0fc88 @name="Unit2">,
#<LV:0x007ffc4cc0f260 @name="Unit3">,
#<LV:0x007ffc4cc0ecc0 @name="Unit4">,
#<LV:0x007ffc4cc0e748 @name="Unit5">,
#<LV:0x007ffc4cc0df50 @name="Unit6">,
#<LV:0x007ffc4cc0d9d8 @name="Unit7">,
#<LV:0x007ffc4cc0d460 @name="Unit8">,
#<LV:0x007ffc4cc0cee8 @name="Unit9">,
#<LV:0x007ffc4cc0c970 @name="Unit10">]Add variable constraints to a variable using the <,>,<=,>=,== operators. Be careful to use '==' and not '=' when expressing equality. Constraints on a variable can only use numeric literals and not other variables. Inter-variable constraints should be expressed as problem constrants. (Explained below.)
X_i < 5
X_i.bounds
=> "X <= 5"
3 <= X_i < 15
X_i.bounds
=> "3 <= X <= 15"
Y_f == 10
Y_f.bounds
=> "y = 10"Constraints are added to a problem using the :[] syntax.
problem = Rulp::Max( 10 * X_i + 6 * Y_i + 4 * Z_i )
problem[
X_i + Y_i + Z_i <= 100
]
problem[
10 * X_i + 4 * Y_i + 5 * Z_i <= 600
]
...
problem.solveYou can add multiple constraints at once by comma separating them as seen in the earlier examples:
Rulp::Max( 10 * X_i + 6 * Y_i + 4 * Z_i ) [
X_i + Y_i + Z_i <= 100,
10 * X_i + 4 * Y_i + 5 * Z_i <= 600,
2 * X_i + 2 * Y_i + 6 * Z_i <= 300
]There are multiple ways to solve the problem or output the problem to an 'lp' file.
Currently the Rulp library supports calling installed executables for Scip, Cbc and Glpk.
For each of these solvers it requires the solver command line binaries to be installed
such that the command which [exec_name] returns a path. (I.e they must be on your PATH. See Installation).
Given a problem there are multiple ways to initiate a solver.
@problem = Rulp::Max( 10 * X_i + 6 * Y_i + 4 * Z_i ) [
X_i + Y_i + Z_i <= 100,
10 * X_i + 4 * Y_i + 5 * Z_i <= 600,
2 * X_i + 2 * Y_i + 6 * Z_i <= 300
]Default solver:
@problem.solve
# this will use the solver specified in the environment variable 'SOLVER' by default.
# This can be 'scip', 'cbc', 'glpk' or 'gurobi'.
# You can also try and run scip or cbc in parallel using by passing an options argument containing { parallel: true }
# If no variable is given it uses 'scip' as a default.If you had a linear equation in a file named 'problem.rb' from the command line you could specify an alternate solver by executing:
SOLVER=cbc ruby problem.rbExplicit solver:
@problem.scip
# Or
@problem.cbc
# Or
@problem.glpk
# Or
@problem.cbc(parallel: true)
# Or
@problem.scip(parallel: true)Or
Rulp::Scip(@problem)
Rulp::Glpk(@problem)
Rulp::Cbc(@problem)
Rulp::scip(@problem, parallel: true)
Rulp::cbc(@problem, parallel: true)For debugging purposes you may wish to see the input and output files generated and consumed by Rulp.
To do this you can pass open_definition and open_solution as options with the following extended syntax:
Rulp::Cbc(@problem, open_definition: true, open_solution: true)The optional booleans will optionally call the 'open' utility to open the problem definition or the solution. (This utility is installed by default on a mac and will not work if the utility is not on your PATH)
You can provide a MIP tolerance to any of the solvers to allow it to return a sub-optimal result within this tolerance from the dual bound.
# Various ways to invoke this option
@problem.cbc(gap: 0.05)
Rulp::Cbc(@problem, gap: 0.05)
@problem.solve(gap: 0.05)You can limit the number of nodes the solver is able to explore before it must return it's current most optimal solution. If it has not discovered a solution by the time it hits the node limit it will return nil. Glpk does not accept a node limit option.
# Various ways to invoke this option
@problem.cbc(node_limit: 10_000)
Rulp::Cbc(@problem, node_limit: 10_000)
@problem.solve(node_limit: 10_000)For Scip you can also specify these limits in a settings file called scip.set in the current directory. Options passed to Rulp will overwrite these values.
# E.g inside ./scip.set
limits/gap = 0.15 # optimality within 0.1%.
limits/nodes = 200000 # No more than 200000 nodes explored
You may not wish to use one of the RULP compatible solvers but instead another solver that is able to read .lp files. (E.g CPLEX) but still want to use Rulp to generate your LP file. In this case you should use Rulp to output your lp problem description to a file of your choice. To do this simply use the following call
@problem.save("/Users/johndoe/Desktop/myproblem.lp")OR
@problem.output("/Users/johndoe/Desktop/myproblem.lp")You should also be able to call
@problem.saveWithout parameters to be prompted for a save location.
Take a look at some basic examples in the ./examples directory in the source code.
Rulp comes bundled with a 'rulp' executable which by default loads the rulp environment and either the Pry or Irb REPL. (Preference for Pry). Once installed you should be able to simply execute 'rulp' to launch this rulp enabled REPL. You can then play with and attempt LP and MIP problems straight from the command line.
[1] pry(main)> 13 <= X_i <= 45 # Declare integer variable
=> X(i)[undefined]
[2] pry(main)> -15 <= Y_f <= 15 # Declare float variable
=> Y(f)[undefined]
[3] pry(main)> @problem = Rulp::Min(X_i - Y_f) # Create min problem
[info] Creating minimization problem
=>
Minimize
obj: X -Y
Subject to
0 X = 0
Bounds
13 <= X <= 45
-15 <= Y <= 15
General
X
End
[4] @problem[ X_i - 2 * Y_f < 40] #Adding a problem constraint
=>
Minimize
obj: X -Y
Subject to
c0: X -2 Y <= 40
Bounds
13 <= X <= 45
-15 <= Y <= 15
General
X
End
[5] pry(main)> @problem.solve # Solve
...
[info] Solver took 0.12337
[info] Parsing result
=> -2.0 #(Minimal result)
[6] pry(main)> Y_f # See value calculated for Y now that solver has run
=> Y(f)[15.0]
[8] pry(main)> X_i
=> X(i)[13.0]
# The result of the objective function (-2.0) was returned by the call to .solve
# Now the solver has run and calculated values for our variables we can also test the
# objective function (or any function) by calling evaluate on it.
# E.g
[9] (X_i - Y_f).evaluate
=> -2.0
[10] pry(main)> (2 * X_i + 15 * Y_f).evaluate
=> 251.0Here is a basic example of how Rulp can help you model problems with a large number of variables. Suppose we are playing an IOS app which contains in-app purchases. Each of these in-app purchases costs a variable amount and gives us a certain number of in-game points. Suppose our mother gave us $55 to spend. We want to find the maximal number of in-game points we can buy using this money. Here is a simple example of how we could use Rulp to formulate this problem.
We decide to model each of these possible purchases as a binary variable (as we either purchase them or we don't. We can't partially purchase one.)
# Generate the data randomly for this example.
costs, points = [*0..1000].map do |i|
[Purchase_b(i) * Random.rand(1.0..3.0), Purchase_b(i) * Random.rand(5.0..10.0)]
end.transpose.map(&:sum) #We sum the array of points and array of costs to create a Rulp expression
# And this is where the magic happens!. We ask rulp to maximise the number of points given
# the constraint that costs must be less than $55
Rulp::Max(points)[
costs < 55
].solve
=> 538.2125623353652 (# You will get a different value as data was generated randomly)
# Now how do we check which purchases were selected?
selected_purchases = [*0..1000].map(&Purchase_b).select(&:selected?)
=> [Purchase27(b)[true],
Purchase86(b)[true],
Purchase120(b)[true],
Purchase141(b)[true],
Purchase154(b)[true],
...Here is another example of using array style variables. Let's use the example of making a cup of coffee. Personally, I like my coffee with 2 creams and 1 sugar. There are many types of products that can add cream, or sugar to taste. Each has a different associated cost. As a price sensitive consumer what combination of products will allow me to flavor my coffee as desired with the lowest total cost?
desired = [
{ ingredient: :cream, amount: 2 },
{ ingredient: :sugar, amount: 1 },
]
products = [
{ name: 'Milk', cost: 0.50, supplies: { cream: 1 } },
{ name: 'Baileys_Irish_Cream', cost: 2.99, supplies: { cream: 1, sugar: 1 } },
{ name: 'Non_Dairy_Creamer', cost: 0.10, supplies: { cream: 1 } },
{ name: 'Sugar', cost: 0.10, supplies: { sugar: 1 } },
]
variables = products.map do |product|
Products_i(product[:name])
end
# => [ ProductMilk_i, ProductBaileys_Irish_Cream_i, ProductNon_Dairy_Creamer_i, ProductSugar_i ]
given[
variables.map { |i| i >= 0 }
]
# given [
# ProductMilk_i >= 0,
# ProductBaileys_Irish_Cream_i >= 0,
# ProductNon_Dairy_Creamer_i >= 0,
# ProductSugar_i >= 0,
# ]
constraints = desired.map do |minimum|
ingredient = minimum[:ingredient]
desired_amount = minimum[:amount]
products.map.with_index do |p, i|
coefficient = p[:supplies][ingredient] || 0
coefficient * variables[i]
end.inject(:+) >= desired_amount
end
# => [
# 1 * ProductMilk_i + 1 * ProductBaileys_Irish_Cream_i + 1 * ProductNon_Dairy_Creamer_i + 0 * ProductSugar_i >= 2
# 0 * ProductMilk_i + 1 * ProductBaileys_Irish_Cream_i + 0 * ProductNon_Dairy_Creamer_i + 1 * ProductSugar_i >= 1
# ]
objective = products.map.with_index { |p, i| p[:cost] * variables[i] }.inject(:+)
# => 0.50 * ProductMilk_i + 2.99 * ProductBaileys_Irish_Cream_i + 0.10 * ProductNon_Dairy_Creamer_i + 0.10 * ProductSugar_i
problem = Rulp::Min(objective)
problem[constraints]
Rulp::Glpk(problem)
# DEBUG -- : Objective: 0.30000000000000004
# Products = 0.0
# Products = 0.0
# Products = 2.0
# Products = 1.0
variables.map(&:value)
# => [ 0, 0, 2, 1 ]