1

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?

PokeLu
  • 767
  • 8
  • 17
  • Could you present `D_feasible_combs` as a set of binary variables? Most likely you can. This should make it possible to solve larger problems. – Przemyslaw Szufel Mar 07 '23 at 23:51

1 Answers1

0

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

Oscar Dowson
  • 2,395
  • 1
  • 5
  • 13