In a previous tutorial you completed a code for the simplex algorithm. This exercise was to give you an idea of how the algorithm works, but in practice very few people code their own solvers for linear programming problems. There are many very good general-purpose solvers that are freely available. In this assignment we will discuss and use two solving packages in R: Rglpk and CVXR.
The GNU Linear Programming Kit (GLPK) is a well-known open-source package for solving linear and mixed-integer linear programming problems. It was originally written in the C computer language by Andrew Makhorin in 2000, and has been improved continuously since then. The official web page is:
https://www.gnu.org/software/glpk/
The Rglpk package is a version of glpk that has been adapted for R. You may install Rglpk in Rstudio using the package manager (see more detailed instructions below). More information for this package can befound here:
https://cran.r-project.org/web/packages/Rglpk/index.html
On the other hand, the CVXR package is a more general solver. CVXR can be used on a wider class of optimization problems, which can be characterized as “convex” (we’ll explain what that means in another tutorial). CVXR is an R-adapted version of CVX, both of which were developed by Stephen Boyd’s group at Stanford University. Like glpk, CVXR is still undergoing continuous improvement. More information on CVXR may be found here:
Since linear programming is a special case of convex optimization, we may use CVXR to solve linear programming problems.
If you are using RStudio, you can simply find the tab labeled “Packages” (lower right pane) and click the “Install” option. It will prompt you to search for a package to install. You can type in Rglpk and make sure you have the box checked to intall dependencies. Next, press the “Install” button. You can install CVXR the exact same way.
When you need to use the functionality of one of these solvers, make sure that it is a package which has been selected. To see if you are able to use it, simply go to the Packages tab and make sure the box next to the package is checked. This lets RStudio know that it may use functions and methods from this package when running scripts or in the console.
Instead of checking the box, you may also include in your R code the statement:
library(“Rglpk”)
(make sure that you use capital R) or
library(“”)
Let’s solve the following linear program:
\[\begin{alignat}{2} & \text{maximize} & \quad & 2 x_1 + 4 x_2 + 3 x_3\nonumber \\ & \text{subject to} & & 3 x_1 + 4 x_2 + 2 x_3 \leq 60 \\ & & & 2 x_1 + x_2 + 2 x_3 \leq 40 \\ & & & x_1 + 3 x_2 + 2 x_3 \leq 80 \\ & & & x_1,x_2,x_3 \geq 0 \nonumber \end{alignat}\]First we need to give the solver appropriate inputs. Here’s this example implemented using the Rglpk solver:
library(Rglpk)
#coefficents from objective functions
obj <- c(2, 4, 3)
#matrix with constraint coefficients
mat <- rbind(c(3, 4, 2),c(2, 1, 2),c(1, 3, 2))
#vector with type and direction of inequality for each constraint
dir <- c("<=", "<=", "<=")
#right and side of constraints
rhs <- c(60, 40, 80)
#set max equal to TRUE since this is a maximization problem. This will print the list of solution variables including opitmum value, solution, and dual solution among others.
ans<-Rglpk_solve_LP(obj, mat, dir, rhs, max=TRUE)
#print optimum value
print(ans$optimum)
#print optimum solution
print(ans$solution)The CVXR package uses a slightly different approach. It uses solver objects that the user creates and then solves the problem from there. It will seem very tedious when entering a large number of constraints as a list, but it will allow for more flexability when solving more complicated problems. The same problem is solved below using CVXR:
library(CVXR)
#create Variable objects that can be manipulated by the solver.
x<-Variable(3)
#coefficients for objective function
C<-c(2,4,3)
#the Maximize function does not find a maximum for this function. It is creating an objective function object that the solver will be able to use.
objective<-Maximize(C %*% x)
#make a list of constraints. x[i] is the ith x variable
constraints<-list(3*x[1]+4*x[2]+2*x[3]<=60,
2*x[1]+x[2]+2*x[3]<=40,
x[1]+3*x[2]+2*x[3]<=80,
x>=0)
#now we formulate the problem using the Problem function. this will create a "Problem" object for the solver
problem<-Problem(objective, constraints)
#now we can get the solution by calling solve. Now we can print out all the information we want.
ans<-solve(problem)
#show status
print(ans$status)
#show optimum value
print(ans$value)
#show values for variables
print(ans$getValue(x))A small business sells two products named Product 1 and Product 2. The production of each ton of Product 1 consumes 30 working hours, and each ton of Product 2 consumes 20 working hours. The business has a maximum of 2,700 working hours for the period considered. As for machine hours, each ton of Products 1 and 2 consumes 5 and 10 machine hours, respectively. There are 850 machine hours available. Each ton of Product 1 yields $20,000 of profit, while Product 2 yields $60,000 for each ton sold. For technical reasons, the firm must produce a minimum of 95 tons in total between both products. We need to know how many tons of Product 1 and 2 must be produced to maximize total profit.
Write this as a maximization problem.
Solve the problem using your simplex algorithm that you created last week (be sure that you put your problem in standard maximization form first). Provide your solution as well as a copy of your output from R (you may use a screenshot).
Solve the problem using the Rglpk solver. Provide the solution as well as approprite output from R.
Solve the problem using the CVXR solver. Provide the solution as well as appropriate output from R.
Consider the following linear program:
\[\begin{alignat}{2} & \text{maximize} & \quad & 3 x_1 + 3 x_2 + x_3\nonumber \\ & \text{subject to} & & 3 x_1 + 4 x_2 + 2 x_3 \leq 60 \\ & & & 2 x_1 + x_2 + 2 x_3 \leq 40 \\ & & & x_1 + 3 x_2 + 2 x_3 \leq 80 \\ & & & x_1,x_2,x_3 \geq 0 \nonumber \end{alignat}\]a)Solve this using the simplex algorithm
b)solve with Rglpk.
c)solve with CVXR.
d)Which solver do you prefer for this problem? Is one easier to use? Does one give better output?
Sometimes it’s necessary to consider linear programs where the solutions are required to take integer values. For example, consider the case where you need to manufacture objects, say tables. It doesn’t make sense to have only half of a table! Optimization problems that require integer solutions are called integer programming problems. Optimizaton problems that require some solution variables to be integers while others can be non-integer are called mixed-integer linear programs.
Finding solutions to these types of problems by hand is very, very tedious. Fortunately, we have technology to come to our rescue. Both Rglpk and CVXR are set up to handle mixed-integer programs.
Consider the following mixed-integer linear program:
\[\begin{alignat}{2} & \text{maximize} & \quad & x_1+2 x_2 â 0.1 x_3 â 3 x_4\nonumber \\ & \text{subject to} & & x_1 + x_2 \leq 5 \\ & & & 2 x_1 - x_2 \geq 0 \\ & & & âx_1 + 3 x_2 \geq 0 \\ & & & x_3 + x_4 \geq 0.5 \\ & & & x_3\geq 1.1 \\ & & & x_3 ~is~ an~ integer\\ & & & x_1,x_2,x_3,x_4\geq 0 \nonumber \end{alignat}\]Using Rglpk we may obtain the solution as follows:
library("Rglpk") # If you've already loaded Rglpk, you don't need this
#coefficents from objective functions
obj <- c(1, 2, -0.1, -3)
#matrix with constraint coefficients
mat <- rbind(c(1, 1, 0, 0),c(2, -1, 0, 0),c(-1, 3, 0, 0), c(0, 0, 1, 1), c(0, 0, 1, 0))
#vector with type and direction of inequality for each constraint
dir <- c("<=", ">=", ">=", ">=", ">=")
#right and side of constraints
rhs <- c(5, 0, 0, 0.5, 1.1)
#need to specify what type "B" for binary/bool, "C" for continuous, "I" for integer. By default all are set to "C"
varType<-c("C", "C", "I", "C")
#do not need to add positive constraint. The bounds on variables here are default set to being positive.
#set max equal to TRUE since this is a maximization problem. This will print the list of solution variables including opitmum value, solution, and dual solution among others.
ans<-Rglpk_solve_LP(obj, mat, dir, rhs, max=TRUE, types=varType)
#print optimum value
print(ans$optimum)
#print optimum solution
print(ans$solution)We can use CVXR to solve the problem as well:
library("CVXR") # If you've already loaded CVXR, this isn't necessary
#Need to create the variables differently than before since one of them can only have integer values. Note that Variables(k) will create a variable object with k
x12 <- Variable(2)
#this takes care of the integer constraint
x3 <- Int(1)
x4 <- Variable(1)
#vstack is similar to the rbind() function but is specific to CVXR
x <- vstack(x12, x3, x4) ## Create x expression
C <- matrix(c(1, 2, -0.1, -3), nrow = 1)
objective <- Maximize(C %*% x)
constraints <- list(
x >= 0,
x[1] + x[2] <= 5,
2 * x[1] - x[2] >= 0,
-x[1] + 3 * x[2] >= 0,
x[3] + x[4] >= 0.5,
x[3] >= 1.1)
problem <- Problem(objective, constraints)
ans<-solve(problem)
#show status
print(ans$status)
#show optimum value
print(ans$value)
#show values for variables
print(ans$getValue(x))A company produces two models of chairs: 4P and 3P. The model 4P needs 4 legs, 1 seat and 1 back. On the other hand, the model 3P needs 3 legs and 1 seat. The company has an initial stock of 200 legs, 500 seats and 100 backs. If the company needs more legs, seats and backs, it can buy standard wood blocks, whose cost is $80 per block. The company can produce 10 seats, 20 legs and 2 backs from a standard wood block. The cost of producing the model 4P is $30 per chair, meanwhile the cost of the model 3P is $40 per chair. Finally, to meet demand the company must produce at least 1,000 units per month. The company’s goal is to minimize the total cost of production.
Formulate this as a linear program. Remember, you cannot produce part of a chair, and you can only purchase whole blocks of wood.
Solve using Rglpk solver. Include solution and appropriate output from R.
Solve using CVXR solver. Include solution and appropriate output from R.
Complete Exercise 3.1 (p. 31) of the book, “Modeling and Solving Linear Programs with R” by Sallan, Lordon, Fernandez (Omnia Science 2015), which is freely available at:
https://www.omniascience.com/books/index.php/scholar/catalog/book/34
Solve the exercises with both Rglpk and CVXR.
Complete Exercise 3.4 from the book by Sallan, Lordon, Fernandez. Solve with both packages.
Solve the following problem using both Rglpk and CVXR:
Suppose that you are a tasked with deciding the best approach to a particular TV advertising campaign. Running the ad at different times/days have different costs and different numbers of viewers. You know the following information:
| Time of day | Cost of one ad | No. of viewers |
|---|---|---|
| Friday-day | $400 | 5000 |
| Saturday-day | $450 | 5500 |
| Sunday-day | $450 | 5700 |
| Friday-night | $500 | 7500 |
| Saturday-night | $550 | 8200 |
| Sunday-night | $550 | 8400 |
Your goal is to have as many people see your advertising campaign as possible. You can’t spend more than $45000 on the entire campaign. Because of other limitations, you can spend a maximum of $11000 and $14400 on Friday an Saturday respectively. You need to the run the advertisement at least 20 total times during the day, and the nightly showings need to be at least 50% of the total. You can’t have more than 12 showings on any particular day, and you can’t have more than 18 showings on any given night.
Hint: You will have six unique variables for this problem.