Lower bound very bad. How to improve?

I have the following MILP:

\begin{alignat}{2} \nonumber \mbox{minimize } \quad & \phi = \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{\underset{\bar{f} \neq f}{\bar{f}=1}}^F \sum_{h \in H} \left( D_{f \bar{f}} \cdot \gamma_{i\bar{f}h} \cdot \gamma_{i+1,f,h} \right) \quad & + & \quad \sum_{f=1}^{F} \sum_{h \in H} D_f^0 \cdot \left( \gamma_{1fh} + \gamma_{mfh} \right) + \\ & \quad + \sum_{i=1}^{m-1} \sum_{f=1}^F \sum_{h \in H} D_f^0 \left[ \gamma_{i+1,f,h} \cdot \left( 1 - \sum_{\bar{f}=1}^F \gamma_{i \bar{f} h} \right) \right] &+& \sum_{i=1}^{m-1} \sum_{f=1}^F \sum_{h \in H} D_f^0 \left[ \gamma_{i,f,h} \cdot \left( 1 - \sum_{\bar{f}=1}^F \gamma_{i+1, \bar{f}, h} \right) \right] \label{obj3}\\ \mbox{subject to} & && \nonumber \\ & \sum_{\ell \in B_j} g^A_{j \ell}\cdot w_{j \ell} = g^*_j + d_j^+ - d_j^-, && \quad j=1,...,k \label{grausdias1}\\ & \sum_{\ell \in B_j} w_{j \ell} = 1 && \quad j=1,...,k \label{grausdias2}\\ & t_j = \sum_{\ell \in B_j} \ell \cdot w_{j \ell} && \quad j=1,...,k \label{tj1}\\ & t_j + t^0_j = \sum_{i=1}^m T_i \cdot x_{ij}, && \quad j=1,...,k \label{tj2}\\ & \sum_{i=1}^m x_{ij} =1, && \quad j=1,...,k \label{umacolheita}\\ & \sum_{j=1}^k P_j \cdot L_j \cdot x_{ij} \geq d_i, && \quad i=1,...,m \label{demanda}\\ % & \sum_{f \in F} y_{if} \leq \theta, && \quad i=1,...,m, \label{maxfaz}\\ & \sum_{j = 1}^k z_{ijh} \leq 1 && \quad i=1,....,m, \quad h \in H \label{maxumamaquina}\\ & x_{ij} \leq y_{if}, && \quad i=1,...,m, \quad j\in J_f, \quad f=1,...,F \label{ligacao1_x_e_y}\\ & y_{if} \leq \sum_{j \in J_f} x_{ij}, && \quad i=1,...,m, \quad f=1,...,F \label{ligacao2_x_e_y}\\ & z_{ijh} \leq y_{if} && \quad i=1,....,m, \quad h \in H, \quad f=1,...,F, \quad j \in J_f \label{ligacao_z_e_y}\\ & x_{ij} \leq \sum_{h \in H} z_{ijh} && \quad i=1,....,m, \quad j \in 1,...,k \label{ligacao1_x_e_z}\\ & \sum_{h \in H} z_{ijh} \leq |H| \cdot x_{ij} && \quad i=1,....,m, \quad j \in 1,...,k \label{ligacao2_x_e_z}\\ & \sum_{i=1}^m \sum_{h \in H} \left( L^{max}_i \cdot C_h \cdot z_{ijh} \right) - e_j = P_j \cdot L_j && \quad j=1,...,k \label{colheita_talhao}\\ & \sum_{j \in J_f} z_{ijh} = \gamma_{ifh} && \quad i=1,...,m, \quad f=1,...,F, \quad h \in H \label{def_gamma}\\ &x_{ij} \in \{0,1\}, \ y_{if} \in \{0,1\}, \ z_{ijh} \in \{0,1\} && \quad i=1,...,m, \quad j=1,...,k, \quad f=1,...,F, \quad h \in H \label{var_xyz}\\ & w_{j\ell} \in \{0,1\}, \ \ t_j \geq 0 && \quad j=1,...,k, \quad \ell \in B_j \label{var_gammat}\\ & \gamma_{ifh} \in \{0,1\}, \ \ d_j^+ \geq 0, \ \ d_j^- \geq 0 && \quad i=1,...,m, \quad j=1,...,k, \quad f=1,...,F, \quad h \in H \label{var_wd}\\ & 0\leq e_j \leq \min_{\substack{h \in H \\ i \in \{1,...,m\}}} \{C_h \cdot L^{max}_i\} - \varepsilon && \quad j = 1,...,k. \label{var_e} \end{alignat}

the variables $$\gamma_{ifh} \in \{0,1\}$$. I have linerized the objective function using the constraints:

\begin{alignat}{2} & \gamma_{i\bar{f}h} + \gamma_{i+1,f,h} - u_{if\bar{fh}} \leq 1, && \quad i=1,...,m,\, \quad f=1,...,F, \quad \bar{f} \in \{1,...,F\} \setminus f, \quad h \in H \label{linearizacao1} \\ & u_{if\bar{fh}} \leq \gamma_{i\bar{f}h}, && \quad i=1,...,m,\, \quad f=1,...,F, \quad \bar{f} \in \{1,...,F\} \setminus f, \quad h \in H \label{linearizacao2} \\ & u_{if\bar{fh}} \leq \gamma_{i+1,f,h} && \quad i=1,...,m,\, \quad f=1,...,F, \quad \bar{f} \in \{1,...,F\} \setminus f, \quad h \in H. \label{linearizacao3} \end{alignat}

where $$\{0,1\} \ni u_{if\bar{fh}} = \gamma_{i\bar{f}h} \cdot \gamma_{i+1,f,h}$$ Then I have a linerized version of the model:

\begin{alignat}{2} \nonumber & \phi^L = \sum_{i=1}^{m-1} \sum_{f=1}^{F} \sum_{\underset{\bar{f} \neq f}{\bar{f}=1}}^F \sum_{h \in H} \left( D_{f \bar{f}} \cdot u_{i,f,\bar{f},h} \right) + \sum_{f=1}^{F} \sum_{h \in H} D_f^0 \cdot \left( \gamma_{1fh} + \gamma_{mfh} \right)\\ \nonumber & \quad + \sum_{i=1}^{m-1} \sum_{f=1}^F \sum_{h \in H} D_f^0 \left( \gamma_{i+1,f,h} - \sum_{\bar{f}=1}^F u_{i,f,\bar{f},h} \right)\\ & \quad + \sum_{i=1}^{m-1} \sum_{f=1}^F \sum_{h \in H} D_f^0 \left( \gamma_{i,f,h} - \sum_{\bar{f}=1}^F u_{i,\bar{f},f,h} \right) \end{alignat}

However, when I apply the gurobi solver with default parameters setting, I have this strange report.

The lower bound and integrality gap are terrible. Any hints to deal with this situation? Any parameters to set to improve this lower bound?


Gurobi Optimizer version 9.1.1 build v9.1.1rc0 (win64)
Thread count: 6 physical cores, 12 logical processors, using up to 12 threads
Optimize a model with 85788 rows, 62396 columns and 393896 nonzeros
Model fingerprint: 0x52171686
Variable types: 3180 continuous, 59216 integer (59116 binary)
Coefficient statistics:
Matrix range     [1e+00, 4e+03]
Objective range  [1e+00, 9e+01]
Bounds range     [4e+03, 4e+03]
RHS range        [1e+00, 2e+04]
Presolve removed 44504 rows and 25844 columns
Presolve time: 0.72s
Presolved: 41284 rows, 36552 columns, 162873 nonzeros
Variable types: 0 continuous, 36552 integer (36552 binary)

Deterministic concurrent LP optimizer: primal and dual simplex
Showing first log only...

Concurrent spin time: 0.00s

Solved with dual simplex

Root relaxation: objective -1.863828e+04, 2873 iterations, 0.16 seconds

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

0     0 -18638.276    0 1403          - -18638.276      -     -    6s
0     0 -18595.473    0 1535          - -18595.473      -     -   11s
0     0 -18560.477    0 1554          - -18560.477      -     -   12s
0     0 -18559.369    0 1617          - -18559.369      -     -   16s
0     0 -18556.823    0 1641          - -18556.823      -     -   17s
0     0 -18547.137    0 1674          - -18547.137      -     -   17s
0     0 -18546.400    0 1587          - -18546.400      -     -   17s
0     0 -18545.283    0 1593          - -18545.283      -     -   17s
0     0 -18545.283    0 1593          - -18545.283      -     -   17s
0     0 -18544.704    0 1622          - -18544.704      -     -   21s
0     0 -18543.019    0 1646          - -18543.019      -     -   23s
0     0 -18522.569    0 1906          - -18522.569      -     -   24s
0     0 -18515.349    0 1603          - -18515.349      -     -   25s
0     0 -18510.954    0 1652          - -18510.954      -     -   25s
0     0 -18509.118    0 1610          - -18509.118      -     -   25s
0     0 -18509.101    0 1619          - -18509.101      -     -   26s
0     0 -18026.647    0 3639          - -18026.647      -     -   34s
0     0 -17706.742    0 3776          - -17706.742      -     -   40s
H    0     0                    4887.5398664 -17706.742   462%     -   43s
0     0 -17672.544    0 3286 4887.53987 -17672.544   462%     -   43s
0     0 -17647.869    0 3017 4887.53987 -17647.869   461%     -   44s
0     0 -17636.426    0 2509 4887.53987 -17636.426   461%     -   45s
0     0 -17634.253    0 2136 4887.53987 -17634.253   461%     -   45s
0     0 -17631.840    0 2226 4887.53987 -17631.840   461%     -   45s
0     0 -17626.992    0 2151 4887.53987 -17626.992   461%     -   46s
0     0 -17626.655    0 2086 4887.53987 -17626.655   461%     -   46s
H    0     0                    2920.7576221 -17626.655   703%     -   56s
H    0     0                    2813.7406641 -17626.655   726%     -   56s
0     0 -17153.247    0 4004 2813.74066 -17153.247   710%     -   57s
H    0     0                    2796.6752197 -17153.247   713%     -   58s
H    0     0                    2701.3257781 -17153.247   735%     -   67s
H    0     0                    2358.2463329 -17153.247   827%     -   67s
0     0 -16903.798    0 4572 2358.24633 -16903.798   817%     -   68s
0     0 -16804.658    0 4427 2358.24633 -16804.658   813%     -   76s
0     0 -16781.521    0 4534 2358.24633 -16781.521   812%     -   78s
0     0 -16767.143    0 4766 2358.24633 -16767.143   811%     -   81s
H    0     0                    2144.9390245 -16767.143   882%     -   83s
0     0 -16760.105    0 5090 2144.93902 -16760.105   881%     -   84s
0     0 -16755.294    0 4526 2144.93902 -16755.294   881%     -   87s
0     0 -16749.748    0 4786 2144.93902 -16749.748   881%     -   89s
0     0 -16747.830    0 4238 2144.93902 -16747.830   881%     -   91s
0     0 -16747.582    0 4266 2144.93902 -16747.582   881%     -   91s
H    0     0                    2056.6362893 -16747.582   914%     -  123s
0     0 -15620.481    0 4811 2056.63629 -15620.481   860%     -  123s
H    0     0                    2054.7356332 -15620.481   860%     -  143s
H    0     0                    2006.0886369 -15620.481   879%     -  143s
H    0     0                    1940.0886369 -15620.481   905%     -  143s
0     0 -15265.905    0 4957 1940.08864 -15265.905   887%     -  143s
0     0 -15062.413    0 5136 1940.08864 -15062.413   876%     -  149s
H    0     0                    1914.3523105 -15062.413   887%     -  154s
0     0 -14930.548    0 5110 1914.35231 -14930.548   880%     -  154s
0     0 -14847.596    0 5048 1914.35231 -14847.596   876%     -  156s
0     0 -14828.768    0 4925 1914.35231 -14828.768   875%     -  159s
H    0     0                    1832.7541387 -14828.768   909%     -  163s
0     0 -14808.250    0 5202 1832.75414 -14808.250   908%     -  163s
0     0 -14793.917    0 5175 1832.75414 -14793.917   907%     -  166s
0     0 -14784.247    0 4960 1832.75414 -14784.247   907%     -  167s
0     0 -14780.462    0 4991 1832.75414 -14780.462   906%     -  168s
0     0 -14777.435    0 5152 1832.75414 -14777.435   906%     -  168s
0     0 -14771.757    0 5369 1832.75414 -14771.757   906%     -  169s
0     0 -14767.884    0 5635 1832.75414 -14767.884   906%     -  170s
0     0 -14766.518    0 5298 1832.75414 -14766.518   906%     -  170s
H    0     0                    1786.0598405 -14766.518   927%     -  189s
0     0 -13825.179    0 4878 1786.05984 -13825.179   874%     -  189s
0     0 -13565.430    0 5955 1786.05984 -13565.430   860%     -  209s
0     0 -13408.977    0 5673 1786.05984 -13408.977   851%     -  225s
H    0     0                    1747.5341110 -13408.977   867%     -  238s
0     0 -13309.643    0 5229 1747.53411 -13309.643   862%     -  238s
0     0 -13250.792    0 5691 1747.53411 -13250.792   858%     -  245s
0     0 -13227.110    0 5660 1747.53411 -13227.110   857%     -  249s
0     0 -13193.397    0 5240 1747.53411 -13193.397   855%     -  256s
0     0 -13181.822    0 5244 1747.53411 -13181.822   854%     -  259s
0     0 -13177.755    0 5178 1747.53411 -13177.755   854%     -  260s
0     0 -13171.537    0 5484 1747.53411 -13171.537   854%     -  262s
0     0 -13166.443    0 5290 1747.53411 -13166.443   853%     -  265s
0     0 -13158.052    0 5109 1747.53411 -13158.052   853%     -  270s
0     0 -13154.900    0 5784 1747.53411 -13154.900   853%     -  271s
0     0 -13154.628    0 5758 1747.53411 -13154.628   853%     -  272s
0     0 -12294.741    0 5852 1747.53411 -12294.741   804%     -  324s
0     0 -12036.908    0 5254 1747.53411 -12036.908   789%     -  349s
H    0     0                    1710.0011502 -12036.908   804%     -  371s
0     0 -11906.954    0 6071 1710.00115 -11906.954   796%     -  371s
0     0 -11843.360    0 5578 1710.00115 -11843.360   793%     -  383s
0     0 -11818.107    0 5663 1710.00115 -11818.107   791%     -  388s
0     0 -11795.351    0 5879 1710.00115 -11795.351   790%     -  393s
0     0 -11777.921    0 5787 1710.00115 -11777.921   789%     -  399s
0     0 -11764.912    0 5677 1710.00115 -11764.912   788%     -  403s
0     0 -11760.378    0 5493 1710.00115 -11760.378   788%     -  405s
0     0 -11758.945    0 5456 1710.00115 -11758.945   788%     -  406s
H    0     0                    1667.9113449 -11758.945   805%     -  451s
H    0     0                    1650.0106968 -11758.945   813%     -  451s
0     0 -11069.754    0 6343 1650.01070 -11069.754   771%     -  452s
0     0 -10884.656    0 5984 1650.01070 -10884.656   760%     -  498s
0     0 -10785.902    0 6296 1650.01070 -10785.902   754%     -  511s
0     0 -10746.495    0 5987 1650.01070 -10746.495   751%     -  520s
0     0 -10731.553    0 6267 1650.01070 -10731.553   750%     -  526s
0     0 -10721.912    0 5193 1650.01070 -10721.912   750%     -  531s
0     0 -10715.129    0 5691 1650.01070 -10715.129   749%     -  536s
0     0 -10710.195    0 6033 1650.01070 -10710.195   749%     -  543s
H    0     0                    1630.3646881 -10710.195   757%     -  572s
H    0     0                    1607.8503360 -10710.195   766%     -  572s
0     0 -10385.912    0 5271 1607.85034 -10385.912   746%     -  572s
H    0     0                    1552.8515166 -10385.912   769%     -  573s
H    0     0                    1517.6361485 -10385.912   784%     -  593s
0     0 -10294.225    0 6356 1517.63615 -10294.225   778%     -  593s
0     0          -    0      1517.63615 -10294.225   778%     -  600s

Cutting planes:
Gomory: 136
Cover: 10766
Clique: 1179
MIR: 33
StrongCG: 2
GUB cover: 157
Zero half: 773
RLT: 682
BQP: 36

Explored 1 nodes (524614 simplex iterations) in 600.10 seconds
Thread count was 12 (of 12 available processors)

Solution count 10: 1517.64 1552.85 1607.85 ... 1832.75

Time limit reached
Best objective 1.517636148458e+03, best bound -1.029422492545e+04, gap 778.3065%

User-callback calls 45491, time in user-callback 0.08 sec
'''

[1]: https://i.stack.imgur.com/XUQbz.png
[2]: https://i.stack.imgur.com/XE4d8.png
[3]: https://i.stack.imgur.com/86Riz.png

• Running it longer can help :-) Jul 30 '21 at 15:39
• I have done this for one hour. But, the gap is yet terrible! (~500%) Jul 30 '21 at 15:41
• 10 minutes (maybe more) at the root node with 12 threads seems a bit long. Maybe try using the barrier method for node LPs (or at least for the root LP)? Just guessing here. Jul 30 '21 at 19:36
• Even if wanted to implement and study the problem, i couldn't as have i no idea what n,m, H and host of other variables you have. Jul 31 '21 at 11:59
• @AngeloAlianoFilho, Are you sure to implement the algebraic modeling correctly? As per the GAP has fluctuation it seems the model might have a numerical issue. Have you tried using a minimal working example to explore this strange behavior? Jul 31 '21 at 18:48