Problems very similar to each other requiring much much different amount of time to be solved

Dear support team,

I have implemented an algorithm which iteratively solves Integer (BINARY) Linear Problems with Gurobi. The problems solved by Gurobi are all very similar to each other: they only vary by the right hand side of an inequality constraint which gets bigger and bigger and so makes the feasible set smaller. By running the algorithm I have experienced something weird: the solving time slightly changes from an iteration to another fo the first n problems and then it heavily increases letting the algorithm proceede much much more slower.

What happens is that the Incumbent stays the same for a while and the gap moves very slowly (see text at the bottom of the post which is the output from Gurobi for a problem requiring quite a lot of time for being solved, compared to the first n iterations).

I have tried the following to solve the problem:

made the code memory-efficient (I have also monitored the RAM usage with a system monitor and there is no heavy memory usage);

adjusted the MIPFocus parameter (I've tried all the possible value);

adjusted the Cuts parameter (same);

all without success. The only result I got was letting the algorithm get stuck 2 or 3 iterations later.

I do not understand why the time required for finding a solution after the first n iterations is much larger than the first n iterations themselves despite the problems being very similar to each other.

I was also wondering if there was a way to let Gurobi explicitly know that the solution found at the previous iteration basically represents a lower bound (I am minimizing the o.f.) for the next problem since as I said any two subsequent problems only differ from the right hand side of a constraint which is increasing as the iterations go by.

Gurobi Optimizer version 9.5.1 build v9.5.1rc2 (linux64)
Thread count: 2 physical cores, 4 logical processors, using up to 4 threads
Optimize a model with 277 rows, 1780 columns and 65940 nonzeros
Model fingerprint: 0x314dc904
Variable types: 0 continuous, 1780 integer (1780 binary)
Coefficient statistics:
  Matrix range     [1e-02, 5e+02]
  Objective range  [4e+01, 2e+03]
  Bounds range     [1e+00, 1e+00]
  RHS range        [3e-01, 5e+05]

MIP start from previous solve did not produce a new incumbent solution
MIP start from previous solve violates constraint 37 by 0.010000000

Presolve removed 154 rows and 110 columns
Presolve time: 0.21s
Presolved: 123 rows, 1670 columns, 30100 nonzeros
Variable types: 0 continuous, 1670 integer (1670 binary)

Root relaxation: objective 3.467589e+03, 103 iterations, 0.01 seconds (0.00 work units)

    Nodes    |    Current Node    |     Objective Bounds      |     Work
 Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

     0     0 3467.58950    0   11          - 3467.58950      -     -    0s
H    0     0                    4350.3148307 3467.58950  20.3%     -    0s
H    0     0                    3554.3652632 3467.58950  2.44%     -    0s
     0     0 3471.96921    0   13 3554.36526 3471.96921  2.32%     -    0s
     0     0 3471.96921    0   11 3554.36526 3471.96921  2.32%     -    0s
     0     0 3479.90341    0   15 3554.36526 3479.90341  2.09%     -    0s
     0     0 3481.60648    0   16 3554.36526 3481.60648  2.05%     -    0s
     0     0 3481.61640    0   18 3554.36526 3481.61640  2.05%     -    0s
     0     0 3481.68817    0   17 3554.36526 3481.68817  2.04%     -    0s
     0     0 3481.68937    0   19 3554.36526 3481.68937  2.04%     -    0s
     0     0 3481.78181    0   23 3554.36526 3481.78181  2.04%     -    0s
     0     0 3481.97604    0   23 3554.36526 3481.97604  2.04%     -    0s
     0     0 3481.97604    0   25 3554.36526 3481.97604  2.04%     -    0s
     0     0 3482.36776    0   23 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   23 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   25 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   25 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   28 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   28 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   18 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   22 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   20 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0   19 3554.36526 3482.36776  2.03%     -    0s
     0     0 3482.36776    0    8 3554.36526 3482.36776  2.03%     -    1s
     0     0 3492.86641    0   16 3554.36526 3492.86641  1.73%     -    1s
     0     0 3493.42453    0   13 3554.36526 3493.42453  1.71%     -    1s
     0     0 3495.49887    0   19 3554.36526 3495.49887  1.66%     -    1s
     0     0 3496.03310    0   17 3554.36526 3496.03310  1.64%     -    1s
     0     0 3496.03398    0   19 3554.36526 3496.03398  1.64%     -    1s
     0     0 3496.03398    0   24 3554.36526 3496.03398  1.64%     -    1s
     0     0 3496.03398    0   25 3554.36526 3496.03398  1.64%     -    1s
     0     0 3496.03490    0   34 3554.36526 3496.03490  1.64%     -    1s
     0     0 3496.04303    0   37 3554.36526 3496.04303  1.64%     -    1s
     0     0 3496.08439    0   31 3554.36526 3496.08439  1.64%     -    1s
     0     0 3496.08439    0   24 3554.36526 3496.08439  1.64%     -    1s
     0     0 3496.11222    0    8 3554.36526 3496.11222  1.64%     -    1s
     0     0 3496.11222    0   22 3554.36526 3496.11222  1.64%     -    1s
     0     0 3496.11222    0   20 3554.36526 3496.11222  1.64%     -    1s
     0     0 3496.11222    0   22 3554.36526 3496.11222  1.64%     -    1s
     0     0 3496.29585    0   23 3554.36526 3496.29585  1.63%     -    1s
     0     0 3496.29585    0   25 3554.36526 3496.29585  1.63%     -    1s
     0     0 3496.38195    0   24 3554.36526 3496.38195  1.63%     -    1s
     0     0 3496.38199    0   27 3554.36526 3496.38199  1.63%     -    1s
     0     0 3496.40290    0   30 3554.36526 3496.40290  1.63%     -    1s
     0     0 3496.40290    0   27 3554.36526 3496.40290  1.63%     -    1s
     0     2 3496.40290    0   26 3554.36526 3496.40290  1.63%     -    1s
*  261   167              48    3553.4652534 3497.61629  1.57%   5.5    2s
H  870   403                    3552.5252576 3511.58071  1.15%   5.2    2s
H 1780   527                    3551.8152716 3512.34184  1.11%   5.6    4s
  2225   584 3512.64527   29   18 3551.81527 3512.64527  1.10%   6.2    5s
  7456  2031 3539.84268   55   11 3551.81527 3522.84786  0.82%   6.3   10s
 12106  3209 3528.10340   39   15 3551.81527 3526.21821  0.72%   6.0   15s
 16686  4322 3545.67292   42   10 3551.81527 3528.55033  0.66%   6.0   20s
 20540  5220 3531.28720   49   13 3551.81527 3529.98618  0.61%   5.7   26s
 21372  5397 3529.98618   44   27 3551.81527 3529.98618  0.61%   5.8   30s
 31602  5940 3533.96348   55   17 3551.81527 3529.98618  0.61%   5.7   35s
 41497  7685 3541.51703   72    4 3551.81527 3531.30422  0.58%   5.4   40s
 48309 10447 3535.27058   73   13 3551.81527 3531.68186  0.57%   5.1   45s
 54619 12917 3532.69861   62    9 3551.81527 3531.69624  0.57%   4.9   50s
 61716 15446 3543.57709   79    8 3551.81527 3531.98297  0.56%   4.8   55s
 69444 18070     cutoff   70      3551.81527 3532.55334  0.54%   4.7   60s
 74703 19719 3548.92139   81   15 3551.81527 3532.72561  0.54%   4.7   65s
 81702 21783 3547.21412   68   12 3551.81527 3533.17281  0.52%   4.6   70s
 88672 23775 3551.36024   60   13 3551.81527 3533.38539  0.52%   4.6   75s
 94391 25759 3538.10058   77   10 3551.81527 3533.52980  0.51%   4.5   80s
 100836 27647 3533.68313   78   15 3551.81527 3533.65884  0.51%   4.5   85s
 106639 28860 3537.53114   84   13 3551.81527 3533.81660  0.51%   4.5   90s
 113383 30327     cutoff   64      3551.81527 3533.99926  0.50%   4.5   95s
 119183 31665 3541.10812   84   11 3551.81527 3534.15547  0.50%   4.5  100s
 124230 32846 3538.58973   70   18 3551.81527 3534.24423  0.49%   4.5  105s
 130319 34404 3534.87382   70    6 3551.81527 3534.49531  0.49%   4.4  110s
 136695 35782 3534.77481   63   14 3551.81527 3534.74254  0.48%   4.4  116s
 142603 37472 infeasible   70      3551.81527 3534.83107  0.48%   4.4  120s
 149899 38955 3541.18089   78    4 3551.81527 3534.98307  0.47%   4.4  125s
 155649 40060 3548.44893   79    8 3551.81527 3535.20103  0.47%   4.4  130s
 162681 41271 infeasible   84      3551.81527 3535.44650  0.46%   4.4  135s
 169526 42528 3536.81948   72    8 3551.81527 3535.63863  0.46%   4.4  140s
 176533 43810 3536.92386   58   17 3551.81527 3535.80629  0.45%   4.4  145s
 184379 45164 3538.94876   71   10 3551.81527 3535.92467  0.45%   4.4  150s
 190445 45997 infeasible   80      3551.81527 3536.11434  0.44%   4.4  155s
 196641 46876 infeasible   82      3551.81527 3536.34551  0.44%   4.4  160s
 203226 47711 3536.61956   74    8 3551.81527 3536.58731  0.43%   4.4  165s
 210294 48690     cutoff   70      3551.81527 3536.77236  0.42%   4.4  170s
 215636 48677 infeasible   76      3551.81527 3536.85954  0.42%   4.4  175s
 222089 49278     cutoff   78      3551.81527 3537.00031  0.42%   4.4  180s
 229481 49741 3547.79949   63   14 3551.81527 3537.12681  0.41%   4.3  185s
 235879 50380 3547.62205   82    7 3551.81527 3537.29476  0.41%   4.3  190s
 242852 51005 infeasible   69      3551.81527 3537.47285  0.40%   4.3  195s
 248778 51563 3550.78303   65    7 3551.81527 3537.66906  0.40%   4.3  200s
 255517 52257 3539.70950   63   13 3551.81527 3537.79899  0.39%   4.3  205s
 259066 52840 3542.96415   57    4 3551.81527 3537.84684  0.39%   4.3  210s
 266598 53410 3549.30060   70    4 3551.81527 3537.99391  0.39%   4.3  215s
 273165 53685 infeasible   64      3551.81527 3538.12166  0.39%   4.3  220s
 279305 54200 3538.27875   67   16 3551.81527 3538.25330  0.38%   4.3  225s
 285967 54736 3541.36934   74    8 3551.81527 3538.40027  0.38%   4.3  230s
 292549 55122 3540.74313   72    8 3551.81527 3538.55919  0.37%   4.3  235s
 298535 55738     cutoff   80      3551.81527 3538.69531  0.37%   4.3  240s
 305162 56309     cutoff   71      3551.81527 3538.79768  0.37%   4.3  245s
 312602 56461 3542.66463   56    6 3551.81527 3538.95052  0.36%   4.3  250s
 319256 56936 3547.26107   74    6 3551.81527 3539.05967  0.36%   4.3  255s
 326392 57268     cutoff   79      3551.81527 3539.21149  0.35%   4.3  260s
 333180 57418 3541.09900   69    7 3551.81527 3539.39152  0.35%   4.3  265s
 340330 58321 infeasible   65      3551.81527 3539.49419  0.35%   4.3  270s
 347117 58844 3549.03083   80    9 3551.81527 3539.61010  0.34%   4.3  275s
 353136 59112 3540.68675   74   18 3551.81527 3539.71910  0.34%   4.3  280s
 359340 59358 3547.67495   72   12 3551.81527 3539.81992  0.34%   4.3  285s
 366361 59874 3539.91823   64   14 3551.81527 3539.89333  0.34%   4.3  290s
 372648 60278 3547.16795   77   14 3551.81527 3539.96557  0.33%   4.3  295s
 380355 60528 3544.09476   78    8 3551.81527 3540.08279  0.33%   4.3  300s
 387246 60728 3541.53403   67   12 3551.81527 3540.15034  0.33%   4.3  305s
 394087 60917 3545.85989   63    6 3551.81527 3540.26737  0.33%   4.3  310s
 400614 60931 infeasible   74      3551.81527 3540.39723  0.32%   4.3  315s
 407264 60936 3548.72440   66    5 3551.81527 3540.52815  0.32%   4.3  320s
 412986 60955 3550.75626   71   16 3551.81527 3540.64927  0.31%   4.3  325s
 419758 59558 infeasible   83      3551.81527 3540.77251  0.31%   4.3  330s
 425866 59364 3542.17593   69   11 3551.81527 3540.86692  0.31%   4.3  335s
 433313 59346 3546.50184   55    6 3551.81527 3540.98221  0.31%   4.3  340s
 439640 59319 infeasible   75      3551.81527 3541.11148  0.30%   4.3  345s
 446204 59211 3541.18760   77    8 3551.81527 3541.17847  0.30%   4.3  350s
 452384 59216 3545.58046   66    9 3551.81527 3541.26185  0.30%   4.3  355s
 460052 59307 3544.30110   69    8 3551.81527 3541.31861  0.30%   4.3  360s
 465289 59314 3541.94678   69    7 3551.81527 3541.38105  0.29%   4.3  365s
 473245 59163 3541.44231   79    4 3551.81527 3541.44231  0.29%   4.3  370s
 480686 59009     cutoff   78      3551.81527 3541.51703  0.29%   4.3  375s
 488563 58854     cutoff   74      3551.81527 3541.59919  0.29%   4.2  380s
 493914 58505 3542.73047   69   14 3551.81527 3541.69339  0.28%   4.2  385s
 499787 58218 3541.89028   69    8 3551.81527 3541.78768  0.28%   4.2  390s
 506875 57811 3550.96527   74    2 3551.81527 3541.89405  0.28%   4.2  395s
 513804 57413 3546.34756   67    9 3551.81527 3542.02983  0.28%   4.2  400s
 520141 56753 infeasible   84      3551.81527 3542.17115  0.27%   4.2  405s
 526978 56588 3547.75410   70    5 3551.81527 3542.28202  0.27%   4.2  410s
 533030 56273     cutoff   73      3551.81527 3542.36777  0.27%   4.2  415s
 538127 55866     cutoff   69      3551.81527 3542.47196  0.26%   4.2  420s
 545079 55317 3542.92246   79    6 3551.81527 3542.60181  0.26%   4.2  425s
 552093 54354 3544.94299   82   10 3551.81527 3542.78061  0.25%   4.2  430s
 558748 53434 3543.35064   76   11 3551.81527 3542.94336  0.25%   4.2  435s
 563192 52833 3543.98332   63   14 3551.81527 3543.04616  0.25%   4.2  440s
 569388 52088     cutoff   73      3551.81527 3543.20128  0.24%   4.2  445s
 575772 51316 3545.53138   71    8 3551.81527 3543.33754  0.24%   4.2  450s
 581794 50407 3544.42755   65   16 3551.81527 3543.49286  0.23%   4.2  455s
 588943 49539 infeasible   69      3551.81527 3543.66810  0.23%   4.2  460s
 595898 48919 3551.19776   71    4 3551.81527 3543.77314  0.23%   4.2  465s
 602392 47898     cutoff   77      3551.81527 3543.92461  0.22%   4.2  470s
 610372 46521 3548.09244   79    9 3551.81527 3544.15407  0.22%   4.2  475s
 616070 45544     cutoff   74      3551.81527 3544.29909  0.21%   4.2  480s
 622530 44711 3544.44899   75    9 3551.81527 3544.44899  0.21%   4.2  485s
 631093 43459 3550.67934   68    6 3551.81527 3544.60598  0.20%   4.2  490s
 638407 41911     cutoff   68      3551.81527 3544.77483  0.20%   4.2  495s
 645147 40628 3545.54042   75   11 3551.81527 3544.96049  0.19%   4.2  500s
 653313 39041     cutoff   85      3551.81527 3545.19352  0.19%   4.2  505s
 660253 37602 3547.18012   74   10 3551.81527 3545.36246  0.18%   4.2  510s
 667192 35919 infeasible   63      3551.81527 3545.57890  0.18%   4.2  515s
 674917 33958 infeasible   69      3551.81527 3545.75082  0.17%   4.2  520s
 681412 31854     cutoff   77      3551.81527 3546.03851  0.16%   4.2  525s
 688621 29460     cutoff   69      3551.81527 3546.39511  0.15%   4.2  530s
 696460 27057 3550.93822   76    7 3551.81527 3546.78215  0.14%   4.2  535s
 703442 24769 infeasible   77      3551.81527 3546.97233  0.14%   4.2  540s
 712222 21976     cutoff   87      3551.81527 3547.33601  0.13%   4.2  545s
 718192 19471     cutoff   60      3551.81527 3547.71742  0.12%   4.2  550s
 725271 16824 infeasible   69      3551.81527 3548.18916  0.10%   4.2  555s
 732605 13904 infeasible   69      3551.81527 3548.75033  0.09%   4.2  560s
 739625 10242 3549.53559   76   15 3551.81527 3549.39061  0.07%   4.2  566s
 746255  7000 infeasible   69      3551.81527 3549.95052  0.05%   4.2  570s
 755276  1529     cutoff   79      3551.81527 3551.10021  0.02%   4.2  575s

Cutting planes:
  Gomory: 27
  Cover: 702
  MIR: 50
  StrongCG: 22
  Flow cover: 14
  GUB cover: 17
  Inf proof: 10

Thanks for your help!

Daniele