# Approaching a Linear Program Correctly

**URL:** <https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354>\
**Category:** Optimization (Mathematical)\
**Tags:** jump, tutorials, duality, linear-programming\
**Created:** [March 25, 2025, 3:33pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354 "2025-03-25T15:33:52Z")\
**Posts on this page:** 16\
**Page:** 1

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 25, 2025, 3:33pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/1 "2025-03-25T15:33:52Z")

</div>

Let’s see the Proposition 5.2.1 of the 2009 Bertsekas’s _convex optimization theory_:

> (Linear Programming Duality Theorem)  
> (a) If **any one** of the 2 programs (primal and dual) has a **finite** optimal objective value, then the 2 programs’ optimal objective value coincide, moreover, attainment is ensured on both sides.

Actually, this theorem only concerns **1.** the normal case (i.e. (a)), and **2.** from unboundedness to infeasibility (i.e. (b) and (c), which I didn’t list here for conciseness).

Given this, in this post I’m addressing the missing **abnormal** circumstances (with step 1 and step 2 below).

Before starting, I mention this formula (★), which was proved in [this](https://discourse.julialang.org/t/a-naive-explanation-of-infeasibility-and-unboundedness/127343) post.  
 \sup \{y | y \ge 0\} = \inf \{ 0 | 0 \le x \le -1\} = + \infty

Let’s start here:  
Suppose now we are dealing with an LP (■), with decision z, as follows  
\sup \{ c^\top z | a^\top z \le b \}

The **1st** step is:  
Focus only on its feasibility system, namely \{z | a^\top z \le b\}. We ask “is it feasible”?  
Well, if it is infeasible, then a^\top z \le b can be transformed (with variable substitution / elimination) to 0 \le x \le -1. The converse is also true.  
If we have proved it is _infeasible_, then we **quit** this topic (no further steps needed). If we succeed in finding a feasible solution, then we continue with step 2.

The **2nd** step is:  
We ask “is it bounded”? Well, if (■) is unbounded, it should be equivalent to the leftmost “sup”-program in (★), whose dual feasibility system is infeasible (like 0 \le x \le -1). (Yes, this is where the name `DUAL_INFEASIBLE` is from). Note that we’ve done step 1 and in step 2 now, therefore `DUAL_INFEASIBLE` here _really_ **implies** `unbounded`. (cf. Gurobi’s Optimization Status Codes, No. 5, which will politely suggests you to **redo step 1** to avoid misinforming). If `DUAL_INFEASIBLE` is true, we **quit** this topic. If we succeed in finding a dual feasible solution, this indicates that (■) has a finite `best dual bound`, indicating that the (a) of [Bertsekas2009] above can be invoked. Then we continue with step 3.

The **3rd** step:  
Normality is ensured here, suggested by (a) of [Bertsekas2009] above.

---

<div class="post-metadata">

**Author:** ![zdenek\_hurak](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/zdenek_hurak/32/53118_2.png) [@zdenek\_hurak](https://discourse.julialang.org/u/zdenek_hurak)\
**Post date:** [March 25, 2025, 4:06pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/2 "2025-03-25T16:06:31Z")

</div>

How can we, users of Julia, help?

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [March 25, 2025, 6:56pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/3 "2025-03-25T18:56:42Z")

</div>

Hi @WalterMadelim, again it’s great to have people so actively posting in the forum 😄

But I might ask that we convert your effort on tutorial-type math focused posts like this one and [A naive explanation of infeasibility and unboundedness](https://discourse.julialang.org/t/a-naive-explanation-of-infeasibility-and-unboundedness/127343) into improvements to the JuMP documentation?

Let’s try to keep the posts on the Julia forum focused on code problems with Julia and JuMP. For example, the bugs you’re finding in Gurobi.jl are excellent and very helpful!

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 25, 2025, 8:22pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/4 "2025-03-25T20:22:14Z")

</div>

If it contains a question, typically a “question” tag will be visible.  
Otherwise typically it is about sharing experience to facilitate developing / referencing / etc., like [this](https://discourse.julialang.org/t/gurobis-tolerance-on-convexity-in-qcp-is-about-1e-13/127297).

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 25, 2025, 8:37pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/5 "2025-03-25T20:37:24Z")

</div>

```julia
help?> JuMP.DUAL_INFEASIBLE
  DUAL_INFEASIBLE::TerminationStatusCode

  An instance of the TerminationStatusCode enum.

  DUAL_INFEASIBLE: The algorithm concluded that no dual bound exists for the problem. If,
  additionally, a feasible (primal) solution is known to exist, this status typically implies that   
  the problem is unbounded, with some technical exceptions.

```

I wonder what is meant by saying “typically”, “some technical exceptions”?  
I thought it should be deterministic, i.e.,  
[primal `feasible` + `DUAL_INFEASIBLE`] _directly implies_ [primal `unbounded`].

---

<div class="post-metadata">

**Author:** ![gdalle](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/gdalle/32/27854_2.png) [@gdalle](https://discourse.julialang.org/u/gdalle)\
**Post date:** [March 25, 2025, 9:03pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/6 "2025-03-25T21:03:32Z")

</div>

> [@WalterMadelim](#):
>
> Otherwise typically it is about sharing experience to facilitate developing / referencing / etc., like [this](https://discourse.julialang.org/t/gurobis-tolerance-on-convexity-in-qcp-is-about-1e-13/127297).

That is precisely why Oscar was suggesting contributions to the JuMP.jl documentation instead. While this forum is great for questions and interactive exchanges, the formal documentation is better suited for “documenting / referencing / etc.”

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 25, 2025, 9:12pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/7 "2025-03-25T21:12:46Z")

</div>

> [@gdalle](#):
>
> contributions to the [JuMP.jl](https://juliaregistries.github.io/General/packages/redirect_to_repo/JuMP) documentation

Okay, I’ll consider that when I’m confident.

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 25, 2025, 9:46pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/8 "2025-03-25T21:46:09Z")

</div>

Oh, I seems to know why.

I here furnish an example (i.e., the data `A, b, c`), which renders the feasibility system on both the primal and dual side `INFEASIBLE`. (I have verified it using `Gurobi` and `Mosek`). The primal and dual LP formulation follows (2.12) and (2.13) in [this](https://docs.mosek.com/modeling-cookbook/linear.html#the-dual-problem) page.

```julia
(A, b, c) = ([-15 10 0 11; -19 0 19 -17; 9 -16 15 -18], [-19, -13, 19], [-19, 0, 15, -12])

```

This is a perfect complement to the Theorem of [Bertsekas2009].  
I’m happy on contributing this 🙂.

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 25, 2025, 11:04pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/9 "2025-03-25T23:04:41Z")

</div>

The above 3-by-4 example was generated by Julia’s `rand()`.  
Here is an easier 2-by-3 example invented by my hand.  
The runnable code is provided here

```julia
import JuMP, MosekTools, Ipopt
import Gurobi; const GRB_ENV = Gurobi.Env();
function optimise(m) return (JuMP.optimize!(m); (JuMP.termination_status(m), JuMP.primal_status(m))) end
function Model(solver, mode)
    solver == "Ipopt" && (m = JuMP.Model(Ipopt.Optimizer))
    solver == "Mosek" && (m = JuMP.Model(() -> MosekTools.Optimizer()))
    solver == "Gurobi" && (m = JuMP.Model(() -> Gurobi.Optimizer(GRB_ENV)))
    occursin("m", mode) && JuMP.set_objective_sense(m, JuMP.MIN_SENSE)
    occursin("M", mode) && JuMP.set_objective_sense(m, JuMP.MAX_SENSE)
    occursin("s", mode) && JuMP.set_silent(m)
    m
end

A, b, c = [1 -1 0; 0 0 1], [0, -1], [0, -1, 1]

model = Model("Mosek", "s")
JuMP.@variable(model, x[eachindex(c)] >= 0)
JuMP.@constraint(model, A * x .== b)
t_primal = optimise(model)[1]

model = Model("Mosek", "s")
JuMP.@variable(model, y[eachindex(b)])
JuMP.@constraint(model, c .>= transpose(A) * y)
t_dual = optimise(model)[1]
println(t_primal, ", ", t_dual) # ✅ INFEASIBLE, INFEASIBLE

```

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [March 25, 2025, 11:15pm UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/10 "2025-03-25T23:15:05Z")

</div>

We have had a number of discussions over the years about the extent to which we want to make the JuMP documentation about JuMP, or whether we want to extend it to be more of a textbook for optimization more generally (e.g., [Suggestions for documentation improvements · Issue #2348 · jump-dev/JuMP.jl · GitHub](https://github.com/jump-dev/JuMP.jl/issues/2348#issuecomment-1378066529)).

We’ve tended to stick fairly close to JuMP. So we’d regard the knowledge that an LP can be both primal and dual infeasible as theory knowledge that is more appropriate somewhere else. It’s up for debate though. This information could be useful in the JuMP documentation.

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 26, 2025, 12:27am UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/11 "2025-03-26T00:27:51Z")

</div>

If one inspects the No.5 termination\_status\_code `UNBOUNDED` of Gurobi’s [doc](https://docs.gurobi.com/projects/optimizer/en/current/reference/numericcodes/statuscodes.html#optimization-status-codes).

> Model was proven to be unbounded. Important note: an unbounded status indicates the presence of an unbounded ray that allows the objective to improve without limit. It says nothing about whether the model has a feasible solution. If you require information on feasibility, you should set the objective to zero and reoptimize.

He might feel a bit weird. Since:  
From a rigorous point of view, if we are handling a `model`.  
The **first and foremost** thing we should make sure is “is it feasible?”  
The _secondary_ thing is then asking “is it unbounded?”  
Therefore, strictly speaking, claiming **[**`model` is “unbounded”**]** before assuring **[** `model` has a feasible solution **]** is meaningless.  
Therefore, the “unbounded ray” which Gurobi claims to exists is also rendered meaningless. (Indeed, only the ray who starts at a feasible point and extends to infinity without hitting the infeasible region is meaningful and desirable in practice).

By comparison, JuMP’s explanation for `DUAL_INFEASIBLE` is less disquieting:  
Its second statement is flawless: `If, additionally, a feasible (primal) solution is known to exist, this status typically implies that the problem is unbounded, with some technical exceptions.` where the `exceptions` can be exemplified by my 2-by-3 case above.

But I can’t fully agree its first statement `The algorithm concluded that no dual bound exists for the problem.` , which I think should be substituted by `The dual program is proved to be infeasible`. (just as its name verbatim, my humble personal opinion, I don’t know how solvers perform behind the scenes).

Things only become unambiguous when `model` is an LP, within which:

1. `DUAL_INFEASIBLE` + `PRIMAL_FEASIBLE` **implies** `PRIMAL_UNBOUNDED`
2. The situation `DUAL_INFEASIBLE` + `PRIMAL_INFEASIBLE` does **exist**

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [March 26, 2025, 1:29am UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/12 "2025-03-26T01:29:47Z")

</div>

The case that solvers report some equivalent to `unbounded` when they really mean “I found an unbounded ray but not necessarily a feasible point” is precisely why JuMP has the status `DUAL_INFEASIBLE` instead of `UNBOUNDED`.

The doc strings are here: [MathOptInterface.jl/src/attributes.jl at 8f2f2539e00fd5039f1eccc015b48c69cc925613 · jump-dev/MathOptInterface.jl · GitHub](https://github.com/jump-dev/MathOptInterface.jl/blob/8f2f2539e00fd5039f1eccc015b48c69cc925613/src/attributes.jl#L2089-L2152)

~~Feel free to open a PR with suggested improvements.~~ I’ve opened on here: [[docs] improve the docstrings of the various enum values by odow · Pull Request #2698 · jump-dev/MathOptInterface.jl · GitHub](https://github.com/jump-dev/MathOptInterface.jl/pull/2698)

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 26, 2025, 4:10am UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/13 "2025-03-26T04:10:08Z")

</div>

> [@odow](#):
>
> JuMP has the status `DUAL_INFEASIBLE` instead of `UNBOUNDED`

Yes, `DUAL_INFEASIBLE` alone does not implies `PRIMAL_UNBOUNDED`, even in the simplest LP setting.  
It appears I’m clearer now. I’ll later update

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 26, 2025, 10:59am UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/14 "2025-03-26T10:59:28Z")

</div>

In this post I expound the essential implication of the termination status `DUAL_INFEASIBLE`.

We need this **L** inear **F** arkas’ **L** emma (Proposition 5.1.2, [Bertsekas 2009])

> ( **LFL** ) The following 2 condition are **equivalent**
> 
> 1. +\infty = \sup\_y \{ b^\top y | A^\top y \le 0 \} 
> 2. \{ x | x \ge 0, A x= b \} = \emptyset

Now suppose our **primal problem** is  
\sup\_y \{ b^\top y | A^\top y \le c \}   
We routinely write its **dual problem** as (in accordance with [this](https://docs.mosek.com/modeling-cookbook/linear.html#the-dual-problem))  
\inf\_x \{ c^\top x | x \ge 0, A x= b \}

In view of ( **LFL** ), we conclude that `DUAL_INFEASIBLE` is essentially saying that

- (♠) the **modified primal problem** \sup\_y \{ b^\top y | A^\top y \le 0 \} is `UNBOUNDED`.

We can see that the **modified primal problem** admits of a trivial solution y = 0.  
But we can **not** claim that the **primal problem** is feasible, unless we set its objective b^\top y to 0 and then hand it to a solver.

If a feasible solution of the **primal problem** is already assured, then at this stage can we immediately conclude that `PRIMAL_UNBOUNDED` (due to (♠)).

---

<div class="post-metadata">

**Author:** ![WalterMadelim](https://avatars.discourse-cdn.com/v4/letter/w/3e96dc/32.png) [@WalterMadelim](https://discourse.julialang.org/u/WalterMadelim)\
**Post date:** [March 27, 2025, 12:23am UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/15 "2025-03-27T00:23:56Z")

</div>

```julia
The algorithm concluded that no dual bound exists for the problem.
 
If the problem is a conic optimization problem (thus also a linear program), this status means the dual
problem is infeasible.

If a primal feasible solution exists, this status typically implies that the
problem is unbounded, with some technical exceptions (for example, if the
problem is a conic optimization problem in which strong duality does not
hold).

To check if the primal is unbounded, set the objective sense to
[`FEASIBILITY_SENSE`](@ref) and re-solve the problem. If a primal feasible
point exists, the original problem is unbounded. If a primal feasible point
does not exist, the original problem is both primal and dual infeasible.

```

Is this the revised docstring? It’s probably not correct either, is it?

The last (4th) segment, shouldn’t it be “To check if the primal is **feasible** , set …”.  
`If a primal feasible point exists, the original problem is unbounded.` this sentence is also not correct (It is correct **only if** the primal is an **LP** ).  
These can be verified just based on the 2-by-2 SDP example you have listed in the Github.

Additionally, I think in the current status, the info is a bit dense. The 2nd and 3rd segment is not problematic, though. But I think the 1st statement can be removed now. I think the 1st statement is a bit aggressive, whose essential meaning can be embodied in my revised one below.  
`A nontrivial bound on the optimal objective value cannot be obtained through further exploring the dual problem.`  
in which `trivial bound` means: `-Inf` for a `inf-program`, `+Inf` for a `sup-program`

---

<div class="post-metadata">

**Author:** ![odow](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/odow/32/28685_2.png) [@odow](https://discourse.julialang.org/u/odow)\
**Post date:** [March 27, 2025, 12:37am UTC](https://discourse.julialang.org/t/approaching-a-linear-program-correctly/127354/16 "2025-03-27T00:37:32Z")

</div>

How about: [[docs] improve the docstring for DUAL\_INFEASIBLE by odow · Pull Request #2701 · jump-dev/MathOptInterface.jl · GitHub](https://github.com/jump-dev/MathOptInterface.jl/pull/2701)?

(Let’s keep future comments to the GitHub PR.)