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?
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