computational-geometry - 列举所有基本可行的解决方案

Question

我想列举线性规划的所有基本可行解。我怎么能用纸浆做到这一点？

我已经阅读了 PuLP文档，但不知道如何去做。您的帮助将不胜感激。

Answer 1

你可以用 Pulp 做到这一点，但这并不容易（当然只适用于小问题）。

首先通过二进制变量对基础进行编码。IE

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.

这里解释了基本算法，除了我们稍早停止：一旦目标恶化。这将枚举所有最佳基础。