0

我目前正在使用 R 中的 ompr 和 roi 包来解决 IP 类型问题。我已经设法解决了一个简单的版本，但是，我现在正在尝试扩展问题，我只想在 1 个背包中包含一个项目（不要让它多次出现在背包中）。下面是我正在使用的示例数据集（称为 KP）：

项目编号 物品种类 价值 重量
1 一个 114 24
2 乙 557 136
3 乙 543 136
4 乙 10 136
5 乙 4 136
6 C 161 152
7 一个 184 24
8 一个 751 24
9 一个 184 24
10 一个 150 24

我使用以下代码解决了我最初版本的背包（背包容量为 240）：

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

# Create variables from data to use in model
n <- nrow(KP)
v <- KP$Value
w <- KP$Weight
c <- 240


solution <- MIPModel() %>%
  add_variable(x[i], i = 1:n, type = "binary") %>%
  set_objective(sum_expr(v[i] * x[i], i = 1:n), "max") %>%
  add_constraint(sum_expr(w[i] * x[i], i = 1:n) <= c) %>%
  solve_model(with_ROI(solver = "glpk")) %>% 
  get_solution(x[i]) 
  #filter(value > 0)

# Now join solution to original dataframe
df <- cbind(KP,capacity=240,solution[,3,drop=FALSE])
ouput <- df %>% filter(value > 0)

我现在想使用容量向量 (200, 150) 解决扩展版本。这是我使用的代码，现在合并了一个 x[i, j] 二进制变量，如果将项目 i 添加到 c[j]，则该变量设置为 1：

# Create variables from data to use in model
n <- nrow(KP)
v <- KP$Value
w <- KP$Weight
c <- c(240,150)
m <- length(c)

# Now solve the model
solution <- MIPModel() %>%
  add_variable(x[i, j], i = 1:n,j=1:m, type = "binary") %>%
  set_objective(sum_expr(v[i] * x[i, j], i = 1:n, j=1:m), "max") %>%
  add_constraint(sum_expr(w[i] * x[i, j], i = 1:n, j=1:m) <= c[j]) %>% #This constraint ensures that the weight of the items must be less than the capacity
  add_constraint(sum_expr(x[i, j], i = 1:n, j=1:m) <= 1) %>% #This constraint ensure that an item can only be included in a single knapsack - not across multiple knapsacks
  solve_model(with_ROI(solver = "glpk")) %>% 
  get_solution(x[i, j]) 
#filter(value > 0)

我试过调试代码，它本质上是没有正确生成的约束（这是发生错误的地方）。这是我得到的错误：

check_for_unknown_vars_impl(model, the_ast) 中的错误：表达式包含不属于模型的变量。

我已经尝试了各种方法来尝试解决这个问题，但似乎无法弄清楚我的约束有什么问题。

4

1 回答 1

0

对于任何感兴趣的人，我需要在右侧索引 j。所以我设法找到了一个解决方案，并将每个项目限制为只能添加到背包中一次：

# Create variables from data to use in model
n <- nrow(KP)
v <- KP$Value
w <- KP$Weight
c <- c(240,150)
m <- length(c)

# Now solve the model
solution <- MIPModel() %>%
  add_variable(x[i, j], i = 1:n,j=1:m, type = "binary") %>%
  set_objective(sum_expr(v[i] * x[i, j], i = 1:n, j=1:m), "max") %>%
  add_constraint(sum_expr(w[i] * x[i, j], i = 1:n) <= c[j], j = 1:m) %>%
  add_constraint(sum_expr(x[i, j], j = 1:m) <= 1, i=1:n) %>%
  solve_model(with_ROI(solver = "glpk")) %>% 
  get_solution(x[i, j]) %>%
  filter(value > 0)
于 2021-09-05T18:14:44.523 回答