How to get a random choice under some constraints using JuMP in Julia

Question

I know JuMP can solve a linear optimization problem under some constraints and maximize an objective function. Is it also possible to get a random choice under some constraints using JuMP? The pseudo-code can be given as:

    possible_transition_lists = Vector{NTuple{length(fleet), Int64}}(undef, 0)


    for x in Iterators.product(D_feasible_combs...)

        check_x_feasibility(x, D) && push!(possible_transition_lists, x)

    end

    return sample(possible_transition_lists)

When D_feasible_combs is small, this code works fine. But when it gets bigger, e.g., Iterators.repeated(collect(1:10), 10), the complexity grows exponentially. Is there a way to reduce the complexity by using JuMP and treat it as a linear optimization problem? Or is there any more efficient algorithm to solve this problem?

Answer 1

If your problem has exponentially many constraints, then the usual way to deal with it is via a lazy constraint:

https://jump.dev/JuMP.jl/stable/manual/callbacks/#Lazy-constraints

It's hard to offer more advice without a reproducible example.

If you want to discuss further, perhaps post on the discourse forum: https://discourse.julialang.org/c/domain/opt/13