如何用Julia的JuMP获取约束下的所有解并随机选择其一

结论 #

可以通过JuMP结合整数规划求解器（如Gurobi）实现需求，具体分为枚举所有可行解后随机选择和随机化求解器参数生成候选解后选择两种思路，可根据可行解规模选择合适方法。

方法一：枚举所有可行解再随机选择 #

适用于可行解数量较少的场景，可通过求解器的批量解收集功能或迭代添加排除约束的方式获取所有解，再随机选取一个。

子方法1：利用求解器的批量解收集功能（以Gurobi为例） #

Gurobi支持通过参数配置收集所有可行解，示例代码如下：

using JuMP, Gurobi, Random

# 初始化Gurobi环境与模型
GRB_ENV = Gurobi.Env()
model = Model(optimizer_with_attributes(() -> Gurobi.Optimizer(GRB_ENV), "OutputFlag" => 0))

# 定义变量与约束
@variable(model, x >= 0, Int)
@variable(model, y >= 0, Int)
@constraint(model, x + y <= 3)

# 设置Gurobi参数以收集所有可行解
set_optimizer_attribute(model, "PoolSearchMode", 2)  # 模式2表示寻找所有可行解
set_optimizer_attribute(model, "PoolSolutions", 1000)  # 设置最大保存解数量，按需调整

optimize!(model)

# 提取所有可行解
num_solutions = result_count(model)
all_solutions = [(value(x; result=i), value(y; result=i)) for i in 1:num_solutions]

# 随机选择一个解
Random.seed!(123)  # 可选：固定随机种子保证结果可复现
random_solution = rand(all_solutions)
println("随机选中的可行解：", random_solution)

子方法2：迭代添加排除约束枚举所有解 #

若求解器不支持批量收集解，可通过循环求解+添加排除约束的方式枚举所有可行解：

using JuMP, Gurobi, Random

GRB_ENV = Gurobi.Env()
model = Model(optimizer_with_attributes(() -> Gurobi.Optimizer(GRB_ENV), "OutputFlag" => 0))

@variable(model, x >= 0, Int)
@variable(model, y >= 0, Int)
@constraint(model, x + y <= 3)

all_solutions = []
while true
    optimize!(model)
    # 检查是否还有可行解
    if termination_status(model) != MOI.FEASIBLE_POINT
        break
    end
    # 记录当前解
    current_x = value(x)
    current_y = value(y)
    push!(all_solutions, (current_x, current_y))
    # 添加约束排除当前解，避免重复找到
    @constraint(model, (x != current_x) || (y != current_y))
end

# 随机选择解
Random.seed!(123)
random_solution = rand(all_solutions)
println("随机选中的可行解：", random_solution)

方法二：随机化求解器参数生成候选解 #

当可行解数量极大时，枚举所有解效率低下，可通过多次随机化求解器参数获取不同可行解，再从中随机选择：

using JuMP, Gurobi, Random

GRB_ENV = Gurobi.Env()
num_trials = 5  # 尝试求解的次数，按需调整
candidate_solutions = []

for _ in 1:num_trials
    # 每次使用不同的随机种子初始化模型
    model = Model(optimizer_with_attributes(() -> Gurobi.Optimizer(GRB_ENV), 
        "OutputFlag" => 0,
        "Seed" => rand(1:10000)
    ))
    @variable(model, x >= 0, Int)
    @variable(model, y >= 0, Int)
    @constraint(model, x + y <= 3)
    
    optimize!(model)
    if termination_status(model) == MOI.FEASIBLE_POINT
        push!(candidate_solutions, (value(x), value(y)))
    end
end

# 对候选解去重后随机选择
unique_solutions = unique(candidate_solutions)
random_solution = rand(unique_solutions)
println("随机选中的可行解：", random_solution)

注意事项 #

• 可行解规模：若问题的可行解数量极大，枚举所有解会占用大量内存与时间，优先选择方法二。
• 求解器支持：不同求解器对批量解收集的支持不同，Gurobi、CPLEX等商业求解器支持较好，开源求解器可能需要用迭代排除的方式。
• 无目标函数处理：JuMP允许模型无目标函数，此时求解器会默认寻找任意一个可行解。

内容的提问来源于stack exchange，提问作者PokeLu