# A note on how to identify redundant constraints using JuMP

**URL:** <https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504>\
**Category:** Optimization (Mathematical)\
**Tags:** jump, lp\
**Created:** [March 30, 2025, 10:37am UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504 "2025-03-30T10:37:39Z")\
**Posts on this page:** 9\
**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 30, 2025, 10:37am UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/1 "2025-03-30T10:37:39Z")

</div>

(In this topic, whenever I write `==`, this really means the Julia’s `==`)  
I use this primal LP model to demonstrate  
**CodeBlock1** :

```julia
import JuMP, Gurobi; GRB_ENV = Gurobi.Env()
primal = JuMP.Model(() -> Gurobi.Optimizer(GRB_ENV))
JuMP.@variable(primal, x)
JuMP.@variable(primal, y)
JuMP.@objective(primal, Min, 2 * y + 0.7 * x)
JuMP.@constraint(primal, c1, 3 * y >= x)
JuMP.@constraint(primal, c2, x >= 0)
JuMP.@constraint(primal, c3, y >= 0)
JuMP.optimize!(primal); JuMP.assert_is_solved_and_feasible(primal; dual = true, allow_local = false)
primal_objval = JuMP.objective_value(primal) # 0.0
c = JuMP.dual.([c1, c2, c3]) # c = [0.6667, 1.3667, 0.0]

```

First we note that `c[3] == 0`, indicating that `c3` is redundant.  
We can do a test to verify

```julia
# reload CodeBlock1
JuMP.delete(primal, c3); JuMP.unregister(primal, :c3)
JuMP.optimize!(primal); JuMP.assert_is_solved_and_feasible(primal; dual = true, allow_local = false)
relaxed_objval = JuMP.objective_value(primal)
relaxed_objval >= primal_objval && print("c3 is indeed redundant")

```

Okay, let’s return to the initial state.  
Note that although `c[1] != 0`, we **cannot** conclude that `c[1]` is **not** a redundant constraint.  
Because, from a primal-side view, we have

```julia
# reload CodeBlock1
JuMP.delete(primal, c1); JuMP.unregister(primal, :c1)
JuMP.optimize!(primal); JuMP.assert_is_solved_and_feasible(primal; dual = true, allow_local = false)
relaxed_objval = JuMP.objective_value(primal)
relaxed_objval >= primal_objval && print("c1 is indeed redundant")

```

Alternatively, from the dual-side view, with an epsilon-relaxation trick we have

```julia
# reload CodeBlock1
JuMP.delete(primal, c1); JuMP.unregister(primal, :c1)
ϵ = 1e-5; JuMP.@constraint(primal, c1, 3 * y + ϵ >= x) # readd an ϵ-relaxed counterpart
JuMP.optimize!(primal); JuMP.assert_is_solved_and_feasible(primal; dual = true, allow_local = false)
JuMP.dual(c1) == 0 && print("c1 is indeed redundant")

```

**Conclusion** :

1. After solving `primal` to `OPTIMAL`, we can drop **all** constraints whose `dual() == 0` without altering the primal-side optimal ObjVal.
2. There are 2 **equivalent** ways (one primal, one dual) to judge whether a constraint is redundant. From the primal side, if you remove that constraint, finding that `relaxed_objval == primal_objval`, then that constraint is redundant. Or, you can ϵ-relax that constraint being investigated, if the `dual(constr) == 0`, then that constraint is redundant. The equivalence can be proved via these facts `0 is an optimal dual solution + min-max strong duality + Lagrangian relaxation`.

---

<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 30, 2025, 7:20pm UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/2 "2025-03-30T19:20:11Z")

</div>

> if the `dual(constr) == 0` , then that constraint is redundant

You should be a bit careful here. If the model is dual degenerate (there are multiple optimal primal solutions), then removing this constraint could cause the solver to find a new solution with the same objective bound that violates the constraint you removed.

```julia
julia> using JuMP, Gurobi

julia> begin
           model = Model(Gurobi.Optimizer)
           set_silent(model)
           @variable(model, x[1:2])
           set_lower_bound(x[1], 0.0)
           @objective(model, Max, x[1] + x[2])
           @constraint(model, c1, x[1] + x[2] <= 1.5)
           @constraint(model, c2, x[2] <= 1)
           optimize!(model)
       end
Set parameter LicenseID to value 890341

julia> dual(c2)
0.0

julia> delete(model, c2)

julia> optimize!(model)

julia> value(x[2]) <= 1
false

```

---

<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 31, 2025, 12:06am UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/3 "2025-03-31T00:06:08Z")

</div>

I only intend to remove trivial constraints, mainly those artificial bounds added to ensure the compactness of the feasible region.  
e.g., The primal problem is \qquad \min\_{y, x} y \ge |x|\_1  
My code for this might be

```julia
# the following 4 lines are the primal problem
JuMP.@variable(primal, y)
JuMP.@variable(primal, x[1:2])
JuMP.@constraint(primal, [y; x] in JuMP.MOI.NormOneCone(3))
JuMP.@objective(primal, Min, y)
# To make the feasible region compact, we artificially add these
JuMP.set_lower_bound.(y, -3); JuMP.set_upper_bound.(y, 3); 
JuMP.set_lower_bound.(x, -4); JuMP.set_upper_bound.(x, 4);
# optimize WITH artificial bounds
JuMP.optimize!(primal); JuMP.assert_is_solved_and_feasible(primal; dual = true, allow_local = false)
S = [JuMP.dual(JuMP.LowerBoundRef(y)) JuMP.dual(JuMP.UpperBoundRef(y));
    JuMP.dual.(JuMP.LowerBoundRef.(x)) JuMP.dual.(JuMP.UpperBoundRef.(x))]
@assert all(S .== 0)
# then we can delete all artificial bounds and reoptimize to retain the same optimal objective_value

```

---

<div class="post-metadata">

**Author:** ![HSt](https://avatars.discourse-cdn.com/v4/letter/h/b38774/32.png) [@HSt](https://discourse.julialang.org/u/HSt)\
**Post date:** [March 31, 2025, 12:14pm UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/4 "2025-03-31T12:14:29Z")

</div>

If I get the example correctly, you actually want to do presolve reductions on redundant constraints, in this case bound strengthening / domain propagation.  
Dominated rows can be discarded, as can fixed variables (lb = ub).

This is what (mostly commercial) solvers are very good at.  
What is your reasoning to reduce redundant constraints at the high level of JuMP?

---

<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 31, 2025, 1:30pm UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/5 "2025-03-31T13:30:01Z")

</div>

> [@HSt](#):
>
> This is what (mostly commercial) solvers are very good at.

No. According to my experience, we can not lean on solvers (e.g. Gurobi’s novel nonconvex solver, I had many posts on this issue, in the optimization category, within 10 days, you can check some of them). Sometimes it’s better to write algorithms ourselves, rather than depending on a black-box solver. Of course, LP solvers are robust as expected. Therefore LP relaxation (cutting plane method) is very robust and should be applied generously.

---

<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:** [April 1, 2025, 4:26am UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/6 "2025-04-01T04:26:16Z")

</div>

A fun fact is that, the dual variable of an obj\_cut can be converted to `true` or `false` without incurring `InexactError`.

```julia
using Gurobi, JuMP
model = Model(Gurobi.Optimizer)
@variables(model, begin x >= 0; y <= 1 end)
@expression(model, obj, x + y); @objective(model, Max, obj)
@constraint(model, c1, 1.5 >= obj)
@constraint(model, c2, 1.5001 >= obj)
@constraint(model, c3, 1.5002 >= obj)
# 1️⃣
optimize!(model); JuMP.assert_is_solved_and_feasible(model; dual = true, allow_local = false)
Bool(JuMP.dual(c1)) && println("c1 is indispensable"); # prints
Bool(JuMP.dual(c2)) && println("c2 is indispensable"); # mute
# 2️⃣
JuMP.delete(model, c1)
optimize!(model); JuMP.assert_is_solved_and_feasible(model; dual = true, allow_local = false)
Bool(JuMP.dual(c2)) && println("c2 is indispensable"); # prints
Bool(JuMP.dual(c3)) && println("c3 is indispensable"); # mute

```

---

<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:** [April 1, 2025, 5:42am UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/7 "2025-04-01T05:42:24Z")

</div>

You should not rely on this behavior in general.

The solver may return any solution in tolerance.

Assuming exact floating point comparisons is always a bad idea (in any numerical problem, not just optimization solvers).

---

<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:** [April 4, 2025, 6:35am UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/8 "2025-04-04T06:35:22Z")

</div>

About Gurobi, I did a test using an moderate LP case.  
If I solve with its default setting, then it is fairly robust ( **this is a facade** , see below)

```julia
solve_to_normality(lpr);
c = JuMP.dual.(c_rlt) # c_rlt are all ≥ constraints
sum(c .< 1e-13) # 2979
sum(c .== 0) # 2979
sum(c .< -1e-9) # 0

```

But if I modify 2 settings, then it becomes somewhat messy

```julia
JuMP.set_attribute(lpr, "Method", 2)
JuMP.set_attribute(lpr, "Crossover", 0)
solve_to_normality(lpr);
c = JuMP.dual.(c_rlt) # c_rlt are all ≥ constraints
sum(c .< 1e-13) # 906
sum(c .== 0) # 0
sum(c .< -1e-9) # 1
sum(c .< -1e-8) # 0

```

But after all, the LP model `lpr` can be solved to normality—`OPTIMAL`, primal-dual both `FEASIBLE_POINT`.

**Update** : Gurobi gives irrational small values with the simplex algorithm as well

```julia
julia> solve_to_normality(lpr)
Gurobi Optimizer version 12.0.1 build v12.0.1rc0 (win64 - Windows 11.0 (26100.2))

Optimize a model with 2379 rows, 219 columns and 11498 nonzeros
Coefficient statistics:
  Matrix range [7e-01, 2e+02]
  Objective range [6e+00, 4e+02]
  Bounds range [1e+00, 2e+02]
  RHS range [7e-01, 8e+02]

Iteration Objective Primal Inf. Dual Inf. Time
       0 1.9359608e+05 1.715876e+04 0.000000e+00 0s
     331 1.8438598e+05 0.000000e+00 0.000000e+00 0s

Solved in 331 iterations and 0.03 seconds (0.02 work units)
Optimal objective 1.843859800e+05

julia> tup = get_dual();

julia> tup.g0_rx[9, 5, 9]
4.551914400963142e-14 # This is NOT 0

```

---

<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:** [April 5, 2025, 4:30am UTC](https://discourse.julialang.org/t/a-note-on-how-to-identify-redundant-constraints-using-jump/127504/9 "2025-04-05T04:30:15Z")

</div>

I have nothing to add, other than to re-affirm that this is expected behavior. Solvers may not find a “nice” rational solution, even if one trivially exists.