Linear programming is used to minimize or maximize a function subject to constraints when both the objective function and the constraints can be expressed as linear equations or inequalities. More generally, these optimization problems can be expressed as follows:
The preceding formula is subject to the following constraints:
It is also subject to the non-negativity constraint ,
, …,
. In other words, we are interested in finding the values for the decision variables
, which minimize the objective function L(x) subject to the constraints and non-negative conditions. The opposite of this is also true to maximize a linear program, as follows:
The preceding formula is subject to the following constraints:
It is also subject to the non-negativity constraint ,
, …,
.
R has a few packages and functions available to help solve linear programming problems. We will go over a few examples to show you how to use these functions to set up and solve linear programs. Let's start by solving the following problem:
The preceding equation is subject to the following constraints:
Firstly, we will plot and solve this problem using the lpSolveAPI package as follows:
> install.packages("lpSolveAPI")
> library("lpSolveAPI")Next, we will create an lpSolve linear program model object with two constraints and two decision variables with the make.lp() function as follows:
> lp1 <- make.lp(2, 2)
Then, we will build the model column-wise using the set.column() function for each decision variable using a vector with to
for
(column 1) and
to
for
(column 2) as given in the following lines of code:
> set.column(lp1, 1, c(1, 1)) > set.column(lp1, 2, c(1, 2))
Now let's set the objective function using the set.objfn() function and a vector with and
, and the constraint type with the
set.constr.type() function for each inequality in a vector as follows:
> set.objfn(lp1, c(4, 7))
> set.constr.type(lp1, rep(">=", 2))Lastly, we set the values to the right-hand side of the constraint inequalities using the set.rhs() function, as given in the following code, using a vector with and
:
> set.rhs(lp1, c(4, 6))
We can see an overview of our model by entering lp1 as follows:
> lp1
Model name:
C1 C2
Minimize 4 7
R1 1 1 >= 4
R2 1 2 >= 6
Kind Std Std
Type Real Real
Upper Inf Inf
Lower 0 0 As you can see, the upper and lower bounds are automatically set to ∞ and 0 by default, so we are ready to solve the problem. We will show you how to change the default settings later. We can plot the model using the plot() function as follows:
> plot(lp1)
The result is shown in the following plot:
In the previous plot, the region in gray shows the values for when neither constraints are satisfied. It seems like the solution to our problem is (2, 2), but let's go through the necessary steps to validate the solution. First, we can double-check our linear program that we entered by saving the model to a file that we will call model1.lp with the write.lp() function as follows:
> write.lp(lp1,'model1.lp',type='lp')
If you open the file in a text editor, you will see the following lines:
/* Objective function */ min: +4 C1 +7 C2; /* Constraints */ +C1 +C2 >= 4; +C1 +2 C2 >= 6;
The preceding lines match our objective function and inequalities as follows:
Next, we check whether an optimal solution has been found for our linear program with the solve() function as follows:
> solve(lp1) [1] 0
Since this is a generic function in R, we need to go to the help page with ?solve.lpExtPtr to be able to know what 0 means, as follows:
> ?solve.lpExtPtr # [… ] Status Codes 0: "optimal solution found" 1: "the model is sub-optimal" 2: "the model is infeasible" 3: "the model is unbounded" 4: "the model is degenerate" 5: "numerical failure encountered" 6: "process aborted" 7: "timeout" 9: "the model was solved by presolve" 10: "the branch and bound routine failed" 11: "the branch and bound was stopped because of a break-at-first or break-at-value" 12: "a feasible branch and bound solution was found" 13: "no feasible branch and bound solution was found" # Output truncated
We can get the values for and
with the
get.variables() function and the minimum value of the objective function with the get.objective() function as follows:
> get.variables(lp1) [1] 2 2 > get.objective(lp1) [1] 22
Alternatively, we could have used the lp() function from the lpSolve package as follows:
> install.packages("lpSolve")
> library(lpSolve)
> lp.ex1 <- lp(objective.in=c(4, 7), const.mat=matrix(c(1,1,1,2), nrow=2), const.rhs=c(4, 6), const.dir=rep(">=", 2)) As you will notice, we specify the and
values for the objective function with the
objective.in argument, the values for the columns as a matrix with the const.mat argument, the constants to the right-hand side of the constraint formulas with the const.rhs argument, and the constraint types with the const.dir argument.
To check whether the problem is solved, we simply need to enter the model lp.ex1 object generated from the lp() function in R as follows:
> lp.ex1 Success: the objective function is 22
The lp.ex1 object is actually a list of multiple elements including the $solution numeric vector containing the values for and
, which we access with
lp.ex1$solution as follows:
> lp.ex1$solution [1] 2 2
We can also solve integer-restricted linear programs with the lpSolveAPI and lpSolve packages. Consider the following example; a company produces laptops and tablets. The profit for the laptops is 52 dollars per laptop and 82 dollars per tablet. Due to production capacity, no more than 100 laptops and 170 tablets can be made per day. The company has a private contract that requires them to produce at least 65 laptops and 92 tablets. If the company only wants to make at most 200 units per day, how many laptops and tablets should they produce to maximize profits? Let's set up the problem as an objective function and inequalities.
Let x1 be the number of laptops to be produced and x2 be the number of tablets to be produced. We will use the following formula to solve this problem:
The constraints are as follows:
These inequalities can be entered into a lpSolveAPI model as follows:
> lp2 <- make.lp(1, 2)
> set.column(lp2, 1, c(1))
> set.column(lp2, 2, c(1))
> set.objfn(lp2, c(50, 82))
> set.constr.type(lp2, c("<="))
> set.rhs(lp2, c(200))Set the boundaries for both decision variables as follows:
> set.bounds(lp2, lower = c(65, 92), columns = c(1, 2)) > set.bounds(lp2, upper = c(100, 170), columns = c(1, 2))
Since and
are necessary integers, we need to set the type to
"integer" as follows:
> set.type(lp2, 1, "integer") > set.type(lp2, 2, "integer")
We can view a summary of the model by entering lp2 as follows:
> lp2
Model name:
C1 C2
Minimize 50 82
R1 1 1 <= 200
Kind Std Std
Type Int Int
Upper 100 170
Lower 65 0 Since we want to maximize the objective function, we need to set the objective direction with the lp.control() function and the sense argument as follows:
> lp.control(lp2,sense='max') # Output not shown
We can check our model by saving lp2 in a file that we can view in a text editor as follows:
> write.lp(lp2,'model2.lp',type='lp') /* Objective function */ max: +50 C1 +82 C2; /* Constraints */ +C1 +C2 <= 200; /* Variable bounds */ 65 <= C1 <= 100; 92 <= C2 <= 170; /* Integer definitions */ int C1,C2;
As you can see, everything is in order and the objective function direction is set to max. Now, to check whether we can solve the linear program with solve(lp2):
> solve(lp2) [1] 0
Since we can solve the problem, we can print the values for the decision variable and the maximum value as follows:
> get.variables(lp2) [1] 65 135 > get.objective(lp2) [1] 14320
Similarly, we can solve this linear program using the lp() function including the direction argument set to "max" and specifying the integer-restricted decision variables in a vector with the int.vec argument. To more easily conceptualize the const.mat argument, we will rewrite the constraint inequalities as follows:
So, const.mat will be matrix(c(1,1,1,0,0,1,0,0,1,1), nrow=5) as follows:
> lp.ex2 <- lp(objective.in=c(50, 82), const.mat=matrix(c(1,1,1,0,0,1,0,0,1,1), nrow=5), const.rhs=c(200, 65, 100, 92, 170), const.dir=c("<=", ">=", "<=", ">=", "<="), direction="max", int.vec=c(1, 2))We can get the optimal solution as follows:
> lp.ex2 Success: the objective function is 14320 > lp.ex2$solution [1] 65 135
The lp() function is set up to solve linear programs for decision variables that satisfy the non-negativity constraints ,
, …,
. One way to overcome this limitation is to replace the unrestricted decision variables
with the difference between two non-negative decision variables
.
For example, let's minimize the following linear program:
The preceding equation is subject to the following constraints:
However, is unrestricted in sign. To solve this problem, we will replace
with
, where
and
, and rewrite the objective function and constraint inequalities as follows:
We can now solve the problem as follows:
> lp.ex3 <- lp(objective.in=c(3, 4, -4), const.mat=matrix(c(1,3,1,2,-1,-1,-2,1,1), nrow=3), const.rhs=c(14, 0, 2), const.dir=c("<=", ">=", "<="), direction="min")
> lp.ex3
Success: the objective function is -8
> lp.ex3$solution
[1] 0 0 2The optimal solution is therefore and
, which means that
.