Получить все крайние точки линейной программы в CPLEX

Question

Мне нужно перечислить всю базу, соответствующую всем крайним точкам LP, с CPLEX API в Java. К сожалению, я не нашел способа сделать это с CPLEX. Есть ли решение?

Если нет, я сделаю это сам, но мне нужно будет поиграть с базой. Есть ли простой способ с CPLEX перечислить всю базу и проверить, является ли база возможным решением?

Answer 1

Краткий ответ: нет.

Нет простого способа сделать это. Один из возможных подходов, но несколько громоздкий, заключается в кодировании базы с использованием двоичных переменных. E.g.:

xb[i] = 1 for basic variables 
        0 for non-basic variables

Нам нужно добавить ограничения на неосновные переменные: они будут на границе. То есть для неотрицательной переменной x[i] имеем

xb[i]=0 => x[i]=0  

(это ограничение индикатора). Кроме того, мы знаем, что

sum(i,xb[i]) = m

(количество базовых переменных равно количеству строк в модели).

Затем используйте пул решений Cplex , чтобы перечислить все возможные выполнимые базы. Иллюстрация для этого подхода показана в этой ссылке . (Этот конкретный пример перечисляет все оптимальные базы, но нетрудно сказать, что Cplex перечисляет все возможные базы).