What does PuLP LpStatus=Undefined actually mean?

Question

When I add a particular constraint to my problem, the LpStatus of the problem after solving changes to "Undefined" (without this constraint, it was "Optimal"). At the top of this page, the possibilities of the return status are shown, but it doesn't seem to explain what they mean. Can anyone explain what an "undefined" status means? It it something like a syntax error in specifying the constraint?

Answer 1

There are five status codes that can be returned from a solver in PuLP:

1. Optimal
2. Not Solved
3. Infeasible
4. Unbounded
5. Undefined

OPTIMAL

Optimal solution exists and is found.

Not Solved

Is the default setting before a problem has been solved.

INFEASIBLE

The problem has no feasible solution.

UNBOUNDED

The cost function is unbounded.

UNDEFINED

Feasible solution hasn't been found (but may exist).

They seem to be a mapping of the status codes from GPLK.

Most of the information comes from reading the source and this resource

Answer 2

"Undefined" means PuLP doesn't know how to interpret the solver's output, but it seems to occur when certain mixed integer programs are infeasible.

Whether you get "Undefined" or "Infeasible" depends on which solver PuLP is using, e.g. CBC, GLPK, COIN etc. These solvers have a "presolve" step and then a solve step; if the infeasibility is detected in presolve it will return "Undefined", if it's detected in the solve step it will return "Infeasible".

I have only used the CBC and GLPK solvers, and I've only seen this particular issue with the CBC solver. This thread suggests that the same bug in the GLPK solver was fixed in GLPK version 4.53.

Here's some additional technical info on where "Undefined" comes from:

My hypothesis is that the 'Undefined' status means that CBC terminated in some weird way, leaving PuLP with an intermediate solution to a relaxation sub-problem. (Because 'Undefined' is the default status when PuLP's readsol_MPS method fails to find any of the other PuLP statuses in the CBC solution file. I found that in solver.py of PuLP.)

And here is the source for the presolve issue.

This may happen when infeasibility is detected by the mip preprocessor (not by the mip solver), which erroneously does not change the mip solution status, so it remains undefined.