Select Page

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. # 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)^2 + 7 * (x-3)^2 + 30
> f
function(x) 4 * (x-1)^2 + 7 * (x-3)^2 + 30```

Setting up the constraints next

```> c <- c(1, 1)
> c
 1 1```

The optimization function is invoked

```> r <- optim(c, f)
> r
\$par
 0.9999207 3.0001660

\$value
 30

\$counts
69   NA

\$convergence
 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
 TRUE```

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

```> r\$par
 0.9999207 3.0001660```

The value of objective function at the minimum is obtained by

```> r\$value
 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)
> objective.in  <- c(25, 20)
> objective.in
 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
 480
> resource_constraints
 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
 1800  480
> direction  <- c("<=", "<=")
> direction
 "<=" "<="
```

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
 45 75
```

The maximum sales figure is –

```> optimum\$objval
 2625```

## Example 2

Below is good example taken from lpsolve’s sourceforge website –

“Suppose a farmer has 75 acres on which to plant two crops: wheat and barley. To produce these crops, it costs the farmer (for seed, fertilizer, etc.) \$120 per acre for the wheat and \$210 per acre for the barley. The farmer has \$15000 available for expenses. But after the harvest, the farmer must store the crops while awaiting avourable market conditions. The farmer has storage space for 4000 bushels. Each acre yields an average of 110 bushels of wheat or 30 bushels of barley. If the net profit per bushel of wheat (after all expenses have been subtracted) is \$1.30 and for barley is \$2.00, how should the farmer plant the 75 acres to maximize profit?”

As we did in the previous example, let’s define the optimization function and the constraints.

maximize
g = (110)(1.30)x + (30)(2.00)y = 143x + 60y

subject to
120x + 210y <= 15000
110x + 30y <= 4000
x + y <= 75
x >= 0
y >= 0

We will be solving this problem in both excel and R.

## Excel Solver

There is a way to solve LP problems using Excel. Firstly we have to define the number of acres to plant for both these crops. Initially they are zero, the optimum values can be obtained by using the solver plugin in excel. Next we need to define the constraints, the equations for the constraints have already been defined. Subject to, The initial values for the number of used resources is set at zero initially. The main workhorse behind these LP problems is to use the sumproduct equation.   The sumproduct equation is basically a product of cost multiplied by the number of acres. Now we define the maximization equation. In this case the profit needs to be maximized. The total profit cell that is seen in the below image. The same sumproduct formula that was previously used is repeated again. Now try changing the values for the wheat and Barley cells. Just put some random number for both the cells. Observe the total profit cell and the used cell for all the constraints. As seen we get a total profit figure, however have a look at the used resources. Clearly the values in the cell are more than the values in the available cells. We can try to decrease the number of acres and see what the resulting values will be. The values are low indeed, but it is not the optimum solution. To get the optimum values for total profit. We use the solver plugin to solve this. Navigate to the data and see if there is the solver option under the analysis tab. If it is not present, follow these steps to install it –

1. Navigate for the file tab and then click on options
2. Click on the Add-ins button, and then go next to the manage Once this is done, a popup should appear. Select the Solver add-in and press OK. There you go now the solver option should show up. Before we proceed further, let’s set the number of acres to zero. Now, set the objective to total profit Set the –

• Solving method to simplex LP.
• The objective to max  Once done press solve, the following popup should show up along with the optimized values for the profit cell. Press OK, now we have the number of acres to plant for Wheat and Barley. Along with the profit value. Implementation in R using LpsolveAPI
We previously used the Lpsolve package, in this example we illustrate how to use LpsolveAPI package. We start off by calling the lpsolveapi package.

```> require(lpSolveAPI)

> lprec <- make.lp(0, 2)
> lprec
Model name:
C1 C2
Minimize     0 0
Kind       Std Std
Type      Real Real
Upper      Inf Inf
Lower        0 0
```

Next we set the objective function to maximization.

```> lp.control(lprec, sense="max")
\$anti.degen
 "none"

\$basis.crash
 "none"

\$bb.depthlimit
 -50

\$bb.floorfirst
 "automatic"

\$bb.rule
 "pseudononint" "greedy"       "dynamic" "rcostfixing"

\$break.at.first
 FALSE

\$break.at.value
 1e+30

\$epsilon
epsb     epsd epsel     epsint epsperturb epspivot
1e-10      1e-09 1e-12      1e-07 1e-05 2e-07

\$improve
 "dualfeas" "thetagap"

\$infinite
 1e+30

\$maxpivot
 250

\$mip.gap
absolute relative
1e-11    1e-11

\$negrange
 -1e+06

\$obj.in.basis
 TRUE

\$pivoting

\$presolve
 "none"

\$scalelimit
 5

\$scaling
 "geometric"   "equilibrate" "integers"

\$sense
 "maximize"

\$simplextype
 "dual"   "primal"

\$timeout
 0

\$verbose
 "neutral"
```

We define the objective function and the constraints

```> set.objfn(lprec, c(143, 60))
> add.constraint(lprec, c(120, 210), "<=", 15000)
> add.constraint(lprec, c(110, 30), "<=", 4000)
> add.constraint(lprec, c(1, 1), "<=", 75)
```

Let’s have a look at the LP problem that we have defined.

```> lprec
Model name:
C1 C2
Maximize   143 60
R1         120 210 <=  15000
R2         110 30 <=   4000
R3           1 1 <=   75
Kind       Std Std
Type      Real Real
Upper      Inf Inf
Lower        0 0```

Solving

```> solve(lprec)
 0```

Getting the optimized profit value

```> get.objective(lprec)
 6315.625```

Let’s finally get the values for how many acres of Wheat and Barley to be planted.

```> get.variables(lprec)
 21.875 53.125```

Thus, to achieve the maximum profit (\$6315.625), the farmer should plant 21.875 acres of wheat and 53.125 acres of barley.

# Conclusion

Now that we have figured out how to solve LP problems using excel solver as well as the packages in R, namely Lpsolve and LpsolveAPI. Go ahead and start solving your own Linear Programming problems.

LP Problem sources –