Strange reporting with respect to feasibility

[chrhansk]

I was solving a problem using JuMP with the Gurobi backend and noticed that the reporting of the termination status is odd. As an example, I get the following output after starting the solution process:

Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (linux64 - "Ubuntu 22.04.3 LTS")                                                                                            
                  Objective                Residual                                                                                                                          
Iter       Primal          Dual         Primal    Dual     Compl     Time                                                                                                    
   0   1.34827307e+08  0.00000000e+00  1.50e-06 1.03e+02  8.35e+03     7s   
...
  51   1.54690402e+06  1.53764581e+06  3.73e+08 4.93e-04  1.12e-01    22s                                                                                                    

Barrier performed 51 iterations in 21.86 seconds (57.71 work units)
Sub-optimal termination - objective 1.54690402e+06

As you can see, the barrier method produces a solution that is completely unusable with a primal residuum of 1e8, so the solution is not feasible. However, @info solution_summary(model) produces the output

┌ Info: * Solver : Gurobi                                                             
│                                              
│ * Status                                  
│   Result count       : 1                                                            
│   Termination status : LOCALLY_SOLVED                             
│   Message from the solver:                
│   "Unable to satisfy optimality tolerances; a sub-optimal solution is available."
│                                           
│ * Candidate solution (result jump-dev/JuMP.jl#1)          
│   Primal status      : FEASIBLE_POINT     
│   Dual status        : NO_SOLUTION        
│   Objective value    : 1.54690e+06        
│                                           
│ * Work counters                                                   
│   Solve time (sec)   : 2.18862e+01        
│   Barrier iterations : 51                 
└   Node count         : 0          

The primal status message indicates that the solution is feasible, which it is not. Sub-optimal solutions may be primally / dually feasible depending on the specific method (for instance with the primal / dual simplex), but the central path followed by the interior point method generally only yields feasible points in the limit (at least as far as I know).

I don't know how the reporting works of feasibility works inside JuMP and which solvers are affected, but it is a bit problematic if a user expects a feasible solution when none exists.

[odow]

Note that Gurobi returned LOCALLY_SOLVED instead of OPTIMAL for the termination status, so we correctly indicate that Gurobi did not find an optimal solution.

If Gurobi is telling is that a suboptimal solution exists, then we set the primal status to FEASIBLE_POINT.

Is the actual solution returned (not just the last iteration of the log) not feasible?

Do you have a reproducible example?

The codes are https://www.gurobi.com/documentation/10.0/refman/optimization_status_codes.html#sec:StatusCodes

[odow]

At the moment we assume that if Gurobi has a solution to return, then it is feasible:

Gurobi.jl/src/MOI_wrapper/MOI_wrapper.jl

Lines 2817 to 2835 in ea2eab0

	function MOI.get(model::Optimizer, attr::MOI.PrimalStatus)
	_throw_if_optimize_in_progress(model, attr)
	term = MOI.get(model, MOI.TerminationStatus())
	if term == MOI.DUAL_INFEASIBLE || term == MOI.INFEASIBLE_OR_UNBOUNDED
	if attr.result_index != 1
	return MOI.NO_SOLUTION
	elseif _has_primal_ray(model)
	return MOI.INFEASIBILITY_CERTIFICATE
	else
	return MOI.NO_SOLUTION
	end
	end
	# Check SolCount explicitly instead of ResultCount to avoid returning 1 when
	# there is a certiticate.
	valueP = Ref{Cint}()
	ret = GRBgetintattr(model, "SolCount", valueP)
	_check_ret(model, ret)
	return 1 <= attr.result_index <= valueP[] ? MOI.FEASIBLE_POINT :
	MOI.NO_SOLUTION

[chrhansk]

Well, I cannot share the problem at the moment unfortunately... Suffice it to say that the saddle point systems solved throughout the iterations are very badly conditioned, hence the numerical problems. But yes, the returned solution is not feasible, with large constraint residuals (> 1e6).

In principle, the solution attributes could be used to answer the questions regarding feasibility / stationarity, notably the "ConstrResidual" and "DualResidual" (in scaled / unscaled form).

Maybe I can try to reproduce a smaller example, but I am rather busy this month, so it may take a while...

[odow]

I wonder if we should just return UNKNOWN_RESULT_STATUS for the non-optimal cases.

Or we could check the MaxVio is less than, say, 1e-6?

cc @simonbowly

[simonbowly]

You could check the violations and residual attributes against the feasibility tolerances, but this one looks more like a numerics issue where barrier just goes a bit haywire. @odow I'm not sure how often a solution from a suboptimal barrier termination is really usable, maybe UNKNOWN_RESULT_STATUS is the better option.

@chrhansk if you are able to share the model at some stage, you can submit it via a support request to Gurobi at https://support.gurobi.com/hc/en-us.