MIP model 1: limiting the number of different shares

Topics covered in this section:

To be able to count the number of different values we are investing in, we introduce a second set of variables buy_s in the LP model developed in Chapter Building models. These variables are indicator variables or binary variables. A variable buy_s takes the value 1 if the share s is taken into the portfolio and 0 otherwise.

We introduce the following constraint to limit the total number of assets to a maximum of MAXNUM. It expresses the constraint that at most MAXNUM of the variables buy_s may take the value 1 at the same time.

We now still need to link the new binary variables buy_s with the variables frac_s, the quantity of every share selected into the portfolio. The relation that we wish to express is `if a share is selected into the portfolio, then it is counted in the total number of values' or `if frac_s > 0 then buy_s = 1'. The following inequality formulates this implication:

If, for some s, frac_s is non-zero, then buy_s must be greater than 0 and hence 1. Conversely, if buy_s is at 0, then frac_s is also 0, meaning that no fraction of share s is taken into the portfolio. Notice that these constraints do not prevent the possibility that buy_s is at 1 and frac_s at 0. However, this does not matter in our case, since any solution in which this is the case is also valid with both variables, buy_s and frac_s, at 0.

Implementation with Java

We extend the LP model developed in Chapter Inputting and solving a Linear Programming problem with the new variables and constraints. The fact that the new variables are binary variables (i.e. they take only the values 0 and 1) is expressed through the type Binary at their creation.

Another common type of discrete variable is an integer variable, which is a variable that can take only on integer values between specified lower and upper bounds. These variables are defined in Java with the type Integer. In the following section (MIP model 2) we shall see yet another example of discrete variables, namely semi-continuous variables.

import static com.dashoptimization.objects.Utils.scalarProduct;
import static com.dashoptimization.objects.Utils.sum;
import static java.util.stream.IntStream.range;

import com.dashoptimization.ColumnType;
import com.dashoptimization.DefaultMessageListener;
import com.dashoptimization.XPRSenumerations.ObjSense;
import com.dashoptimization.objects.Variable;
import com.dashoptimization.objects.XpressProblem;

/**
 * Modeling a small MIP problem to perform portfolio optimization. -- Limiting
 * the total number of assets --
 */
public class FolioMIP {
    /* Max. number of different assets */
    private static final int MAXNUM = 4;
    /* Number of shares */
    private static final int NSHARES = 10;
    /* Number of high-risk shares */
    private static final int NRISK = 5;
    /* Number of North-American shares */
    private static final int NNA = 4;
    /* Estimated return in investment */
    private static final double[] RET = new double[] { 5, 17, 26, 12, 8, 9, 7, 6, 31, 21 };
    /* High-risk values among shares */
    private static final int[] RISK = new int[] { 1, 2, 3, 8, 9 };
    /* Shares issued in N.-America */
    private static final int[] NA = new int[] { 0, 1, 2, 3 };

    private static void printProblemStatus(XpressProblem prob) {
        System.out.println(String.format("Problem status:%n\tSolve status: %s%n\tSol status:
                %s", prob.attributes().getSolveStatus(), prob.attributes().getSolStatus()));
    }

    public static void main(String[] args) {
        try (XpressProblem prob = new XpressProblem()) {
            // Output all messages.
            prob.callbacks.addMessageCallback(DefaultMessageListener::console);

            /**** VARIABLES ****/
            Variable[] frac = prob.addVariables(NSHARES)
                    /* Fraction of capital used per share */
                    .withName(i -> String.format("frac_%d", i))
                    /* Upper bounds on the investment per share */
                    .withUB(0.3).toArray();

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

            /**** CONSTRAINTS ****/
            /* Limit the percentage of high-risk values */
            prob.addConstraint(sum(NRISK, i -> frac[RISK[i]]).leq(1.0 / 3.0).setName("Risk"));

            /* Minimum amount of North-American values */
            prob.addConstraint(sum(NNA, i -> frac[NA[i]]).geq(0.5).setName("NA"));

            /* Spend all the capital */
            prob.addConstraint(sum(frac).eq(1.0).setName("Cap"));

            /* 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)));

            /* Objective: maximize total return */
            prob.setObjective(scalarProduct(frac, RET), ObjSense.MAXIMIZE);

            /* Solve */
            prob.optimize();

            /* Solution printing */
            printProblemStatus(prob);
            System.out.println("Total return: " + prob.attributes().getObjVal());
            double[] sol = prob.getSolution();
            range(0, NSHARES).forEach(i -> System.out.println(String
                    .format("%s : %.2f%s (%.1f)", frac[i].getName(),
                             100.0 * frac[i].getValue(sol), "%", buy[i].getValue(sol))));
        }
    }
}

As with the previous chapter, the problem is solved by calling the optimize method. Since the problem now contains integer (binary) variables, the Xpress Optimizer solves the MIP problem via Branch-and-Bound.

Just as with the LP problem in the previous chapter, it is usually helpful to check the solution status before accessing the solution—only if the MIP status is `feasible (solution found)' or `optimal' will a meaningful solution be printed:

System.out.println(String.format("Solution status: %s", prob.attributes().getSolStatus()));

Analyzing the solution

As the result of the execution of our program we obtain the following output:

Maximizing MILP  using up to 20 threads and up to 31GB memory, with default controls
Original problem has:
        14 rows           20 cols           49 elements        10 entities
Presolved problem has:
        13 rows           19 cols           46 elements         9 entities
LP relaxation tightened
Presolve finished in 0 seconds

...

Dual solved problem

...

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

 Its Type    BestSoln    BestBound   Sols    Add    Del     Gap     GInf   Time
c           13.100000    14.066667      1                  6.87%       0      0
   1  K     13.100000    13.908571      1      1      0    5.81%       2      0
   2  K     13.100000    13.580000      1     11      0    3.53%       3      0
 *** Search completed ***
Uncrunching matrix
Final MIP objective                   : 1.310000000000000e+01
Final MIP bound                       : 1.310001310000000e+01
  Solution time / primaldual integral :      0.01s/ 43.157167%
  Number of solutions found / nodes   :         1 /         1
  Max primal violation      (abs/rel) : 5.551e-17 / 5.551e-17
  Max integer violation     (abs    ) :       0.0
Problem status:
	Solve status: Completed
	Sol status: Optimal
Total return: 13.1
frac_0 : 20.00% (1.0)
frac_1 : 0.00% (0.0)
frac_2 : 30.00% (1.0)
frac_3 : 0.00% (0.0)
frac_4 : 20.00% (1.0)
frac_5 : 30.00% (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)

At the beginning we see the log of the execution of Xpress Optimizer: the problem statistics (we now have 14 constraints and 20 variables, out of which 10 are MIP variables, refered to as `entities'), the log of the execution of the LP algorithm, the log of the built-in MIP heuristics (a solution with the value 13.1 has been found) and the automated cut generation (a total of 12 cuts of type `K' = knapsack have been generated). Since this problem is very small, it is solved by the MIP heuristics and the addition of cuts (additional constraints that cut off parts of the LP solution space, but no MIP solution) tightens the LP formulation in such a way that the solution to the LP relaxation becomes integer feasible. The Branch-and-Bound process therefore is not initiated and no log of the Branch-and-Bound search is displayed.

The output printed by our program tells us that the problem has been solved to optimality (i.e. the MIP search has been completed and at least one integer feasible solution has been found). The maximum return is now lower than in the original LP problem due to the additional constraint. As required, only four different shares are selected to form the portfolio.