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

返回1. 我就是不明白这个结果背后的编程。因为这个小小的线性问题显然有两个最优解。

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

为什么JuMP会返回1？

我最好的猜测是GLPK不支持整数编程的多解，因为文档中说。

有些解算器支持返回多个解。你可以使用 result_count 来检查有多少个解可以查询。

然后我又试了另一个求解器。Cbc, 但结果是一样的. 如果我的问题是这两个求解器都不支持多解，那我怎么会有支持多解的JuMP求解器列表呢？

Answer 1

传统的MIP求解器只返回一个解。大多数（甚至所有）免费的求解器都遵循这种方法，只返回一个解。一些商业解算器有一个叫做解池的东西，用来存放多个解。

有一种方法可以通过在问题上添加一个切口来列举最优或次优的MIP解，并解决。请看 如何使用JuMP向MIP请求次优解决方案？.