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

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

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

Answer 2

如果您想要一些约束：

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

后者是你的建模工具应该支持的一种形式。它只包含常量积之和。