On the solution of an unbounded optimization problem

using JuMP, HiGHS
M =  Model(HiGHS.Optimizer)
@variable(M, y, Bin)
@variable(M, η)
@objective(M, Min, y + η)
optimize!(M)

The result:

Running HiGHS 1.7.0 (git hash: 50670fd4c): Copyright (c) 2024 HiGHS under MIT licence terms
Coefficient ranges:
  Cost   [1e+00, 1e+00]
  Bound  [1e+00, 1e+00]
Presolving model
Presolve: Primal infeasible or unbounded

Solving report
  Status            Primal infeasible or unbounded
  Primal bound      inf
  Dual bound        -inf
  Gap               inf
  Solution status   -
  Timing            0.00 (total)
                    0.00 (presolve)
                    0.00 (postsolve)
  Nodes             0
  LP iterations     0 (total)
                    0 (strong br.)
                    0 (separation)
                    0 (heuristics)

This is obviously an unbounded problem. Based on mathematical knowledge, its optimal value should be -Inf and the corresponding value of η should also be -Inf, and the value of y should be some feasible value. I expect the solving report to tell me its status is Unbounded but it reports Primal infeasible or unbounded, a very uncertain conclusion. And when I try to check the optimal value of the variables and the objective with value(y), value(η) and objective_value(M), I failed.

My question is why JuMP gives non-conventional results?

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 :slight_smile:

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.

4 Likes

Thanks! I see. It’s very clear. :handshake:

1 Like