4
$\begingroup$

Supose that I have an integer feasible solution for a MIP and I provide this one for CPLEX. I have tested this situation in a problem and CPLEX have reported the following:

CPXPARAM_TimeLimit                               600
CPXPARAM_MIP_Tolerances_MIPGap                   0.01       
Warning:  Non-integral bounds for integer variables rounded.
5 of 6 MIP starts provided solutions.
MIP start 'm1' defined initial solution with objective 8711.0000.
Warning:  Non-integral bounds for integer variables rounded.     
Tried aggregator 3 times.
MIP Presolve eliminated 41041 rows and 5542 columns.
MIP Presolve modified 12819 coefficients.
Aggregator did 102 substitutions.
Reduced MIP has 15022 rows, 13813 columns, and 81253 nonzeros.
Reduced MIP has 12735 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.19 sec. (256.82 ticks)
Probing fixed 900 vars, tightened 0 bounds.
Probing time = 0.08 sec. (66.81 ticks)
Tried aggregator 2 times.
MIP Presolve eliminated 93 rows and 902 columns.
MIP Presolve modified 1396 coefficients.
Aggregator did 3 substitutions.
Reduced MIP has 14926 rows, 12908 columns, and 76009 nonzeros.        
Reduced MIP has 12858 binaries, 15 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.08 sec. (105.79 ticks)
Probing time = 0.00 sec. (6.36 ticks)
Clique table members: 11526.
MIP emphasis: balance optimality and feasibility.    
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 0.98 sec. (883.29 ticks)

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

*     0+    0                         8711.0000  -458520.0000              --- 
      0     0   -17149.9829  2477     8711.0000   -17149.9829        0  296.88%
*     0+    0                         7205.0000   -17149.9829           338.03%
      0     0   -15317.4801  2303     7205.0000     Cuts: 572    16267  312.60%
      0     0   -14779.1052  2136     7205.0000     Cuts: 440    21296  305.12%
      0     0   -14380.2661  2301     7205.0000     Cuts: 320    31470  299.59%
      0     0   -14103.7735  2526     7205.0000     Cuts: 448    37793  295.75%
      0     0   -13732.7994  2426     7205.0000     Cuts: 400    43124  290.60%
      0     0   -13445.8090  2638     7205.0000     Cuts: 392    50169  286.62%
      0     0   -13155.3050  2773     7205.0000     Cuts: 372    59588  282.59%
      0     0   -12823.9768  2893     7205.0000     Cuts: 364    67111  277.99%
      0     0   -12599.0288  2404     7205.0000     Cuts: 337    75557  274.87%
      0     0   -12430.1956  2773     7205.0000     Cuts: 382    85578  272.52%
      0     0   -12150.1949  2883     7205.0000     Cuts: 408    96883  268.64%
      0     0   -11987.4450  3172     7205.0000     Cuts: 388   117106  266.38%
      0     0   -11798.6406  2739     7205.0000     Cuts: 380   128615  263.76%
      0     0   -11592.1280  2515     7205.0000     Cuts: 367   141135  260.89%
      0     0   -11195.5796  2557     7205.0000     Cuts: 558   163911  255.39%
      0     0   -10867.8034  2569     7205.0000     Cuts: 485   182024  250.84%
      0     0   -10563.4191  2822     7205.0000     Cuts: 425   204140  246.61%
      0     0   -10321.3655  3025     7205.0000     Cuts: 417   215627  243.25%
      0     0   -10150.4502  2638     7205.0000     Cuts: 421   233232  240.88%
      0     0   -10048.7581  2715     7205.0000     Cuts: 378   245798  239.47%
      0     0    -9945.2271  2933     7205.0000     Cuts: 360   257496  238.03%
      0     0    -9832.7526  3319     7205.0000     Cuts: 363   271374  236.47%
      0     0    -9736.9997  3211     7205.0000     Cuts: 396   285686  235.14%
      0     0    -9652.8245  2848     7205.0000     Cuts: 340   298003  233.97%
      0     0    -9550.7594  3086     7205.0000     Cuts: 366   311895  232.56%
      0     0    -9448.1725  3051     7205.0000     Cuts: 416   331676  231.13%
      0     0    -9353.9779  3025     7205.0000     Cuts: 380   342695  229.83%
      0     0    -9281.6027  3068     7205.0000     Cuts: 390   354086  228.82%
      0     0    -9193.7089  3084     7205.0000     Cuts: 370   368795  227.60%
*     0+    0                         6997.0000    -9193.7089           231.40%
      0     0    -9099.7451  3741     6997.0000     Cuts: 387   381566  230.05%
*     0+    0                         6835.5000    -9099.7451           233.12%
*     0+    0                         6510.5000    -9099.7451           239.77%
      0     0    -9044.4629  3377     6510.5000     Cuts: 363   389565  238.92%
      0     0    -8964.7389  2960     6510.5000     Cuts: 349   407833  237.70%
      0     0    -8911.6534  2837     6510.5000     Cuts: 372   422932  236.88%
*     0+    0                         6167.0000    -8911.6534           244.51%
*     0+    0                         6096.0000    -8911.6534           246.19%
*     0+    0                         5401.0000    -8911.6534           265.00%
      0     0    -8835.6035  3156     5401.0000     Cuts: 345   438079  263.59%
*     0+    0                         5384.0000    -8835.6035           264.11%
      0     0    -8759.5640  3011     5384.0000     Cuts: 372   448024  262.70%

GUB cover cuts applied:  213
Clique cuts applied:  14
Cover cuts applied:  59
Implied bound cuts applied:  96
Flow cuts applied:  33
Mixed integer rounding cuts applied:  176
Zero-half cuts applied:  1721
Gomory fractional cuts applied:  12

Root node processing (before b&c):
  Real time             =  600.09 sec. (300168.69 ticks)
Parallel b&c, 12 threads:
  Real time             =    0.00 sec. (0.00 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =  600.09 sec. (300168.69 ticks)

Are there any suggestion in the CPLEX paraameters to accelerate/improve the lower bound of my problem and, consequenty, improve the relative GAP when CPLEX runs? I will apreciate any suggestion. Thank you so much.

$\endgroup$
3
  • $\begingroup$ As the hint that @Pro. prubin mentioned, would you sure your MP formulation is correct or the Initial solution you provided works fine? What is the solving status which the solver shows? $\endgroup$
    – A.Omidi
    Jan 21 at 11:06
  • $\begingroup$ The formulation is correct. The objective is quadratic (nonconvex) binary, I used trick of integer programming as: or.stackexchange.com/questions/37/… CPLEX stopped because elapsed 10 minutes (maximum time allowed). Maybe the problem is this linearization. Hints? The initial solution is feasible. $\endgroup$ Jan 21 at 15:27
  • $\begingroup$ The relative gap increase/decrease because the upper/lower bound is improved. $\endgroup$ Jan 21 at 15:33
3
$\begingroup$

You can try setting the MIP Emphasis parameter (Java name loCplex.Param.Emphasis.MIP) to 3, which emphasizes tightening the best bound. This may result in slower progress on the primal bound (best known solution), and it is not guaranteed to help. There are also a variety of parameters related to adding cuts (how frequently cuts are added, how much emphasis is put on adding cuts). It is possible that playing with those would make the bound increase faster, but again there is no guarantee. Tweaking the repeat presolve parameter (Java name IloCplex.Param.Preprocessing.RepeatPresolve) also might (or might not) help. The same is true for node presolve (Java name IloCplex.Param.MIP.Strategy.PresolveNode).

The fact that your lower bounds are negative has me wondering whether negative objective values are actually feasible in practice, or whether the optimum must have a positive objective value. If the latter is true, you might look for ways to tighten your formulation (beyond the trivial one of just constraining the objective to be nonnegative).

$\endgroup$
1
  • $\begingroup$ Of fact, my objective is positive. i have added a constraint ensure that my objective is positive, so the relative gap is now 100% in 10 minutes yet. My objective function is quadratic (nonconvex) and I have employed tricks of integer programming to linerize it. Maybe this destroy my problem. Hints are acceptable. Thanks. $\endgroup$ Jan 21 at 15:13
3
$\begingroup$

You can use the automatic parameter tuning in cplex, or try parameters yourself and see which ones work best. There is a guide by IBM on what they suggest: https://www.ibm.com/support/pages/cplex-performance-tuning-mixed-integer-programs

You can give the problem more runtime and it will most likely improve the gap.

You can try to find a better inital feasible solution and hope that it prunes the tree faster. Based on the size of your gap, this will likely not help very much.

But to get any real improvement, you will likely need to improve the formulation of your problem.

$\endgroup$

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.