是否可以在 Ompr 优化中使用乘积表达式作为约束？

Question

我知道 ompr 包中的 sum_expr 函数是一种创建具有动态总和的约束的方法。但是，我想知道是否有办法创建一个使用乘积而不是总和的约束。或者这在 linear 优化中是不可能的？

例如：

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

n <- 20
score <- round(runif(n, 0, 25))
penalties <- round(runif(n, 0, 25))

model <- MIPModel() %>%
  add_variable(x[i], i = 1:n, type = "binary") %>%
  set_objective(sum_expr(score[i] * x[i], i = 1:n), "max") %>%
  add_constraint(sum_expr(penalties[i] * x[i], i = 1:n) <= 100)

result <- solve_model(model, with_ROI(solver = "glpk", verbose = TRUE))
result$solution

有没有办法 add_constraint(product_expr()) 而不是 add_constraint(sum_expr())？

如果无法进行线性优化，我应该去哪里找？

Answer 1

二进制变量的乘积可以线性化如下。

假设我们要建模

y = prod(i, x(i))
x(i), y ∈ {0,1}

我们可以将其写成一组线性不等式：

y ≤ x(i)   ∀i
y ≥ sum(i, x(i)) - card(i) + 1
x(i), y ∈ {0,1}

其中 card(i) 是 i 的数量。通常事情可以进一步简化，但这取决于模型的细节。

这可以在 OMPR 中直接实现，并且可以使用任何线性 MIP 求解器求解。

Answer 2

我设法找到了我最初问题的答案。如果对任何人使用，我需要的约束是：

add_constraint(sum_expr(x[i] * log(penalties[i]), i = 1:n) >= log(100))

换句话说，我将对数变换的惩罚值（x[i] = 1）与对数变换的惩罚总数相加，以模拟乘积约束。

我原来的问题错误地暗示了一些可能误导读者的东西。我正在寻找 x[i] = 1 的所有处罚的乘积。不是值 (penalties[i] * x[i]) 的乘积，一旦任何 x[i] = 0 变为 0.

是否可以在 Ompr 优化中使用乘积表达式作为约束？

Is it possible to use a product expression as a constraint in an Ompr optimisation?

r

optimization

linear-programming

glpk