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.
Data scientist focusing on simulation, optimization and modeling in R, SQL, VBA and Python
Leave a Reply