# Solver iterates then declares model infeasible - what could explain this behaviour for a linear problem?

**URL:** <https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702>\
**Category:** Optimization (Mathematical)\
**Created:** [August 19, 2019, 7:26am UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702 "2019-08-19T07:26:55Z")\
**Posts on this page:** 8\
**Page:** 1

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [August 19, 2019, 7:26am UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702/1 "2019-08-19T07:26:55Z")

</div>

I’m solving a linear problem with JuMP and Gurobi, and for some formulations I end up getting the following behaviour:

```julia-repl
Academic license - for non-commercial use only
Optimize a model with 6725 rows, 6346 columns and 17254 nonzeros
Coefficient statistics:
  Matrix range [1e-07, 1e+07]
  Objective range [1e+00, 1e+00]
  Bounds range [0e+00, 0e+00]
  RHS range [4e-07, 1e+04]
Warning: Model contains large matrix coefficient range
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.
Presolve removed 3752 rows and 3944 columns
Presolve time: 0.01s
Iteration Objective Primal Inf. Dual Inf. Time
       0 0.0000000e+00 1.983774e+06 0.000000e+00 0s

Solved in 1501 iterations and 0.10 seconds
Infeasible model

```

For another slightly different formulation I get the following behaviour:

```julia-repl
Academic license - for non-commercial use only
Optimize a model with 11717 rows, 28042 columns and 42022 nonzeros
Coefficient statistics:
  Matrix range [1e-07, 1e+07]
  Objective range [1e+00, 1e+00]
  Bounds range [0e+00, 0e+00]
  RHS range [4e-07, 1e+04]
Warning: Model contains large matrix coefficient range
         Consider reformulating model or setting NumericFocus parameter
         to avoid numerical issues.

Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...

Presolve removed 6345 rows and 17873 columns
Presolve time: 0.04s
Ordering time: 0.00s

Barrier statistics:
 Dense cols : 5
 AA' NZ : 3.203e+04
 Factor NZ : 1.407e+05 (roughly 17 MBytes of memory)
 Factor Ops : 1.899e+06 (less than 1 second per iteration)
 Threads : 1

                  Objective Residual
Iter Primal Dual Primal Dual Compl Time
   0 2.07059225e+11 0.00000000e+00 8.23e+04 0.00e+00 9.10e+07 0s
   1 1.54480975e+11 -1.14052489e+19 6.12e+04 3.31e+02 4.76e+07 0s
   2 1.51813177e+11 -7.80999362e+18 6.02e+04 1.78e+02 4.51e+07 0s
   3 1.51787625e+11 1.02396826e+23 6.01e+04 6.55e+04 5.77e+17 0s
   4 2.07059225e+11 0.00000000e+00 8.23e+04 0.00e+00 9.10e+07 0s
   5 4.56873171e+11 1.32645209e+12 8.23e+04 5.01e+03 6.31e+08 0s
   6 1.71300159e+13 3.64537610e+13 8.25e+04 8.04e+04 4.34e+10 0s
   7* 6.13167144e+14 3.83194214e+15 1.46e+03 3.02e+03 9.62e+05 0s
   8* 4.84800700e+14 4.41350337e+15 5.97e+00 4.29e+02 6.86e+02 0s
   9* 4.85688050e+14 6.48184468e+18 2.27e-02 4.86e+03 1.72e+01 0s
  10* 5.41950241e+14 2.31123405e+20 3.59e-04 8.06e+04 1.03e+00 0s
  11* 3.65150700e+15 5.81597939e+21 6.48e-06 2.87e+04 3.23e-02 0s
  12* 7.39521619e+17 1.91153773e+24 2.78e-08 2.87e+04 3.47e-04 0s
  13* 2.00856258e+20 6.97456139e+27 1.16e-10 1.79e+06 4.30e-05 0s
  14* 5.70132227e+20 7.42676517e+27 5.80e-11 1.16e+07 1.72e-05 0s
  15* 5.67160405e+21 1.34732737e+28 8.55e-11 9.81e+05 1.81e-06 0s
  16* 7.16629699e+22 8.91224219e+28 5.04e-11 1.16e+06 1.50e-07 0s
  17* 1.43364707e+23 2.00534601e+29 5.04e-11 3.15e+06 8.12e-08 0s
  18* 6.70396621e+24 9.25905832e+30 5.04e-11 1.53e+06 1.93e-09 0s
  19* 6.62645808e+25 8.94264368e+31 5.04e-11 1.56e+06 2.16e-10 0s
  20* 2.51510982e+27 3.23937260e+33 7.13e-11 1.21e+06 6.05e-12 0s
  21* 4.75050996e+28 6.05403813e+34 4.25e-19 4.60e+06 3.41e-13 0s
  22* 5.14534672e+29 6.14728408e+35 3.93e-20 4.03e+06 3.24e-14 1s
  23* 9.04011922e+30 1.08644506e+37 7.13e-11 1.51e+06 2.04e-15 1s
  24* 4.85776882e+31 6.79262814e+37 5.04e-11 2.51e+06 4.29e-16 1s
  25* 2.00748030e+32 2.53176143e+38 5.04e-11 1.80e+06 1.17e-16 1s
  26* 5.75209253e+32 6.73021608e+38 3.51e-23 2.14e+06 4.51e-17 1s
  27* 1.14373815e+33 1.22404304e+39 1.77e-23 9.35e+05 2.16e-17 1s
  28* 2.27956404e+33 2.08548685e+39 8.87e-24 7.34e+05 9.17e-18 1s
  29* 1.97980222e+34 2.71902152e+40 1.02e-24 2.68e+06 1.09e-18 1s
  30* 5.28152333e+34 7.63361159e+40 3.83e-25 4.37e+06 4.39e-19 1s
  31* 6.80137849e+35 1.07539142e+42 2.97e-26 2.41e+06 3.83e-20 1s

Barrier performed 31 iterations in 0.70 seconds
Numerical trouble encountered

Iteration Objective Primal Inf. Dual Inf. Time
       0 0.0000000e+00 1.983774e+06 0.000000e+00 1s

Solved with dual simplex
Solved in 7608 iterations and 1.61 seconds
Infeasible model

```

What I don’t understand is why the solver declares the model to be infeasible AFTER iterating - surely for a linear problem this could / should be determined before solving? Is it possible that this is due to the large range of matrix coefficients?

---

<div class="post-metadata">

**Author:** ![loisel](https://sea2.discourse-cdn.com/julialang/user_avatar/discourse.julialang.org/loisel/32/50626_2.png) [@loisel](https://discourse.julialang.org/u/loisel)\
**Post date:** [August 19, 2019, 9:06am UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702/2 "2019-08-19T09:06:02Z")

</div>

I don’t know anything about this particular implementation but typically for optimization and linear programming, the algorithm runs in two phases. In phase 1, the algorithm looks for a feasible solution. In phase 2, the feasible solution is optimized to find the optimal solution.

Both phases use essentially the same algorithm, so determining whether a problem is feasible does indeed require iteration.

---

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [August 19, 2019, 10:05am UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702/3 "2019-08-19T10:05:48Z")

</div>

That sort of makes sense to me. I was thinking that in the presolve phase, the solver uses the inequality constraints to determine whether a feasible region exists or not. I assume that means solving a system of linear equations, so makes sense that you would have to iterate there as well as when you find the optimal solution. Thank you! Hopefully I figure out what I’m doing wrong soon…

---

<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:** [August 19, 2019, 1:37pm UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702/4 "2019-08-19T13:37:14Z")

</div>

You should read: [https://www.gurobi.com/documentation/8.1/refman/numerics\_gurobi\_guidelines.html](https://www.gurobi.com/documentation/8.1/refman/numerics_gurobi_guidelines.html).

The poor problem scaling is almost certainly the issue. My guess is that Gurobi re-scales your model, finds an initial “feasible” solution to the re-scaled problem and solves. But, when it attempts to un-scale the solution back to the original problem, the solution is numerically infeasible.

When every you see this warning, take it’s advice:

> Warning: Model contains large matrix coefficient range  
> Consider reformulating model or setting NumericFocus parameter  
> to avoid numerical issues.

---

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [August 20, 2019, 11:24am UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702/5 "2019-08-20T11:24:05Z")

</div>

Thanks, I’m going to try scaling. One question I have is that I have a parameter which varies between 0 and 1. Ideally, I would like Gurobi (or any solver really) to ignore coefficients which are less than say 10^-4, but how do I do that? I could write my constraints as something like:

```julia
for i in I, j in J
    if P[i,j] >= 10^-4
        <write constraint>
    end
end

```

But writing that for every constraint feels clunky. Does Gurobi understand that `0.0` is `0`? Otherwise another thing I could do is just set any values less than 10^-4 to 10^-4 (i.e. small) and hope that my solution doesn’t change.

---

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [August 20, 2019, 11:59am UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702/6 "2019-08-20T11:59:56Z")

</div>

Answering myself: it would appear that Gurobi does understand that `0.0 == 0`

---

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [August 29, 2019, 11:34am UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702/7 "2019-08-29T11:34:07Z")

</div>

So I finally scaled my problem, but the issue persists. For one formulation of my problem I get the following Gurobi output:

```julia-repl
Academic license - for non-commercial use only
Optimize a model with 6725 rows, 6346 columns and 17263 nonzeros
Coefficient statistics:
  Matrix range [2e-04, 1e+02]
  Objective range [1e+00, 1e+00]
  Bounds range [0e+00, 0e+00]
  RHS range [3e-07, 1e+01]
Presolve removed 3752 rows and 4783 columns
Presolve time: 0.01s
Iteration Objective Primal Inf. Dual Inf. Time
       0 0.0000000e+00 1.953717e+03 0.000000e+00 0s

Solved in 1422 iterations and 0.18 seconds
Infeasible model

```

For another variation, it uses the barrier method and then encounters trouble:

```julia-repl
Academic license - for non-commercial use only
Optimize a model with 19397 rows, 72202 columns and 93871 nonzeros
Coefficient statistics:
  Matrix range [2e-04, 1e+02]
  Objective range [1e+00, 1e+00]
  Bounds range [0e+00, 0e+00]
  RHS range [3e-07, 1e+01]

Concurrent LP optimizer: dual simplex and barrier
Showing barrier log only...

Presolve removed 12415 rows and 58390 columns
Presolve time: 0.07s
Ordering time: 0.00s

Barrier statistics:
 Dense cols : 5
 AA' NZ : 9.540e+04
 Factor NZ : 2.983e+05 (roughly 40 MBytes of memory)
 Factor Ops : 6.285e+06 (less than 1 second per iteration)
 Threads : 1

                  Objective Residual
Iter Primal Dual Primal Dual Compl Time
   0 1.06504414e+08 0.00000000e+00 1.40e+04 0.00e+00 1.00e+06 0s
   1 3.83234641e+07 -3.02018884e+10 6.94e+03 7.96e+02 6.75e+05 0s
   2 1.10211654e+07 -5.02756800e+11 2.12e+03 7.07e+01 1.41e+05 0s
   3 7.11284686e+06 2.04399751e+12 1.33e+03 5.49e+00 6.78e+04 0s
   4 6.61804040e+06 4.02602279e+12 1.22e+03 2.04e+00 5.86e+04 1s
   5 6.57141187e+06 4.82447188e+12 1.22e+03 7.57e-01 5.74e+04 1s
   6 6.55816035e+06 1.10978718e+13 1.21e+03 1.92e-01 1.15e+05 1s
   7 5.53183892e+06 2.01732728e+13 1.01e+03 3.71e-01 3.00e+07 1s
   8 5.30852950e+06 1.07958831e+14 9.65e+02 4.02e-01 8.98e+07 1s
   9 3.61275769e+07 1.07980272e+14 9.04e+02 9.56e-01 8.25e+07 1s
  10 3.44459883e+07 6.03739955e+13 8.28e+02 9.63e-01 7.36e+07 1s
  11 5.31688414e+08 0.00000000e+00 7.00e+04 0.00e+00 2.50e+07 1s
  12 5.20458817e+08 3.44165368e+07 7.02e+04 4.42e+03 3.97e+07 1s
  13 5.57607722e+08 1.73358504e+09 7.04e+04 3.81e+03 2.92e+08 1s
  14* 7.33081478e+08 1.58066983e+10 2.81e+04 9.51e+03 1.58e+05 2s
  15* 2.49536043e+09 1.56669489e+11 2.81e+03 9.24e+02 1.54e+04 2s
  16* 2.01173615e+10 1.56530454e+12 2.81e+02 9.15e+01 1.52e+03 2s
  17* 1.96461284e+11 1.56645515e+13 2.81e+01 9.10e+00 1.51e+02 2s
  18* 1.96141751e+12 1.56743622e+14 2.81e+00 9.14e-01 1.51e+01 2s
  19* 1.96262747e+13 1.56871354e+15 2.81e-01 1.24e-01 1.51e+00 2s
  20* 1.96239087e+14 1.56865961e+16 2.81e-02 1.09e+00 1.51e-01 2s
  21* 1.96412243e+15 1.56992367e+17 2.81e-03 8.55e-02 1.51e-02 2s
  22* 1.96575929e+16 1.57130989e+18 2.81e-04 4.15e-01 1.51e-03 2s
  23* 1.96713584e+17 1.57262347e+19 2.81e-05 6.67e-01 1.52e-04 2s
  24* 1.96707127e+18 1.57233972e+20 2.81e-06 6.26e-01 1.52e-05 2s
  25* 1.96769603e+19 1.57367209e+21 2.81e-07 7.84e-01 1.52e-06 3s
  26* 1.96762427e+20 1.57346604e+22 2.81e-08 2.19e+00 1.52e-07 3s
  27* 1.96762882e+21 1.57479930e+23 2.81e-09 3.79e-01 1.52e-08 3s
  28* 1.96750339e+22 1.57479208e+24 2.84e-10 4.13e-02 1.52e-09 3s
  29* 1.96745616e+23 1.57610226e+25 3.15e-11 6.64e-02 1.53e-10 3s
  30* 1.96739190e+24 1.57746041e+26 1.07e-11 2.64e-01 1.53e-11 3s
  31* 1.96735306e+25 1.57881146e+27 7.28e-12 3.43e+00 1.53e-12 3s
  32* 1.96731797e+26 1.57877841e+28 2.80e-14 7.91e-01 1.53e-13 3s
  33* 1.96724584e+27 1.57874978e+29 2.80e-15 1.89e+00 1.53e-14 3s
  34* 1.96710602e+28 1.58009814e+30 1.93e-11 1.38e-01 1.53e-15 3s
  35* 1.96688056e+29 1.58139464e+31 7.28e-12 5.36e-01 1.53e-16 4s
  36* 1.96669131e+30 1.58262329e+32 2.82e-11 1.10e-01 1.54e-17 4s
  37* 1.96662715e+31 1.58245245e+33 1.46e-11 1.57e-01 1.53e-18 4s
  38* 1.96576631e+32 1.58362842e+34 1.26e-11 1.26e-01 1.53e-19 4s
  39* 1.96569145e+33 1.58315466e+35 1.26e-11 1.63e-01 1.53e-20 4s
  40* 1.96550951e+34 1.58296969e+36 1.26e-11 6.03e-01 1.53e-21 4s
  41* 1.96524070e+35 1.58320426e+37 1.26e-11 5.48e-01 1.53e-22 4s
  42* 1.96476274e+36 1.58206951e+38 1.26e-11 4.69e-02 1.53e-23 4s
  43* 1.96083237e+37 1.50260161e+39 1.26e-11 1.96e-01 1.49e-24 4s
  44* 1.93476344e+38 9.70953281e+39 1.26e-11 8.07e-01 1.15e-25 4s
  45* 1.68535124e+39 9.70953281e+39 1.26e-11 2.15e-02 5.80e-27 5s
  46* 7.46371629e+39 9.70953281e+39 1.26e-11 4.86e-03 5.46e-28 5s

Barrier performed 46 iterations in 4.70 seconds
Numerical trouble encountered

Crossover log...

       0 DPushes remaining with DInf 1.6076253e+45 5s

   40518 PPushes remaining with PInf 3.1010172e+08 5s
      32 PPushes remaining with PInf 5.7832297e+06 5s

  Push phase complete: Pinf 5.7832297e+06, Dinf 1.6076253e+45 5s

Iteration Objective Primal Inf. Dual Inf. Time
   40495 2.0880234e+03 4.222410e+03 0.000000e+00 5s
   40599 2.0880234e+03 3.766935e+03 0.000000e+00 5s

Solved with dual simplex
Solved in 13921 iterations and 9.63 seconds
Infeasible model

```

I assume that this is not a numerical issue anymore, and actually something wrong with my problem formulation. Will update when I find out what.

---

<div class="post-metadata">

**Author:** ![gobs](https://avatars.discourse-cdn.com/v4/letter/g/bc8723/32.png) [@gobs](https://discourse.julialang.org/u/gobs)\
**Post date:** [November 5, 2019, 3:13pm UTC](https://discourse.julialang.org/t/solver-iterates-then-declares-model-infeasible-what-could-explain-this-behaviour-for-a-linear-problem/27702/8 "2019-11-05T15:13:11Z")

</div>

I recently replaced a lot of my dummy variables (e.g. `y = sum(x)` where both `y` and `x` are JuMP variables) with JuMP expressions, since for various reasons I assumed that this must be the cause of the problem. I have yet to confirm, but it looks like it was.