Introduction to Linear Optimization
Optimization is a technique for finding out the best possible solution for a given problem for all the possible solutions. Optimization uses a rigorous mathematical model to find out the most efficient solution to the given problem.
To start with an optimization problem, it is important to first identify an objective. An objective is a quantitative measure of performance. For example: to maximize profits, minimize time, minimize costs, maximize sales.
Optimization problems can be classified into two groups
- Linear Programming (LP): It is also known as linear optimization and in this problem, the aim is to achieve the best outcome in a mathematical model where the objective and all of the constraints are linear functions of the decision variables.
- Quadratic Programming (QP): In Quadratic Programming, the objective is the quadratic function of the decision variables and constraints which are linear functions of the variables. A quadratic function is also one type of Non-Linear Programming.
For this post, only Linear Programming problem has been explained.
Linear Optimization in R:
Common packages available for optimization in R are:
|Linear Programming (LP)|
|Quadratic Programming (QP)|
All of these packages are listed in CRAN Task View: “Optimization and Mathematical Programming”
Examples of built-in function for general optimization problems:
- General argument structure for these procedures is:
optimizer(objective, constraints, bounds=NULL, types=NULL, maximum=FALSE)
- Define objective function
f <- function(x) 2 * (x-1)^2 + 5 * (x-3)^2 + 10
- Call optimization function
r <- optim(c(1, 1), f)
- Check if the optimization converged to a minimum
r$convergence == 0 ## Returns TRUE if converged to minimum ##  TRUE
- Optimal input arguments
r$par ##  1.000168 3.000232
- Value of objective function at the minimum
r$value ##  10
Linear Programming (LP)
Linear programming is represented as:
Example for Linear Programming:
- A company wants to maximize the profit for two products A and B which are sold at $ 25 and $ 20 respectively. There are 1800 resource units available every day and product A requires 20 units while B requires 12 units. Both of these products require a production time of 4 minutes and total available working hours are 8 in a day. What should be the production quantity for each of the products to maximize profits.
The objective function in the above problem will be:
The constraints (resource and time) in the problem:
Solving the above problem in R:
As this is a linear programming problem, we will use lpsolve package and lp() function to find the optimal solution. The syntax for lp() function is:
lp(direction="min", objective.in, const.mat, const.dir, const.rhs)
- direction controls whether to minimize or maximize
- Coefficients c are encoded a vector objective.in
- Constraints A are given as a matrix const.mat with directions const.dir
- Constraints b are inserted as a vector const.rhs
## Load the package lpsolve library(lpsolve) ## Set the coefficients of the decision variables objective.in <- c(25, 20) ## Create constraint martix const.mat <- matrix(c(20, 12, 4, 4), nrow=2, byrow=TRUE) ## define constraints time_constraint <- (8*60) resource_constraint <- 1800 ## RHS for the constraints const.rhs <- c(resource_constraint, time_constraint) ## Constraints direction const.dir <- c("<=", "<=") ## Find the optimal solution optimum <- lp(direction="max", objective.in, const.mat, const.dir, const.rhs)
## Display the optimum values for x1 and x2 optimum$solution ##  45 75 ## Check the value of objective function at optimal point optimum$objval ##  2625
From the above output, we can see that the company should produce 45 units of Product A and 75 units of Product B to get sales of $2625.
We can extend the same approach to solve other LP problems in R after formulating the objective function and constraints.