• 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 TimeLimit to value 36000
Set parameter Method to value 2
Set parameter CrossoverBasis to value 1
Set parameter DegenMoves to value 0
Set parameter MIPFocus to value 2
Set parameter NodeMethod to value 2
Set parameter Presolve to value 2
Gurobi 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 threads

Optimize a model with 5788538 rows, 33964001 columns and 20903685 nonzeros
Model fingerprint: 0x42bb536f
Variable 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 columns
Presolve time: 16.61s
Presolved: 1223992 rows, 1104223 columns, 5898957 nonzeros
Variable types: 1102060 continuous, 2163 integer (0 binary)
Root relaxation presolve removed 1018 rows and 879 columns
Root relaxation presolved: 300131 rows, 289373 columns, 1349671 nonzeros

Root barrier log...

Ordering time: 7.09s

Barrier 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)

Objective                Residual
Iter       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   409s

Barrier solved model in 60 iterations and 409.15 seconds (131.30 work units)
Optimal objective 1.41506958e+02

Root crossover log...

Warning: 1 variables dropped from basis
Warning: 7 variables dropped from basis
Warning: 3 variables dropped from basis
Warning: 1 variables dropped from basis

Restart 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    576s

Root 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 Method to value 3
Set parameter Crossover to value 0
Set parameter Presolve to value 2
Gurobi 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 threads

Optimize a model with 5728812 rows, 33483000 columns and 20773610 nonzeros
Model fingerprint: 0xab138f5f
Coefficient 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 columns
Presolve time: 19.02s
Presolved: 330108 rows, 314446 columns, 1541173 nonzeros

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

Warning: Concurrent optimizer requires crossover - forcing it on
Elapsed ordering time = 5s
Ordering time: 9.55s

Barrier 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)

Objective                Residual
Iter       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   187s

Barrier solved model in 48 iterations and 187.27 seconds (104.59 work units)
Optimal objective 1.12193952e+02

Crossover 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    193s

Iteration    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 Method to value 3
Set parameter BarHomogeneous to value 1
Set parameter CrossoverBasis to value 1
Set parameter MIPFocus to value 2
Set parameter Presolve to value 2
Gurobi 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 threads

Optimize a model with 10467386 rows, 61304216 columns and 37558905 nonzeros
Model fingerprint: 0x34fdcf2a
Variable 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 columns
Presolve time: 18.12s
Presolved: 2233889 rows, 2010202 columns, 10663726 nonzeros
Variable types: 2008028 continuous, 2174 integer (25 binary)
Root relaxation presolve removed 2071 rows and 1616 columns
Root relaxation presolved: 669564 rows, 637506 columns, 2962093 nonzeros

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

Root barrier log...

Elapsed ordering time = 10s
Elapsed ordering time = 15s
Ordering time: 22.23s

Barrier 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)

Objective                Residual
Iter       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   834s

Barrier solved model in 80 iterations and 833.76 seconds (454.25 work units)
Optimal objective 1.40733414e+02

Root crossover log...

Warning: 1 variables dropped from basis
Warning: 1 variables dropped from basis

Restart 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    878s

Root 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    880s

Solved with barrier
263483    1.4073338e+02   0.000000e+00   0.000000e+00    882s

Root 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      -     -  895s
H    0     0                     140.7333794  140.73338  0.00%     -  900s

Explored 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 tolerance
Warning: max bound violation (1.2568e-06) exceeds tolerance
Best objective 1.407333794148e+02, best bound 1.407333794148e+02, gap 0.0000%
Elapsed time is 1457.046333 seconds.

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