JuMP - 整数和 0-1 编程的多种解决方案

Question

在 JuMP 中，Julia v1.3.1，

using JuMP, GLPK


function example_basic(n = 4)
    model = Model(GLPK.Optimizer)
    @variable(model, x1, Bin)
    @variable(model, x2, Bin)
    @variable(model, C <= 1)

    @objective(model, Max,   C)

    @constraint(model, x1 + x2 <= C)

    # if verbose
    #     print(model)
    # end

    JuMP.optimize!(model)

    obj_value = JuMP.objective_value(model)
    # num_results = 1
    num_results = result_count(model)
    @show num_results

end

Returns 1.我只是不明白这个结果背后的编程。因为这个微小的线性问题显然有 2 个最优解：

(x1,x2)=(0,1)=(1,0)

JuMP returns 1 怎么来的？

我最好的猜测是 GLPK 不支持整数规划的多个解决方案，因为文档说：

Some solvers support returning multiple solutions. You can check how many solutions are available to query using result_count.

然后我尝试了另一个求解器：Cbc，但结果是一样的。如果我的问题是两个求解器都不支持多个解决方案，我怎么能得到支持的 JuMP 求解器列表？

Answer 1

传统上 MIP 求解器只是 return 一种解决方案。大多数（甚至所有）免费求解器都遵循这种方法，只有 return 一种解决方案。一些商业求解器有一个称为解决方案池的东西来保存多个解决方案。

有一种方法可以通过对问题添加切割并解决来枚举最佳或次优 MIP 解决方案。参见 How to ask for second best solution to a MIP using JuMP。

JuMP - 整数和 0-1 编程的多种解决方案

JuMP - multiple solutions in Integer and 0-1 Programming

linear-programming

julia

julia-jump