Optimizer option for solution limit

[chriscoey]

I see there is a solver status code for solution limit: https://jump.dev/MathOptInterface.jl/stable/reference/models/#MathOptInterface.SOLUTION_LIMIT

But I didn't see an option for collecting up to N solutions. I think this would be useful to abstract over at least for MIP solvers and constraint solvers like MiniZinc? e.g. MiniZinc has https://www.minizinc.org/doc-2.7.6/en/command_line.html?highlight=max%20solutions#cmdoption-n

[odow]

We did this recently for ObjectiveLimit: #2257

MOA has SolutionLimit: https://github.com/jump-dev/MultiObjectiveAlgorithms.jl/blob/665cf9c98b6e4f7c37d0f8a794631c9a2e5097ef/src/MultiObjectiveAlgorithms.jl#L256-L263

So it seems reasonable.

[chriscoey]

Do you know off-hand which MIP solvers allow you to specify a max number of solutions/results to collect? does setting such an option tell them to look for more than one solution if by default they would only return one?

[odow]

Gurobi has https://www.gurobi.com/documentation/10.0/refman/solutionlimit.html#parameter:SolutionLimit

But I think they're all an upper bound on the number of feasible solutions that are available. Not about the number of optimal ones.

julia> using JuMP, Gurobi

julia> function main(attributes...)
           model = Model(Gurobi.Optimizer)
           set_silent(model)
           set_attributes(model, attributes...)
           @variable(model, 1 <= x <= 10, Int)
           @variable(model, 1 <= y <= 10, Int)
           @variable(model, z)
           @constraint(model, z >= x - y)
           @constraint(model, z >= y - x)
           @objective(model, Min, z)
           optimize!(model)
           display(solution_summary(model))
           return model
       end
main (generic function with 1 method)

julia> main();
* Solver : Gurobi

* Status
  Result count       : 1
  Termination status : OPTIMAL
  Message from the solver:
  "Model was solved to optimality (subject to tolerances), and an optimal solution is available."

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : NO_SOLUTION
  Objective value    : 0.00000e+00
  Objective bound    : 0.00000e+00
  Relative gap       : 0.00000e+00
  Dual objective value : 0.00000e+00

* Work counters
  Solve time (sec)   : 4.34875e-04
  Barrier iterations : 0
  Node count         : 0


julia> main("SolutionLimit" => 1);
* Solver : Gurobi

* Status
  Result count       : 1
  Termination status : SOLUTION_LIMIT
  Message from the solver:
  "Optimization terminated because the number of solutions found reached the value specified in the SolutionLimit parameter."

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : NO_SOLUTION
  Objective value    : 0.00000e+00
  Objective bound    : -1.00000e+100
  Relative gap       : 1.00000e+100
  Dual objective value : -1.00000e+100

* Work counters
  Solve time (sec)   : 4.00543e-05
  Barrier iterations : 0
  Node count         : 0


julia> main("SolutionLimit" => 10);
* Solver : Gurobi

* Status
  Result count       : 1
  Termination status : OPTIMAL
  Message from the solver:
  "Model was solved to optimality (subject to tolerances), and an optimal solution is available."

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : NO_SOLUTION
  Objective value    : 0.00000e+00
  Objective bound    : 0.00000e+00
  Relative gap       : 0.00000e+00
  Dual objective value : 0.00000e+00

* Work counters
  Solve time (sec)   : 5.29051e-04
  Barrier iterations : 0
  Node count         : 0

You'd need to follow https://jump.dev/tutorials/2021/11/02/tutorial-multi-jdf/

But this enumerates feasible solutions, not optimal ones:

julia> model = main("PoolSearchMode" => 2, "PoolSolutions" => 100);
* Solver : Gurobi

* Status
  Result count       : 100
  Termination status : OPTIMAL
  Message from the solver:
  "Model was solved to optimality (subject to tolerances), and an optimal solution is available."

* Candidate solution (result #1)
  Primal status      : FEASIBLE_POINT
  Dual status        : NO_SOLUTION
  Objective value    : 0.00000e+00
  Objective bound    : 0.00000e+00
  Relative gap       : 0.00000e+00
  Dual objective value : 0.00000e+00

* Work counters
  Solve time (sec)   : 2.30002e-03
  Barrier iterations : 0
  Node count         : 199


julia> ret = [(value(model[:x]; result = i), value(model[:y]; result = i)) for i in 1:result_count(model)];

julia> sort(ret)
100-element Vector{Tuple{Float64, Float64}}:
 (1.0, 1.0)
 (1.0, 2.0)
 (1.0, 3.0)
 (1.0, 4.0)
 (1.0, 5.0)
 (1.0, 6.0)
 (1.0, 7.0)
 (1.0, 8.0)
 (1.0, 9.0)
 (1.0, 10.0)
 (2.0, 1.0)
 (2.0, 2.0)
 (2.0, 3.0)
 (2.0, 4.0)
 (2.0, 5.0)
 (2.0, 6.0)
 (2.0, 7.0)
 (2.0, 8.0)
 (2.0, 9.0)
 (2.0, 10.0)
 (3.0, 1.0)
 (3.0, 2.0)
 (3.0, 3.0)
 (3.0, 4.0)
 (3.0, 5.0)
 (3.0, 6.0)
 (3.0, 7.0)
 (3.0, 8.0)
 (3.0, 9.0)
 (3.0, 10.0)
 (4.0, 1.0)
 (4.0, 2.0)
 (4.0, 3.0)
 ⋮
 (7.0, 9.0)
 (7.0, 10.0)
 (8.0, 1.0)
 (8.0, 2.0)
 (8.0, 3.0)
 (8.0, 4.0)
 (8.0, 5.0)
 (8.0, 6.0)
 (8.0, 7.0)
 (8.0, 8.0)
 (8.0, 9.0)
 (8.0, 10.0)
 (9.0, 1.0)
 (9.0, 2.0)
 (9.0, 3.0)
 (9.0, 4.0)
 (9.0, 5.0)
 (9.0, 6.0)
 (9.0, 7.0)
 (9.0, 8.0)
 (9.0, 9.0)
 (9.0, 10.0)
 (10.0, 1.0)
 (10.0, 2.0)
 (10.0, 3.0)
 (10.0, 4.0)
 (10.0, 5.0)
 (10.0, 6.0)
 (10.0, 7.0)
 (10.0, 8.0)
 (10.0, 9.0)
 (10.0, 10.0)

[odow]

So maybe this is not useful, because I can see people getting confused with why it doesn't control the number of solutions returned.

[chriscoey]

It seems useful, especially for CSPs. If there is a SOLUTION_LIMIT status it would make sense to have a solution limit option.

[odow]

If there is a SOLUTION_LIMIT status it would make sense to have a solution limit option

I think this is the main argument

[odow]

See #2291