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 buys that are linked logically to the continuous variables:
Through this relation, a variable buys will be at 1 if a fraction fracs greater than 0 is selected into the portfolio. If, however, buys equals 0, then fracs 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.
© 2001-2020 Fair Isaac Corporation. All rights reserved. This documentation is the property of Fair Isaac Corporation (“FICO”). Receipt or possession of this documentation does not convey rights to disclose, reproduce, make derivative works, use, or allow others to use it except solely for internal evaluation purposes to determine whether to purchase a license to the software described in this documentation, or as otherwise set forth in a written software license agreement between you and FICO (or a FICO affiliate). Use of this documentation and the software described in it must conform strictly to the foregoing permitted uses, and no other use is permitted.