• Gurobi Staff

Hi Antonios,

Your model is quite large, and according to your log, the progress does not even pass the root relaxation phase. It seems that the simplex algorithm has a hard time with your model, this is why the barrier finishes first. But barrier solutions need to be transformed into a basic solution in the crossover phase (where, again, simplex comes into play). This crossover phase takes far longer than barrier took. However, for using simplex during branch-and-bound, you need a basic solution. Alternatively, you could completely switch to barrier, both in the root relaxation and during branch-and-bound, and deactivate crossover (with parameters Method=2, Crossover=0, NodeMethod=2). This could, however, harm the branch-and-bound progress. Still worth a try.

If you quickly need a feasible solution, you might try the NoRel heuristic, by setting parameter NoRelHeurTime=<# seconds> to the amount of seconds that NoRel is allowed to run. This heuristic runs before the root relaxation and often finds solutions even for very large models.

Best regards,
Mario

Dear Mario,

thank you for the quick reply. In my present mathematical program, I minimize two objective functions. To cast this in a tractable format, I utilize the ε-constraint technique, where I minimize the first objective function, but I need to respect the ε-constraint that I have imposed.

Let us consider the case where ε=0. This completely disregards the effect of the second objective function, and I optimize solely based on the first objective function.

In other words, I want to solve the optimization problem for different values of ε, i.e., ε=0,10,20,...,100.

For the question I have posed in the post, I have considered that ε=0, which essentially is the simplest case, for which I know beforehand the optimal solution.

I followed your suggestion and set Method=2, CrossOver=0, NodeMethod=2, and indeed, I was able to receive a feasible solution for the optimization for each value of ε mentioned above. However, the solution I received was the same for each value of ε, which is not what I want to achieve.

I guess that setting the above-mentioned values for these parameters triggered the behavior that you predicted before in terms of harming the branch-and-bound progress when considering different values of ε.

My current objective is to pinpoint the optimal solution for each value of ε. Hence, the feasibility aspect alone is not enough.
I saw from the Gurobi manual that when one needs to focus on optimality rather than feasibility, then setting MIPFocus=2 might help.

It appears that setting: CrossoverBasis=1, Method=2, presolve=2, DegenMoves=0, MIPFocus=2, NodeMethod=2, and Crossover=-1 (default value) leads to a significant reduction in terms of the root crossover phase. Still, the root simplex log continues indefinitely until the time-limit=36000 seconds, parameter is exceeded, where I get a message stating that my optimization formulation leads to Infeasibility.

I attach a part of the log for ε=0:

Set parameter UsernameSet parameter TimeLimit to value 36000Set parameter Method to value 2Set parameter CrossoverBasis to value 1Set parameter DegenMoves to value 0Set parameter MIPFocus to value 2Set parameter NodeMethod to value 2Set parameter Presolve to value 2Academic license - for non-commercial use only - expires 2025-01-15Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 11+.0 (22631.2))CPU model: Intel(R) Core(TM) i7-8665U CPU @ 1.90GHz, instruction set [SSE2|AVX|AVX2]Thread count: 4 physical cores, 8 logical processors, using up to 8 threadsOptimize a model with 5788538 rows, 33964001 columns and 20903685 nonzerosModel fingerprint: 0x42bb536fVariable types: 33963001 continuous, 1000 integer (1000 binary)Coefficient statistics:  Matrix range     [4e-03, 7e+01]  Objective range  [8e-03, 8e-03]  Bounds range     [1e+00, 3e+03]  RHS range        [1e-02, 5e+03]Presolve removed 0 rows and 0 columns (presolve time = 5s) ...Presolve removed 2157164 rows and 31156761 columns (presolve time = 10s) ...Presolve removed 4564546 rows and 32859778 columns (presolve time = 15s) ...Presolve removed 4564546 rows and 32859778 columnsPresolve time: 16.61sPresolved: 1223992 rows, 1104223 columns, 5898957 nonzerosVariable types: 1102060 continuous, 2163 integer (0 binary)Root relaxation presolve removed 1018 rows and 879 columnsRoot relaxation presolved: 300131 rows, 289373 columns, 1349671 nonzerosRoot barrier log...Ordering time: 7.09sBarrier statistics: AA' NZ     : 2.119e+06 Factor NZ  : 5.954e+07 (roughly 700 MB of memory) Factor Ops : 8.835e+10 (roughly 2 seconds per iteration) Threads    : 4                  Objective                ResidualIter       Primal          Dual         Primal    Dual     Compl     Time   0  -1.83776659e+06 -9.22270921e+07  6.60e+04 1.66e-01  2.17e+03   184s   1  -1.15607668e+06 -8.26299870e+07  4.15e+04 9.18e-01  1.37e+03   186s   2  -2.44687059e+05 -5.06140893e+07  8.82e+03 2.24e-14  3.16e+02   189s   3  -5.48555135e+04 -1.62430242e+07  2.01e+03 2.15e-14  7.19e+01   191s   4  -3.58659859e+04 -7.76871845e+06  1.34e+03 1.83e-14  4.07e+01   194s   5  -1.53869121e+04 -3.83820064e+06  6.03e+02 1.37e-13  1.79e+01   197s   6  -3.60422842e+03 -1.80446322e+06  1.82e+02 7.86e-14  5.92e+00   199s   7  -4.41503269e+02 -7.94178764e+05  6.85e+01 1.59e-13  2.24e+00   202s   8   4.21437881e+02 -4.59696030e+05  3.67e+01 9.15e-14  1.20e+00   205s   9   9.40556606e+02 -2.51454189e+05  1.63e+01 8.48e-14  5.81e-01   209s  10   1.10006292e+03 -1.84091525e+05  9.52e+00 1.28e-13  3.86e-01   212s  11   1.16722208e+03 -1.46670565e+05  6.37e+00 9.95e-14  2.88e-01   215s  12   1.20630052e+03 -1.05760933e+05  4.35e+00 1.71e-13  2.02e-01   218s  13   1.23144111e+03 -7.50210468e+04  2.76e+00 1.71e-13  1.38e-01   222s  14   1.23506049e+03 -7.01291034e+04  2.49e+00 1.85e-13  1.27e-01   225s  15   1.24221200e+03 -4.51251108e+04  1.77e+00 3.41e-13  8.30e-02   229s  16   1.24147357e+03 -3.26602717e+04  1.12e+00 3.55e-13  5.82e-02   233s  17   1.21926128e+03 -2.65944978e+04  6.29e-01 1.56e-13  4.46e-02   237s  18   1.21229171e+03 -1.68446065e+04  5.38e-01 1.53e-13  2.98e-02   240s  19   1.18471255e+03 -1.64844871e+04  3.99e-01 2.40e-13  2.80e-02   243s  20   1.15612857e+03 -9.72894147e+03  2.96e-01 7.53e-13  1.75e-02   247s  21   1.09270379e+03 -6.69935105e+03  1.80e-01 5.42e-13  1.22e-02   250s  22   1.03967957e+03 -5.22180658e+03  1.37e-01 4.14e-13  9.70e-03   254s  23   9.43192262e+02 -3.95305696e+03  8.73e-02 3.28e-13  7.41e-03   258s  24   7.89004189e+02 -1.83771506e+03  5.07e-02 2.42e-13  3.98e-03   261s  25   5.73835954e+02 -9.57789084e+02  2.16e-02 2.20e-13  2.26e-03   265s  26   4.15135280e+02 -3.92385290e+02  1.06e-02 3.55e-13  1.19e-03   269s  27   2.93036113e+02 -9.89520440e+01  4.71e-03 4.12e-13  5.73e-04   272s  28   2.18067624e+02  4.58911476e+01  1.95e-03 5.68e-13  2.51e-04   276s  29   1.76404572e+02  1.01254516e+02  8.16e-04 6.82e-13  1.09e-04   280s  30   1.62453304e+02  1.28193720e+02  4.80e-04 9.09e-13  5.05e-05   284s  31   1.54194918e+02  1.34656058e+02  2.88e-04 7.11e-13  2.89e-05   287s  32   1.52656882e+02  1.35718868e+02  2.52e-04 6.96e-13  2.51e-05   290s  33   1.49602103e+02  1.37365179e+02  1.83e-04 8.24e-13  1.81e-05   294s  34   1.46819020e+02  1.38614104e+02  1.23e-04 9.52e-13  1.21e-05   297s  35   1.44813476e+02  1.39767533e+02  7.55e-05 8.38e-13  7.45e-06   300s  36   1.43274081e+02  1.40571489e+02  3.97e-05 4.69e-13  3.98e-06   305s  37   1.42586064e+02  1.41045031e+02  2.42e-05 5.83e-13  2.27e-06   311s  38   1.42058131e+02  1.41219043e+02  1.23e-05 6.11e-13  1.22e-06   317s  39   1.41820194e+02  1.41312766e+02  6.94e-06 4.69e-13  7.35e-07   322s  40   1.41684093e+02  1.41364804e+02  4.02e-06 3.69e-13  4.59e-07   329s  41   1.41636565e+02  1.41406575e+02  2.93e-06 2.27e-13  3.30e-07   333s  42   1.41591631e+02  1.41442005e+02  1.90e-06 1.56e-13  2.14e-07   336s  43   1.41557305e+02  1.41472143e+02  1.12e-06 1.07e-13  1.22e-07   341s  44   1.41533775e+02  1.41486450e+02  5.92e-07 8.17e-14  6.73e-08   345s  45   1.41522027e+02  1.41498212e+02  3.29e-07 3.20e-14  3.38e-08   350s  46   1.41515677e+02  1.41503151e+02  1.91e-07 3.07e-13  1.78e-08   355s  47   1.41511790e+02  1.41504567e+02  1.05e-07 5.03e-13  1.02e-08   358s  48   1.41510154e+02  1.41505621e+02  6.94e-08 6.83e-13  6.41e-09   362s  49   1.41509030e+02  1.41505949e+02  4.49e-08 1.09e-12  4.34e-09   365s  50   1.41508222e+02  1.41506242e+02  2.74e-08 1.87e-12  2.78e-09   368s  51   1.41507805e+02  1.41506542e+02  1.86e-08 1.55e-12  1.77e-09   372s  52   1.41507529e+02  1.41506729e+02  1.26e-08 1.12e-12  1.12e-09   376s  53   1.41507324e+02  1.41506835e+02  8.24e-09 1.40e-12  6.82e-10   380s  54   1.41507187e+02  1.41506866e+02  5.38e-09 9.25e-13  4.48e-10   384s  55   1.41507096e+02  1.41506887e+02  6.18e-08 7.87e-13  2.91e-10   388s  56   1.41507046e+02  1.41506906e+02  1.27e-07 6.16e-13  1.94e-10   392s  57   1.41507012e+02  1.41506911e+02  1.84e-07 4.89e-13  1.40e-10   395s  58   1.41506990e+02  1.41506919e+02  1.31e-07 3.07e-13  9.82e-11   400s  59   1.41506968e+02  1.41506924e+02  8.38e-08 2.36e-13  6.09e-11   405s  60   1.41506958e+02  1.41506928e+02  8.34e-08 1.67e-13  4.17e-11   409sBarrier solved model in 60 iterations and 409.15 seconds (131.30 work units)Optimal objective 1.41506958e+02Root crossover log...Warning: 1 variables dropped from basisWarning: 7 variables dropped from basisWarning: 3 variables dropped from basisWarning: 1 variables dropped from basisRestart crossover...  155050 DPushes remaining with DInf 2.3193758e+00               413s   45282 DPushes remaining with DInf 2.2681186e+00               418s   25378 DPushes remaining with DInf 2.8049372e+00               420s    9378 DPushes remaining with DInf 1.6338431e+01               425s    7070 DPushes remaining with DInf 1.4328665e+02               430s    6760 DPushes remaining with DInf 1.4304647e+02               435s    6540 DPushes remaining with DInf 1.4314778e+02               440s    6310 DPushes remaining with DInf 1.4419668e+02               447s    6148 DPushes remaining with DInf 1.4213751e+02               451s    5761 DPushes remaining with DInf 1.4183685e+02               458s    5460 DPushes remaining with DInf 1.4186856e+02               460s    5025 DPushes remaining with DInf 1.4190322e+02               469s    4755 DPushes remaining with DInf 1.4253893e+02               473s    4473 DPushes remaining with DInf 1.4255367e+02               477s    4243 DPushes remaining with DInf 1.4252963e+02               482s    4053 DPushes remaining with DInf 1.4253040e+02               487s    3761 DPushes remaining with DInf 1.4238763e+02               492s    3527 DPushes remaining with DInf 1.4225116e+02               497s    3367 DPushes remaining with DInf 1.4176143e+02               502s    3182 DPushes remaining with DInf 1.4158194e+02               507s    2972 DPushes remaining with DInf 1.4124914e+02               511s    2800 DPushes remaining with DInf 1.4140023e+02               516s    2629 DPushes remaining with DInf 1.4142658e+02               520s    2274 DPushes remaining with DInf 1.4088455e+02               529s    2048 DPushes remaining with DInf 1.4091375e+02               534s    1813 DPushes remaining with DInf 9.5401829e+05               539s    1638 DPushes remaining with DInf 9.5059732e+05               542s    1405 DPushes remaining with DInf 9.4984910e+05               546s     943 DPushes remaining with DInf 9.3858874e+05               553s     733 DPushes remaining with DInf 9.4386758e+05               556s     148 DPushes remaining with DInf 9.4367720e+05               562s       0 DPushes remaining with DInf 8.9608356e+05               564s    3354 PPushes remaining with PInf 5.6353371e+06               564s    2800 PPushes remaining with PInf 5.5306680e+06               566s    1182 PPushes remaining with PInf 4.4791295e+06               571s       0 PPushes remaining with PInf 3.9397902e+06               575s  Push phase complete: Pinf 3.9397902e+06, Dinf 2.9455736e+02    576sRoot simplex log...Iteration    Objective       Primal Inf.    Dual Inf.      Time   91280    1.3690781e+02   0.000000e+00   2.945574e+02    576s   91420    1.3690781e+02   0.000000e+00   1.556222e+01    580s   91700    1.3690781e+02   0.000000e+00   2.600401e+01    589s   91840    1.3690781e+02   0.000000e+00   4.294042e+02    594s   91980    1.3690780e+02   0.000000e+00   4.174520e+03    599s   92120    1.3690777e+02   0.000000e+00   7.386196e+02    604s   92270    1.3690759e+02   0.000000e+00   5.380789e+03    609s   92460    1.3690724e+02   0.000000e+00   6.821016e+06    614s   92630    1.3690620e+02   0.000000e+00   1.354219e+05    620s   92780    1.3690557e+02   0.000000e+00   3.663916e+03    625s   92950    1.3690547e+02   0.000000e+00   8.712810e+04    630s   93110    1.3690335e+02   0.000000e+00   6.271512e+05    636s   93230    1.3690312e+02   0.000000e+00   7.540669e+05    641s   93340    1.3690302e+02   0.000000e+00   8.410555e+05    647s   93440    1.3690299e+02   0.000000e+00   1.005486e+06    652s   93540    1.3690264e+02   0.000000e+00   4.220777e+05    656s   93640    1.3690173e+02   0.000000e+00   5.300029e+06    660s   93850    1.3690115e+02   0.000000e+00   5.156432e+05    670s   93950    1.3690053e+02   0.000000e+00   1.634074e+06    676s   94050    1.3689991e+02   0.000000e+00   4.538791e+03    682s   94150    1.3689975e+02   0.000000e+00   1.494716e+05    691s   94250    1.3689972e+02   0.000000e+00   7.784185e+04    695s   94370    1.3689950e+02   0.000000e+00   4.034519e+05    700s   94490    1.3689949e+02   0.000000e+00   2.884548e+05    706s   94610    1.3689934e+02   0.000000e+00   2.229441e+06    711s   94740    1.3689931e+02   0.000000e+00   1.875407e+06    716s   94860    1.3689918e+02   0.000000e+00   1.118993e+06    721s   94980    1.3689913e+02   0.000000e+00   1.795967e+06    726s   95100    1.3689909e+02   0.000000e+00   1.072492e+06    731s   95220    1.3689903e+02   0.000000e+00   8.564352e+05    736s   95340    1.3689861e+02   0.000000e+00   2.103654e+03    741s   95480    1.3689849e+02   0.000000e+00   1.925698e+05    747s   95610    1.3689846e+02   0.000000e+00   8.037324e+05    753s   95740    1.3689843e+02   0.000000e+00   3.862034e+05    760s   95870    1.3689836e+02   0.000000e+00   1.007762e+06    768s   95990    1.3689795e+02   0.000000e+00   3.254240e+07    778s   96110    1.3689781e+02   0.000000e+00   1.371776e+06    786s   96250    1.3689778e+02   0.000000e+00   5.009658e+06    793s   96400    1.3689752e+02   0.000000e+00   5.652216e+06    801s   96540    1.3689749e+02   0.000000e+00   2.522830e+05    807s   96690    1.3689747e+02   0.000000e+00   3.422328e+05    819s   96870    1.3689686e+02   0.000000e+00   8.157110e+04    835s   96970    1.3689680e+02   0.000000e+00   1.182152e+05    842s   97080    1.3689668e+02   0.000000e+00   2.285819e+05    849s   97190    1.3689667e+02   0.000000e+00   4.367865e+05    857s   97340    1.3689615e+02   0.000000e+00   1.948211e+06    869s   97490    1.3689534e+02   0.000000e+00   1.011943e+07    878s   97680    1.3689269e+02   0.000000e+00   1.651718e+03    886s   97840    1.3689262e+02   0.000000e+00   9.189352e+04    896s

What would you suggest so that I can force Gurobi to try to find the optimal solution for each value of ε? So far, I have 5788538 constraints and 33964001 decision variables, out of which 1000 are binary. Do you think that Gurobi has trouble finding the optimal solution for such a model?

Could it be the case that my problem is subject to numerical instability?

Any advice would be more than welcome.

Thank you.

Hello there,

as a side comment relevant to the discussion above, to reduce the number of d.v. and constraints, respectively, I tried to remove the constraints, which contained the binary quantities, and solve an LP instead. This version of the original problem makes sense only for the case where ε=0. In this case, I expect to obtain exactly the same response solving the LP with the solution obtained from the MILP.

As it turns out, though, for a horizon K=200, LP cannot provide me a feasible solution, either.

I also switched to a much stronger PC, and I have left it running for nearly a day, but still Gurobi is still running.

I attach a part of the log file for the LP.

Set parameter UsernameSet parameter Method to value 3Set parameter Crossover to value 0Set parameter Presolve to value 2Academic license - for non-commercial use only - expires 2025-01-15Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 10.0 (19044.2))CPU model: Intel(R) Core(TM) i9-10980XE CPU @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]Thread count: 18 physical cores, 36 logical processors, using up to 18 threadsOptimize a model with 5728812 rows, 33483000 columns and 20773610 nonzerosModel fingerprint: 0xab138f5fCoefficient statistics:  Matrix range     [8e-03, 7e+01]  Objective range  [8e-03, 8e-03]  Bounds range     [1e+01, 3e+03]  RHS range        [4e-03, 5e+03]Presolve removed 4786349 rows and 32760936 columns (presolve time = 6s) ...Presolve removed 5222063 rows and 33168554 columns (presolve time = 10s) ...Presolve removed 5398704 rows and 33168554 columns (presolve time = 16s) ...Presolve removed 5398704 rows and 33168554 columnsPresolve time: 19.02sPresolved: 330108 rows, 314446 columns, 1541173 nonzerosConcurrent LP optimizer: primal simplex, dual simplex, and barrierShowing barrier log only...Warning: Concurrent optimizer requires crossover - forcing it onElapsed ordering time = 5sOrdering time: 9.55sBarrier statistics: AA' NZ     : 2.559e+06 Factor NZ  : 1.170e+08 (roughly 1.2 GB of memory) Factor Ops : 4.201e+11 (roughly 1 second per iteration) Threads    : 16                  Objective                ResidualIter       Primal          Dual         Primal    Dual     Compl     Time   0  -1.36228938e+07 -5.84032845e+06  3.34e+06 2.49e-03  7.00e+03    32s   1  -4.85496197e+06 -5.33746124e+06  1.19e+06 5.16e-02  2.58e+03    33s   2  -1.02199515e+06 -3.07473539e+06  2.51e+05 5.00e-15  5.92e+02    35s   3  -2.68729925e+05 -1.14055368e+06  6.64e+04 8.47e-16  1.54e+02    37s   4  -1.16316785e+05 -4.71436607e+05  2.90e+04 1.05e-15  6.05e+01    39s   5  -5.82280927e+04 -2.39332011e+05  1.47e+04 1.49e-15  2.90e+01    41s   6  -3.27473707e+04 -1.31532010e+05  8.43e+03 3.47e-15  1.55e+01    43s   7  -1.65170676e+04 -8.74630966e+04  4.44e+03 2.84e-15  8.53e+00    45s   8  -9.25344329e+03 -5.33385694e+04  2.65e+03 2.46e-15  4.86e+00    46s   9  -4.74520613e+03 -3.32345406e+04  1.53e+03 2.11e-15  2.79e+00    48s  10  -2.53825441e+03 -2.74463357e+04  9.81e+02 2.69e-15  2.02e+00    49s  11  -1.28385001e+03 -1.74961915e+04  6.64e+02 4.53e-15  1.32e+00    51s  12   2.49569840e+02 -9.63840698e+03  2.63e+02 4.19e-15  6.59e-01    53s  13   7.05573576e+02 -5.34815464e+03  1.05e+02 4.76e-15  3.43e-01    55s  14   7.54448303e+02 -2.59927525e+03  3.38e+01 5.20e-15  1.63e-01    57s  15   6.11320117e+02 -1.59257273e+03  1.48e+01 4.48e-15  9.94e-02    58s  16   3.90384864e+02 -5.23774867e+02  6.67e+00 5.31e-15  4.07e-02    60s  17   2.73083377e+02 -1.66152446e+02  3.29e+00 3.93e-15  1.93e-02    62s  18   1.93370850e+02 -1.42198061e+01  1.41e+00 3.65e-15  8.96e-03    63s  19   1.57184904e+02  4.84961549e+01  7.35e-01 2.62e-15  4.66e-03    65s  20   1.38357689e+02  8.07257485e+01  4.15e-01 2.21e-15  2.46e-03    67s  21   1.26904076e+02  9.44426891e+01  2.27e-01 1.30e-15  1.38e-03    69s  22   1.20916303e+02  1.00388916e+02  1.32e-01 8.76e-16  8.68e-04    71s  23   1.17476352e+02  1.04815043e+02  7.84e-02 1.11e-15  5.33e-04    75s  24   1.15443649e+02  1.08333087e+02  4.76e-02 5.73e-16  3.00e-04    80s  25   1.14183473e+02  1.10776209e+02  2.88e-02 4.83e-16  1.45e-04    85s  26   1.13340696e+02  1.11381577e+02  1.65e-02 4.72e-16  8.33e-05    89s  27   1.12908588e+02  1.11642475e+02  1.01e-02 5.23e-16  5.37e-05    93s  28   1.12621031e+02  1.11880038e+02  6.00e-03 3.96e-13  3.14e-05    98s  29   1.12459987e+02  1.11999342e+02  3.71e-03 7.52e-13  1.95e-05   102s  30   1.12346172e+02  1.12071032e+02  2.11e-03 8.65e-13  1.16e-05   106s  31   1.12294133e+02  1.12136224e+02  1.38e-03 7.71e-13  6.71e-06   111s  32   1.12250497e+02  1.12159344e+02  7.74e-04 6.60e-13  3.87e-06   115s  33   1.12227002e+02  1.12176405e+02  4.48e-04 4.73e-13  2.15e-06   120s  34   1.12214870e+02  1.12185059e+02  2.83e-04 3.23e-13  1.27e-06   124s  35   1.12205286e+02  1.12187640e+02  1.56e-04 2.59e-13  7.50e-07   129s  36   1.12202094e+02  1.12189629e+02  1.12e-04 2.10e-13  5.30e-07   133s  37   1.12199912e+02  1.12192118e+02  8.15e-05 1.42e-13  3.34e-07   137s  38   1.12197049e+02  1.12192953e+02  4.27e-05 1.06e-13  1.76e-07   142s  39   1.12195639e+02  1.12193359e+02  2.33e-05 8.08e-14  9.76e-08   147s  40   1.12194823e+02  1.12193635e+02  1.21e-05 5.51e-14  5.08e-08   151s  41   1.12194516e+02  1.12193802e+02  7.86e-06 3.17e-14  3.07e-08   156s  42   1.12194305e+02  1.12193841e+02  5.00e-06 2.48e-14  1.99e-08   160s  43   1.12194187e+02  1.12193891e+02  3.39e-06 1.44e-14  1.28e-08   164s  44   1.12194080e+02  1.12193908e+02  1.95e-06 9.44e-15  7.41e-09   168s  45   1.12194015e+02  1.12193918e+02  1.07e-06 6.43e-15  4.17e-09   173s  46   1.12193983e+02  1.12193923e+02  6.46e-07 4.54e-15  2.58e-09   178s  47   1.12193963e+02  1.12193928e+02  3.75e-07 2.83e-15  1.51e-09   182s  48   1.12193952e+02  1.12193931e+02  2.24e-07 1.65e-15  8.90e-10   187sBarrier solved model in 48 iterations and 187.27 seconds (104.59 work units)Optimal objective 1.12193952e+02Crossover log...  139696 DPushes remaining with DInf 0.0000000e+00               188s    2723 DPushes remaining with DInf 0.0000000e+00               190s       0 DPushes remaining with DInf 0.0000000e+00               192s     554 PPushes remaining with PInf 2.8812486e-01               192s       0 PPushes remaining with PInf 2.6714164e-02               193s  Push phase complete: Pinf 2.6714164e-02, Dinf 1.4622707e-01    193sIteration    Objective       Primal Inf.    Dual Inf.      Time  116685    1.1219393e+02   0.000000e+00   1.462271e-01    193s  116874    1.1219393e+02   2.254370e+00   0.000000e+00    195s  117174    1.1219393e+02   4.223246e+01   0.000000e+00    200s  117454    1.1219393e+02   5.389088e+00   0.000000e+00    206s  117744    1.1219393e+02   3.938426e+01   0.000000e+00    212s  117884    1.1219393e+02   4.837359e+00   0.000000e+00    216s  118174    1.1219393e+02   6.655419e+00   0.000000e+00    222s  118304    1.1219393e+02   8.920969e+01   0.000000e+00    226s  118584    1.1219393e+02   2.106979e+01   0.000000e+00    232s  118714    1.1219393e+02   3.197743e+00   0.000000e+00    235s  118974    1.1219393e+02   2.024033e+01   0.000000e+00    242s  119084    1.1219393e+02   1.378090e+01   0.000000e+00    247s  119354    1.1219393e+02   1.757188e+01   0.000000e+00    253s  119484    1.1219393e+02   4.493260e+01   0.000000e+00    256s  119724    1.1219393e+02   1.174536e+02   0.000000e+00    263s  119844    1.1219393e+02   3.977736e+01   0.000000e+00    267s  119954    1.1219393e+02   3.102618e+01   0.000000e+00    271s  120064    1.1219393e+02   8.474358e+00   0.000000e+00    275s  120304    1.1219393e+02   5.400832e+00   0.000000e+00    284s  120414    1.1219393e+02   6.832231e+01   0.000000e+00    289s  120534    1.1219393e+02   8.862741e+00   0.000000e+00    292s  120644    1.1219393e+02   3.257071e+01   0.000000e+00    297s  120754    1.1219393e+02   4.985082e+01   0.000000e+00    301s  120864    1.1219393e+02   2.238688e+01   0.000000e+00    305s  121114    1.1219393e+02   2.705567e+01   0.000000e+00    312s  121224    1.1219393e+02   2.520392e+01   0.000000e+00    317s  121334    1.1219393e+02   9.999440e+00   0.000000e+00    321s  121444    1.1219393e+02   9.164429e+00   0.000000e+00    325s  121684    1.1219393e+02   5.715591e+00   0.000000e+00    334s  121804    1.1219393e+02   1.193015e+01   0.000000e+00    338s  121934    1.1219393e+02   4.972224e+00   0.000000e+00    342s  122064    1.1219393e+02   1.236829e+01   0.000000e+00    346s  122184    1.1219393e+02   2.970491e+01   0.000000e+00    351s  122324    1.1219393e+02   2.837768e+01   0.000000e+00    355s  122624    1.1219393e+02   2.193168e+01   0.000000e+00    364s  122824    1.1219393e+02   1.072201e+01   0.000000e+00    368s  122954    1.1219393e+02   1.284792e+01   0.000000e+00    372s  123094    1.1219393e+02   4.519194e+00   0.000000e+00    376s
704883    2.9073335e+00   3.046197e+10   0.000000e+00  84473s  704965    2.9485023e+00   3.224106e+09   0.000000e+00  84485s  705047    3.0058571e+00   6.477419e+09   0.000000e+00  84497s  705129    3.0529927e+00   5.247282e+09   0.000000e+00  84509s  705211    3.0875018e+00   7.677923e+09   0.000000e+00  84522s  705293    3.1417447e+00   6.748626e+09   0.000000e+00  84534s  705375    3.2089049e+00   8.996742e+09   0.000000e+00  84546s  705457    3.2552455e+00   2.183582e+09   0.000000e+00  84560s  705539    3.3260879e+00   3.983228e+09   0.000000e+00  84574s  705621    3.3696096e+00   3.002335e+09   0.000000e+00  84586s  705703    3.4143499e+00   2.849120e+09   0.000000e+00  84599s  705785    3.4789302e+00   1.342194e+10   0.000000e+00  84612s  705867    3.5314868e+00   5.890742e+10   0.000000e+00  84625s  705949    3.5758631e+00   5.415225e+09   0.000000e+00  84637s  706031    3.6296801e+00   3.719260e+09   0.000000e+00  84650s  706113    3.6727097e+00   3.721645e+09   0.000000e+00  84662s  706195    3.7206641e+00   3.011163e+09   0.000000e+00  84674s  706277    3.7558270e+00   1.596684e+10   0.000000e+00  84685s  706359    3.7985990e+00   4.542603e+09   0.000000e+00  84697s  706441    3.8583435e+00   3.756144e+09   0.000000e+00  84710s  706523    4.0361014e+00   5.696311e+09   0.000000e+00  84722s  706605    4.0830197e+00   1.886730e+11   0.000000e+00  84734s  706687    4.1343751e+00   5.683547e+09   0.000000e+00  84747s  706769    4.1778727e+00   6.165751e+09   0.000000e+00  84760s  706851    4.7204975e+00   3.448853e+09   0.000000e+00  84773s  706933    4.9771278e+00   4.416990e+09   0.000000e+00  84785s  707015    5.2292974e+00   4.164623e+10   0.000000e+00  84798s  707097    5.2701552e+00   1.239990e+10   0.000000e+00  84810s  707179    5.3151071e+00   5.271186e+09   0.000000e+00  84823s  707261    5.3648799e+00   5.112130e+09   0.000000e+00  84835s  707343    5.4246979e+00   1.535598e+10   0.000000e+00  84848s  707425    5.5130759e+00   5.223042e+10   0.000000e+00  84861s  707507    5.5502431e+00   1.031650e+10   0.000000e+00  84874s  707589    5.6003449e+00   1.668026e+10   0.000000e+00  84887s  707671    5.6535677e+00   3.864215e+09   0.000000e+00  84898s  707753    5.6787237e+00   1.441807e+10   0.000000e+00  84910s

Obviously, my problem is prone to scalability and even casting the original MILP problem to an LP equivalent version, the problem still pertains. Could you please tell me how I should proceed to solve these two problems, namely the LP first and later the MILP?

It seems to me that playing with the parameters will not change significantly the performance of the optimizer. Or, it could work for a single value of ε, while for a different value of ε, I need again to select a new pair of parameters.

Could the automatic parameter tuning tool be considered? Unfortunately, I am using Matlab and If I recall correctly, this toolbox cannot be invoked from the Matlab environment.

Kind Regards,

Antonis

• Gurobi Staff

Hi Antonis,

Since your model is a significant challenge for the simplex algorithms, I still think avoiding simplex is the way to go, i.e., Method=2, Crossover=0, NodeMethod=2. I do not think that tuning simplex parameters will significantly improve your situation.

The question is why do you get the same solution for each epsilon value? Where does the progress get stuck when using the parameters above? Does it hit the time limit or stop before that? Your additional parameters Presolve=2, DegenMoves=0, and MIPFocus=2 make sense here and can be beneficial.

Usually, there is one direction for the epsilon values (low to high, or high to low) where the solution of the previous iteration is feasible for the current one, but potentially can be improved because of the relaxed eps value.

As you already mentioned, the tuning tool is not available in Matlab but you can run it from the command line (grbtune) with your model exported in Matlab as an MPS file. Still, the runtimes are very long, so you would need a large compute cluster to test 100+ parameter settings.

Mario

Hello Mario,

I experimented a little bit with the constraints, and I realized that one constraint was the source of the problem for the LP. When I deactivated this constraint, I was able to solve the LP in less than 5 minutes.

I deactivated the same constraint for the MILP as well and again, when I solve the MILP for different values of epsilon, I also obtain the same solution. Altough the optimization deems that this solution is feasible, when I provide it as input to my simulator, then I get a message that I violate some equations in the simulator.

The behavior that I am expecting from the optimization is that while I increase the value of epsilon, the corresponding value of my objective function will decrease until it converges around a value. This means that after a point when I increase the value of epsilon, I will not experience any further reduction in the value of objective value.

Maybe there is something wrong going on with the branching, and I haven't expressed the dynamics in the optimization properly.

Do you have any other idea why I could be getting this behavior?

I attach a log from the MILP when setting epsilon=10

Set parameter UsernameSet parameter Method to value 3Set parameter BarHomogeneous to value 1Set parameter CrossoverBasis to value 1Set parameter MIPFocus to value 2Set parameter Presolve to value 2Academic license - for non-commercial use only - expires 2025-01-15Gurobi Optimizer version 11.0.0 build v11.0.0rc2 (win64 - Windows 10.0 (19044.2))CPU model: Intel(R) Core(TM) i9-10980XE CPU @ 3.00GHz, instruction set [SSE2|AVX|AVX2|AVX512]Thread count: 18 physical cores, 36 logical processors, using up to 18 threadsOptimize a model with 10467386 rows, 61304216 columns and 37558905 nonzerosModel fingerprint: 0x34fdcf2aVariable types: 61303216 continuous, 1000 integer (1000 binary)Coefficient statistics:  Matrix range     [4e-03, 7e+01]  Objective range  [8e-03, 8e-03]  Bounds range     [1e+00, 3e+03]  RHS range        [1e-02, 5e+03]Presolve removed 63004 rows and 52859731 columns (presolve time = 5s) ...Presolve removed 6734816 rows and 57505595 columns (presolve time = 10s) ...Presolve removed 8177870 rows and 59261607 columns (presolve time = 15s) ...Presolve removed 8233497 rows and 59294014 columnsPresolve time: 18.12sPresolved: 2233889 rows, 2010202 columns, 10663726 nonzerosVariable types: 2008028 continuous, 2174 integer (25 binary)Root relaxation presolve removed 2071 rows and 1616 columnsRoot relaxation presolved: 669564 rows, 637506 columns, 2962093 nonzerosConcurrent LP optimizer: primal simplex, dual simplex, and barrierShowing barrier log only...Root barrier log...Elapsed ordering time = 10sElapsed ordering time = 15sOrdering time: 22.23sBarrier statistics: Dense cols : 18 AA' NZ     : 4.663e+06 Factor NZ  : 2.377e+08 (roughly 2.4 GB of memory) Factor Ops : 8.163e+11 (roughly 1 second per iteration) Threads    : 15                  Objective                ResidualIter       Primal          Dual         Primal    Dual     Compl     Time   0  -4.60116967e+06 -5.00305391e+08  7.23e+04 1.87e-01  5.75e+03   150s   1  -1.82372639e+06 -4.08257762e+08  2.85e+04 1.76e-01  2.28e+03   153s   2  -5.37871013e+05 -2.18979865e+08  8.47e+03 2.93e-14  6.77e+02   156s   3  -1.37824596e+05 -8.93114191e+07  2.21e+03 4.06e-14  1.83e+02   160s   4  -4.69408034e+04 -3.31266220e+07  7.89e+02 5.02e-14  5.44e+01   165s   5  -1.55225856e+04 -9.73601567e+06  2.97e+02 3.94e-14  1.49e+01   169s   6  -4.05641450e+03 -3.60961181e+06  1.17e+02 7.69e-14  4.58e+00   174s   7  -1.30515951e+02 -1.53208638e+06  5.48e+01 5.33e-14  1.72e+00   179s   8   1.24625492e+03 -9.99173435e+05  3.27e+01 1.23e-13  1.02e+00   183s   9   1.87569665e+03 -5.07355059e+05  2.22e+01 3.72e-13  5.58e-01   187s  10   2.40389344e+03 -3.72505803e+05  1.25e+01 3.36e-13  3.61e-01   191s  11   2.56368127e+03 -3.00135566e+05  9.17e+00 1.99e-13  2.80e-01   199s  12   2.62198018e+03 -2.29297226e+05  7.81e+00 2.54e-13  2.19e-01   206s  13   2.70948892e+03 -1.74765804e+05  5.48e+00 3.41e-13  1.60e-01   215s  14   2.73610093e+03 -1.36125043e+05  4.73e+00 2.94e-13  1.27e-01   223s  15   2.75614471e+03 -1.09159828e+05  3.89e+00 4.50e-13  1.02e-01   232s  16   2.76162563e+03 -1.05117001e+05  3.53e+00 4.13e-13  9.58e-02   240s  17   2.76803684e+03 -7.25704922e+04  2.67e+00 2.83e-13  6.69e-02   248s  18   2.75851952e+03 -4.72568435e+04  2.03e+00 4.31e-13  4.50e-02   257s  19   2.72648929e+03 -3.03455920e+04  1.45e+00 9.32e-13  2.95e-02   266s  20   2.66552198e+03 -2.58956497e+04  1.07e+00 7.03e-13  2.41e-02   274s  21   2.63827245e+03 -2.29330412e+04  9.62e-01 6.30e-13  2.14e-02   283s  22   2.54922058e+03 -1.58752835e+04  7.19e-01 4.69e-13  1.53e-02   292s  23   2.46198572e+03 -1.49490023e+04  5.87e-01 4.47e-13  1.39e-02   301s  24   2.39065473e+03 -1.23688661e+04  5.05e-01 3.86e-13  1.17e-02   310s  25   2.25980492e+03 -9.17221754e+03  3.96e-01 2.93e-13  8.96e-03   319s  26   2.08291170e+03 -8.27891484e+03  2.99e-01 2.82e-13  7.81e-03   328s  27   1.97718735e+03 -7.08563931e+03  2.62e-01 3.59e-13  6.80e-03   337s  28   1.66620844e+03 -3.94583185e+03  1.78e-01 1.74e-13  4.20e-03   346s  29   1.33655554e+03 -2.70601395e+03  1.25e-01 3.38e-13  2.98e-03   354s  30   1.09688075e+03 -2.27489586e+03  9.28e-02 4.54e-13  2.43e-03   364s  31   8.88186559e+02 -1.90925388e+03  6.78e-02 3.41e-13  1.98e-03   374s  32   6.77886726e+02 -6.28800247e+02  4.54e-02 1.28e-12  9.48e-04   384s  33   5.40294178e+02 -4.15331106e+02  3.23e-02 9.31e-13  6.86e-04   393s  34   4.27406523e+02 -3.09985423e+02  2.22e-02 9.64e-13  5.19e-04   402s  35   3.33552255e+02 -2.07205940e+02  1.35e-02 1.38e-12  3.72e-04   411s  36   2.91861118e+02 -1.82374324e+01  1.02e-02 1.35e-12  2.18e-04   420s  37   2.40955407e+02  5.03769909e+01  6.56e-03 2.24e-13  1.34e-04   428s  38   2.05071575e+02  8.44590327e+01  4.12e-03 2.47e-13  8.41e-05   437s  39   1.86920682e+02  1.03766816e+02  2.93e-03 4.36e-13  5.80e-05   446s  40   1.77924171e+02  1.12007456e+02  2.34e-03 3.39e-13  4.59e-05   453s  41   1.67985135e+02  1.19995406e+02  1.71e-03 6.54e-13  3.33e-05   461s  42   1.60068118e+02  1.27305637e+02  1.21e-03 1.26e-12  2.28e-05   469s  43   1.53883514e+02  1.31992218e+02  8.22e-04 9.92e-13  1.52e-05   478s  44   1.49735091e+02  1.35118811e+02  5.63e-04 6.34e-13  1.01e-05   487s  45   1.47198747e+02  1.37113541e+02  4.05e-04 6.45e-13  7.02e-06   496s  46   1.44677257e+02  1.37885403e+02  2.46e-04 5.44e-13  4.67e-06   504s  47   1.43546727e+02  1.38638243e+02  1.76e-04 8.17e-13  3.36e-06   513s  48   1.42543497e+02  1.39563462e+02  1.13e-04 8.89e-13  2.05e-06   522s  49   1.41897662e+02  1.39972108e+02  7.34e-05 8.47e-13  1.32e-06   531s  50   1.41490866e+02  1.40189750e+02  4.82e-05 1.27e-12  8.85e-07   540s  51   1.41219168e+02  1.40418615e+02  3.12e-05 1.29e-12  5.44e-07   549s  52   1.41032767e+02  1.40536129e+02  1.94e-05 6.82e-13  3.36e-07   558s  53   1.40923357e+02  1.40622329e+02  1.25e-05 3.92e-13  2.03e-07   567s  54   1.40870565e+02  1.40675002e+02  9.09e-06 2.97e-13  1.32e-07   575s  55   1.40819335e+02  1.40698527e+02  5.78e-06 1.90e-13  8.13e-08   584s  56   1.40791139e+02  1.40715430e+02  3.94e-06 2.19e-13  5.09e-08   593s  57   1.40771099e+02  1.40722062e+02  2.60e-06 1.77e-13  3.28e-08   602s  58   1.40760492e+02  1.40726969e+02  1.89e-06 8.56e-14  2.24e-08   611s  59   1.40751529e+02  1.40729140e+02  1.28e-06 1.02e-13  1.49e-08   620s  60   1.40744575e+02  1.40730520e+02  7.95e-07 5.80e-14  9.30e-09   629s  61   1.40740548e+02  1.40731790e+02  5.17e-07 4.00e-14  5.78e-09   638s  62   1.40738363e+02  1.40732123e+02  3.64e-07 1.83e-14  4.10e-09   646s  63   1.40736700e+02  1.40732563e+02  2.45e-07 3.63e-14  2.70e-09   655s  64   1.40735670e+02  1.40732898e+02  1.71e-07 5.90e-14  1.80e-09   665s  65   1.40734965e+02  1.40733067e+02  1.19e-07 2.92e-14  1.23e-09   674s  66   1.40734544e+02  1.40733166e+02  8.80e-08 3.30e-14  8.91e-10   683s  67   1.40734202e+02  1.40733216e+02  6.26e-08 4.09e-14  6.35e-10   692s  68   1.40733965e+02  1.40733274e+02  4.49e-08 4.39e-14  4.44e-10   702s  69   1.40733783e+02  1.40733319e+02  3.12e-08 8.97e-14  2.97e-10   714s  70   1.40733647e+02  1.40733339e+02  4.29e-07 6.82e-14  1.97e-10   728s  71   1.40733564e+02  1.40733355e+02  3.01e-07 4.62e-14  1.35e-10   741s  72   1.40733522e+02  1.40733363e+02  2.65e-07 3.90e-14  1.03e-10   753s  73   1.40733506e+02  1.40733365e+02  2.38e-07 3.57e-14  9.14e-11   763s  74   1.40733499e+02  1.40733365e+02  2.25e-07 2.72e-14  8.66e-11   773s  75   1.40733472e+02  1.40733367e+02  2.59e-07 2.27e-14  6.84e-11   784s  76   1.40733452e+02  1.40733371e+02  2.36e-07 6.20e-14  5.30e-11   794s  77   1.40733444e+02  1.40733372e+02  2.59e-07 5.32e-14  4.75e-11   804s  78   1.40733433e+02  1.40733373e+02  2.13e-07 4.24e-14  3.93e-11   814s  79   1.40733421e+02  1.40733374e+02  1.72e-07 2.19e-14  3.08e-11   824s  80   1.40733414e+02  1.40733375e+02  1.45e-07 2.61e-14  2.59e-11   834sBarrier solved model in 80 iterations and 833.76 seconds (454.25 work units)Optimal objective 1.40733414e+02Root crossover log...Warning: 1 variables dropped from basisWarning: 1 variables dropped from basisRestart crossover...  465564 DPushes remaining with DInf 3.2886588e-01               837s   31539 DPushes remaining with DInf 2.4721683e-01               840s   14696 DPushes remaining with DInf 2.4141226e-01               845s   11336 DPushes remaining with DInf 2.4141226e-01               850s    7976 DPushes remaining with DInf 2.4141226e-01               855s    5035 DPushes remaining with DInf 2.4141226e-01               860s    2516 DPushes remaining with DInf 2.4141226e-01               866s    1256 DPushes remaining with DInf 2.4086236e-01               871s       0 DPushes remaining with DInf 2.4086236e-01               876s     740 PPushes remaining with PInf 1.4109479e-03               876s       0 PPushes remaining with PInf 2.5412004e-02               878s  Push phase complete: Pinf 2.5412004e-02, Dinf 7.3294286e+00    878sRoot simplex log...Iteration    Objective       Primal Inf.    Dual Inf.      Time  263186    1.4073444e+02   0.000000e+00   7.329429e+00    878s  263483    1.4073338e+02   0.000000e+00   0.000000e+00    880sSolved with barrier  263483    1.4073338e+02   0.000000e+00   0.000000e+00    882sRoot relaxation: objective 1.407334e+02, 263483 iterations, 765.34 seconds (394.07 work units)    Nodes    |    Current Node    |     Objective Bounds      |     Work Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time     0     0  140.73338    0    1          -  140.73338      -     -  895sH    0     0                     140.7333794  140.73338  0.00%     -  900sExplored 1 nodes (267145 simplex iterations) in 1418.30 seconds (476.49 work units)Thread count was 18 (of 36 available processors)Solution count 2: 140.733 140.733 Optimal solution found (tolerance 1.00e-04)Warning: max constraint violation (2.9022e-06) exceeds toleranceWarning: max bound violation (1.2568e-06) exceeds toleranceBest objective 1.407333794148e+02, best bound 1.407333794148e+02, gap 0.0000%Elapsed time is 1457.046333 seconds.

Thank you in advance.

Kind Regards,

Antonis

• Gurobi Staff

As you can see at the end of the solver output, the solution has slight violations in the order of 1e-6. Does your simulator account for tolerances, especially when checking equalities?

If you obtain the same solutions for increasing epsilon values, then you are probably already at the point where you cannot improve anymore. Can you construct a counter-example, i.e., a better solution for a higher eps value that the solver cannot find?

Sometimes it helps to write out the model as a readable file with model.write("model.lp"), then you can check whether your simulator and your model consider the same constraints. For example, if the simulator says that the solution is not feasible, what about the corresponding constraint in the model?

Dear Mario,

the difficult part with my simulator is that I cannot find the optimal value of the objective function of interest, since the combinations increase exponentially as I increase the value of epsilon. Just as an indication, in my case, I have 5^25 candidate combinations. What I want is to find a high-quality solution that can be close to the optimal one through the optimization framework, without having to analytically compute each possible combination in a brute force format.

For example, when ε=0, I get only 1 possible combination.
When ε=10, I get 26 combinations and so on and so forth.

Regarding what you said, I have made some comparisons between the solution obtained from the optimization.

1. For ε=0, the solution (derived pair of actual school start times - this is reflected in my binary variables) perfectly coincides between the simulation and the optimization and is FEASIBLE for both of them.

2. For ε=10, the solution obtained from the optimization is FEASIBLE and when inserted to the simulator I get an INFEASIBILITY.

I get a similar behaviour for different values of ε. However, as I stated before, I cannot easily construct a counter-example in the simulator, because it would entail the analytic evaluation of a very large number of combinations.

What would you suggest I try to identify why the optimization gives a solution that is later infeasible in the simulator?

I also did what you stated in terms of the readable file and both the optimization and the simulation consider the same constraints.

Thank you.

Antonis

• Gurobi Staff

Hi Antonis,

I think you really need to dig deeper into case 2, where the solver returns a feasible solution, and the simulator says this is infeasible. I am not aware of the details of your simulator, but can you adapt it to give you more information on why the solution is infeasible? Is it just a numerical issue that the simulator realizes that some constraints are not satisfied by a very small amount?

The solver will give you a solution that satisfies all constraints and bounds in the model (subject to tolerances or small violations). If the simulator detects infeasibility, not just by a small amount, then some constraints might be missing in the model.

It often helps to reduce the problem instance as much as possible in terms of size, then debugging is usually easier.

Hi Mario,

I dug into case 2, and I also considered many other cases considering different values of epsilon as input to the solver, and I realized that there were some mistakes in terms of the simulation horizon. At this point, I solve a separate MILP for the following values, ε=0,10,20,...50. The solution I obtain from the optimization is later fed to the simulator to check if I get feasibility issues. I do not face a problem up to ε=40. However, when ε=50, the solution I get from optimization leads to Infeasibility in the simulator.

I checked why I obtained an infeasibility in the simulator, and it is not a numerical issue. Let us say that I consider a simulation horizon of K=360 time steps in the simulation and the optimization alike. When I run the simulation (for ε=50) considering as input the solution from the optimization, a specific constraint is violated at the time step, k=83. The strange thing is that for the previous values of epsilon, I didn't face any problems, and none of the constraints of the simulation was violated. However, I am still trying to figure out what is going wrong with the current value of epsilon.

Any idea why this might be happening? Do I need to play with the parameter tuning part, or this issue does not have to do with that?

Thank you.

Antonis

Hi Mario,

I am not sure if you read my response, but do you have any suggestions related to this issue?

Antonis

• Gurobi Staff

I do not think that this is related to solver parameters.

You said that you considered all time steps both in your simulator and in your model. If your simulator says that the solution is infeasible for k=83, then how are those values different from the solution values for k=83 in the solver's result?

Mario,

maybe I did not express my concern properly.

The original optimization problem is a Mixed Integer Nonlinear Program (MINLP). Therefore, the dynamics associated with the traffic simulator have a nonlinear and nonconvex nature. As these problems are difficult to handle with nonlinear optimization solvers, we have pursued a relaxation procedure to approximate each nonconvex and nonlinear constraint of the original MINLP with a block of linear constraints. In this sense, we obtain a Mixed Integer Linear Program (MILP) in which the ε-constraint technique is employed. This is why I mentioned the notion of ε-constraint in the conversation.

So, the conversation that has already taken place in this post concerns the MILP, after a relaxation procedure has been performed. Therefore, the solution I obtain from the MILP is an approximate one with respect to the original problem. This is why the solution obtained from the MILP violates a specific constraint when being fed to the nonlinear and nonconvex simulator.

Hello there,

does anybody have an idea why I get such a behavior?

Thank you.

Antonis

• Gurobi Staff

Well, this is indeed an important information. If your MILP is just an approximation of your original MINLP, then it is not surprising that there are MILP solutions that violate constraints of your original model. The solver just does not know the original MINLP.

There are several options:

• You improve your MILP approximation of the original MINLP.
• You use lazy constraints in a callback to add further constraints to the MILP dynamically, or just reject a solution that you checked in a callback (probably with your simulator) and that turned out to be infeasible.
• You model and solve the original MINLP with Gurobi. The newest v11 includes an exact global MINLP solver.

Dear Mario,

I really appreciate these suggestions. I will have a look and I hope that some of them might be able to resolve the current problem I face.

Thank you.

Antonis