ECON457 R lab 3 Optimization in R

Information about optimizaion in R

http://cran.r-project.org/web/views/Optimization.html

https://www.rdocumentation.org/packages/ROI/versions/0.2-1

This file can be downloaded at https://github.com/ECON457-fa16/labs/raw/master/lab03/lab03.Rmd

The R Optimization Infrastructure (ROI)

The R Optimization Infrastructure (ROI) package promotes the development and use of interoperable (open source) optimization problem solvers for R.

ROI handle LP up to MILP and MIQCP problems using the following supported solvers :

1. lpSolve

2. quadprog

3. Rcplex

4. Rglpk (default)

5. Rsymphony

more…

Solvers

CPLEX is a commercial solver. Students can get academic license.

GLPK is free. R has the high level interface Rglpk.

http://winglpk.sourceforge.net/

https://cran.r-project.org/web/packages/Rglpk/index.html

Install all the packages.

Uncomment the code in follow chunk and install all packages.

#install.packages("ROI")
#install.packages(c( "Rglpk","ROI.plugin.symphony","ROI.plugin.glpk","ROI.plugin.quadprog","ROI.plugin.nloptr","ROI.plugin.ipop","ROI.plugin.ecos"))

Linear Progarmming

library("ROI")

ROI: R Optimization Infrastructure
Registered solver plugins: nlminb, ecos, glpk, ipop, nloptr, quadprog, symphony.
Default solver: auto.

$$ \[\begin{align*} \text{maximize: } 2 x_1 &+ 4 x_2 + 3 x_3\\ \text{subject to: } 3 x_1 &+ 4 x_2 + 2 x_3 & <= 60 \\ 2 x_1 &+ x_2 + x_3 & <= 40 \\ x_1 &+ 3 x_2 + 2 x_3 & <= 80 \end{align*}\]

$$

LP # model named as LP

ROI Optimization Problem:

Maximize a linear objective function with
- 3 objective variables,

subject to
- 3 constraints of type linear.

Solve

sol

Optimal solution found.
The objective value is: 9.000000e+01

Solutions

solution(sol, type = c("dual"))  # solution for dual problem: minimize by subject to A'y >= c

[1] -2.5 -2.0  0.0

Extract solutions

sol$message # detailed message for solution 

$optimum
[1] 90

$solution
[1]  0  0 30

$status
[1] 5

$solution_dual
[1] -2.5 -2.0  0.0

$auxiliary
$auxiliary$primal
[1] 60 30 60

$auxiliary$dual
[1] 1.5 0.0 0.0

Quadratic Progarmming

It will require putting problem in matrix form.

three decision variables: x1, x2, x3

$$ \[\begin{align*} \text{minimize: } - 5 x_2 + 1/2 (x_1^2 + x_2^2 + x_3^2)\\ \text{subject to: } -4 x_1 - 3 x_2 & >= -8 \\ 2 x_1 + x_2 & >= 2 \\ - 2 x_2 + x_3 & >= 0 \end{align*}\]

$$

QP

ROI Optimization Problem:

Minimize a quadratic objective function with
- 3 objective variables,

subject to
- 3 constraints of type linear.

Solve

sol

Optimal solution found.
The objective value is: -2.380952e+00

Extract solutions

sol$message

NULL

Solutions

solution(sol, type = c("dual"))

[1] NA

Portfolio optimization - minimum variance

To minimize the risk, we choose invest in 30 stocks and we need to decide the share for each stock. Decision variables: x1, x2,…, x30. sum(x, i) = 1. If xi is allowed to negative, it means we can borrow stock and sell it.

(op <- OP( objective = obj, constraints = full_invest )) 

ROI Optimization Problem:

Minimize a quadratic objective function with
- 30 objective variables,

subject to
- 1 constraints of type linear.

Solution

round( sol[ which(sol > 1/10^6) ], 3 )

  IBM   MCD   MRK    PG     T    VZ   WMT   XOM 
0.165 0.301 0.005 0.138 0.031 0.091 0.169 0.101 

LP with boundary

three decision variables: x1, x2

$$ \[\begin{align*} \text{minimize: } x_1 + 2* x_2\\ \text{subject to: } x_1 + x_2 & = 2 \\ x_1 & <= 3 \\ x_2 & <= 3 \end{align*}\]

$$

lp

ROI Optimization Problem:

Minimize a linear objective function with
- 2 objective variables,

subject to
- 1 constraints of type linear.

Solutions

 x$solution

[1] 2 0

Change boundary

$$ \[\begin{align*} \text{minimize: } x_1 + 2* x_2\\ \text{subject to: } x_1 + x_2 & = 2 \\ x_1 & <= 1 \\ x_2 & <= 1 \end{align*}\]

$$

Solutions

 y$solution

[1] 1 1

---

Other optimization package in R

We also can solve optimization problem using other packages.

Install packages

Uncomment the code in follow chunk and install all packages.

install.packages(c("quadprog", "nlme","Rglpk"))

Error in install.packages : Updating loaded packages

suppressMessages(library(Rglpk))

Error in library(Rglpk) : there is no package called æ… glpk?

args() function tells us how we can use those functions such as lp, solve.QP, Rglpk_solve_LP

args(lp)
args(solve.QP)
args(Rglpk_solve_LP)
#args(nlminb)
#args(optim)
#args(Rcplex)

Linear Programming by lpsolve

Here is a list of some key features of lp_solve:

• Mixed Integer Linear Programming (MILP) solver

• Basically no limit on model size

• It is free and with sources

• Supports Integer variables, Semi-continuous variables and Special Ordered Sets

Example by lpSolveAPI

straightforward

If we have 4 decision variables: x1,…, x4

\[\begin{align*} \text{minimize: } x_1 + 3 x_2 + 6.24 x_3 + 0.1 x_4\\ \text{subject to: } 78.26 x_2 + 2.9 x_4 & >= 92.3 \\ 0.2 x_1 + 11.91 x_3 & <= 14.8 \\ 12.68 x_1 + 0.08 x_3 + 0.9 x_4 &>= 4 \\ 18 <= x_4 & <= 48.98 \\ x_1 & >= 28.6 \end{align*}\]

Set up model

Setup objective function

set.objfn(lpmodel, c(1, 3, 6.24, 0.1))  #　object function, vector c 

Error in set.objfn(lpmodel, c(1, 3, 6.24, 0.1)) : 
  object 'lpmodel' not found

Add constraints

Set bounds

Setup names

Show model setting

lpmodel

Not necessary

lpmodel

Model name: 
             C1     C2     C3     C4          
Minimize      1      3   6.24    0.1          
R1            0  78.26      0    2.9  >=  92.3
R2         0.24      0  11.31      0  <=  14.8
R3        12.68      0   0.08    0.9  >=     4
Kind        Std    Std    Std    Std          
Type       Real   Real   Real   Real          
Upper       Inf    Inf    Inf  48.98          
Lower      28.6      0      0     18          

Solve the model

solve(lpmodel)

[1] 0

Extract solutions

get.constraints(lpmodel)

[1]  92.3000   6.8640 391.2928

Example by lpSolve

provide a lot of information including sensitivities analysis.

\[\begin{align*} \text{maximize: } x_1 + 9 x_2 + x_3 \\ \text{subject to: } x_1 + 2 x_2 + 3 x_3 & <= 9 \\ 3 x_1 + 2 x_2 + 2 x_3 & <= 15 \end{align*}\]

Setup objective function

Setup constraints

Solve the model

lp ("max", model_obj, model_con, model_dir, model_rhs)

Success: the objective function is 40.5 

Extract solutions

lp ("max", model_obj, model_con, model_dir, model_rhs)$solution

[1] 0.0 4.5 0.0

Get sensitivities

lp ("max", model_obj, model_con, model_dir, model_rhs, compute.sens=TRUE)$duals.to  

[1] 1.5e+01 1.0e+30 3.0e+00 1.0e+30 3.0e+00

Intergr Programming

Previous model with constraints that all decision variables are integer.

lp ("max", model_obj, model_con, model_dir, model_rhs, int.vec=1:3, compute.sens=TRUE)$duals

[1]  1  0  0  7 -2

Quadratic Programming by quadprog

solving quadratic programming problems of the form

min(c’ x + 1/2 x’ D x)

with the constraints A’ x >= b_0.

$$ \[\begin{align*} \text{minimize: } - 5 x_2 + 1/2 (x_1^2 + x_2^2 + x_3^2)\\ \text{subject to: } -4 x_1 - 3 x_2 & >= -8 \\ 2 x_1 + x_2 & >= 2 \\ - 2 x_2 + x_3 & >= 0 \end{align*}\]

$$

D is diagnal matix . 1/2 is convetion.

solve.QP(Dmat,cvec,Amat,bvec=bvec)

$solution
[1] 0.4761905 1.0476190 2.0952381

$value
[1] -2.380952

$unconstrained.solution
[1] 0 5 0

$iterations
[1] 3 0

$Lagrangian
[1] 0.0000000 0.2380952 2.0952381

$iact
[1] 3 2

Football MIP by glpk

Trying to pick the best possible fantasy football team given different constraints.

Goal is to pick the players that maximize the sum of their projected points.

Decision variabls are binary, 0 or 1 for one player to play in this match.

The constraints are:

1. The team must include:

   • 1 QB

   • 2 RBs

   • 2 WRs

   • 1 TE

2. A player’s risk must not exceed 6

3. The sum of the players’ costs must not exceed 300.

maximize cx points

subject Ax <= b

pos == "TE"

 [1] FALSE FALSE FALSE FALSE FALSE FALSE FALSE FALSE  TRUE  TRUE

Solve the model with glpk

sol

$optimum
[1] 836

$solution
 [1] 1 0 1 0 1 1 0 1 1 0

$status
[1] 0

$solution_dual
[1] NA

$auxiliary
$auxiliary$primal
 [1]   1.0   2.0   2.0   1.0   2.9   0.0   0.7   0.0   3.5   5.0   0.0   4.7   3.7   0.0 298.0

$auxiliary$dual
[1] NA

Solve it using ROI

football <- OP( f, # objective function, vector c
          L_constraint(L = A, # linear constraint: Maxtrix A
          dir = dir,  # direction
          rhs = b), # right hand side: vector b 
          types = var.types,  
          max = TRUE)
football

ROI Optimization Problem:

Maximize a linear objective function with
- 10 objective variables,

subject to
- 15 constraints of type linear.

Some of the objective variables are of type binary or integer.

Solve

sol

Optimal solution found.
The objective value is: 8.360000e+02

Solutions

solution(sol, type = c("dual"))  # solution for dual problem: minimize by subject to A'y >= c

[1] NA

Extract solutions

sol$message # detailed message for solution 

$optimum
[1] 836

$solution
 [1] 1 0 1 0 1 1 0 1 1 0

$status
[1] 5

$solution_dual
[1] NA

$auxiliary
$auxiliary$primal
 [1]   1.0   2.0   2.0   1.0   2.9   0.0   0.7   0.0   3.5   5.0   0.0   4.7   3.7   0.0 298.0

$auxiliary$dual
[1] NA