Originally posted by: hllsen

I got very different performances from CPLEX 12.5 and 12.5.1 while solving a problem with convex quadratic objective function. More specifically, although CPLEX 12.5 solves the problem within couple of milliseconds, it takes "centuries" for CPLEX v12.5.1.. (not just for this instance but for all the instances I tried.)
I also checked the results with the Interactive Optimizer (by solving the attached "Configuration2.sav" with both versions) and the problem persists. I suspect that this issue is related to the "Approximate Minimum Degree ordering".. For reference I post the results that I obtained:

 

C:\Program Files\IBM\ILOG\CPLEX_Studio125\cplex\bin\x64_win64>cplex.exe

Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.5.0.0
  with Simplex, Mixed Integer & Barrier Optimizers
###
Copyright IBM Corp. 1988, 2012.  All Rights Reserved.

Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.

CPLEX> CPLEX> read D:\Users\...\Configuration2.sav
Problem 'D:\Users\...\Configuration2.sav' read.
Read time = 0.00 sec. (0.43 ticks)
CPLEX> optim
Tried aggregator 1 time.
MIQP Presolve eliminated 0 rows and 1 columns.
Number of nonzeros in lower triangle of Q = 9900
Using Approximate Minimum Degree ordering
Total time for automatic ordering = 0.02 sec. (0.20 ticks)
Summary statistics for factor of Q:
  Rows in Factor            = 200
  Integer space required    = 200
  Total non-zeros in factor = 10100
  Total FP ops to factor    = 676700
Reduced MIQP has 100 rows, 200 columns, and 200 nonzeros.
Reduced MIQP has 200 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 20000 nonzeros.
Presolve time = 0.02 sec. (7.57 ticks)
Probing time = 0.00 sec. (0.03 ticks)
Clique table members: 200.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.03 sec. (19.28 ticks)

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

      0     0   103010.4197    24                 103010.4197       11
*     0+    0                       103044.0000   103010.4197       11    0.03%
      0     2   103024.8296    16   103044.0000   103010.4197       13    0.03%
Elapsed time = 0.11 sec. (63.33 ticks, tree = 0.01 MB, solutions = 1)

Root node processing (before b&c):
  Real time             =    0.09 sec. (53.78 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.00 sec. (3.49 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.09 sec. (57.27 ticks)

Solution pool: 1 solution saved.

MIP - Integer optimal, tolerance (0.0001/1e-006):  Objective = 1.0304400000e+005

Current MIP best bound = 1.0303538082e+005 (gap = 8.61918, 0.01%)
Solution time =    0.13 sec.  Iterations = 15  Nodes = 2 (2)
Deterministic time = 64.97 ticks  (519.74 ticks/sec)

CPLEX> quit

C:\Program Files\IBM\ILOG\CPLEX_Studio1251\cplex\bin\x64_win64>cplex

Welcome to IBM(R) ILOG(R) CPLEX(R) Interactive Optimizer 12.5.1.0
  with Simplex, Mixed Integer & Barrier Optimizers
###
Copyright IBM Corp. 1988, 2013.  All Rights Reserved.

Type 'help' for a list of available commands.
Type 'help' followed by a command name for more
information on commands.

CPLEX> read D:\Users\...\Configuration2.sav
Problem 'D:\Users\...\Configuration2.sav' read.
Read time = 0.02 sec. (0.43 ticks)
CPLEX> optim
Found incumbent of value 268856.000000 after 0.00 sec. (0.13 ticks)
Tried aggregator 1 time.
MIQP Presolve eliminated 0 rows and 1 columns.
MIQP Presolve added 19800 rows and 9900 columns.
Reduced MIQP has 19900 rows, 10100 columns, and 39800 nonzeros.
Reduced MIQP has 200 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.02 sec. (2.29 ticks)
Probing time = 0.02 sec. (1.10 ticks)
Clique table members: 263.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.11 sec. (39.69 ticks)

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

*     0+    0                       268856.0000                    469     ---
*     0+    0                       256901.0000                    469     ---
      0     0    10702.0000   200   256901.0000    10702.0000      469   95.83%
*     0+    0                       178073.0000    10702.0000      469   93.99%
*     0+    0                       113871.0000    10702.0000      471   90.60%
      0     0    10704.5000   200   113871.0000     Fract: 49      471   79.49%
      0     0    10709.5000   200   113871.0000     Fract: 45      476   79.49%
*     0+    0                       113386.0000    23352.0000      476   79.40%
      0     2    10709.5000   200   113386.0000    25358.0000      476   77.64%
Elapsed time = 11.06 sec. (7954.37 ticks, tree = 0.01 MB, solutions = 4)
      2     4    12007.0000   198   113386.0000    25358.0000     2531   77.64%
      4     6    20860.0000   196   113386.0000    25358.0000     3642   77.64%
     17    19    32065.0000   192   113386.0000    25358.0000    12734   77.64%
     40    42    51238.0000   182   113386.0000    25358.0000    26020   77.64%
     56    58    51389.0000   176   113386.0000    25358.0000    34864   77.64%
    107   109    68679.5000   166   113386.0000    25358.0000    56478   77.64%
    155   157    81510.0000   158   113386.0000    25358.0000    80133   77.64%
    206   208    89759.0000   144   113386.0000    25358.0000   107312   77.64%
    262   262        cutoff         113386.0000    25358.0000   131218   77.64%
    387   355    37714.5000   186   113386.0000    25358.0000   172527   77.64%
Elapsed time = 19.23 sec. (11464.39 ticks, tree = 1.95 MB, solutions = 4)
*   489+  455                       113230.0000    25358.0000   214032   77.60%
*   489+  455                       112948.0000    25358.0000   214032   77.55%
*   496   462      integral     0   112863.0000    25358.0000   214196   77.53%
*   498   462      integral     0   112860.0000    25358.0000   214201   77.53%
*   499   461      integral     0   112858.0000    25358.0000   214202   77.53%

Gomory fractional cuts applied:  94

Root node processing (before b&c):
  Real time             =   11.03 sec. (7944.93 ticks)
Parallel b&c, 8 threads:
  Real time             =   10.33 sec. (4291.45 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =   21.36 sec. (12236.38 ticks)

Solution pool: 10 solutions saved.

MIP - Aborted, integer feasible:  Objective = 1.1285800000e+005
Current MIP best bound = 2.5358000000e+004 (gap = 87500, 77.53%)
Solution time =   21.36 sec.  Iterations = 216968  Nodes = 502 (463)
Deterministic time = 12236.38 ticks  (572.89 ticks/sec)
 

Hope you'll be able to find and fix the issue.

Cheers,

h.

Edit: File attached.

In general things like this can happen between CPLEX versions because there may be slight changes in CPLEX default settings.

It seems like you forgot to attach the Configuration2.sav file so I could not check any details. Could you please attach the file?

Can you try to explicitly set minimum degree ordering in 12.5.1? This is parameter CPX_PARAM_BARORDER and you have to set it to 1.

Originally posted by: hllsen

I tried what you proposed however still getting the same result. (I even set CPX_PARAM_STARTALG to CPX_ALG_BARRIER but it didn't change anything, it's like CPLEX 12.5.1 does not use it at all.)

cplex.setParam(IloCplex::BarOrder, CPX_BARORDER_AMD);

What strikes me most is that the ofv of the "root relaxations" are not equal -- i.e., 103010.4197 vs.10702.0000. Is it wrong to think that they [the objectives of the root relaxations] must be the same.

PS: I attached the file to the first post.

The issue is an additional presolve operation that was introduced between 12.5.0 and 12.5.1. This additional operation usually results in a speedup but unfortunately not in your case.

The operation can be disabled by setting hidden parameter number 4012 to 0 (note that hidden parameters may change between releases without further notice). If you don't know how to set a hidden parameter in your API of choice just get back here and tell me which API you are using.

Originally posted by: hllsen

Hi Daniel,

Thanks for the information, as a matter of fact I didn't :) but found it in here. So, I think I am going to use the following command in Concert:

cplex.setParam (static_cast<IloCplex::IntParam>(4012), 0);

I don't know how to set it in Interactive Optimizer though. Nevertheless this parameter did it!

However this behavior still seems weird to me, because I was explicitly setting IloCplex::BarOrder parameter (as you suggested) but Cplex was not applying it.

Cheers,

h.

The presolve operation I mentioned turns your MIQP into a plain MIP (no more Q). That is why the dual bound at the root changes and why the minimum degree ordering is not applied.

You can see this by writing out the presolved model, reading it back in and then solving it:

set mip lim nod 1
opt
write presolved.pre
read presolved.pre
opt

The second 'opt' will just start optimizing a plain MIP.

Originally posted by: hllsen

I really appreciate the explanation.

h.

Originally posted by: hllsen

Hi again!

At first I thought disabling the hidden parameter "4012" solved my performance problem, however apparently it is not because 12.5.1 still rejects to apply the minimum degree ordering. Root relaxation bounds are now the same though.

CPLEX 12.5.1.0
Found incumbent of value 1124233.000000 after 0.00 sec. (0.07 ticks)
Tried aggregator 1 time.
MIQP Presolve eliminated 0 rows and 1 columns.
Reduced MIQP has 60 rows, 180 columns, and 180 nonzeros.
Reduced MIQP has 180 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 10800 nonzeros.
Presolve time = 0.03 sec. (4.07 ticks)
Probing time = 0.00 sec. (0.05 ticks)
Clique table members: 60.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (3.62 ticks)

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

*     0+    0                      1124233.0000        0.0000      180  100.00%
      0     0   345102.6786    45  1124233.0000   345102.6786      180   69.30%
*     0+    0                       345737.0000   345102.6786      180    0.18%
*     0+    0                       345494.0000   345102.6786      180    0.11%
      0     2   345102.6786    45   345494.0000   345102.6786      180    0.11%
Elapsed time = 0.14 sec. (33.40 ticks, tree = 0.01 MB, solutions = 3)
*     4+    2                       345440.0000   345134.3146      201    0.09%
*     4+    2                       345403.0000   345134.3146      201    0.08%
*     5+    3                       345403.0000   345134.3146      209    0.08%
     28    13   345360.7220    33   345403.0000   345190.7593      276    0.06%

Root node processing (before b&c):
  Real time             =    0.14 sec. (32.32 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.67 sec. (424.98 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.81 sec. (457.30 ticks)

In the above screen output note that there is no notification about the ordering method and the statistics whatsoever. CPLEX 12.5.0 gives the "statistics for factor of Q" summary table and the ordering method changes according to what I setted it to be.

CPLEX 12.5.0.0

Tried aggregator 1 time.
MIQP Presolve eliminated 0 rows and 1 columns.
Number of nonzeros in lower triangle of Q = 5310
Total time for approximate-min-degree ordering = 0.00 sec. (0.11 ticks)
Summary statistics for factor of Q:
  Rows in Factor            = 180
  Integer space required    = 180
  Total non-zeros in factor = 5490
  Total FP ops to factor    = 221430
Reduced MIQP has 60 rows, 180 columns, and 180 nonzeros.
Reduced MIQP has 180 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 10800 nonzeros.
Presolve time = 0.03 sec. (4.07 ticks)
Probing time = 0.00 sec. (0.04 ticks)
Clique table members: 60.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 8 threads.
Root relaxation solution time = 0.00 sec. (3.62 ticks)

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

      0     0   345102.6786    45                 345102.6786      180
*     0+    0                       345737.0000   345102.6786      180    0.18%
*     0+    0                       345403.0000   345102.6786      180    0.09%
      0     2   345102.6786    45   345403.0000   345102.6786      180    0.09%
Elapsed time = 0.14 sec. (34.68 ticks, tree = 0.01 MB, solutions = 2)

Root node processing (before b&c):
  Real time             =    0.09 sec. (29.44 ticks)
Parallel b&c, 8 threads:
  Real time             =    0.19 sec. (77.22 ticks)
  Sync time (average)   =    0.00 sec.
  Wait time (average)   =    0.00 sec.
                          ------------
Total (root+branch&cut) =    0.28 sec. (106.66 ticks)

Therefore I got the following results (note the time difference).

I understand that some default parameters may have changed but I couldn't find a way to export all the parameters to find what is the difference (CPLEX only exports the parameters that are setted to a non-default value).

Cheers,

h.

I checked in a debugger. 12.5.1 still does the same, it just does not display these statistics

Total time for approximate-min-degree ordering = 0.00 sec. (0.11 ticks)
Summary statistics for factor of Q:
  Rows in Factor            = 180
  Integer space required    = 180
  Total non-zeros in factor = 5490
  Total FP ops to factor    = 221430

anymore. Another difference in the 12.5.0 and 12.5.1 logs you posted is that the improved heuristics in 12.5.1 quickly find a feasible solution, even before the root LP relaxation is solved. In 12.5.0 the first solution was not found that quickly.

Are you concerned about the small changes in sub-second solution times (maybe because you are solving many of those models) or are just interested in what changed from 12.5.0 to 12.5.1?

Originally posted by: hllsen

I was interested in the difference because of the change in the solution times ^^. I wanted to be sure before cocluding that "some specific model" behaves poorly on some instances. I'll solve larger instances and taking all the `runs` with both versions was not an option. I was so curious because I thought there was some other "hidden" parameter that is responsible for this performance difference (~%200 in ticks and sec). Thanks to you I can say it in confidence now.

Cheers,

h.