Capturing best solution from a JuMP model that times out

Specific Domains Optimization (Mathematical)
1

I have a mixed integer problem that I think is sufficiently hard that it won’t complete in sensible time.

I am probably using HiGHS.

I would like to see the best feasible solution that was found.
Actually I might like to see a bunch of solution that were tested, maybe all of them.

One idea is maybe I could use solver independent callbacks to write them to a global variable.

if JuMP is terminated via timeout will the solution object be set to the best it has found?

2

Yes. At least that’s my understanding and what I’ve observed with HiGHS.

EDIT: to be clearer, I analyze my MILP results with code similar to this:

optimize!(model)
if termination_status(model) == TIME_LIMIT
    if primal_status(model) == FEASIBLE_POINT
        @warn "Time limit with feasible solution" code=termination_status(model) status=raw_status(model)
    else
        @error "Time limit without any feasible solution" code=termination_status(model) status=raw_status(model)
        throw(Infeasible())
    end
elseif termination_status(model) != OPTIMAL
    @error "JuMP did not solve to optimality" code=termination_status(model) status=raw_status(model)
    throw(Infeasible())
end
3 Likes
3

@ffevotte is correct here :smile:

if JuMP is terminated via timeout will the solution object be set to the best it has found?

It depends on the solver, and whether the solver found a feasible solution before the time limit.

But yes, you can use primal_status(model) to check if it is a FEASIBLE_POINT, and termination_status(model) to check whether the point is OPTIMAL or suboptimal because of a limit like TIME_LIMIT.

2 Likes
4

What if I want to acquire a list of all feasible solutions considered by the solver?

1 Like
5

Maybe using a callback and storing the solutions in the callback function is the way to go. Don’t know how drastic the performance hit would be.
Link to callback doc: Solver-independent Callbacks · JuMP

6

This depends heavily on the solver.

With Gurobi, you can set some parameters: Finding multiple feasible solutions | JuMP We should probably figure out how to add that to the docs.

With HiGHS, there’s no easy way. It’d need to be something like this, but the callback is still somewhat immature so it is not documented.

using JuMP, HiGHS
model = Model(HiGHS.Optimizer)
N = 100
@variable(model, 0 <= x[1:N] <= 2, Int)
@constraint(model, rand(N)' * x <= 0.1 * N)
@objective(model, Max, rand(N)' * x)
solutions = Vector{Float64}[]
function user_callback(
    callback_type::Cint,
    message::Ptr{Cchar},
    data_out::HiGHS.HighsCallbackDataOut,
)::Cint
    if callback_type == kHighsCallbackMipSolution
        p::Ptr{Cdouble} = Highs_getCallbackDataOutItem(Ref(data_out), "mip_solution")
        push!(solutions, copy(unsafe_wrap(Array, p, N)))
    end
    return 0
end
set_attribute(model, HiGHS.CallbackFunction(), user_callback)
optimize!(model)
unique(solutions)
2 Likes