[RFC] New Status Mechanism

[blegat]

It seems that MPB statuses needs to be reworked. See e.g.:

• MISOCP solves returning status "Unknown" (different from #100) MOSEK/Mosek.jl#101
• save optimization data for stat !=: Optimal nlp problems  jump-dev/JuMP.jl#938
• getsolution() returns infeasible solution for an unbounded problem jump-dev/Gurobi.jl#80
• Test that getsolution is feasible when problem is Unbounded #144

Following @erling-d-andersen's comment, it would help to separate the statuses in

• Feasibility/Optimality of getsolution
• Feasibility/Optimality of getdual
• Feasibility/Boundedness of the primal
• Feasibility/Boundedness of the dual
• Optimizer status : why he has stopped

I do not claim to have a perfect solution for a new status mechanism, I am just hoping to open the discussion with a reasonable start.

Optimizer status

Afther calling optimize!, status would return:

Name	Reason of stopping
Success	Found something to share (e.g. infeasibility ray)
NumericalError	Encountered numerical difficulties
Stall	Stopped because no more progress could be made but the time limit/iteration limit was not reached
UserLimit	Stopped because of time limit/iteration limit was reached
Out Of Memory	More space needs to be allocated than what is available
Error	Other reason than listed above

Questions:

• Should the status be a symbol of a subtype of abstract AbstractOptimizerStatus ? If it is a subtype then UserLimit could contain a string message giving more precision that would be printed if we call show on it or UserLimit could be an abstract type that is subtyped by each solver. What would you prefer ?

Problem Status

We could split the primal (resp. dual) status in 2:

	Yes	No	Unknown
Feasible
Bounded

In view of this, we could define:

• isprimalfeasible(m):
  • true if it is sure that the primal is feasible,
  • false if it is sure it is infeasible,
  • throws an error otherwise,
• knowsprimalfeasibility(m):
  • true: isprimalfeasible would return
  • false: isprimalfeasible would throw an error

and likewise isprimalbounded, knowsprimalboundedness, isdualfeasible; knowsdualfeasible, isdualbounded, knowsdualboundedness.
These functions would only reflect the knowledge acquired by the last optimize! called !

Questions:

• What if someone wants to save the problem status to be used later ? We could add a function problemstatus which would return a object of type ProblemStatus which can answer to the same 8 function is.../knows....
• Does Unbounded also means Feasible or simply that an unbounded ray has been found (See Test that getsolution is feasible when problem is Unbounded #144 ) ?
• Does Bounded also means Feasible ? I would say no to that. Typically it means that the dual is feasible. By the way the boundedness of the primal might seem redundant with the feasibility of the dual. However, it might happen that the primal is bounded and the dual is infeasible in case of (infinite) strong duality failure (I do not have any example to give but I don't see what prevents it to happen).

Solution Status

• primalsolutionavailable(m) the solver allows to retrieve values for primal variables, i.e. getsolution would not throw an error.
• dualsolutionavailable the solver allows to retrieve values for variable and constraint dual variables, i.e. getdual, ... would not throw an error.

issolutionfeasible(m) (resp. issolutionoptimal(m)) would true if we are sure that the solution that would be returned by getsolution(m) is feasible (resp. optimal), otherwise, it returns false.
false would not mean that we are sure that it is not feasible (resp. not optimal), it would just mean that we do not know whether it is optimal/feasible.

Questions:

• What if we want to store the solution status to query it later ? We could define solutionstatus(m) that would return SolutionStatus which could reply to issolutionfeasible and issolutionoptimal.

[ccoffrin]

I am also a fan of revising how solver statuses are treated in MPB. Having a separate status field for the solver algorithm vs the mathematical problem makes sense to me.

Regarding this proposal, would Success mean the algorithm terminated as expected? This would be synonyms with properties like: converged (in the cases like LP and IPM), search completed in MIP, and proofs of infeasibility in LP/Convex/MIP?

How would we distinguish between converging to a point of local infeasibly (e.g. in IPM solvers) and providing a proof of global infeasibly (e.g. in LP / convex / IP solvers)?

A common status I see in solvers is some kind of numerical difficulties, maybe adding an explicit name for this (e.g. NumericalError) would be helpful.

It is worth noting that the cases of Success, Stall, UserLimit, NumericalError all refer to properties of the algorithm/software, while Out Of Space has a hardware aspect. Is it worth have a separate class for hardware issues?

Being a nitpick, I would recommend Out Of Space be called Out Of Memory (OOM), this name is widely recognized in other CS disciplines.

[mlubin]

I'll just comment on a small part of this for the moment. One thing that would be very useful to have is a way to ask the solver if the primal and dual solutions should be returned to the user (and if so, what they mean). In jump-dev/JuMP.jl#938 for example the issue is that Ipopt determines the problem is infeasible but it's still desired to return something as a primal solution. In JuMP, I'd like to be able to do something like

if primalsolutionavailable(m)
    # Load primal solution into JuMP variables
end
if dualsolutionavailable(m)
    # Load dual solution into JuMP variables (and constraints)
end

[blegat]

@ccoffrin I have added your suggestion of statuses. What would you mean by local infeasibility ?
@mlubin I have added it

[ccoffrin]

@blegat regarding local infeasibility.

Many nonlinear solvers are based around the KKT conditions, which are local optimality conditions. In the case of non-convex problems, it is possible that the KKT conditions are satisfied at a point that is infeasible, and because these conditions are local, this does not provide a proof of infeasibility for the whole problem. In contrast to MIP/Convex solvers, which can produce a proof of problem infeasibility.

[blegat]

@ccoffrin That is a good question. I would suggest that Success means, "I have found something and since I am lazy I am stopping now, waiting for a new request". This means that it should be possible to see what was discovered, e.g. dual unboundedness, and react about it. In your case, no knowledge can be obtained according to the current information getters (knowsprimalfeasibility, issolutionfeasible, ...). The only thing that could be given is a primal solution with no guarantee on it (since it is in not feasible). On the other hand, we could add a way to get the information that what is returned by getsolution satisfies the KKT solutions but is infeasible. In that case, the solver has some information to share and the user can react about it, e.g. restart the optimization with a initial iterate far from this point.

[ccoffrin]

This sounds responsible to me.

In my mind, Success means, the solver's algorithm has reached its "completion criteria". Where, the criteria of completion are defined on an algorithm specific basis (e.g. MIP, the search tree is complete, in IPM a KKT point is reached). It is up to the user to understand enough about the algorithm's properties to know what the formal guarantees of Success are.

[mlubin]

I'd also like to expand on UserLimit. It's a bit too generic, and it would be nicer to know if a time limit or iteration limit was reached, for example.

How does Stall differ from NumericalError?

[ccoffrin]

Re Stall vs NumericalError, it is not clear to me why there is a distinction here, but I have noticed this behavior in Gurobi's QCQP solver. Some times it gives a clear status of NumericalError other times it converges to what it calls a SubOptimal solution. This SubOptimal termination seems to be consistent with the Stall ideal discussed in MOSEK/Mosek.jl#101.

@erling-d-andersen, can you comment on why solvers should have Stall and NumericalError status instead of just NumericalError?

[IssamT]

Another old related issue:
jump-dev/CPLEX.jl#77

[erling-d-andersen]

To me NumericalError means a numerical problem occurred. Stall means it started iterating and for some reason could not make progress in some iteration. You can lump the two into in one if you like. 2017-02-14 21:02 GMT+01:00 Carleton Coffrin <notifications@github.com>:

…

Re Stall vs NumericalError, it is not clear to me why there is a distinction here, but I have noticed this behavior in Gurobi's QCQP solver. Some times it gives a clear status of NumericalError other times it converges to what it calls a SubOptimal solution. This SubOptimal termination seems to be consistent with the Stall ideal discussed in MOSEK/Mosek.jl#101 <MOSEK/Mosek.jl#101>. @erling-d-andersen <https://github.com/erling-d-andersen>, can you comment on why solvers should have Stall and NumericalError status instead of just NumericalError? — You are receiving this because you were mentioned. Reply to this email directly, view it on GitHub <#156 (comment)>, or mute the thread <https://github.com/notifications/unsubscribe-auth/AJwCcQTKuZFPVSkg27ja7D5ojyaYOhvhks5rcghigaJpZM4L9loR> .

[mlubin]

It makes sense to keep NumericalError and Stall (suboptimal) separate since it seems like this is a distinction made by multiple solvers.

[mlubin]

Closing in favor of #164