Перечисление всех основных возможных решений

Question

Я хочу перечислить все основные возможные решения линейной программы.Как я могу сделать это с PuLP ?

Я прочитал документацию PuLP , но не смог узнать, как это сделать.Ваша помощь действительно будет оценена.

Answer 1

Вы можете сделать это с помощью Pulp, но это нелегко (и, конечно, работает только для небольших задач).

Сначала закодируйте базу двоичными переменными.Т.е.

b(i) = 1 if x(i) is basic (x(i) are all variables: structural and logical)
       0 otherwise

Затем добавьте ограничения:

1. if b(i)=0 then x(i)=0 (i.e. if nonbasic then the variable should
                          be zero -- assuming non-negative variables).
2. sum(i, b(i)) = m      (the number of basic variables is equal to 
                          the number of constraints) 

Затем используйте этот алгоритм:

step 1. Solve as a MIP.
        If infeasible: STOP 
step 2. Add cut to prevent the previous basis
        Go to step 1.

Базовый алгоритм объяснен здесь кроме того, что мы остановимся чуть раньше: как только цель ухудшится.Это будет перечислять все оптимальные базы.