在线性规划中使用索引进行优化

Question

我遇到过几个优化问题，涉及在最大化或最小化成本的向量中识别一个或多个 indices。有没有办法在线性规划中识别这些指标？我愿意接受 mathprog、CVXR、CVXPY 或任何其他 API.

中的解决方案

例如，变化点问题需要确定一个指标（找到函数变化的指标），对旅行商问题设置距离限制（在累积距离Y之前访问城市X）。

作为一个简单的例子，假设我们要确定向量中两边的和最相等（它们的差最小）的位置。在此示例中，解决方案是索引 5:

x = c(1, 3, 6, 4, 7, 9, 6, 2, 3)

尝试 1

使用 CVXR，我尝试声明 split_index 并将其用作索引（例如，x[1:split]）：

library(CVXR)
split_index = Variable(1, integer = TRUE)
objective = Minimize(abs(sum(x[1:split_index]) - sum(x[(split_index+1):length(x)])))
result = solve(objective)

错误 1:split_index 为 NA/NaN argument。

尝试 2

声明一个显式索引向量（indices）并进行元素逻辑测试是否split_index <= indices。然后将该二进制向量与 x 逐元素相乘到 select 拆分的一侧或另一侧：

indices = seq_along(x)
split_index = Variable(1, integer = TRUE)
is_first = split_index <= indices
objective = Minimize(abs(sum(x * is_first) - sum(x * !is_first)))
result = solve(objective)

它在 x * is_first 和 non-numeric argument to binary operator 中出错。我怀疑出现此错误是因为 is_first 现在是一个 IneqConstraint 对象。

Answer 1

归根结底，如果您要按索引选择内容，我认为您需要使用一组相应的二元选择变量来解决这个问题。您在示例问题中选择 "things in a row" 的事实只是需要通过对二进制变量的约束来处理。

为了解决你提出的问题，我做了一组二元选择变量，称之为s[i] where i = {0, 1, 2, ..., len(x)} 然后constrained:

s[i] <= s[i-1] for i = {1, 2, ..., len(x)}

从开始到第一次未选择以及之后强制执行 "continuity"。

我的解决方案在Python。 LMK 如果你想让我 post。上面的概念，我想，就是你问的。

Answer 2

红色符号是决策变量，蓝色符号是常量。

R代码：

> library(Rglpk)
> library(CVXR)
> 
> x <- c(1, 3, 6, 4, 7, 9, 6, 2, 3)
> n <- length(x)
> delta <- Variable(n, boolean=T)
> y <- Variable(2)
> order <- list()
> for (i in 2:n) {
+     order[[as.character(i)]] <- delta[i-1] <= delta[i]
+ }
> 
> 
> problem <- Problem(Minimize(abs(y[1]-y[2])),
+                    c(order,
+                      y[1] == t(1-delta) %*% x,
+                      y[2] == t(delta) %*%x))
> result <- solve(problem,solver = "GLPK", verbose=T)
GLPK Simplex Optimizer, v4.47
30 rows, 12 columns, 60 non-zeros
      0: obj =  0.000000000e+000  infeas = 4.100e+001 (2)
*     7: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
*     8: obj =  0.000000000e+000  infeas = 0.000e+000 (0)
OPTIMAL SOLUTION FOUND
GLPK Integer Optimizer, v4.47
30 rows, 12 columns, 60 non-zeros
9 integer variables, none of which are binary
Integer optimization begins...
+     8: mip =     not found yet >=              -inf        (1; 0)
+     9: >>>>>  1.000000000e+000 >=  0.000000000e+000 100.0% (2; 0)
+     9: mip =  1.000000000e+000 >=     tree is empty   0.0% (0; 3)
INTEGER OPTIMAL SOLUTION FOUND
> result$getValue(delta)
      [,1]
 [1,]    0
 [2,]    0
 [3,]    0
 [4,]    0
 [5,]    0
 [6,]    1
 [7,]    1
 [8,]    1
 [9,]    1
> result$getValue(y)
     [,1]
[1,]   21
[2,]   20
>

绝对值由CVXR自动线性化。

在线性规划中使用索引进行优化

Optimize with indexing in linear programming

linear-programming

mathprog

cvxpy

cvxr

尝试 1

尝试 2