Solving Linear Programming Problems with the Gnu Linear Programming Kit

September 20th, 2009

The GNU Linear Programming Kit (GLPK) can be accessed in R and used for solving large-scale linear programming (LP), mixed integer programming (MIP) and other scenarios. The Rglpk package can be installed and provides a simple interface to using the GLPK.

The main function of interest in this package is Rglpk_solve_LP and there are various options that can be specified by the user. The specification for the function is:

Rglpk_solve_LP(obj, mat, dir, rhs, types = NULL, max = FALSE, bounds = NULL,
  verbose = FALSE)

To make use of this function we need to determine the variables and how they combine to form our objective function that will either be minimised or maximised subject to a set of constraints. The obj argument is specified as a vector of the coefficients of the variables in the objective function.

The constraints are specified across three arguments (mat, dir, and rhs) that correspond to the coefficients of the constraints (using a matrix), the sign associated with the constraints (e.g. greater than) and the value for the constraint condition (the right hand side of the constraint equations). The types argument is optimal and will specify whether the variable is binary, integer or a continuous value. The max variable is logical (TRUE or FALSE) and determines whether the objective function should be minimised or maximised.

As an example consider a shop that manufactures and sells two models of the same item, a basic and deluxe version. These two models retail for £5 and £20 respectively. The manufacturing costs can be divided into materials and labour costs. For the basic model these costs are £2 and £1 respectively and for the deluxe model these costs are £6 and £4 respectively. Each week the shop can allocate 75 hours to manufacturing the items and the basic model takes 0.5 hours and the deluxe model takes 1.75 hours to manufacture. In a given week the shop owner will not expect to be able to sell more than 75 units of the basic model and 25 units of the deluxe model.

We need to convert these conditions and relationships into linear equations that can be used by the linear programming algorithms to identify a solution. The objective function is based on the retail price minus the materials and labour costs so for B and D units of the basic and deluxe mode we have:

(5*B + 20*D) - (2*B + 6*D) - (1*B + 4*D) = 2*B + 10*D

and we want to maximise this value. The construction constraint is based on 75 hours maximum and using the time to build from above we have:

0.5*B + 1.75*D <= 75

The number of units that can be sold can be specified reasonably simply as

B <= 100
D <= 25

We can specify the various arguments to the functions as objects:

obj = c(2, 10)
mat = matrix(c(0.5, 1.75, 1, 0, 0, 1), nrow = 3, byrow = T)
dir = c("<=", "<=", "<=")
types = c("I", "I")
rhs = c(75, 100, 25)

It should be reasonably straight forward to match these values up with the equations described above. The obj argument is a vector of two elements, which are the coefficients of the function to maximise. The mat object is a matrix of the coefficients for the three condition statements. The dir vector is character strings specifying the type of condition and the rhs vector is the values on the right hand side of the constraint equations. The types argument is specified as integers as we can’t build a non integer number of units.

The function call to solve this problem is:

Rglpk_solve_LP(obj, mat, dir, rhs, types, max = TRUE)

and the output from this function call:

[1] 374
[1] 62 25
[1] 0

The function has been maximised to a value of £374, which corresponds to making 62 of the basic model and 25 of the deluxe model during the week.

One response to “Solving Linear Programming Problems with the Gnu Linear Programming Kit”

  1. Dan says:

    Great post! I’ve been looking for tutorials to do LP with R. Your post is good for a beginner like me! Would you recommend some books, websites, videos, etc to learn LP (and OR/MS in general)? Thanks a lot!