MIQP

We now wish to express the fact that at most a given number MAXNUM of different assets may be selected into the portfolio, subject to all other constraints of the previous QP model. In Chapter 11 we have already seen how this can be done, namely by introducing an additional set of binary decision variables buy_s that are linked logically to the continuous variables:

Through this relation, a variable buy_s will be at 1 if a fraction frac_s greater than 0 is selected into the portfolio. If, however, buy_s equals 0, then frac_s must also be 0.

To limit the number of different shares in the portfolio, we then define the following constraint:

Implementation with BCL

We may modify the previous QP model or simply append the following lines to the program of the previous section, just after the solution printing: the problem is then solved once as a QP and once as a MIQP in a single program run.

 XPRBvar buy[NSHARES];             // 1 if asset is in portfolio, 0 otherwise

// Create the decision variables
 for(s=0;s<NSHARES;s++)
  buy[s] = p.newVar(XPRBnewname("buy(%d)",s+1), XPRB_BV);

// Limit the total number of assets
 for(s=0;s<NSHARES;s++) Num += buy[s];
 p.newCtr(Num <= MAXNUM);

// Linking the variables
 for(s=0;s<NSHARES;s++) p.newCtr(frac[s] <= buy[s]);

// Solve the problem
 p.mipOptimize("");

// Solution printing
 cout << "With a target of " << TARGET << " and at most " << MAXNUM <<
         " assets, minimum variance is " << p.getObjVal() << endl;
 for(s=0;s<NSHARES;s++)
  cout << s << ": " << frac[s].getSol()*100 << "% (" << buy[s].getSol()
       << ")" << endl;

When executing the MIQP model, we obtain the following solution output:

Reading Problem FolioQP
Problem Statistics
          14 (    514 spare) rows
          20 (      0 spare) structural columns
          54 (   5056 spare) non-zero elements
          76 quadratic elements
Global Statistics
          10 entities        0 sets        0 set members
Minimizing MIQP FolioQP
Original problem has:
        14 rows           20 cols           54 elements        10 globals
        76 qobjelem
Presolved problem has:
        14 rows           20 cols           54 elements        10 globals
        76 qobjelem
LP relaxation tightened
Will try to keep branch and bound tree memory usage below 14.8Gb
Crash basis containing 0 structural columns created

   Its         Obj Value      S   Ninf  Nneg        Sum Inf  Time
     0           .000000      p      1     4        .100000     0
     8           .000000      p      0     0        .000000     0
     8          4.609000      p      0     0        .000000     0

   Its         Obj Value      S   Nsft  Nneg       Dual Inf  Time
    27           .557393     QP      0     0        .000000     0
QP solution found
Optimal solution found
Primal solved problem
  27 simplex iterations in 0s

Final objective                         : 5.573934108103899e-01
  Max primal violation      (abs / rel) : 1.804e-16 / 1.804e-16
  Max dual violation        (abs / rel) : 1.776e-15 / 1.776e-15
  Max complementarity viol. (abs / rel) : 2.670e-16 / 1.007e-16
All values within tolerances

Starting root cutting & heuristics

 Its Type    BestSoln    BestBound   Sols    Add    Del     Gap     GInf   Time
a            4.094715      .557393      1                 86.39
b            1.839000      .557393      2                 69.69
q            1.825619      .557393      3                 69.47
k            1.419003      .557393      4                 60.72
   1  K      1.419003      .557393      4      3      0   60.72      0
   2  K      1.419003      .557393      4      9      2   60.72      0
   3  K      1.419003      .557393      4      7      6   60.72      0
   4  K      1.419003      .557393      4      5      6   60.72      0
   5  K      1.419003      .557393      4     11      5   60.72      0
   6  K      1.419003      .558122      4      8     10   60.67      0
   7  K      1.419003      .570670      4     11      9   59.78      0
   8  K      1.419003      .570670      4      5     12   59.78      0
   9  K      1.419003      .583638      4      5      3   58.87      0
  10  K      1.419003      .612496      4      4      0   56.84      0
  11  K      1.419003      .618043      4      6      5   56.45      0
  12  K      1.419003      .620360      4      8      4   56.28      0
  13  K      1.419003      .620360      4      0      6   56.28      0
Heuristic search started
Heuristic search stopped

Cuts in the matrix         : 14
Cut elements in the matrix : 138

Starting tree search.
Deterministic mode with up to 8 running threads and up to 16 tasks.

    Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
a      9     1.248762      .919281      5      2      5   26.38
 *** Search completed ***     Time:     0 Nodes:         15
Number of integer feasible solutions found is 5
Best integer solution found is     1.248762
Best bound is     1.248752
Uncrunching matrix
With a target of 9 and at most 4 assets, minimum variance is 1.24876
0: 30% (1)
1: 20% (1)
2: 0% (0)
3: 0% (0)
4: 23.8095% (1)
5: 26.1905% (1)
6: 0% (0)
7: 0% (0)
8: 0% (0)
9: 0% (0)

The log of the Branch-and-Bound search tells us this time that 5 integer feasible solutions have been found (all by the MIP heuristics) and a total of 15 nodes have been enumerated to complete the search.With the additional constraint on the number of different assets the minimum variance is more than twice as large as in the QP problem.