在 ompr 线性规划约束中使用平均值

Question

我正在使用 ompr 包来求解整数程序。我想包含一个基于另一个二进制变量的平均值的约束。

在下面的例子中，我有一些食物，我想找到至少 5 件物品并尽量减少成本。我希望平均卡路里数高于某个最低值。在下面的代码中，第一个约束是卡路里的总和高于 min_avg_cal。这是否可以重写，因此约束条件是所选食物的平均卡路里高于 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

Answer 1

如果你想要一些约束：

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

其中 cal_x 是常量，x_x 是二进制变量，

修改为：

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

和：

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 ...

后者是您的建模工具应该支持的一种形式。它只包含常数变量乘积的总和。

Answer 2

根据 Sascha 的建议，可以通过重新排列约束将均值重写为变量乘积的总和。特别是，您可以更改此约束：

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

进入

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

这只是对均值定义的重新排列。

完整的解决方案与替换了单个约束的原始代码相同：

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)]

在 ompr 线性规划约束中使用平均值

Using an average in a ompr linear programming constraint

r

optimization

mathematical-optimization

linear-programming

glpk