Julia Jump：获取 mip 的所有可行解决方案

Question

我希望拥有所有可行（次优）向量，而不仅仅是 mip 的最佳解决方案向量。
\n我在这里发现了一些老问题，但我不确定它们是如何工作的。

\n

首先，是否有任何新的库工具/方法可以自动执行此操作？
\n我尝试了这个，但是什么也没做：

\n

if termination_status(m) == MOI.FEASIBLE_POINT\n    println(x)\nend\noptimize!(m);\n

\n

如果没有，最简单的方法是什么？
\n我想到扫描最优解，直到找到第一个非零决策变量，然后将该变量约束为零并再次求解模型。

\n

for i in 1:active_variables\n    if value.(z[i])==1\n        @constraint(m, x[i] == 0)\n        break\n    end\nend\n\noptimize!(m);\n

\n

但我用这个方法看到了这个问题**：

\n

\n
1. \xce\x99f 我将 x[i] 约束为零，在下一步中我可能希望再次删除此约束？这取决于是否可以存在两种（或更多）不同的解决方案，其中x[i]==1
\n

\n

---

\n

Answer 1

以下是布尔问题的全解查找器的示例。此类问题更容易处理，因为解决方案空间很容易枚举（即使它仍然可以呈指数级增长）。

首先，让我们获取包并定义示例问题：

using Random, JuMP, HiGHS, MathOptInterface

function example_knapsack()
    profit = [5, 3, 2, 7, 4]
    weight = [2, 8, 4, 2, 5]
    capacity = 10
    minprofit = 10
    model = Model(HiGHS.Optimizer)
    set_silent(model)
    @variable(model, x[1:5], Bin)
    @objective(model, FEASIBILITY_SENSE, 0)
    @constraint(model, weight' * x <= capacity)
    @constraint(model, profit' * x >= minprofit)
    return model
end

（这是 JuMP 文档中的背包问题）。

接下来，我们使用递归来探索所有可能解决方案的树。树不会沿着没有解决方案的分支向下延伸（因此运行时间并不总是指数级的）：

function findallsol(model, x)
    perm = shuffle(1:length(x))
    res = Vector{Float64}[]
    _findallsol!(res, model, x, perm, 0)
    return res
end

function _findallsol!(res, model, x, perm, depth)
    n = length(x)
    depth > n && return
    optimize!(model)
    if termination_status(model) == MathOptInterface.OPTIMAL
        if depth == n
            push!(res, value.(x))
            return
        else
            idx = perm[depth+1]
            v = value(x[idx])
            newcon = @constraint(model, x[idx] == v)
            _findallsol!(res, model, x, perm, depth + 1)
            delete(model, newcon)
            newcon = @constraint(model, x[idx] == 1 - v)
            _findallsol!(res, model, x, perm, depth + 1)
            delete(model, newcon)
        end
    end
    return
end

现在我们可以：

julia> m = example_knapsack()
A JuMP Model
Maximization problem with:
Variables: 5
...
Names registered in the model: x

julia> res = findallsol(m, m.obj_dict[:x])
5-element Vector{Vector{Float64}}:
 [1.0, 0.0, 0.0, 1.0, 1.0]
 [0.0, 0.0, 0.0, 1.0, 1.0]
 [1.0, 0.0, 1.0, 1.0, 0.0]
 [1.0, 0.0, 0.0, 1.0, 0.0]
 [0.0, 1.0, 0.0, 1.0, 0.0]

我们得到一个包含所有解决方案的向量。

如果所讨论的问题是布尔问题，则可以按原样使用此方法。如果它有非布尔变量，递归将必须以某种均匀的方式分割可行空间。例如，选择一个变量并将其域切成两半，然后在该变量上使用较小的域递归到每一半（以确保终止）。

PS 这不是最佳方法。这个问题已经得到了很好的研究。可能要搜索的术语是“模型计数”（尤其是在布尔域中）。

（更新：将目标更改为使用可行）