Same box-constrained nonconvex QP: direct x’Qx formulation solves in 397 s, explicit lifting X = xx’ stalls at 11.8% gap after 7200 s. Why?

Hi Gurobi Engineers,

I’m comparing two mathematically equivalent formulations of a box-constrained nonconvex QP (n = 250, Gurobi 13.0.2, academic license, TimeLimit=7200, all other parameters default, 8 threads on a 4-core / 8-thread Xeon @ 2.20GHz). Both runs were on the same machine with no other jobs running.

Formulation 1 (lifted): min ⟨Q,X⟩ + c’x s.t. 0 ≤ x ≤ 1, X = xx’
Formulation 2 (direct): min x’Qx + c’x s.t. 0 ≤ x ≤ 1

Q is sparse (1,644 nonzero quadratic terms). In the lifted model, X_ij is created for all i ≤ j (31,375 variables and constraints X_ij = x_i x_j), including pairs with Q_ij = 0.

Formulation 2 solves to optimality in 397 s, while Formulation 1 hits the 7200 s limit with an 11.8% gap. From the logs: after presolve, Formulation 2 has 569 binary variables and 360 bilinear constraints, while Formulation 1 has 0 integer variables and 1,577 bilinear constraints; Formulation 2 uses Gomory/MIR/Zero-half/Flow-cover cuts, Formulation 1 only RLT/BQP/PSD.

My questions:

1. Is it expected that explicitly adding X = xx’ makes Gurobi lose the box-QP-specific handling it applies to the direct formulation? What does presolve do differently in the two cases?
2. We plan to add our own valid inequalities on X (RLT/PSD-type) in follow-up experiments. Is there a recommended way to do this without losing the structure Gurobi exploits in the direct formulation?

Truncated logs are below (middle of the node log omitted).

Thanks a lot for any insight!

Formulation 1:
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (linux64 - "Ubuntu 24.04.5 LTS")

CPU model: Intel(R) Xeon(R) CPU @ 2.20GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Non-default parameters:
TimeLimit  7200

Optimize a model with 0 rows, 31625 columns and 0 nonzeros (Min)
Model has 1657 linear objective coefficients
Model has 31375 quadratic constraints
Coefficient statistics:
 Matrix range     [0e+00, 0e+00]
 QMatrix range    [1e+00, 1e+00]
 QLMatrix range   [1e+00, 1e+00]
 Objective range  [1e+00, 1e+02]
 Bounds range     [1e+00, 1e+00]
 RHS range        [0e+00, 0e+00]

Continuous model is non-convex -- solving as a MIP

Found heuristic solution: objective 0.0000000
Presolve removed 0 rows and 31375 columns
Presolve time: 0.02s
Presolved: 3108 rows, 1896 columns, 7859 nonzeros
Presolved model has 67 quadratic constraint(s)
Presolved model has 1577 bilinear constraint(s)
Found heuristic solution: objective -0.0000000
Variable types: 1896 continuous, 0 integer (0 binary)
Performing another presolve...
Presolve removed 0 rows and 1 columns
Presolve time: 0.05s
Found heuristic solution: objective -14331.92571

Root relaxation: objective -2.011100e+04, 1710 iterations, 0.07 seconds (0.05 work units)

   Nodes    |    Current Node    |     Objective Bounds      |     Work
Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

    0     0 -20111.000    0 1570 -14331.926 -20111.000  40.3%     -    0s
    0     0 -17827.268    0 1470 -14331.926 -17827.268  24.4%     -    0s
    0     0 -17677.424    0 1457 -14331.926 -17677.424  23.3%     -    0s
    0     0 -17675.778    0 1457 -14331.926 -17675.778  23.3%     -    0s
    0     2 -17675.778    0 1457 -14331.926 -17675.778  23.3%     -    3s
H  118   120                    -14381.60282 -17534.525  21.9%   110    4s
  ...
 2038  1475 -16071.368   28 1611 -14381.603 -17120.536  19.0%   154   30s
  ...
12022 10450 -15199.195   44 1578 -14381.603 -16764.917  16.6%   164   90s
  ...
H31963 26280                    -14383.92750 -16600.891  15.4%   169  215s
  ...
143371 107431     cutoff   47      -14383.927 -16360.533  13.7%   172  900s
  ...
504425 363267 -15968.029   30 1594 -14383.927 -16184.328  12.5%   181 3284s
  ...
1073999 748076     cutoff   46      -14383.927 -16076.944  11.8%   188 7200s

Cutting planes:
 RLT: 389
 BQP: 12
 PSD: 128

Explored 1074652 nodes (202370603 simplex iterations) in 7200.06 seconds (5487.33 work units)
Thread count was 8 (of 8 available processors)

Solution count 5: -14383.9 -14381.6 -14331.9 ... 0

Time limit reached
Best objective -1.438392749998e+04, best bound -1.607676278062e+04, gap 11.7689%

Formulation 2
Gurobi Optimizer version 13.0.2 build v13.0.2rc1 (linux64 - "Ubuntu 24.04.5 LTS")

CPU model: Intel(R) Xeon(R) CPU @ 2.20GHz, instruction set [SSE2|AVX|AVX2]
Thread count: 4 physical cores, 8 logical processors, using up to 8 threads

Non-default parameters:
TimeLimit  7200

Optimize a model with 0 rows, 250 columns and 0 nonzeros (Min)
Model has 13 linear objective coefficients
Model has 1644 quadratic objective terms
Coefficient statistics:
 Matrix range     [0e+00, 0e+00]
 Objective range  [1e+00, 5e+01]
 QObjective range [2e+00, 2e+02]
 Bounds range     [1e+00, 1e+00]
 RHS range        [0e+00, 0e+00]

Continuous model is non-convex -- solving as a MIP

Found heuristic solution: objective 0.0000000
Presolve removed 0 rows and 1 columns
Presolve time: 0.02s
Presolved: 2505 rows, 1888 columns, 7235 nonzeros
Presolved model has 67 quadratic constraint(s)
Presolved model has 360 bilinear constraint(s)
Variable types: 1319 continuous, 569 integer (569 binary)
Found heuristic solution: objective -58.0000000
Found heuristic solution: objective -14331.92571

Root relaxation: objective -2.011100e+04, 1635 iterations, 0.05 seconds (0.04 work units)

   Nodes    |    Current Node    |     Objective Bounds      |     Work
Expl Unexpl |  Obj  Depth IntInf | Incumbent    BestBd   Gap | It/Node Time

    0     0 -20111.000    0  723 -14331.926 -20111.000  40.3%     -    0s
    0     0 -17679.269    0  705 -14331.926 -17679.269  23.4%     -    0s
    0     0 -17285.204    0  713 -14331.926 -17285.204  20.6%     -    0s
    0     0 -17089.295    0  715 -14331.926 -17089.295  19.2%     -    1s
    ...
    0     0 -16334.713    0  841 -14331.926 -16334.713  14.0%     -    3s
    0     2 -16334.713    0  841 -14331.926 -16334.713  14.0%     -    4s
    7    12 -15881.210    3  817 -14331.926 -16047.801  12.0%   834    5s
  183   172 -15374.574    8  774 -14331.926 -16030.556  11.9%   444   10s
H  366   288                    -14333.06857 -16030.556  11.8%   354   13s
  ...
 1024   533 -14706.738   24  864 -14383.927 -15275.994  6.20%   394   95s
  ...
 4004  1226 -14395.672   25  845 -14383.927 -14896.770  3.57%   329  152s
  ...
H 8588  1792                    -14400.14828 -14758.318  2.49%   302  223s
  ...
19937   152     cutoff   32      -14400.148 -14519.715  0.83%   271  394s
20541     0     cutoff   29      -14400.148 -14420.753  0.14%   268  397s

Cutting planes:
 Gomory: 44
 MIR: 53
 Flow cover: 74
 Zero half: 329
 RLT: 172
 BQP: 5
 PSD: 211

Explored 21479 nodes (5512753 simplex iterations) in 397.13 seconds (376.06 work units)
Thread count was 8 (of 8 available processors)

Solution count 7: -14400.1 -14383.9 -14372.5 ... 0
No other solutions better than -14400.1

Optimal solution found (tolerance 1.00e-04)
Best objective -1.440014827921e+04, best bound -1.440014827921e+04, gap 0.0000%