Optimization under constraint under a list of possibilities in R

Question

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!

Have you tried implementing a penalty for other suggested values than those in `c(0,1,2)`? E.g in `g()`, check if `x` and `y`, rounded to a level of precision is in `c(0,1,2`, if not then return e.g. `1E6`? — mhovd, Sep 23 '22 at 14:57
Does this answer your question? [How to optimize for integer parameters (and other discontinuous parameter space) in R?](https://stackoverflow.com/questions/11110848/how-to-optimize-for-integer-parameters-and-other-discontinuous-parameter-space) — mhovd, Sep 23 '22 at 14:59

G. Grothendieck · Accepted Answer · 2022-09-23T16:44:48.393

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

score 0 · Answer 2 · answered Sep 23 '22 at 16:15

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

Optimization under constraint under a list of possibilities in R

2 Answers2