CPLEX Root node processing (before b&c) CPU Time extremely higher than JuMP Time Limit

Specific Domains Optimization (Mathematical)
, , ,
1

I have recently switched from Gurobi to CPLEX and am very surprised I found several instances where all ticks and CPU time is spent at Root node processing and more disconcerting the total time (before B&C and root node) is extremely higher than my set time limit.

i.e.

Root node processing (before b&c):
  Real time             = 4035.04 sec. (2046454.85 ticks)

And
CPXPARAM_TimeLimit 900

I expected the model to solve within 15 minutes (900s) which is not the case at all! How can I tell CPLEX that I want the total solve time to be lesser than a given amount of seconds? I do not remember having such issue in Gurobi.


Version identifier: 12.10.0.0 | 2019-11-26 | 843d4de
CPXPARAM_Threads                                 4
CPXPARAM_TimeLimit                               900
CPXPARAM_MIP_Tolerances_MIPGap                   0.01
Found incumbent of value 0.000000 after 0.11 sec. (49.96 ticks)
Tried aggregator 1 time.
Reduced MIP has 8479 rows, 1993750 columns, and 5981010 nonzeros.
Reduced MIP has 1993750 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 8.87 sec. (2176.17 ticks)
Tried aggregator 1 time.
Detecting symmetries...
Elapsed time for symmetry detection = 9.79 sec. (10016.50 ticks)
Found 3.388971e+10070 symmetric permutations.
Reduced MIP has 8479 rows, 1993750 columns, and 5981010 nonzeros.
Reduced MIP has 1993750 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 27.84 sec. (18181.09 ticks)
Probing time = 2.73 sec. (337.13 ticks)
Clique table members: 3866669.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 4 threads.
Root relaxation solution time = 52.37 sec. (26532.65 ticks)

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

*     0+    0                            0.0000  2188691.8597              ---
*     0+    0                        33835.2070  2188691.8597              ---
*     0+    0                        34473.5731  2188691.8597              ---
      0     0  1450634.2495   191    34473.5731  1450634.2495       59     ---
*     0+    0                      1366924.0628  1450634.2495             6.12%
      0     0  1444294.5449   191  1366924.0628    Cuts: 2219    50336    5.66%
      0     0  1441334.5073   191  1366924.0628    Cuts: 2219   101597    5.44%

Clique cuts applied:  415
Mixed integer rounding cuts applied:  100
Zero-half cuts applied:  22

Root node processing (before b&c):
  Real time             = 4035.04 sec. (2046454.85 ticks)
Parallel b&c, 4 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) = 4035.04 sec. (2046454.85 ticks)
termination_status(model) = MathOptInterface.TIME_LIMIT

It seems that this issue was known 5 years ago in the following StackOverflow post:

However, there are no answers to this question

2

Time limits are somewhat soft. Often the solver will finish the step it is doing before checking rto terminate.

This is a particularly bad example, but since CPLEX did eventually terminate it looks like a solver issue, not something we can fix in JuMP or CPLEX.jl.

You could try more recent version of CPLEX but if the issye persists… you’re out of luck. This is unlikely to get fixed by IBM.

1 Like
3

First, the time limits in Cplex do not affect the time it takes to solve the root node. I believe Gurobi time limits work similarly, not limiting the resolution of the root node.

Second, your problem is quite big with ~2 million binary variables, so it’s no surprise it takes a long time to solve the root node. As for the differences you observed with Gurobi, it’s likely that they have enhanced the performance of their heuristics and branching variable selection processes to expedite resolution at the root. However, the overall complexity of your problem remains a significant factor.

You may want to consult the documentation link (“Too much time at node 0” in the Ibm documentation) and consider limiting any “fancy stuff” that occurs under the hood at the root node. In C++, this can be accomplished with specific parameters, so you should look for their equivalent names.

cplex.setParam(IloCplex::Param::MIP::Strategy::HeuristicFreq, -1);
cplex.setParam(IloCplex::Param::MIP::Strategy::VariableSelect, 4);
cplex.setParam(IloCplex::Param::Emphasis::MIP, 1);

However, I don’t think they’ll make much of a difference for a problem of that size.

My safe approach would be to increase your time limits to allow for the resolution of all root nodes for the larger instances, or document in your results that the root node could not be solved within 900 seconds.