在线性编程中使用索引进行优化 [英] Optimize with indexing in linear programming

问题描述

我遇到了几个优化问题，这些问题涉及在最大化或最小化成本的向量中识别一个或多个索引.有没有办法在线性编程中识别此类索引?我愿意使用 mathprog ， CVXR ， CVXPY 或任何其他API的解决方案.

I have encountered several optimization problems that involve identifying one or more indices in a vector that maximizes or minimizes a cost. Is there a way to identify such indices in linear programming? I'm open to solutions in mathprog, CVXR, CVXPY, or any other API.

例如，对于更改点问题(确定函数发生变化的索引)，需要标识一个索引，从而将距离约束置于旅行推销员问题上(在累积距离Y之前访问城市X).

For example, identifying an index is needed for change point problems (find the index at which the function changes), putting distance constraints on the traveling salesman problem (visit city X before cumulative distance Y).

作为一个简单的示例，假设我们要确定向量中任一侧的和最相等(它们的差最小)的位置.在此示例中，解决方案是索引5:

As a simple example, suppose we want to identify the location in a vector where the sum on either side is the most equal (their difference is smallest). In this example, the solution is index 5:

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

尝试1

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

Attempt 1

Using CVXR, I tried declaring split_index and using that as an index (e.g., 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)

使用 NA/NaN参数错误的 1:split_index .

声明一个明确的索引向量( indices )并进行元素逻辑测试，以确定 split_index< =索引.然后将那个二进制向量与 x 逐元素相乘以选择拆分的一侧或另一侧:

Declare an explicit index-vector (indices) and do an elementwise logical test whether split_index <= indices. Then element-wise-multiply that binary vector with x to select one or the other side of the split:

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 中出现错误，并为二进制运算符提供了非数字参数.我怀疑出现此错误是因为 is_first 现在是一个 IneqConstraint 对象.

It errs in x * is_first with non-numeric argument to binary operator. I suspect that this error arises because is_first is now an IneqConstraint object.

推荐答案

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

Symbols in red are decision variables and symbols in blue are constants.

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自动线性化.

The absolute value is automatically linearized by CVXR.

这篇关于在线性编程中使用索引进行优化的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！