0
$\begingroup$

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?


Academic license - for non-commercial use only - expires 2021-08-04
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
$\endgroup$
5
  • 1
    $\begingroup$ Running it longer can help :-) $\endgroup$ Jul 30 at 15:39
  • $\begingroup$ I have done this for one hour. But, the gap is yet terrible! (~500%) $\endgroup$ Jul 30 at 15:41
  • $\begingroup$ 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. $\endgroup$
    – prubin
    Jul 30 at 19:36
  • $\begingroup$ 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. $\endgroup$ Jul 31 at 11:59
  • $\begingroup$ @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? $\endgroup$
    – A.Omidi
    Jul 31 at 18:48

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.