英文:
How to find all solutions under some constraints using JuMP in Julia
问题
如前所述，我想找到满足一些线性约束条件的所有可能的变量组合。更具体地说，我想在所有这些组合中随机选择一个。
通常，在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)]
# 从组合中获取随机选择
(x,y) = sample(all_xy_combs)
是否可以使用JuMP实现这个目标？
英文:
As mentioned, I want to find all possible variable combinations that satisfy some linear constraints. More specifically, I want to get a random choice in all these combinations.
Normally, an LP problem in JuMP can be described and solved as follows:
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)
In my case, I don't need an objective function but I want to get all possible solutions that satisfy the constraints. In this example, I want to acquire the following solutions to get a random choice:
all_xy_combs = [(0,3), (1,2), (2,1), (3,0)]
# acquire a random choice from combs
(x,y) = sample(all_xy_combs)
Is it possible using JuMP?
答案1
得分: 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
英文:
This is not generally possible in JuMP. But it is possible for some solvers to return multiple solutions by setting solver-specific parameters.
For example:
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
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论