如何在Ompr线性规划模型中强制要求至少选择2个分组

问题背景 #

现有线性规划任务需满足：总成本不超过20的前提下，从10个物品中选取3个以最大化总权重。当前因分组a的物品权重设置极高，模型仅选中了分组a的3个物品。需要修改Ompr模型，强制要求选中的物品至少来自2个分组。

修改方案 #

核心思路是新增分组选择标识变量，通过约束关联物品选择与分组选择，最终限制选中的分组数量≥2。

修改后的完整代码 #

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

set.seed(1)
d <- data.frame(
  id = seq_len(10),
  weight = c(rep(100, 3), runif(7, 1, 50)),
  cost = runif(10, 1, 10),
  group = c(rep("a", 3), rep("b", 3), rep("c", 3), "d")
)

# 获取所有唯一分组
groups <- unique(d$group)

m <- ompr::MIPModel() %>%
  
  # 原物品选择变量：x[i]=1表示选中物品i
  ompr::add_variable(x[i],
                     i = d$id,
                     type = "binary") %>%
  
  # 新增分组选择变量：y[g]=1表示分组g有物品被选中
  ompr::add_variable(y[g],
                     g = groups,
                     type = "binary") %>%
  
  # 目标函数：最大化总权重（原逻辑不变）
  ompr::set_objective(
    ompr::sum_over(d$weight[i] * x[i],
                   i = d$id), "max"
  ) %>%
  
  # 约束1：总成本不超过20（原逻辑不变）
  ompr::add_constraint(
    ompr::sum_over(d$cost[i] * x[i],
                   i = d$id) <= 20
  ) %>% 
  
  # 约束2：仅选3个物品（原逻辑不变）
  ompr::add_constraint(
    ompr::sum_over(x[i], i = d$id) == 3
  ) %>%
  
  # 约束3：关联物品选择与分组选择
  # 若分组g内有物品被选中，则y[g]必须为1
  ompr::add_constraint(
    ompr::sum_over(x[i], i = d$id[d$group == g]) <= 3 * y[g],
    g = groups
  ) %>%
  
  # 约束4：强制选中至少2个分组
  ompr::add_constraint(
    ompr::sum_over(y[g], g = groups) >= 2
  )

res <- ompr::solve_model(m, ompr.roi::with_ROI(solver = "glpk"))

# 查看选中的物品
res %>%
  ompr::get_solution(x[i]) %>% 
  dplyr::filter(.data$value > 0) %>% 
  dplyr::inner_join(d, by = c("i" = "id"))

代码修改说明 #

1. 新增分组变量y[g]：每个分组对应一个二进制变量，用于标记该分组是否有物品被选中。
2. 关联物品与分组的约束：sum_over(x[i], i = d$id[d$group == g]) <= 3 * y[g]
   • 当y[g]=0时，分组g内所有x[i]必须为0（即该分组无物品被选中）；
   • 当y[g]=1时，分组g内可以选中1-3个物品（符合总选3个的限制）。
3. 强制多分组约束：sum_over(y[g], g = groups) >= 2直接限制选中的分组数量至少为2，避免全选同一分组的情况。

运行结果示例 #

修改后运行代码，输出的选中物品会来自至少2个分组（例如可能选中2个a组物品+1个其他组物品），既满足权重最大化，又符合多分组要求。

内容的提问来源于stack exchange，提问作者Giovanni Colitti