15

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?

David Doria
  • 9,873
  • 17
  • 85
  • 147
  • how do I fix PuLP infeasible solution? https://datascience.stackexchange.com/questions/49707/how-do-i-fix-pulp-infeasible-solution – KHAN irfan Apr 22 '19 at 06:45

2 Answers2

16

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

Community
  • 1
  • 1
Noelkd
  • 7,686
  • 2
  • 29
  • 43
  • 5
    So what can you do if UNDEFINED is returned to make it try harder? – David Doria Jul 23 '14 at 22:42
  • What can I do in case of infeasible solution? – KHAN irfan Apr 22 '19 at 06:32
  • `OPTIMAL : Optimal solution exists and is found` is actually false for MIP, since the `LpStatusOptimal` problem status is also returned when a feasible (but non-optimal) solution is found. One should rather use the solution status `LpSolution[prob.sol_status]`, since `LpSolutionIntegerFeasible` is returned in such cases. See https://github.com/coin-or/pulp/discussions/382 for a thread on the subject, and https://github.com/coin-or/pulp/blob/master/pulp/constants.py for the list of solution statuses. (Note : the official documentation is not up to date with the solution statuses names). – RandomGuy Dec 14 '22 at 13:48
3

"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.

thomaskeefe
  • 1,900
  • 18
  • 19