This is expected behavior; the return status reported by JuMP reflects the result returned by HiGHS. Note that Gurobi would likely give you the same output (see INF_OR_UNBD
in Gurobi’s docs).
- The
INFEASIBLE_OR_UNBOUNDED
status means that a primal unbounded ray has been found, but the solver does not have a primal-feasible solution. This typically happens if such a ray is detected at presolve (note the Presolve: Primal infeasible or unbounded
in the log), and only guarantees that the dual problem is infeasible.
The primal problem may be unbounded, or it may be infeasible (I give two examples below).
- You were not able to query the primal solution nor objective value because HiGHS has not determined whether the (primal) problem was feasible or not; note that the solver’s output reports an infinity gap (primal bound is
inf
and dual bound is -inf
).
To deal with this situation:
- solve solvers allow you to explicitly request that the solver performs additional work and check whether the (primal) problem is infeasible or unbounded. I know that Gurobi lets you do that by either setting
DualReductions
to 0
, or through the InfUnbdInfo
parameter).
I do no know which HiGHS options would be similar
- you can try disabling presolve altogether. This will typically result in a more conclusive result, but you will likely pay a (steep) price in terms of computing times.
Example 1: primal unbounded
This is the example in the OP:
\begin{align}
\min_{y, \eta} \quad & y + \eta\\
s.t. \quad & 0 \leq y \leq 1
\end{align}
The unbounded ray is (y, \eta) = (0, -1) is “unbounded” and a certificate that the dual is infeasible.
The primal solution (y, \eta) = (0, 0) is feasible, hence the primal problem is unbounded.
HiGHS’ presolve stops after finding the ray.
Example 2: primal infeasible
\begin{align}
\min_{x, y} \quad & x\\
s.t. \quad & 1 \leq y \leq 0
\end{align}
the ray (x, y) = (-1, 0) is unbounded and a certicate of dual infeasibility.
The constraint 1 \leq y \leq 0 is trivially infeasible, hence the primal problem is infeasible.
More math
Some definitions to be clear about everything
Consider the LP problem
\begin{align}
\min_{x} \quad & c^{\top} x\\
s.t. \quad & A x = b, \\ & x \geq 0
\end{align}
whose dual is
\begin{align}
\max_{y, z} \quad & b^{\top}y\\
s.t. \quad & A^{\top}y + z = c,\\ & z \geq 0
\end{align}
A primal-unbounded ray is a vector \bar{x} \in \mathbb{R}^{n} such that \bar{x} \geq 0, A\bar{x} = 0, and c^{\top}\bar{x} < 0.
Note that if \hat{x} is feasible \hat{x}, i…e., A \hat{x} = b, \hat{x} \geq 0, then \hat{x} + \lambda \bar{x} is feasible for any \lambda \geq 0, and its cost becomes arbitrarily low (negative) as \lambda \rightarrow +\infty.
The status “Infeasible or unbounded” is returned when a solver has found such a ray \bar{x}, but does not know whether there exists a feasible solution \hat{x}.
Note from the examples above that existence of a primal unbounded ray does not guarantee that there exists a feasible solution.