在线性编程中使用索引优化

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逐元素相乘，以选择分割的一侧或另一侧：

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

归根结底，如果您要通过索引选择内容，我认为您需要使用一组相应的二进制选择变量来进行处理。正如您在示例问题中那样，选择“连续的东西”这一事实仅是需要对二进制变量进行约束的处理。

为了解决您提出的问题，我制作了一组二进制选择变量，将其命名为s[i]，其中i = {0, 1, 2, ..., len(x)}，然后加以约束：

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

从开始到第一次未选择，然后是此后，将强制执行“连续性”。

我的解决方案是在Python中。 LMK（如果您希望我发布）。我想上面的概念就是您要问的。