What does it mean that CPLEX restart the root node solution after found an infeasiable objective?a

Hi. I would like to know what means that CPLEX restart the root node solution after found an infeaseable objective. When it happens usually the second root solution takes much longer (especially in the relaxation), so it would be great if there is some way to prevent that.
My problem is a MIQP. Part of the solution output is shown below.

Presolve eliminates 0 constraints and 166208 variables.
Adjusted problem:
135861 variables:
1392 binary variables
1131 integer variables
48960 nonlinear variables
84378 linear variables
216417 constraints, all linear; 904423 nonzeros
101370 equality constraints
115047 inequality constraints
1 nonlinear objective; 74847 nonzeros.

CPLEX 20.1.0.0: mipgap=3e-2
mipdisplay=2
rinsheur=100
nodes=1000
return_mipgap=7
Retaining values of one MIP start for possible repair.
MIQP Presolve eliminated 78530 rows and 3422 columns.
MIQP Presolve modified 31 coefficients.
Reduced MIQP has 135736 rows, 130288 columns, and 814482 nonzeros.
Reduced MIQP has 984 binaries, 1131 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 47052 nonzeros.
Probing fixed 0 vars, tightened 254813 bounds.
Probing time = 5.91 sec. (3673.54 ticks)
Reduced MIQP has 135736 rows, 130288 columns, and 814482 nonzeros.
Reduced MIQP has 984 binaries, 1131 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 47052 nonzeros.
Classifier predicts products in MIQP should be linearized.
Probing fixed 0 vars, tightened 120180 bounds.
Probing time = 4.81 sec. (1342.51 ticks)
Clique table members: 2208.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 756.09 sec. (1183507.55 ticks)

    Nodes                                         Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

  0     0    infeasible                                      25951         

Root node processing (before b&c):
Real time = 804.08 sec. (1230112.84 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) = 804.08 sec. (1230112.84 ticks)
Clique table members: 1522.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 12 threads.
Root relaxation solution time = 2007.50 sec. (2199398.66 ticks)

    Nodes                                         Cuts/

Node Left Objective IInf Best Integer Best Bound ItCnt Gap

  0     0    17022.6839  1023                  17022.6839   124610         
  • 0+    0                        18140.4799    17022.6839             6.16%
    0     0    17139.0531  1079    18140.4799     Cuts: 567   128178    5.52%
    0     0    17139.7121  1086    18140.4799   MIRcuts: 46   128339    5.52%
    0     0    17139.8192  1086    18140.4799    MIRcuts: 5   128389    5.52%
    

Heuristic still looking.
0 2 17139.8192 1086 18140.4799 17139.8192 128389 5.52%
Elapsed time = 4468.66 sec. (3533283.43 ticks, tree = 0.02 MB)
1 3 17142.1491 1088 18140.4799 17139.8192 130043 5.52%
2 4 17142.6028 1082 18140.4799 17139.8192 132083 5.52%
3 5 17169.6273 1081 18140.4799 17139.8192 132267 5.52%
4 3 17288.7713 1102 18140.4799 17139.8192 133662 5.52%
5 4 17270.7188 1083 18140.4799 17139.8192 132678 5.52%
6 6 17174.0142 1062 18140.4799 17139.8192 134415 5.52%
7 7 17294.8080 1094 18140.4799 17142.1790 139536 5.50%
8 9 17193.8068 1072 18140.4799 17142.6028 143547 5.50%
9 10 17294.9808 1089 18140.4799 17142.6028 144982 5.50%
10 7 17306.2008 1089 18140.4799 17142.6028 139465 5.50%
Elapsed time = 4707.67 sec. (3622505.19 ticks, tree = 0.02 MB)
11 11 17195.1018 1070 18140.4799 17142.6028 146341 5.50%
12 12 17298.2337 1096 18140.4799 17142.6028 146931 5.50%

Thanks in advance

You are seeing “infeasible” in this context:

Root relaxation solution time = 756.09 sec. (1183507.55 ticks)

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

      0     0    infeasible                                      25951         

When “infeasible” appears like this, it means that the root relaxation is infeasible: CPLEX has determined that, even when the integrality restrictions on the variables are relaxed, the constraints have no feasible solution.

What’s not clear is why CPLEX then appears to start the solve again, and shows that a feasible solution could be found. There are some problems with the formatting of the listing that make it hard to analyze this, however. Can you copy the complete listing beginning with “Presolve eliminates . . .” into a file, and then reply with the file as an attachment?

Thanks for your explanation, Robert.
I attached the whole results of my code. You can see that the same situation happens in iterations 24, 26 and 30. Iteration 24 is particularly strange because it declares the objective as infeasible, but in the same line find an integer solution with gap 0.0%.
results_69_large_4.dat (754.0 KB)

After an integer-feasible solution is found, “infeasible” in the Objective column means that a particular subproblem in the search has been found by CPLEX to be infeasible. It’s not an indication that the entire problem is infeasible. So when you see

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

*     0+    0                        17236.5672 -5032401.1023              --- 
      0     0    infeasible          17236.5672                  12179    0.00%

the first line is reporting that an integer-feasible solution was found, with objective value 17236.5672. The second line indicates that the gap has been reduced to zero, and hence the feasible solution is optimal. But a lot could be happening between the first and the second line, that CPLEX is not reporting clearly.

In the other cases, the mystery is why CPLEX seems to report an infeasible root relaxation, then solves a different root relaxation and quickly finds an integer-feasible solution. The message

Classifier predicts products in MIQP should be linearized

indicates that CPLEX has a choice of how to handle the problem’s quadratic objective expressions, and is choosing to convert to a linear formulation rather than handling the quadratic objective directly by use of a quadratic programming extension to the solver. Maybe in a few cases, this choice leads to a relaxation that cannot be solved reliably, and CPLEX switches to the other alternative. The CPLEX option that controls this choice is as follows:

qtolin   Whether to linearize products of bounded variables
         in quadratic objectives:
            -1 = automatic choice (default)
             0 = no
             1 = yes.

The default (qtolin=-1) is to let CPLEX choose, and the message suggests that it is choosing qtolin=1. But you could experiment with specifying qtolin=0 in your cplex_options string instead, to see if that gives different results that might provide a clue as to what is happening. (To get results that are comparable, you should run the first, say, 25 iterations as before, and then add qtolin=0 before executing the 26th iteration.)