Skip to content

wouterken/rulp

Folders and files

NameName
Last commit message
Last commit date

Latest commit

 

History

69 Commits
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

Repository files navigation

Rulp Gem Version Downloads Inline docs Codeship Status for wouterken/rulp

Table of Contents generated with DocToc

Rulp

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".

Sample Code

	# 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
	##

Installation

To use Rulp as a complete solver toolkit you will need one of either Glpsol(GLPK), Scip, Coin-Cbc or HiGHS 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.

UG (Scip parallel)

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

HiGHS:

Install HiGHS following the installation instructions at https://ergo-code.github.io/HiGHS/dev/interfaces/cpp/

Usage

Variables

	# 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">]

Variable Constraints

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"

Problem constraints

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.solve

You 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
		          ]

Solving or saving 'lp' files

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.rb

Explicit 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)

Additional Options

Mip tolerance.

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)
Node Limit.

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

Saving LP files.

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.save

Without parameters to be prompted for a save location.

Examples.

Take a look at some basic examples in the ./examples directory in the source code.

Rulp Executable

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.0

A larger example

Here 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],
 ...

MIP Minimization Example

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 ]