Solving a large scale MILP problem with cplex takes long time

Specific Domains Optimization (Mathematical)
,
1

i am solving a large scale MILP problem with cplex, it takes too much time and cannot obtain the sollution, does it means that cplex is not suitable for this large scale MILP problem? what can i do to acceralate the solving process? any suggestion would be welcome.

Version identifier: 22.1.0.0 | 2022-03-09 | 1a383f8ce
CPXPARAM_Read_DataCheck                          1
CPXPARAM_Threads                                 12
CPXPARAM_MIP_Strategy_LBHeur                     1
CPXPARAM_Barrier_Algorithm                       3
CPXPARAM_MIP_Strategy_HeuristicFreq              10
CPXPARAM_MIP_Tolerances_AbsMIPGap                0.0001
CPXPARAM_MIP_Tolerances_MIPGap                   0.01
CPXPARAM_MIP_Strategy_HeuristicEffort            10
Tried aggregator 6 times.
MIP Presolve eliminated 185595 rows and 105205 columns.
MIP Presolve modified 15498 coefficients.
Aggregator did 26370 substitutions.
Reduced MIP has 126802 rows, 150142 columns, and 904422 nonzeros.
Reduced MIP has 21861 binaries, 1 generals, 0 SOSs, and 1826 indicators.
Presolve time = 1.19 sec. (1633.97 ticks)
Probing fixed 0 vars, tightened 29564 bounds.
Probing time = 0.42 sec. (105.98 ticks)
Tried aggregator 2 times.
Detecting symmetries...
MIP Presolve eliminated 1764 rows and 3544 columns.
MIP Presolve modified 44298 coefficients.
Aggregator did 8 substitutions.
Reduced MIP has 125036 rows, 146590 columns, and 877678 nonzeros.
Reduced MIP has 21853 binaries, 1 generals, 0 SOSs, and 1804 indicators.
Presolve time = 0.63 sec. (1321.64 ticks)
Probing time = 0.42 sec. (26.72 ticks)
Cover probing fixed 6 vars, tightened 678 bounds.
Clique table members: 1485.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 7.19 sec. (5615.35 ticks)

        Nodes                                         Cuts/
   Node  Left     Objective  IInf  Best Integer    Best Bound    ItCnt     Gap

*     0+    0                       390292.7011   230399.3047            40.97%
      0     0   292308.3148   542   390292.7011   292308.3148       83   25.11%
      0     0   292675.5106   110   390292.7011     Cuts: 830      430   25.01%
      0     0   292676.6371   100   390292.7011     Cuts: 101      524   25.01%
      0     0   292676.6917    95   390292.7011      Cuts: 44      563   25.01%
      0     0   292676.6917    93   390292.7011      Cuts: 41      590   25.01%
      0     0   292676.6917    94   390292.7011      Cuts: 13      616   25.01%
*     0+    0                       389249.6672   292676.6917            24.81%
      0     2   292676.6917    94   389249.6672   292676.6917      616   24.81%
Elapsed time = 61.00 sec. (66443.62 ticks, tree = 0.02 MB, solutions = 2)
      6     8   293020.4837    89   389249.6672   292676.6917      787   24.81%
     12     6   292864.1368    88   389249.6672   292676.6917      667   24.81%
     42    28   292864.1368    86   389249.6672   292678.7230     1244   24.81%
    109    36   293022.1633    86   389249.6672   292679.8796     1342   24.81%
    149   115   293022.1633    83   389249.6672   292679.8796     1527   24.81%
    225   172   292864.1368    83   389249.6672   292679.8796     1584   24.81%
    271   205   293022.1633    81   389249.6672   292679.8796     1617   24.81%
    345   273   292794.0828    81   389249.6672   292679.8796     1685   24.81%
    400   313   293022.1633    76   389249.6672   292679.8796     1725   24.81%
    635   471   292794.0828    72   389249.6672   292679.8796     1883   24.81%
Elapsed time = 67.27 sec. (69692.11 ticks, tree = 14.22 MB, solutions = 2)
    885   773   293022.1633    59   389249.6672   292679.8796     2178   24.81%
   1132  1008   292865.8164    56   389249.6672   292679.8796     2413   24.81%
   1376  1188   292864.1368    43   389249.6672   292679.8796     2593   24.81%
   1590  1404   292865.8164    38   389249.6672   292679.8796     2809   24.81%
   1792  1657   354151.2727    35   389249.6672   292679.8796     5054   24.81%
   1982  1838   355752.2914    31   389249.6672   292679.8796     6625   24.81%
   2202  1901        cutoff         389249.6672   292679.8796     7782   24.81%
   2365  2127   354734.4868     7   389249.6672   292679.8796     8652   24.81%
   2555  2235   292864.1368    71   389249.6672   292679.8796     9235   24.81%
   2741  2473   327728.3913     2   389249.6672   292680.1782    10413   24.81%
Elapsed time = 86.38 sec. (79269.94 ticks, tree = 110.69 MB, solutions = 2)
   2886  2570   292864.1368    83   389249.6672   292680.1782    10914   24.81%
   2951  2690   377025.3358    29   389249.6672   292680.1782    16737   24.81%
   3103  2756   292686.6714    69   389249.6672   292680.1782    16835   24.81%
   3297  2865   292778.7797    38   389249.6672   292680.1782    20360   24.81%
   3503  3153   389161.0323   116   389249.6672   292680.1782    22853   24.81%
   3689  3332   354825.1618    56   389249.6672   292680.1782    25018   24.81%
   3884  3409   354647.6964    42   389249.6672   292680.1782    26048   24.81%

Performing restart 1

Repeating presolve.
Tried aggregator 3 times.
MIP Presolve eliminated 1729 rows and 396 columns.
MIP Presolve modified 490062 coefficients.
Aggregator did 8885 substitutions.
Reduced MIP has 114422 rows, 137309 columns, and 593351 nonzeros.
Reduced MIP has 21568 binaries, 1 generals, 0 SOSs, and 1553 indicators.
Presolve time = 0.83 sec. (1107.12 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 1 rows and 117 columns.
MIP Presolve modified 84 coefficients.
Aggregator did 11 substitutions.
Reduced MIP has 114414 rows, 137181 columns, and 593220 nonzeros.
Reduced MIP has 21451 binaries, 1 generals, 0 SOSs, and 1433 indicators.
Presolve time = 0.59 sec. (708.67 ticks)
Represolve time = 3.81 sec. (2744.07 ticks)
   3922     0   333899.9091   157   389249.6672    Cuts: 3680   100707   14.22%
   3922     0   336227.1846    79   389249.6672     Cuts: 331   100858   13.62%
   3922     0   336227.4112    84   389249.6672     Cuts: 184   100920   13.62%
   3922     0   336237.3541    84   389249.6672     Cuts: 186   101165   13.62%
   3922     0   336740.0499    95   389249.6672     Cuts: 278   101460   13.49%
   3922     0   336823.2427    60   389249.6672     Cuts: 498   101574   13.47%
   3922     0   337473.9876    64   389249.6672     Cuts: 161   101624   13.30%
   3922     0   337473.9881    50   389249.6672     Cuts: 167   101677   13.30%
   3922     0   337473.9937    53   389249.6672     Cuts: 116   101724   13.30%
   3922     0   337473.9937    45   389249.6672     Cuts: 120   101750   13.30%
   3922     0   337474.0045    44   389249.6672      Cuts: 29   101775   13.30%
   3922     0   337474.0045    43   389249.6672     Cuts: 132   101812   13.30%
   3922     0   337474.0542    43   389249.6672      Cuts: 49   101833   13.30%
*  3922+    0                       389237.1672   337474.0542            13.30%
   3922     0  -1.00000e+75     0   389237.1672   337474.0542   101833   13.30%
   3922     2   337474.0542    30   389237.1672   337474.0542   101833   13.30%
   3932     7   356426.6306    73   389237.1672   342847.0071   103532   11.92%
   3982    35   342939.4618    31   389237.1672   342852.6805   104902   11.92%
Elapsed time = 356.33 sec. (291708.70 ticks, tree = 0.58 MB, solutions = 3)
   4089   108   355937.2271    31   389237.1672   342852.6805   112530   11.92%
   4205   157   388908.8321    31   389237.1672   342852.6805   119156   11.92%
   4287   230   388702.6668     5   389237.1672   342852.6805   128426   11.92%
   4363   280        cutoff         389237.1672   342852.6805   135275   11.92%
   4471   354   363821.7406    11   389237.1672   342852.6805   145418   11.92%
   4632   397   349483.2493    11   389237.1672   342852.6805   150693   11.92%
   4818   520        cutoff         389237.1672   342852.6805   162296   11.92%
   4897   557   349484.9289     9   389237.1672   342852.6805   163997   11.92%
   4963   642        cutoff         389237.1672   342852.6805   170172   11.92%
   5096   697   377713.2016    10   389237.1672   342852.6805   173795   11.92%
Elapsed time = 383.66 sec. (302355.50 ticks, tree = 46.57 MB, solutions = 3)
   5277   845   380895.8008     4   389237.1672   342852.6805   178648   11.92%
   5429   837   349483.2493    11   389237.1672   342852.6805   178481   11.92%
   5602   903   384961.2956     2   389237.1672   342852.6805   182760   11.92%
   5776  1132   374087.2993     9   389237.1672   342852.6805   220252   11.92%
   5938  1068   370648.7102     9   389237.1672   342852.6805   218848   11.92%
   6117  1196        cutoff         389237.1672   342852.6805   235840   11.92%
   6285  1344   386775.4393    13   389237.1672   342852.6805   248236   11.92%
   6474  1464   358101.1352    16   389237.1672   342852.6805   251222   11.92%
   6612  1618   358268.8352     4   389237.1672   342852.6805   262466   11.92%
   6780  1700   387585.4793   332   389237.1672   342852.6805   269059   11.92%
Elapsed time = 427.39 sec. (311952.39 ticks, tree = 88.95 MB, solutions = 3)
   6952  1841   370659.4373     7   389237.1672   342852.6805   276798   11.92%
   7127  1891   388907.4619     1   389237.1672   342852.6805   277638   11.92%
   7298  2068   358301.1602    14   389237.1672   342852.6805   285826   11.92%
   7475  2190   387585.4813   247   389237.1672   342852.6805   291352   11.92%
   7655  2279   386040.1691     1   389237.1672   342852.6805   297156   11.92%
   7834  2453   383345.6832    28   389237.1672   342852.6805   300811   11.92%
   8009  2504   384023.2596    62   389237.1672   342852.6805   304878   11.92%
   8211  2681   362634.8865     5   389237.1672   342852.6805   313966   11.92%
   8405  2776        cutoff         389237.1672   342852.6805   314702   11.92%
   8595  3011   388432.1944   111   389237.1672   342852.6805   317028   11.92%
Elapsed time = 453.66 sec. (321545.06 ticks, tree = 152.93 MB, solutions = 3)
   8801  3129   362098.5743    22   389237.1672   342852.6805   317973   11.92%
   9009  3237   361860.5743    23   389237.1672   342852.6805   320788   11.92%
   9207  3560   388417.2659   233   389237.1672   342852.6805   328098   11.92%
   9388  3656        cutoff         389237.1672   342852.6805   329707   11.92%
   9571  3896   387689.1261    59   389237.1672   342852.6805   335979   11.92%
   9765  4072   362061.9289    16   389237.1672   342852.6805   338780   11.92%
   9963  4157   356493.6162     6   389237.1672   342852.6805   339482   11.92%
  10174  4331   363030.2983    21   389237.1672   342852.6805   342164   11.92%
  10367  4561   379755.3829     3   389237.1672   342852.6805   346118   11.92%
  10548  4617   342852.8349    20   389237.1672   342852.7009   346968   11.92%
Elapsed time = 474.88 sec. (331128.41 ticks, tree = 227.43 MB, solutions = 3)
  10724  4762   385332.6239     1   389237.1672   342852.7009   350237   11.92%
  10884  4975   363247.4707     5   389237.1672   342853.0820   353886   11.92%
  11051  5046   362060.2493    14   389237.1672   342853.0820   354837   11.92%
  11243  5278   388422.0951    54   389237.1672   342854.1047   360346   11.92%
  11408  5452        cutoff         389237.1672   342869.4078   364150   11.91%
  11585  5565   355350.0087    19   389237.1672   342869.4078   367273   11.91%
  11735  5585   370668.4163    23   389237.1672   342869.4078   369423   11.91%
  11904  5808   370753.7767     7   389237.1672   342869.4078   373886   11.91%
  12077  6012   370587.5601    21   389237.1672   342869.4078   384050   11.91%
  12268  6031   370587.5634     4   389237.1672   342869.4078   384113   11.91%
Elapsed time = 497.02 sec. (340717.16 ticks, tree = 296.99 MB, solutions = 3)
  12446  6217   370587.5601     9   389237.1672   344603.4691   398650   11.47%
  12636  6391   349682.5172     9   389237.1672   349413.1953   403547   10.23%
  12844  6450   349697.8203     8   389237.1672   349413.1953   405028   10.23%
  13019  6789   370683.7194    15   389237.1672   349559.5172   420484   10.19%
  13212  6838   361990.1953     8   389237.1672   349559.5172   422015   10.19%
  13399  6984   362103.8922     3   389237.1672   349559.5172   426266   10.19%
  13575  7055   370683.7194    16   389237.1672   349559.5172   428122   10.19%
  13760  7321   362103.8922     8   389237.1672   349559.5172   434149   10.19%
  13969  7561   355351.6883     8   389237.1672   349559.5172   442526   10.19%
  14154  7665        cutoff         389237.1672   349559.5172   445504   10.19%
Elapsed time = 519.06 sec. (350301.77 ticks, tree = 371.74 MB, solutions = 3)
  14329  7764   388795.9268     1   389237.1672   349559.5172   447673   10.19%
  14548  7930   354241.0189    29   389237.1672   349559.5172   453325   10.19%
  14763  7987   382020.7277     2   389237.1672   349559.5172   456495   10.19%
  14966  8258   380344.0075     2   389237.1672   349559.5172   459635   10.19%
  15144  8455   354260.4551     9   389237.1672   349559.5172   471991   10.19%
  15326  8360   354246.4337    14   389237.1672   349559.5172   465591   10.19%
  15538  8634   388783.1997     1   389237.1672   349665.4953   476877   10.17%
  15714  8813        cutoff         389237.1672   349665.4953   482082   10.17%
  15926  9117   354247.7317    17   389237.1672   349665.4953   488601   10.17%
  16784  9624   367496.0159     6   389237.1672   354241.0189   500117    8.99%
Elapsed time = 547.59 sec. (362720.48 ticks, tree = 463.83 MB, solutions = 3)
  17630 10136   368366.1820     2   389237.1672   354241.0189   511778    8.99%
  18422 10641   380353.8814     2   389237.1672   354241.0189   525845    8.99%
  19295 11302        cutoff         389237.1672   354241.0189   544396    8.99%
  20125 11914   380353.8814     7   389237.1672   354241.0189   562229    8.99%
  20979 12248   368366.1820     2   389237.1672   354241.0189   570768    8.99%
  21817 13003   354241.0189    10   389237.1672   354241.0189   589036    8.99%
  22666 13326   380353.8814     3   389237.1672   354241.0189   597872    8.99%
  23550 13907        cutoff         389237.1672   354241.0189   614507    8.99%
  24381 14685   354241.0189     9   389237.1672   354241.0189   635112    8.99%
  25257 15010   368366.1820     3   389237.1672   354241.0189   643633    8.99%
Elapsed time = 665.74 sec. (400901.87 ticks, tree = 716.81 MB, solutions = 3)
  26140 15763   367494.7189     6   389237.1672   354241.0189   663824    8.99%
  27024 16322    infeasible         389237.1672   354241.0189   678433    8.99%
  27846 16936   380353.8814     4   389237.1672   354241.0189   695934    8.99%
  28721 17326   380353.8814     5   389237.1672   354241.0189   706335    8.99%
  29596 18008   380353.8814     5   389237.1672   354241.0189   724568    8.99%
  30491 18465   367494.7189     7   389237.1672   354241.0189   736131    8.99%
  31388 18935   367494.7189     4   389237.1672   354241.0189   748263    8.99%
  32209 19762        cutoff         389237.1672   354241.0189   771903    8.99%
  33098 20021   368366.1820     3   389237.1672   354241.0189   779118    8.99%
  33989 20520   367494.7189     7   389237.1672   354241.0189   794447    8.99%
Elapsed time = 863.58 sec. (439103.18 ticks, tree = 976.87 MB, solutions = 3)
  34871 21229   368366.1820     2   389237.1672   354241.0189   814159    8.99%
  35724 21913        cutoff         389237.1672   354241.0189   833898    8.99%
  36587 22624   367494.7189     3   389237.1672   354241.0189   852245    8.99%
  37455 23197        cutoff         389237.1672   354241.0189   867564    8.99%
  38281 23331   380353.8814     7   389237.1672   354241.0189   871494    8.99%
  39161 24132   367494.7189     4   389237.1672   354241.0189   893776    8.99%
  40001 24841   354241.0189    12   389237.1672   354241.0189   913435    8.99%
  40841 25243   368366.1820     2   389237.1672   354241.0189   925267    8.99%
  41649 25697   354241.0189    10   389237.1672   354241.0189   937663    8.99%
  42090 26269   368366.1820     2   389237.1672   354241.0189   953482    8.99%
Elapsed time = 988.08 sec. (477308.40 ticks, tree = 1272.52 MB, solutions = 3)
  42520 26514   354241.0189     8   389237.1672   354241.0189   960515    8.99%
  42950 26910   367494.7189     4   389237.1672   354241.0189   972114    8.99%
  43373 27278   380353.8814     4   389237.1672   354241.0189   982122    8.99%
  43802 27325   367494.7189     5   389237.1672   354241.0189   983440    8.99%
* 44078+25972                       389198.3172   354241.0189             8.98%
  44250 27474        cutoff         389198.3172   354241.0189   987932    8.98%
  44662 27951   380353.8814     6   389198.3172   354241.0189  1001548    8.98%
  45087 28217   368366.1820     2   389198.3172   354241.0189  1009124    8.98%
* 45327+25867                       389198.3172   354241.0189             8.98%
  45518 28414   354241.0189    12   389198.3172   354241.0189  1014742    8.98%
  45964 28931   367494.7189     6   389198.3172   354241.0189  1028043    8.98%
  46411 29039   367494.7189     6   389198.3172   354241.0189  1031574    8.98%
Elapsed time = 1119.86 sec. (515588.22 ticks, tree = 1405.52 MB, solutions = 3)
  46853 29146   367494.7189     6   389198.3172   354241.0189  1034544    8.98%
  47290 29675   368366.1820     3   389198.3172   354241.0189  1049284    8.98%
  47719 29779   367494.7189     6   389198.3172   354241.0189  1052833    8.98%
  48144 30281   380353.8814     2   389198.3172   354241.0189  1066783    8.98%
  48595 30514        cutoff         389198.3172   354241.0189  1073896    8.98%
  49021 30682   380353.8814     2   389198.3172   354241.0189  1078966    8.98%
  49464 30850        cutoff         389198.3172   354241.0189  1084527    8.98%
  49871 31263   367494.7189     4   389198.3172   354241.0189  1096473    8.98%
  50323 31571   367494.7189     4   389198.3172   354241.0189  1105284    8.98%
  50770 31799   368366.1820     3   389198.3172   354241.0189  1111627    8.98%
Elapsed time = 1371.11 sec. (553796.11 ticks, tree = 1536.45 MB, solutions = 3)
  51193 32028   367494.7189     6   389198.3172   354241.0189  1118378    8.98%
  51644 32343   367494.7189     6   389198.3172   354241.0189  1127562    8.98%
  52075 32762   380353.8814     6   389198.3172   354241.0189  1139864    8.98%
  52499 32810   368297.8570     4   389198.3172   354241.0189  1141113    8.98%
  52964 33366   368366.1820     3   389198.3172   354241.0189  1157332    8.98%
  53393 33568   354241.0189     8   389198.3172   354241.0189  1163054    8.98%
  53838 33904   367494.7189     6   389198.3172   354241.0189  1172685    8.98%
  54255 34226   355163.8358    10   389198.3172   354241.0189  1182056    8.98%
  54680 34555   367494.7189     4   389198.3172   354241.0189  1191550    8.98%
  55139 34484   380353.8814     6   389198.3172   354241.0189  1189561    8.98%
Elapsed time = 1572.03 sec. (592025.06 ticks, tree = 1667.85 MB, solutions = 3)
  55550 34953   380353.8814     5   389198.3172   354241.0189  1203828    8.98%
  55983 35336   354241.0189     9   389198.3172   354241.0189  1215043    8.98%
  56439 35339   367494.7189     5   389198.3172   354241.0189  1214690    8.98%
  56877 35760        cutoff         389198.3172   354241.0189  1227496    8.98%
  57326 36044        cutoff         389198.3172   354241.0189  1235901    8.98%
2

Hi @JOHN1, welcome to the community!
Can you share any more details about your problem, ideally a complete reproducible example, at least a mathematical description?
In general, MILPs are hard problems, and as few as tens of variables can be difficult to solve given the right combinatorial structure. Yours has over 100 000, so depending on what’s inside, it may very well be beyond the reach of a naive solving approach. In that case, decomposition methods or more sophisticated algorithms can give you a leg up.

1 Like
3

Your language is a bit vague.

If that “large scale MILP problem” is you original problem, then you should form a plan in your mind

  1. how much time can I tolerate

  2. what’s my expected accuracy

For example, if cplex can reduce the relative gap to below 0.05% in 24 hours, and you are happy with it. Then your aim is already achieved. (In your case, cplex spends 1572 seconds to achieve a 8.98% rgap.)

No. You can always deliver your original problem—no matter how large it is—to a black box MIP solver. And typically you had best try solving it directly before you try any customized decomposition methods, because otherwise there are numerous nontrivial issues you may encounter. And much experience is entailed for you to successfully implement them.

For decomposition methods:

  1. From primal side, we have Benders decomposition

  2. From dual side, we have dual decomposition (by relaxing some complicating constraints with Lagrangian multipliers)

  3. Dantzig-Wolfe’s method is merely a dual perspective of the Lagrangian’s method, therefore at least for me, it is overshadowed

1 Like
4

Hi @JOHN1, welcome to the forum :smile:

I see you have cross-posted this at https://or.stackexchange.com/questions/13239/solving-a-large-scale-milp-problem-with-cplex-takes-long-time.

If you post the same question in multiple places, please leave links so that we don’t repeat work answering a question twice. Also note that this forum is for Julia-related questions. The or.stackexchange is probably a more relevant forum for discussing MIP formulations.

1 Like