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

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

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:

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?

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.

1 Like

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…

You should read: 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.

3 Likes

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:

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.

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

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

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:

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.