如何在 Julia 中使用 JuMP 在某些约束下找到所有解决方案

Question

如前所述，我想找到满足某些线性约束的所有可能的变量组合。更具体地说，我想在所有这些组合中随机选择。

通常，JuMP 中的一个 LP 问题可以描述和解决如下：

model = Model(optimizer_with_attributes(() -> Gurobi.Optimizer(GRB_ENV), "OutputFlag"=>0))
@variable(model, x >= 0::Int)
@variable(model, y >= 0::Int)
@objective(model, Max, x-y) # not required
@constraint(model, x+y<=3)
optimize!(model)

在我的例子中，我不需要目标函数，但我想获得满足约束条件的所有可能的解决方案。在这个例子中，我想获得以下解决方案来获得随机选择：

all_xy_combs = [(0,3), (1,2), (2,1), (3,0)]
# acquire a random choice from combs
(x,y) = sample(all_xy_combs)

是否可以使用 JuMP？

Answer 1

这在 JuMP 中通常是不可能的。但是某些求解器可以通过设置特定于求解器的参数来返回多个解。

例如：

julia> using JuMP, Gurobi

julia> model = Model(Gurobi.Optimizer);

julia> set_silent(model)

julia> set_attribute(model, "PoolSearchMode", 2)

julia> set_attribute(model, "PoolSolutions", GRB_MAXINT)

julia> @variable(model, x >= 0, Int)
x

julia> @variable(model, y >= 0, Int)
y

julia> @constraint(model, x + y <= 3)
x + y ≤ 3.0

julia> @objective(model, Max, x - y)
x - y

julia> optimize!(model)

julia> solutions = map(1:result_count(model)) do i
           return (
               x = value(x; result = i), 
               y = value(y; result = i),
               obj = objective_value(model; result = i),
           )
       end
10-element Vector{NamedTuple{(:x, :y, :obj), Tuple{Float64, Float64, Float64}}}:
 (x = 3.0, y = -0.0, obj = 3.0)
 (x = 2.0, y = -0.0, obj = 2.0)
 (x = 1.0, y = -0.0, obj = 1.0)
 (x = 2.0, y = 1.0, obj = 1.0)
 (x = -0.0, y = -0.0, obj = -0.0)
 (x = 1.0, y = 1.0, obj = -0.0)
 (x = 1.0, y = 2.0, obj = -1.0)
 (x = -0.0, y = 1.0, obj = -1.0)
 (x = -0.0, y = 2.0, obj = -2.0)
 (x = -0.0, y = 3.0, obj = -3.0)

https://www.gurobi.com/documentation/9.5/refman/poolsearchmode.html#parameter:PoolSearchMode https://www.gurobi.com/documentation/9.5/refman/poolsolutions.html#parameter:PoolSolutions