获得继最佳解决方案之后的下一个最佳解决方案

Question

我有一个简单的求解器，我用它来解决类似背包的问题。我希望在牢记约束的同时最大化价值

    self.solver = pywraplp.Solver(
                'FD',
                pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING
            )
        self.objective = self.solver.Objective()
        self.objective.SetMaximization()
self.solver.solve()

我省略了定义变量的代码，但我的问题是：运行此代码将获得最佳阵容。有没有办法找到第二、第三等最佳解决方案？

Answer 1

带有 CBC 编号。CPLEX，Gurobi 确实支持保留更多解决方案，但这在 OR-Tools 中仅通过 NextSolution(( 方法提供给 Gurobi。

如果您的模型是纯积分的，您可以查看 CP-SAT 求解器。

诀窍是，除非您探索所有解决方案，否则第二好的解决方案充其量是启发式的。

Answer 2

在类似背包的问题中，在迭代过程中直接获得下一个最佳解决方案。

首次解决问题后，可以添加一个约束，其中左侧对最优解中包含的所有项目求和，右侧将此总和限制为比最佳解决方案中包含的项目数少 1。

这本质上是一个从解空间中排除第一个最优解的切口。因此，在添加附加约束后通过解决问题将获得不同的解决方案。