Оптимизация с индексацией в линейном программировании

Question

Я столкнулся с несколькими проблемами оптимизации, которые связаны с определением одного или нескольких индексов в векторе, который максимизирует или минимизирует стоимость. Есть ли способ идентифицировать такие показатели в линейном программировании? Я открыт для решений в mathprog, CVXR, CVXPY или любом другом API.

Например, определение индекса требуется для проблем с точкой изменения (найдите индекс, в котором функция изменения), накладывая ограничения на расстояние для задачи коммивояжера (посетите город X до совокупного расстояния Y).

В качестве простого примера предположим, что мы хотим определить положение в векторе, где сумма с обеих сторон является наиболее равной (их разница наименьшая). В этом примере решением является индекс 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

Символы красного цвета - это переменные решения, а символы синего цвета - константы.

Код 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.

Answer 2

В конце концов, если вы выбираете вещи по индексу, я думаю, вам нужно работать с набором соответствующих переменных двоичного выбора. Тот факт, что вы выбираете «вещи подряд», как в вашем примере задачи, - это просто то, что нужно обрабатывать с ограничениями на двоичные переменные.

Чтобы решить поставленную вами проблему, я сделал набор двоичные переменные выбора, назовите их s[i], где i = {0, 1, 2, ..., len(x)}, а затем ограничьте:

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

, что обеспечивает «непрерывность» от начала до первого невыбора, а затем после этого.

Мое решение находится в Python. LMK, если вы хотите, чтобы я опубликовал. Я думаю, что изложенная выше концепция - это то, о чем вы спрашиваете.