使用R的ompr或其他优化函数进行赋值

Question

想知道这个问题是否可以用ompr R package (或任何其他优化package)来解决。

我有n处理和m细胞株，对于每个处理:细胞系对，我运行了一个实验，读数是细胞系对处理的敏感性。

现在我需要运行一个验证性实验，我需要选择i处理，对于每个处理，我需要选择j敏感和j不敏感的细胞系(在我的例子中，i = 40和j = 4)。在这个验证性实验中，我在同一个平板上运行处理和细胞系，所以我的目标是最小化细胞系的总数。

我想知道这是否可以转换为R ompr可以解决的assignment problem术语？

Answer 1

假设我正确地解释了您的问题，我使用ompr对其进行了建模。如果我没理解错的话，你想要将治疗的一个子集与细胞系相匹配。每个处理应与两个敏感细胞系和两个非敏感细胞系相匹配。我进一步假设，细胞系可以在不同的处理之间共享，否则就不需要最小化细胞系的数量。

首先，我们需要为模型创建输入数据。我使用您在问题中选择的符号。

# For testing I chose small numbers.
# Number of treatments
n <- 10
# Number of cell lines
m <- 10
# Number of treatments for confirmatory experiment
i <- 4

# simulation of treatment results
# a data.frame with a sensitivity result for each treatment/cell_line combination.
# the result is either TRUE (sensitive) or FALSE (not sensitive)
treatment_results <- expand.grid(treatment = 1:n, cell_line = 1:m)
treatment_results$result <- runif(nrow(treatment_results)) < 0.3

此外，我还创建了两个辅助函数，这两个函数将在以后制定模型时派上用场。

# helper function to identify positive or negative 
# treatment/cell_line combinations in order to make the modelling easier to read
is_sensitive <- function(k, j) {
  purrr::map_lgl(j, function(j) {
    record <- treatment_results$treatment == k & treatment_results$cell_line == j
    treatment_results[record, "result"]
  })
}
is_not_sensitive <- function(k, j) {
  !is_sensitive(k, j)
}

现在是模型。我添加了内联注释来描述约束/决策变量。请使用最新版本的ompr。

library(ompr)
library(magrittr)
model <- MIPModel() %>%

  # 1 if treatment k is applied to cell_line j
  add_variable(x[k, j], k = 1:n, j = 1:m, type = "binary") %>%

  # 1 if treatment k is selected for confirmatory experiment
  add_variable(y[k], k = 1:n, type = "binary") %>%

  # 1 if cell_line j is used
  add_variable(z[j], j = 1:m, type = "binary") %>%

  # minimize the number of assigned cell lines
  set_objective(sum_expr(z[j], j = 1:m), direction = "min") %>%

  # we want to test i treatments
  add_constraint(sum_expr(y[k], k = 1:n) == i) %>%

  # each tested treatment has to have 2 sensitive and 2 non-sensitive cell lines
  # 2 sensitives
  add_constraint(sum_expr(x[k, j], j = 1:m, is_sensitive(k, j)) == 2 * y[k]
                 , k = 1:n) %>%
  # 2 not sensitives
  add_constraint(sum_expr(x[k, j], j = 1:m, is_not_sensitive(k, j)) == 2 * y[k]
                 , k = 1:n) %>%

  # last constraint is to mark cell lines as being assigned for the obj. fun.
  add_constraint(sum_expr(x[k, j], k = 1:n) <= n * z[j], j = 1:m)

在给定模型的情况下，我们可以使用GLPK来解决。请注意，对于较大的参数，模型可能需要很长时间。

# you can solve the model using GLPK for example
library(ompr.roi)
library(ROI.plugin.glpk)
result <- solve_model(model, with_ROI("glpk", verbose = TRUE))

# let's examine the solution
library(dplyr)
# this is the list of treatments selected for testing
filter(get_solution(result, y[k]), value > 0)$k

# this is the list of cell_lines selected for testing
filter(get_solution(result, z[j]), value > 0)$j

# the actual matching of treatment and cell_line is in the x variable
get_solution(result, x[k, j]) %>%
  filter(value > 0) %>%
  inner_join(treatment_results, by = c("k" = "treatment", "j" = "cell_line"))