Hello.
I am playing around with some MBQPs with Cplex, and I am noticing a, perhaps, strange behaviour. For instance, when executing Cplex over the MBQP instance meanvar-orl400_05_e_8, I obtain the following logs:
Version identifier: 22.1.1.0 | xxxx-xx-xx | xxxxxxxxx
Tried aggregator 1 time.
MIQP Presolve eliminated 7 rows and 400 columns.
MIQP Presolve modified 400 coefficients.
Reduced MIQP has 1596 rows, 1200 columns, and 4386 nonzeros.
Reduced MIQP has 400 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 160400 nonzeros.
Presolve time = 0.01 sec. (19.35 ticks)
Probing fixed 0 vars, tightened 183 bounds.
Probing time = 0.00 sec. (0.30 ticks)
Tried aggregator 1 time.
MIQP Presolve modified 396 coefficients.
Reduced MIQP has 1596 rows, 1200 columns, and 4386 nonzeros.
Reduced MIQP has 400 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 160400 nonzeros.
Presolve time = 0.00 sec. (17.73 ticks)
Classifier predicts products in MIQP should be linearized.
Probing time = 0.00 sec. (0.28 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 20 threads.
Root relaxation solution time = 0.17 sec. (301.35 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
0 0 97.6002 23 97.6002 25
* 0+ 0 105.8823 97.6002 7.82%
* 0+ 0 99.8910 97.6002 2.29%
Repeating presolve.
Tried aggregator 1 time.
MIQP Presolve eliminated 1197 rows and 900 columns.
MIQP Presolve modified 218 coefficients.
Reduced MIQP has 399 rows, 300 columns, and 1093 nonzeros.
Reduced MIQP has 100 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 10100 nonzeros.
Presolve time = 0.02 sec. (73.48 ticks)
Probing time = 0.00 sec. (0.07 ticks)
Tried aggregator 1 time.
MIQP Presolve modified 21 coefficients.
Reduced MIQP has 399 rows, 300 columns, and 1093 nonzeros.
Reduced MIQP has 100 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 10100 nonzeros.
Presolve time = 0.00 sec. (1.23 ticks)
Represolve time = 0.02 sec. (76.19 ticks)
Probing time = 0.00 sec. (0.07 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 20 threads.
Root relaxation solution time = 0.02 sec. (16.43 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 99.8910 97.6611 2.23%
0 0 97.6002 23 99.8910 97.6611 63 2.23%
0 2 97.6002 23 99.8910 97.8373 63 2.06%
Elapsed time = 0.94 sec. (1286.55 ticks, tree = 0.02 MB, solutions = 2)
* 35+ 6 99.4826 97.8373 1.65%
Root node processing (before b&c):
Real time = 0.93 sec. (1285.23 ticks)
Parallel b&c, 20 threads:
Real time = 0.15 sec. (135.91 ticks)
Sync time (average) = 0.08 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 1.09 sec. (1421.14 ticks)
Solution pool: 4 solutions saved.
MIP - Integer optimal, tolerance (0.0001/1e-06): Objective = 9.9482645011e+01
Current MIP best bound = 9.9473292095e+01 (gap = 0.00935292, 0.01%)
Solution time = 1.10 sec. Iterations = 7934 Nodes = 2342 (14)
Deterministic time = 1421.14 ticks (1295.80 ticks/sec)
Which is just fine, but, if I run Cplex over the QAP insatnce had20 (lp file in attachment), I obtain the following log.
Version identifier: 22.1.1.0 | xxxx-xx-xx | xxxxxxxxx
Found incumbent of value 2950640.000000 after 0.00 sec. (1.12 ticks)
Tried aggregator 1 time.
MIP Presolve added 144400 rows and 72200 columns.
Reduced MIP has 144440 rows, 72600 columns, and 289600 nonzeros.
Reduced MIP has 72600 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.03 sec. (19.92 ticks)
Probing time = 0.08 sec. (6.40 ticks)
Tried aggregator 1 time.
Detecting symmetries...
MIP Presolve eliminated 72200 rows and 0 columns.
Reduced MIP has 72240 rows, 72600 columns, and 217400 nonzeros.
Reduced MIP has 72600 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.12 sec. (173.60 ticks)
Classifier predicts products in MIQP should not be linearized.
Represolve...
Tried aggregator 1 time.
Repairing indefinite Q in the objective.
Reduced MIQP has 40 rows, 400 columns, and 800 nonzeros.
Reduced MIQP has 400 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 144800 nonzeros.
Presolve time = 0.02 sec. (137.88 ticks)
Probing time = 0.00 sec. (0.04 ticks)
Tried aggregator 1 time.
Reduced MIQP has 40 rows, 400 columns, and 800 nonzeros.
Reduced MIQP has 400 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 144800 nonzeros.
Presolve time = 0.01 sec. (77.58 ticks)
Probing time = 0.00 sec. (0.04 ticks)
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 20 threads.
Root relaxation solution time = 0.08 sec. (345.23 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 2950640.0000 0.0000 100.00%
0 0 -110203.9147 400 2950640.0000 0.0000 8 100.00%
* 0+ 0 12912.0000 0.0000 100.00%
* 0+ 0 12648.0000 0.0000 100.00%
0 0 -1.00000e+75 0 12648.0000 0.0000 8 100.00%
0 2 -110203.9147 400 12648.0000 0.0000 8 100.00%
Elapsed time = 1.26 sec. (2715.31 ticks, tree = 0.02 MB, solutions = 3)
29 11 -100624.3332 391 12648.0000 0.0000 29 100.00%
765 657 -104906.2025 381 12648.0000 0.0000 785 100.00%
* 1084+ 696 12248.0000 0.0000 100.00%
* 1120+ 802 11992.0000 0.0000 100.00%
1162 1112 -91429.6840 345 11992.0000 0.0000 1320 100.00%
* 1206+ 980 11770.0000 0.0000 100.00%
* 1232+ 1010 11552.0000 0.0000 100.00%
* 1311+ 1083 10782.0000 0.0000 100.00%
1512 1350 -84071.9297 305 10782.0000 0.0000 1606 100.00%
2326 1926 -68998.7127 255 10782.0000 0.0000 2275 100.00%
3609 2823 -46325.2851 157 10782.0000 0.0000 3308 100.00%
4711 4243 -68268.6903 214 10782.0000 0.0000 5014 100.00%
Performing restart 1
Repeating presolve.
Tried aggregator 1 time.
Reduced MIQP has 40 rows, 400 columns, and 800 nonzeros.
Reduced MIQP has 400 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 144800 nonzeros.
Presolve time = 0.01 sec. (77.58 ticks)
Tried aggregator 1 time.
Reduced MIQP has 40 rows, 400 columns, and 800 nonzeros.
Reduced MIQP has 400 binaries, 0 generals, 0 SOSs, and 0 indicators.
Reduced MIQP objective Q matrix has 144800 nonzeros.
Presolve time = 0.01 sec. (77.58 ticks)
Represolve time = 0.03 sec. (161.94 ticks)
* 5072+ 0 10654.0000 -109050.2308 ---
5072 0 -1.00000e+75 0 10654.0000 -109050.2308 6033 ---
5072 2 -110203.9147 400 10654.0000 -109050.2308 6033 ---
5082 12 -109257.6830 390 10654.0000 -109050.2308 6045 ---
* 5092+ 8 10520.0000 -108353.0759 ---
5426 314 -104294.6788 360 10520.0000 -108274.3535 6371 ---
Elapsed time = 5.55 sec. (8785.30 ticks, tree = 0.06 MB, solutions = 16)
5584 462 -104299.4093 381 10520.0000 -108146.2613 6561 ---
* 9395+ 1076 10156.0000 -108146.2613 ---
10610 1374 -43441.9009 107 10156.0000 -108146.2613 7510 ---
* 13998+ 2604 9034.0000 -107526.4753 ---
* 14027+ 2604 8942.0000 -107526.4753 ---
* 14062+ 2604 8572.0000 -107526.4753 ---
17125 9487 -35357.9377 142 8572.0000 -107187.7235 17272 ---
* 23289+15889 8526.0000 -106997.1526 ---
* 23349+15889 8458.0000 -106997.1526 ---
* 23448+15889 8446.0000 -106997.1526 ---
* 23822+15889 8202.0000 -106997.1526 ---
24219 17427 -96021.4099 350 8202.0000 -106997.1526 26431 ---
* 24732+16801 8176.0000 -106997.1526 ---
32583 25274 -63902.3627 213 8176.0000 -106458.1459 34845 ---
* 32633+25553 7804.0000 -106458.1459 ---
* 32633+25553 7788.0000 -106301.2476 ---
* 32633+26117 7772.0000 -106301.2476 ---
40493 32195 -93276.8193 328 7772.0000 -105812.0000 42294 ---
46957 38723 -66947.2844 217 7772.0000 -105605.4017 49343 ---
^C 53827 46672 -57691.5406 187 7772.0000 -105480.7255 57942 ---
Root node processing (before b&c):
Real time = 1.20 sec. (2671.67 ticks)
Parallel b&c, 20 threads:
Real time = 14.02 sec. (15143.87 ticks)
Sync time (average) = 3.94 sec.
Wait time (average) = 0.02 sec.
------------
Total (root+branch&cut) = 15.22 sec. (17815.54 ticks)
Solution pool: 48 solutions saved.
MIP - Aborted, integer feasible: Objective = 7.7720000000e+03
Current MIP best bound = 0.0000000000e+00 (gap = 7772, 100.00%)
Solution time = 15.25 sec. Iterations = 60007 Nodes = 53919 (48549)
Deterministic time = 17815.55 ticks (1168.28 ticks/sec)
Note that, I interrupted the algorithm (to make this post short), but after a couple minutes Cplex is able to find the optimal solution. What intrigues me, are the values obtained by the continuous relaxations, they are negative, and not only negative, they are "extremely" negative. Furthermore, the GAP info starts with 100% and then becomes absent. This behaviour doesn't manifest when solving the instance meanvar-orl400_05_e_8.
I am not entirely sure of how Cplex manages QPs, but my guess is that, behind the hood, Cplex converts the given QP into a MILP, based on a solving of a KKT system (as showed here and here). And that, when the integrality constraints are not met (when at least a non-integer variable is not fixed or does not have an integer value in the relaxation), the values of the langrangian multipliers at the objective function of the resulting KKT system, become to loose.
Since the orthogonality constraints, in the continuous search space, not necessarily will be met.
My guess is that, the reason for obtaining so loose relaxations comes from possibly too large big-Ms, and that wisest picked big-Ms would result in better relaxations. For instance, I have coded my own KKT system for QPs, and I have debbugged the had20 instance by inputing its optimal soution and then retrieving its corresponding optimal lagrangian multipliers, and then inputing these obtained multipliers as bounds (big-Ms) for the lagrangean multipliers (the resulting lp file follows in the attachment). Obtaining the following results:
Version identifier: 22.1.1.0 | xxxx-xx-xx | xxxxxxxxx
Tried aggregator 2 times.
MIP Presolve eliminated 2420 rows and 1178 columns.
MIP Presolve modified 22 coefficients.
Aggregator did 411 substitutions.
Reduced MIP has 1251 rows, 1251 columns, and 293644 nonzeros.
Reduced MIP has 400 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.13 sec. (137.37 ticks)
Found incumbent of value 4.0758452e+08 after 0.17 sec. (187.92 ticks)
Probing time = 0.45 sec. (11.01 ticks)
Tried aggregator 1 time.
Detecting symmetries...
MIP Presolve modified 800 coefficients.
Reduced MIP has 1251 rows, 1251 columns, and 293644 nonzeros.
Reduced MIP has 400 binaries, 0 generals, 0 SOSs, and 0 indicators.
Presolve time = 0.09 sec. (106.26 ticks)
Probing time = 0.03 sec. (11.68 ticks)
Clique table members: 40.
MIP emphasis: balance optimality and feasibility.
MIP search method: dynamic search.
Parallel mode: deterministic, using up to 20 threads.
Root relaxation solution time = 0.25 sec. (671.91 ticks)
Nodes Cuts/
Node Left Objective IInf Best Integer Best Bound ItCnt Gap
* 0+ 0 4.07585e+08 6554.0000 100.00%
* 0+ 0 8353.0000 6554.0000 21.54%
0 0 6554.6884 62 8353.0000 6554.6884 1577 21.53%
* 0+ 0 6922.0000 6554.6884 5.31%
0 0 6602.4816 59 6922.0000 Cuts: 27 2076 4.62%
0 0 6603.9797 62 6922.0000 Fract: 1 2158 4.59%
Detecting symmetries...
0 2 6603.9797 62 6922.0000 6603.9797 2158 4.59%
Elapsed time = 1.85 sec. (3378.41 ticks, tree = 0.02 MB, solutions = 3)
5 4 6652.2249 57 6922.0000 6604.0445 2947 4.59%
48 11 6703.7662 53 6922.0000 6606.2999 4316 4.56%
113 97 6689.1319 55 6922.0000 6606.6828 22566 4.56%
224 176 cutoff 6922.0000 6606.6828 33722 4.56%
384 272 6804.0455 41 6922.0000 6606.6828 45335 4.56%
530 396 6861.1800 44 6922.0000 6606.6828 62905 4.56%
638 471 6754.5960 54 6922.0000 6606.6828 75279 4.56%
795 570 6914.8467 38 6922.0000 6606.6828 91228 4.56%
951 674 6709.9988 45 6922.0000 6606.6828 106323 4.56%
1560 1035 6735.0445 50 6922.0000 6611.6060 160020 4.48%
Elapsed time = 5.91 sec. (6509.61 ticks, tree = 0.69 MB, solutions = 3)
2364 1497 6698.7324 53 6922.0000 6618.7467 210190 4.38%
3313 2254 6811.7825 44 6922.0000 6621.0801 264980 4.35%
^C
Implied bound cuts applied: 8
Gomory fractional cuts applied: 4
Root node processing (before b&c):
Real time = 1.80 sec. (3329.38 ticks)
Parallel b&c, 20 threads:
Real time = 7.13 sec. (5797.90 ticks)
Sync time (average) = 2.38 sec.
Wait time (average) = 0.00 sec.
------------
Total (root+branch&cut) = 8.92 sec. (9127.27 ticks)
Solution pool: 3 solutions saved.
MIP - Aborted, integer feasible: Objective = 6.9220000000e+03
Current MIP best bound = 6.6210801102e+03 (gap = 300.92, 4.35%)
Solution time = 8.93 sec. Iterations = 301956 Nodes = 3593 (2930)
Deterministic time = 9127.28 ticks (1022.15 ticks/sec)
Note that, again, I also interrupted the optimization process. Does some one know any strategy for finding better big-Ms for the orthogonality constraints? In order to tight further the continuous relaxation.
Case there is any error in my post, please, let me know. Thanks and regards.
------------------------------
Matheus Andrade
------------------------------