做ILP时的多种解决方案

Question

目前我使用PuLP来解决最大化问题。它工作正常，但我希望能够获得N-best解决方案，而不仅仅是一个。有没有办法在PuLP或任何其他免费/ Python解决方案中做到这一点？我试图从最佳解决方案中随机挑选一些变量并抛出并重新运行，但这似乎是一个彻头彻尾的破解。

Answer 1

所以我想出了如何（通过RTFM）获得多个soutions。在我的代码基本上有：

number_unique = 1 # The number of variables that should be unique between runs 

model += objective 
model += constraint1 
model += constraint2 
model += constraint3 

for i in range(1,5): 
    model.solve() 
    selected_vars = [] 
    for p in vars: 
     if p_vars[p].value() != 0: 
      selected_vars.append(p) 
    print_results() 

    # Add a new constraint that the sum of all of the variables should 
    # not total up to what I'm looking for (effectively making unique solutions) 
    model += sum([p_vars[p] for p in selected_vars]) <= 10 - number_unique 

这个伟大的工程，但我意识到，我真的需要去随机路线。我有10个不同的变量，通过只抛出几个变量，我的解决方案在所有的排列中倾向于具有相同的重加权变量（这是可以预料的）。

Answer 2

如果您的问题很快解决，您可以尝试从上面逐步限制目标。对于examle，如果最优解的目标值是X，尝试用一个额外的约束重新运行问题：

problem += objective <= X - eps, "" 

在还原步骤eps取决于你的问题的知识。

当然，如果你只是盲目地选择一些eps并得到一个解决方案，你不知道解决方案是第二好的，第10好还是1000最好......但是你可以做一些系统的搜索（二进制，网格）eps参数（如果问题确实很快解决）。