Initializing help system before first use

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:

∀ s ∈ SHARES: fracs ≤ buys

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:

s ∈ SHARES buys ≤ MAXNUM

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.