pulp reports Infeasible for Unbounded HiGHS MIPs

[robertHowlett]

Details for the issue

Pulp incorrectly reports infeasible for Primal infeasible/Unbounded MIPs solved with HiGHs. Unbounded LPs work fine.

What did you do?

I ran the script:

import pulp

# Problem formulation
m = pulp.LpProblem("myProblem", pulp.LpMinimize)
var_cont = pulp.LpVariable("var_cont", lowBound=None, upBound=None, cat=pulp.LpContinuous)
var_int = pulp.LpVariable("var_int", lowBound=0, upBound=1, cat=pulp.LpInteger)
m += var_cont + var_int

m.solve(
    pulp.HiGHS(
        timeLimit=30,
        gapRel=0.01,
        threads=1,
        msg=True,
        log_to_console=True,
    )
)

print("Status:", pulp.LpStatus[m.status])
assert m.status == pulp.LpStatusUnbounded

What did you expect to see?

<some solver logs>
Status: Unbounded

What did you see instead?

Running HiGHS 1.12.0 (git hash: 755a8e0): Copyright (c) 2025 HiGHS under MIT licence terms
MIP has 0 rows; 2 cols; 0 nonzeros; 1 integer variables (1 binary)
Presolving model
Presolve: Primal infeasible or unbounded

Src: B => Branching; C => Central rounding; F => Feasibility pump; H => Heuristic;
     I => Shifting; J => Feasibility jump; L => Sub-MIP; P => Empty MIP; R => Randomized rounding;
     S => Solve LP; T => Evaluate node; U => Unbounded; X => User solution; Y => HiGHS solution;
     Z => ZI Round; l => Trivial lower; p => Trivial point; u => Trivial upper; z => Trivial zero

        Nodes      |    B&B Tree     |            Objective Bounds              |  Dynamic Constraints |       Work
Src  Proc. InQueue |  Leaves   Expl. | BestBound       BestSol              Gap |   Cuts   InLp Confl. | LpIters     Time

         0       0         0   0.00%   -inf            inf                  inf        0      0      0         0     0.0s

Solving report
  Status            Primal infeasible or unbounded
  Primal bound      inf
  Dual bound        -inf
  Gap               inf
  P-D integral      0
  Solution status   -
  Timing            0.00
  Max sub-MIP depth 0
  Nodes             0
  Repair LPs        0
  LP iterations     0
Status: Infeasible
Traceback (most recent call last):
  File "C:\Temp\bad_reported_value.py", line 20, in <module>
    assert m.status == pulp.LpStatusUnbounded
           ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
AssertionError

Useful extra information

The info below often helps, please fill it out if you're able to. :)

What operating system are you using?

• Windows: ( version: 11)
• Linux: ( distro: ___ )
• Mac OS: ( version: ___ )
• Other: ___

I'm using python version:

• 3.7
• 3.8
• 3.9
• 3.10
• 3.11
• Other: 3.12.3

I installed PuLP via:

• pypi (python -m pip install pulp)
• github (python -m pip install -U git+https://github.com/coin-or/pulp)
• Other: ___ (conda?)

Relevant package versions

PuLP==3.3.0
highspy==1.12.0

Did you also

• Tried out the latest github version: https://github.com/coin-or/pulp
• Searched for an existing similar issue: https://github.com/coin-or/pulp/issues?utf8=%E2%9C%93&q=is%3Aissue%20

[robertHowlett]

This is maybe a highspy limitation, they're reporting HighsModelStatus.kUnboundedOrInfeasible which is being converted to Infeasible by pulp.

[odow]

The issue is in PuLP. This part isn't correct:

pulp/pulp/apis/highs_api.py

Lines 458 to 461 in a7c761a

	HighsModelStatus.kUnboundedOrInfeasible: (
	constants.LpStatusInfeasible,
	constants.LpSolutionInfeasible,
	),

[SteefCoder]

What should be the expected behaviour for PuLP here?
In this instance the model is unbounded but PuLP doesn't know that. From just the HighsModelStatus.kUnboundedOrInfeasible status code there is no way to tell if the problem is unbounded or infeasible. It seems like the only options are to just return one of the two (and be wrong half of the time) or to create a constants.LpStatusUnboundedOrInfeasible status code.
Looks like this problem is not specifically with HiGHS, but with any solver returning an UnboundedOrInfeasible status code.

[odow]

What should be the expected behaviour for PuLP here?

PuLP should have a way to communicate a termination status of "unbounded or infeasible".

See all of the status codes that JuMP uses: https://jump.dev/JuMP.jl/stable/api/JuMP/#TerminationStatusCode

[odow]

Looking here:

pulp/pulp/constants.py

Lines 45 to 78 in a7c761a

	# problem status
	LpStatusNotSolved = 0
	LpStatusOptimal = 1
	LpStatusInfeasible = -1
	LpStatusUnbounded = -2
	LpStatusUndefined = -3
	LpStatus = {
	LpStatusNotSolved: "Not Solved",
	LpStatusOptimal: "Optimal",
	LpStatusInfeasible: "Infeasible",
	LpStatusUnbounded: "Unbounded",
	LpStatusUndefined: "Undefined",
	}
	# solution status
	LpSolutionNoSolutionFound = 0
	LpSolutionOptimal = 1
	LpSolutionIntegerFeasible = 2
	LpSolutionInfeasible = -1
	LpSolutionUnbounded = -2
	LpSolution = {
	LpSolutionNoSolutionFound: "No Solution Found",
	LpSolutionOptimal: "Optimal Solution Found",
	LpSolutionIntegerFeasible: "Solution Found",
	LpSolutionInfeasible: "No Solution Exists",
	LpSolutionUnbounded: "Solution is Unbounded",
	}
	LpStatusToSolution = {
	LpStatusNotSolved: LpSolutionInfeasible,
	LpStatusOptimal: LpSolutionOptimal,
	LpStatusInfeasible: LpSolutionInfeasible,
	LpStatusUnbounded: LpSolutionUnbounded,
	LpStatusUndefined: LpSolutionInfeasible,
	}

It should probably return LpStatusUndefined and LpSolutionNoSolutionFound.

[SteefCoder]

Probably. In the other solvers it's handled quite inconsistently.

unbounded or infeasible becomes LpStatusUndefined:

• cuOpt

unbounded or infeasible becomes LpStatusUnbounded:

• SAS

unbounded or infeasible becomes LpStatusInfeasible:

• COPT
• CPLEX
• Gurobi
• HiGHS

unbounded or infeasible becomes LpStatusNotSolved:

• SCIP

I also found this comment:

pulp/pulp/apis/cuopt_api.py

Lines 116 to 120 in 8e414c2

	# cuOpt returns UnboundedOrInfeasible when the presolver
	# detects one of the two but cannot disambiguate. PuLP has
	# no combined status, so map to Undefined (matches how
	# GLPK_CMD reports the same situation).
	11: LpStatusUndefined, # Unbounded or Infeasible

I think the best thing to do is change it all to LpStatusUndefined.