# On the solution of an unbounded optimization problem

**URL:** <https://discourse.julialang.org/t/on-the-solution-of-an-unbounded-optimization-problem/112373>\
**Category:** Optimization (Mathematical)\
**Tags:** question, jump, optimization, mathematica\
**Created:** [April 1, 2024, 10:24am UTC](https://discourse.julialang.org/t/on-the-solution-of-an-unbounded-optimization-problem/112373 "2024-04-01T10:24:01Z")\
**Posts on this page:** 3\
**Page:** 1

<div class="post-metadata">

**Author:** ![WuSiren](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/wusiren/32/42529_2.png) [@WuSiren](https://discourse.julialang.org/u/WuSiren)\
**Post date:** [April 1, 2024, 10:24am UTC](https://discourse.julialang.org/t/on-the-solution-of-an-unbounded-optimization-problem/112373/1 "2024-04-01T10:24:01Z")

</div>

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

```

The result:

```julia
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?

---

<div class="post-metadata">

**Author:** ![mtanneau](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/mtanneau/32/17787_2.png) [@mtanneau](https://discourse.julialang.org/u/mtanneau)\
**Post date:** [April 1, 2024, 2:11pm UTC](https://discourse.julialang.org/t/on-the-solution-of-an-unbounded-optimization-problem/112373/2 "2024-04-01T14:11:15Z")

</div>

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](https://www.gurobi.com/documentation/current/refman/optimization_status_codes.html)).

- 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](https://www.gurobi.com/documentation/11.0/refman/infunbdinfo.html)).  
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.

---

<div class="post-metadata">

**Author:** ![WuSiren](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/wusiren/32/42529_2.png) [@WuSiren](https://discourse.julialang.org/u/WuSiren)\
**Post date:** [April 2, 2024, 1:38am UTC](https://discourse.julialang.org/t/on-the-solution-of-an-unbounded-optimization-problem/112373/3 "2024-04-02T01:38:19Z")

</div>

Thanks! I see. It’s very clear. 🤝