Decision Optimization

 View Only

Too loose continuous relaxation in MBQPs

  • 1.  Too loose continuous relaxation in MBQPs

    Posted Mon October 23, 2023 07:00 AM
    Edited by Matheus Andrade Mon October 23, 2023 07:00 AM

    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.

    https://yetanothermathprogrammingconsultant.blogspot.com/2016/06/solving-non-convex-qp-problems-as-mip.html
    Since the orthogonality constraints, in the continuous search space, not necessarily will be met.
    https://yetanothermathprogrammingconsultant.blogspot.com/2016/06/solving-non-convex-qp-problems-as-mip.html
    Of course, good choices of big-Ms may be helful in this regard, since they will bound the values that the langrangian multpliers may assume.
    https://yetanothermathprogrammingconsultant.blogspot.com/2016/06/solving-non-convex-qp-problems-as-mip.html

    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
    ------------------------------