CODEWITHSUNDEEP
r
Alex Germain
Alex Germain

Reputation: 441

Optimization under constraint under a list of possibilities in R

I'm trying to optimize a function using two variables in R. My concern is that these 2 variables have only specific possible values. I found solution with lower/upper limits using noptr but I'm not able to "force" the value taken by both variables. An example will be easier to understand using constrOptim function:

g <- function(x,y) 100*x+150*y
gb <- function(x) g(x[1], x[2])

A <- matrix(c(1,0,0,1,100,150),3,2,byrow=T)
b <- c(0,0,350)

constrOptim(theta=c(2,2), f=gb, grad=NULL, ui=A, ci=b)

Thus, I want x & y to take the values 0, 1 or 2. In my example, the constraints are further written as x>=0,y>=0 and 100x+150y>=350.

My goal is to minimize 100*x+150*y respecting 100x+150y>=350 where x and y are taking values in c(0,1,2) only!

Upvotes: 2

Views: 187

Answers (2)

G. Grothendieck
G. Grothendieck

Reputation: 269471

Depending on what features of the example apply to your actual problem you may be able to use brute force (if problem is not too large), integer linear programming (if objective and constraints are linear) or integer convex programming (if objective and constraints are convex). All of these hold for the example in the question.

# brute force
list(grid = expand.grid(x = 0:2, y = 0:2)) |>
  with(cbind(grid, g = apply(grid, 1, gb))) |>
  subset(g >= 350) |>
  subset(g == min(g))
##   x y   g
## 6 2 1 350

# integer linear programming
library(lpSolve)
res <- lp("min", c(100, 150), A, c("<=", "<=", ">="), c(2, 2, 350), all.int = TRUE)
res
## Success: the objective function is 350 
res$solution
## [1] 2 1

# integer convex programming
library(CVXR)
X <- Variable(2, integer = TRUE)
v <- c(100, 150)
objective <- Minimize(sum(v * X))
constraints <- list(X >= 0, X <= 2, sum(v * X) >= 350)
prob <- Problem(objective, constraints)
CVXR_result <- solve(prob)
CVXR_result$status
## [1] "optimal"
CVXR_result$getValue(X)
##           [,1]
## [1,] 2.0000228
## [2,] 0.9999743

Upvotes: 2

SteveM
SteveM

Reputation: 2301

Since your objective function and constraint are both linear, your problem is a standard Mixed Integer Linear Programming (MIP) problem. There is a collection of solvers to solve those problems. Here is a formulation using the ompr package as the model manager and the glpk solver:

g <- c(100, 150)
rhs <- 350
model <- MIPModel() %>% 
   add_variable(x[i], i = 1:2, type = "integer", lb = 0, ub = 2) %>% 
   set_objective(sum_over(g[i] * x[i], i = 1:2), "min") %>% 
   add_constraint(sum_over(g[i] * x[i], i = 1:2) >= rhs)

   result <- solve_model(model, with_ROI(solver = "glpk"))
   result
   Status: success
   Objective value: 350
   solution <- get_solution(result, x[i])
   solution
      variable i value
    1        x 1     2
    2        x 2     1

ompr uses simple algebraic notation and is easy to learn: https://dirkschumacher.github.io/ompr/index.html

Upvotes: 0

Related Questions