Simple linear programming with integer variables in R, using lpSolve

In the previous post (http://www.supplychaindataanalytics.com/solving-a-simple-linear-programming-problem-using-lpsolve-in-r/) I demonstrated how a simple linear optimization problem can be modelled and solved using the lpSolve package in R.

In this post I want to add the topic of modelling integer variables.

In the previous post we maximized objective function 2x + 3y, with the constraint that x + y <= 3. When both variables are continous non-negative, the solution is y=3 with optimal value of the objective function equalling 9.

In this post we add as another constraint, that y must be an integer. Moreover, I adjust the initial constraint such that now x + y <= 3.9. Using the lpSolve package in R the integer variable constraint can be considered by specifying the int.vec parameter, representing a vector with the indices of the integer variables to be considered by the problem. In this case the index is 2, since y is an integer.

I start by solving a simple linear programming problem similar to the past one, only that x + y <= 3.9 (instead of 3.0). The objective function is unchanged – hence this is the non-integer problem (serving as a benchmark):

library(lpSolve)
f.obj <- c(2,3)                           # coefficient vector of objective function
f.con <- matrix(c(1,1),nrow=1,byrow=TRUE) # coefficient matrix for constraint matrix
f.dir <- c("<=")                          # constraint direction vector
f.rhs <- c(3.9)                           # constraint values
#f.intvec <- NA                            # indices of the variables that must be integers

solution <- lp(direction = "max",
               objective.in = f.obj,
               const.mat = f.con, 
               const.dir = f.dir, 
               const.rhs = f.rhs#,
               #int.vec = f.intvec,        # specifying this function parameter indicates which variables are integers
               #all.int = FALSE
               )

solution
## Success: the objective function is 11.7

The optimal solution to the non-integer problem with the constraint x + y <= 3.9 has the following optimum (= maximum).

solution$solution
## [1] 0.0 3.9

Now, I model and solve above model once again – but with y being specified as an integer variable.

library(lpSolve)
f.obj <- c(2,3)                           # coefficient vector of objective function
f.con <- matrix(c(1,1),nrow=1,byrow=TRUE) # coefficient matrix for constraint matrix
f.dir <- c("<=")                          # constraint direction vector
f.rhs <- c(3.9)                           # constraint values
f.intvec <- c(2)                          # indices of the variables that must be integers

solution <- lp(direction = "max",
               objective.in = f.obj,
               const.mat = f.con, 
               const.dir = f.dir, 
               const.rhs = f.rhs,
               int.vec = f.intvec#,        # specifying this function parameter indicates which variables are integers
               #all.int = FALSE
               )

solution
## Success: the objective function is 10.8

The maximum value of the objective function, considering the additional integer constraint, has lowered. The optimal point is now:

solution$solution
## [1] 0.9 3.0

As we can see, the optimal solution is no longer that y be 3.9 but instead that y be equal to 3 – which is indeed an integer value!

If you are interested in linear programming please check out my other blog posts on this topic. Also, please – if interested – check out my posts on non-linear and quadratic programming. Lastly, you might also be interested in reading my post on linear programming in Python, using the SciPy module.

Leave a Reply

Leave a Reply

Your email address will not be published. Required fields are marked *

Close

Meta