如何在线性程序中使用 'OR' 语句？

Question

我有兴趣在线性程序中构建本质上是 or 语句的内容。目前我在 R 中使用 lpSolveAPI，但我也希望得到有关此类问题的线性规划最佳实践的答案。

下面是一些使用 lpSolveAPI 包的工作代码：

library(lpSolveAPI)

# Defines the 'score' which we seek to maximize
mat <- data.frame(score = c(0.04, 0.04, -.11, -.03, 0.04, 0.04, -0.06, 0.01))

# Side specifies whether something is a 'sell' or a 'buy'
mat[, 'side'] <- c(1, 1, -1, -1, 1, 1, -1, -1)

# 'a' and 'b' are descriptive factors defining what something is thing a or thing b. 
mat[, 'a'] <- c(1, 1, 1, 1, 0, 0, 0, 0)
mat[, 'b'] <- c(0, 0, 0, 0, 1, 1, 1, 1)


# the lower bound for all sides = -1 have a lower bound of some negative value and an upper bound of zero
mat[, "lb"] <- c(0, 0, -0.2, -0.4, 0, 0, -.1, -.2)
# the upper bound for all sides = 1 have a lower bound of zero and an upper bound of 1
mat[, 'ub'] <- c(1, 1, 0, 0, 1, 1, 0, 0)
# this is just initializing our variables field which will be populated later
mat[, 'x'] <- rep(0, 8)


# using the lpSolveAPI package, create a program with the number of rows in the matrix 'mat'
LP <- make.lp(0, nrow(mat))

set.objfn(LP, -mat[, 'score'])
set.bounds(LP, lower = mat[, 'lb'])
set.bounds(LP, upper = mat[, 'ub'])

# This constraint requires that the sum of all of x must be equal to zero. In other words, the amount of sells equals the amount of buys
add.constraint(LP, rep(1, nrow(mat)), "=", 0)

solve(LP)
get.objective(LP)
get.variables(LP)

mat$x <- get.variables(LP)

当您运行此代码并查看结果时，您会看到 x6 = 0.9、x7 = -0.1 和 x8 = -0.2。对此的解释是 b 的 90% 被购买，b 的 30% 被出售。

我想建立一个约束，要求如果 a 或 b 在任何地方出售，它也不能被购买. （反之亦然）

在这种特殊情况下，我希望最佳解决方案是售出 a 的 20% (x3) 和 b[ 的 20% =31=] 已购买（x5 或 x6）。 x = (0, 0, -0.2, 0, 0.2, 0, 0, 0)

换句话说，如果您选择 x1 and/or x2 中的值不是零，则 x3 和 x4 中的值必须为 0。同样，如果您选择 x3 and/or x4 中的值不是零，则 x1 和 x2 中的值必须为零。

Answer 1

一般来说，"all of these variables are either non-negative or non-positive" 形式的约束需要引入一个二元变量来指示是否选择了正例或负例。

让我们以前四个变量为例；我们将引入一个二元变量 p1 来指示我们是处于非负态（p1=1）还是非正态（p1=0）。现在我们有以下限制：

0 <= x1 <= 1
0 <= x2 <= 1
-0.2 <= x3 <= 0
-0.4 <= x4 <= 0

如果p1=1，则下限必须至少为0，如果p1=0，则上限必须不大于0。我们可以将约束重写为：

0 <= x1 <= 1 * p1
0 <= x2 <= 1 * p1
-0.2 * (1-p1) <= x3 <= 0
-0.4 * (1-p1) <= x4 <= 0

基本上，我们需要将所有正上限乘以p1，如果我们处于非负space，这没有影响，如果我们将上限设置为0在非阳性情况下。类似地，我们需要将所有负下界乘以 (1-p1)，如果我们处于非正 space，这没有影响，如果我们处于非 space，则将下界设置为 0 -负例。

我们同样为第二组变量定义了一个新的二进制变量p2，并按如下方式更新我们的约束：

0 <= x5 <= 1 * p2
0 <= x6 <= 1 * p2
-0.1 * (1-p2) <= x7 <= 0
-0.2 * (1-p2) <= x8 <= 0

在代码中，这看起来像：

n <- nrow(mat)
LP <- make.lp(0, n+2)
set.objfn(LP, c(-mat[, 'score'], 0, 0))
set.type(LP, n+1, "binary")
set.type(LP, n+2, "binary")
set.bounds(LP, lower = c(mat[, 'lb'], 0, 0))
set.bounds(LP, upper = c(mat[, 'ub'], 1, 1))

for (i in 1:n) {
  add.constraint(LP, c(i == (1:n), (mat[i,'a'] == 1) * mat[i,'lb'], (mat[i,'b'] == 1) * mat[i,'lb']), ">=", mat[i,'lb'])
  add.constraint(LP, c(i == (1:n), -(mat[i,'a'] == 1) * mat[i,'ub'], -(mat[i,'b'] == 1) * mat[i,'ub']), "<=", 0)
}
add.constraint(LP, c(rep(1, n), 0, 0), "=", 0)

solve(LP)
get.objective(LP)
# [1] -0.058
round(head(get.variables(LP), -2), 3)
# [1]  0.0  0.0 -0.2 -0.4  0.0  0.6  0.0  0.0

找到的最佳解决方案 objective 值为 0.058，实际上优于 OP 手动找到的解决方案（只有 objective 值为 0.03）。

如何在线性程序中使用 'OR' 语句？

How can I make use of an 'OR' statement in a linear program?

r

mathematical-optimization

linear-programming

lpsolve