CODEWITHSUNDEEP
roptimizationmathematical-optimizationlinear-programmingglpk
Nate A
Nate A

Reputation: 71

Using an average in a ompr linear programming constraint

I'm using the ompr package for solving integer program. I wanted to include a constraint that based on the average value of another binary variable.

In the example below, I have some food and I want to find at least 5 items and minimize the cost. I would like the average calorie count to be above some minimum. In the code below, the first constraint is that the sum of the calories is above min_avg_cal. Can this be rewritten so the constraint is that the average calorie of the chosen food is above min_avg_cal? 

library(dplyr)
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)


n <- 20
cost <- runif(n, 0, 10)
calories <- runif(n, 100, 200)
min_avg_cal <- 140

model <- MIPModel() %>%
  add_variable(x[i], i =1:n, type = "binary") %>%
  set_objective(sum_expr(cost[i] * x[i], i = 1:n), "min") %>%
  add_constraint(sum_expr(calories[i] * x[i], i = 1:n) >= min_avg_cal) %>% 
  add_constraint(sum_expr(x[i], i = 1:n) >= 5) 

result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))
result$solution

Upvotes: 0

Views: 1431

Answers (2)

Nate A
Nate A

Reputation: 71

Based on a Sascha's suggestion, the mean can be rewritten as a sum of variable products by rearranging the constraint. In particular, you can change this constraint:

add_constraint(sum_expr(calories[i] * x[i], i = 1:n) >= min_avg_cal)

into

add_constraint(sum_expr(calories[i] * x[i] - x[i] * min_avg_cal, i = 1:n) >= 0)

which is just a rearrangement of the definition of the mean.

The full solution is the same as the original code with that single constraint replaced:

library(dplyr)
library(ROI)
library(ROI.plugin.glpk)
library(ompr)
library(ompr.roi)


n <- 20
cost <- runif(n, 0, 10)
calories <- runif(n, 100, 200)
min_avg_cal <- 140

model <- MIPModel() %>%
  add_variable(x[i], i =1:n, type = "binary") %>%
  set_objective(sum_expr(cost[i] * x[i], i = 1:n), "min") %>%
  add_constraint(sum_expr(calories[i] * x[i] - x[i]*min_avg_cal , i = 1:n) >= 0) %>% 
  add_constraint(sum_expr(x[i], i = 1:n) >= 5) 

result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))

calories[as.logical(result$solution)]

Upvotes: 0

sascha
sascha

Reputation: 33532

If you want some constraint:

mean(cal_0 * x_0 + cal_1 * x_1 + cal_2 * x_2 ...) >= min_avg_cal

where cal_x are constants, x_x are binary-variables,

reform it to:

cal_0 * x_0 + cal_1 * x_1 + cal_2 * x_2 ... >= min_avg_cal
-------------------------------------------
x_0 + x_1 + x_2 + ...

and:

cal_0 * x_0 + cal_1 * x_1 + cal_2 * x_2 ... >=
                              min_avg_cal * x_0 +
                              min_avg_cal * x_1 +
                              min_avg_cal * x_2 ...

The latter is a form your modelling-tool should support. It only containts sums of constant-variable products.

Upvotes: 1

Related Questions