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 Mixed Integer Programming we have already seen how this can be done 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 Java

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.

/***** Second problem: limit total number of assets *****/
            Variable[] buy = prob.addVariables(NSHARES)
                    /* Fraction of capital used per share */
                    .withName(i -> String.format("buy_%d", i))
                    .withType(ColumnType.Binary).toArray();

            /* Limit the total number of assets */
            prob.addConstraint(sum(buy).leq(MAXNUM).setName("MaxAssets"));

            /* Linking the variables */
            /* frac .<= buy */
            prob.addConstraints(NSHARES, i -> frac[i].leq(buy[i])
                     .setName(String.format("link_%d", i)));

            /* Solve */
            prob.optimize();

            /* Solution printing */
            printProblemStatus(prob);
            System.out.println("With a target of " + TARGET + " and at most " + MAXNUM +
                    " assets, minimum variance is " + prob.attributes().getObjVal());
            double[] solmip = prob.getSolution();
            range(0, NSHARES).forEach(i -> System.out.println(String.
                    format("%s : %.2f%s (%.1f)", frac[i].getName(),
                           100.0 * frac[i].getValue(solmip), "%", buy[i].getValue(solmip))));

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

Minimizing MIQP  using up to 20 threads and up to 31GB memory, with default controls
Original problem has:
        14 rows           20 cols           54 elements        10 entities
        76 qobjelem
Presolved problem has:
        14 rows           20 cols           54 elements        10 entities
        76 qobjelem
LP relaxation tightened
Presolve finished in 0 seconds
Heap usage: 2671KB (peak 11MB, 117KB system)

Coefficient range                    original                 solved
  Coefficients   [min,max] : [ 1.00e+00,  3.10e+01] / [ 6.25e-02,  1.00e+00]
  RHS and bounds [min,max] : [ 3.00e-01,  9.00e+00] / [ 5.00e-01,  4.80e+00]
  Objective      [min,max] : [      0.0,       0.0] / [      0.0,       0.0]
  Quadratic      [min,max] : [ 2.00e-01,  5.60e+01] / [ 7.81e-03,  6.88e-01]
Autoscaling applied standard scaling

Will try to keep branch and bound tree memory usage below 10.8GB
Crash basis containing 10 structural columns created

   Its         Obj Value      S   Ninf  Nneg   Sum Dual Inf  Time
     0           .000000      D      3     0        .000000     0
     3           .000000      D      0     0        .000000     0
     3          1.544000      P      0     0        .000000     0

   Its         Obj Value      S   Nsft  Nneg       Dual Inf  Time
    11           .557393     QP      0     0        .000000     0
QP solution found
Optimal solution found
Primal solved problem
  11 simplex iterations in 0.00 seconds at time 0

Final objective                       : 5.573934108103896e-01
  Max primal violation      (abs/rel) : 4.337e-17 / 4.337e-17
  Max dual violation        (abs/rel) :       0.0 /       0.0
  Max complementarity viol. (abs/rel) : 1.967e-16 / 8.590e-17

Starting root cutting & heuristics
Deterministic mode with up to 4 additional threads

 Its Type    BestSoln    BestBound   Sols    Add    Del     Gap     GInf   Time
a            4.094716      .557393      1                 86.39%       0      0
b            1.839005      .557393      2                 69.69%       0      0
q            1.568666      .557393      3                 64.47%       0      0
k            1.419001      .557393      4                 60.72%       0      0
   1  K      1.419001      .557393      4      5      0   60.72%       7      0
   2  K      1.419001      .557393      4      3      2   60.72%       7      0
   3  K      1.419001      .557393      4     10      2   60.72%       7      0
   4  K      1.419001      .560790      4      7      7   60.48%       7      0
   5  K      1.419001      .570150      4     13      7   59.82%       8      0
   6  K      1.419001      .611241      4     16     10   56.92%       9      0
   7  K      1.419001      .623987      4     19     13   56.03%       9      0
   8  K      1.419001      .628253      4      8     17   55.73%       8      0
   9  K      1.419001      .628253      4      0      9   55.73%       9      0
Heuristic search 'R' started
Heuristic search 'R' stopped

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

Starting tree search.
Deterministic mode with up to 20 running threads and up to 64 tasks.
Heap usage: 3324KB (peak 11MB, 123KB system)

    Node     BestSoln    BestBound   Sols Active  Depth     Gap     GInf   Time
       1     1.419001      .628257      4      2      1   55.73%       9      0
       2     1.419001      .628257      4      2      3   55.73%       5      0
       5     1.419001      .628257      4      2      4   55.73%       5      0
       6     1.419001      .628257      4      2      4   55.73%       5      0
       7     1.419001      .628257      4      2      4   55.73%       2      0
       8     1.419001      .628257      4      2      3   55.73%       5      0
       9     1.419001      .628257      4      2      4   55.73%       4      0
      10     1.419001      .628257      4      2      4   55.73%       7      0
a     17     1.248762      .984678      5      2      6   21.15%       0      0
      21     1.248762      .984678      5      1      5   21.15%       3      0
 *** Search completed ***
Numerical issues encountered:
   Singular bases   :      5 out of        79 (ratio: 0.0633)
Uncrunching matrix
Final MIP objective                   : 1.248761964861501e+00
Final MIP bound                       : 1.248751964861501e+00
  Solution time / primaldual integral :      0.03s/ 56.546729%
  Number of solutions found / nodes   :         5 /        25
  Max primal violation      (abs/rel) :       0.0 /       0.0
  Max integer violation     (abs    ) :       0.0
Problem status:
	Solve status: Completed
	Sol status: Optimal
With a target of 9 and at most 4 assets, minimum variance is 1.2487619648615007
frac_0 : 30.00% (1.0)
frac_1 : 20.00% (1.0)
frac_2 : 0.00% (0.0)
frac_3 : 0.00% (0.0)
frac_4 : 23.81% (1.0)
frac_5 : 26.19% (1.0)
frac_6 : 0.00% (0.0)
frac_7 : 0.00% (0.0)
frac_8 : 0.00% (0.0)
frac_9 : 0.00% (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 25 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.