KDnuggets Home » News » 2018 » May » Tutorials, Overviews » Optimization Using R ( 18:n21 )

Optimization Using R


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.



By Perceptive Analytics

Header image

What is 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.

 

There are a variety of optimization techniques -

 

Unconstrained optimization

In certain cases the variable can be freely selected within it’s full range. The optim() function in R can be used for 1- dimensional or n-dimensional problems. The general format for the optim() function is -

optim(objective, constraints, bounds = NULL, types= NULL, maximum = FALSE)


We start off with an example, let’s define the objective function what we are looking to solve -

> f <- function(x) 4 * (x[1]-1)^2 + 7 * (x[2]-3)^2 + 30
> f
function(x) 4 * (x[1]-1)^2 + 7 * (x[2]-3)^2 + 30


Setting up the constraints next

> c <- c(1, 1)
> c
[1] 1 1


The optimization function is invoked

> r <- optim(c, f)
> r
$par
[1] 0.9999207 3.0001660

$value
[1] 30

$counts
function gradient 
      69   NA 

$convergence
[1] 0

$message
NULL


Next we check if the optimization converged to a minimum or not. The easy way to do this is to check if

> r$convergence == 0
[1] TRUE


The optimization has converged to minimum. Finding out the input arguments for the optimization function can be obtained by

> r$par
[1] 0.9999207 3.0001660


The value of objective function at the minimum is obtained by

> r$value
[1] 30


 

Linear programming

 
Here is a good definition from technopedia - “Linear programming is a mathematical method that is used to determine the best possible outcome or solution from a given set of parameters or list of requirements, which are represented in the form of linear relationships. It is most often used in computer modeling or simulation in order to find the best solution in allocating finite resources such as money, energy, manpower, machine resources, time, space and many other variables. In most cases, the "best outcome" needed from linear programming is maximum profit or lowest cost.

An example of a LP problem is -

Maximize or Minimize objective function: f(y1, y2) = g1.y1 + g2.y2
 
Subjected to inequality constraints:

  • g11.y1 + g12.y2 <= p1
  • g21.y1 + g22.y2 <= p2
  • g31.y1 + g32.y2 <= p3
  • y1 >= 0, y2 >=0

 

Example 1

 
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?

A LP problem can either be a maximization problem or a minimization problem. The Above problem is a maximization problem. Some of the steps that should be followed while defining a LP problem are -  

  • Identify the decision variables
  • Write the objective function
  • Mention the constraints
  • Explicitly state the non-negativity restriction

Lets walk through the above example -

As already defined this is a maximization problem, first we define the objective function.  

max(Sales) = max(25 y1 + 20 y2)

where,

  • y1 is the units of Product A produced
  • y2 is the units of Product B produced
  • y1 and y2 are called the decision variables
  • 25 and 20 are the selling price of the products

We are trying to maximize the sales while finding out the optimum number of products to manufacture. Now we set the constraints for this particular LP problem. We are dealing with both resource and time constraints.

20y1 + 12 y2 <= 1800 (Resource Constraint)
4y1 + 4y2 <= 8*60 (Time constraint)

 

There are two ways to solve a LP problem

 

  • Graphical Method
  • Simplex Method

We will be solving this problem using the simplex method but in R. We shall also explain another example with excel’s solver. There are a couple of packages in R to solve LP problems. Some of the popular ones are -

  • lpsolve
  • lpsolveAPI

 

Implementation in R using Lpsolve

 
Let’s use lpsolve for this problem. First we need to set the objective function, this has already been defined.

> require(lpSolve)
Loading required package: lpSolve
> objective.in  <- c(25, 20)
> objective.in
[1] 25 20


Creating a matrix for the constraints, we create a 2 by 2 matrix for this. And then setting constraints.

> const <- matrix(c(20,  12, 4, 4), nrow=2, byrow=TRUE)
> const
     [,1] [,2]
[1,]   20 12
[2,]    4 4
> time_constraints <- (8*60)
> resource_constraints <- 1800
> time_constraints
[1] 480
> resource_constraints
[1] 1800


Now we are basically creating the equations that we have already defined by setting the rhs and the direction of the constraints.

> rhs <- c(resource_constraints, time_constraints)
> rhs
[1] 1800  480
> direction  <- c("<=", "<=")
> direction
[1] "<=" "<="


The final step is to find the optimal solution. The syntax for the lpsolve package is -

lp(direction , objective, const.mat, const.dir, const.rhs)

> optimum <-  lp(direction="max",  objective.in, const, direction,  rhs)
> optimum
Success: the objective function is 2625
> summary(optimum)
                 Length Class Mode     
direction        1 -none- numeric  
x.count          1 -none- numeric  
objective        2 -none- numeric  
const.count      1 -none- numeric  
constraints      8 -none- numeric  
int.count        1 -none- numeric  
int.vec          1 -none- numeric  
bin.count        1 -none- numeric  
binary.vec       1 -none- numeric  
num.bin.solns    1 -none- numeric  
objval           1 -none- numeric  
solution         2 -none- numeric  
presolve         1 -none- numeric  
compute.sens     1 -none- numeric  
sens.coef.from   1 -none- numeric  
sens.coef.to     1 -none- numeric  
duals            1 -none- numeric  
duals.from       1 -none- numeric  
duals.to         1 -none- numeric  
scale            1 -none- numeric  
use.dense        1 -none- numeric  
dense.col        1 -none- numeric  
dense.val        1 -none- numeric  
dense.const.nrow 1      -none- numeric 
dense.ctr        1 -none- numeric  
use.rw           1 -none- numeric  
tmp              1 -none- character
status           1 -none- numeric


Now we get the optimum values for y1 and y2, i.e the number of product A and product B that should be manufactured.

> optimum$solution
[1] 45 75


The maximum sales figure is -

> optimum$objval
[1] 2625



Sign Up