Stuck with infeasibility certificates in JuMP.jl

Specific Domains Optimization (Mathematical)
1

I’m trying to work with infeasibility certificates and different solvers.

MWE using GLPK:

using JuMP
import HiGHS, Gurobi, GLPK

model = JuMP.Model(() -> GLPK.Optimizer(; want_infeasibility_certificates = true))
@variable(model, x; lower_bound=0, upper_bound=10)
@variable(model, θ)
@objective(model, FEASIBILITY_SENSE, x + θ)
optimize!(model)

result_count(model)     # 1
JuMP.value(x)           # 0.0
JuMP.value(θ)           # 0.0

This seems to “work” (but just by using want_infeasibility_certificates, not depending on FEASIBILITY_SENSE, since it works with Min as well). Using HiGHS fails though:

using JuMP
import HiGHS, Gurobi, GLPK

model = JuMP.Model(HiGHS.Optimizer)
@variable(model, x; lower_bound=0, upper_bound=10)
@variable(model, θ)
@objective(model, FEASIBILITY_SENSE, x + θ)
optimize!(model)

result_count(model)     # 0
JuMP.value(x)           # ERROR: ...
JuMP.value(θ)           # ERROR: ...

Notes:

  • print(model) “correctly” shows the objective as Feasibility
  • objective_function(model) still prints x + θ; does that mean that this is still being passed to the solver? I assume yes, since using @objective(model, FEASIBILITY_SENSE, x) influences which feasible solution the solver returns, depending on whether I pass x or -x as "objective. If so, is there an advantage of doing that (instead of passing any constant as objective function), besides that it enables us to later use set_objective_sense(...) to change it (which is nice for not rebuilding the objective function, but then maybe objective_function(…)should check theObjectiveSense`)?
  • Similar to want_infeasibility_certificates = true for GLPK using set_optimizer_attribute(model, "InfUnbdInfo", 1) for Gurobi works, again independent of FEASIBILITY_SENSE.
  • I assume it only fails for HiGHS, since I couldn’t find a solver specific attribute to set there.

Sticking to the documentation, I tried checking the TerminationStatus as well as the PrimalStatus:

GLPK:
Termination status : DUAL_INFEASIBLE | Primal status : NO_SOLUTION
Gurobi:
Termination status : DUAL_INFEASIBLE | Primal status : INFEASIBILITY_CERTIFICATE
HiGHS:
Termination status : DUAL_INFEASIBLE | Primal status : NO_SOLUTION

which indicates probably also that the InfUnbdInfo setting for Gurobi is properly detected, while want_infeasibility_certificates is not (so I can’t distinguish between a successful run and one that failed)?

So, maybe I’m looking for the wrong thing: Is there any solver-independent way to set the “I want infeasibility certificates” attribute (e.g. failing for solvers that do not support that, or just ignoring it and properly indicating that in the PrimalStatus).

2

In general, there is no guarantee that a solver will find an infeasibility certificate for an infeasible or unbounded problem. For example, in some cases that can prove infeasibility during preserve without generating a certificate.

If you have a solver that doesn’t return a certificate, you’ll generally need to change some solver-specific settings, the most common being to disable the solver’s presolve. For HiGHS, try setting "presolve" to "off": List of options · HiGHS Documentation.

Also, I need to double check what’s going on with explicitly providing FEASIBILITY_SENSE and an objective. The definition of FEASIBILITY_SENSE is that the model does not have an objective, so it’s likely that the solver is ignoring the objective. JuMP should probably throw an error here.

1 Like