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 included in 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 Mosel

We extend the LP model developed in Chapter Inputting and solving a Linear Programming problem (using the initialization of data from file introduced in Chapter Working with data) with the new variables and constraints. The fact that the new variables are binary variables (i.e. they only take the values 0 and 1) is expressed through the is_binary constraint.

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

model "Portfolio optimization with MIP"
 uses "mmxprs"                      ! Use Xpress Optimizer

 parameters
  MAXRISK = 1/3                     ! Max. investment into high-risk values
  MAXVAL = 0.3                      ! Max. investment per share
  MINAM = 0.5                       ! Min. investment into N.-American values
  MAXNUM = 4                        ! Max. number of different assets
 end-parameters

 declarations
  SHARES: set of string             ! Set of shares
  RISK: set of string               ! Set of high-risk values among shares
  NA: set of string                 ! Set of shares issued in N.-America
  RET: array(SHARES) of real        ! Estimated return in investment
 end-declarations

 initializations from "folio.dat"
  RISK RET NA
 end-initializations

 declarations
  frac: array(SHARES) of mpvar      ! Fraction of capital used per share
  buy: array(SHARES) of mpvar       ! 1 if asset is in portfolio, 0 otherwise
 end-declarations

! Objective: total return
 Return:= sum(s in SHARES) RET(s)*frac(s)

! Limit the percentage of high-risk values
 sum(s in RISK) frac(s) <= MAXRISK

! Minimum amount of North-American values
 sum(s in NA) frac(s) >= MINAM

! Spend all the capital
 sum(s in SHARES) frac(s) = 1

! Upper bounds on the investment per share
 forall(s in SHARES) frac(s) <= MAXVAL

! Limit the total number of assets
 sum(s in SHARES) buy(s) <= MAXNUM

 forall(s in SHARES) do
  buy(s) is_binary                  ! Turn variables into binaries
  frac(s) <= buy(s)                 ! Linking the variables
 end-do

! Solve the problem
 maximize(Return)

! Solution printing
 writeln("Total return: ", getobjval)
 forall(s in SHARES)
  writeln(s, ": ", getsol(frac(s))*100, "% (", getsol(buy(s)), ")")

end-model

In the model foliomip1.mos above we have used the second form of the forall loop, namely forall/do, that needs to be used if the loop encompasses several statements. Equivalently we could have written

 forall(s in SHARES) buy(s) is_binary
 forall(s in SHARES) frac(s) <= buy(s)

Analyzing the solution

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

Total return: 13.1
treasury: 20% (1)
hardware: 0% (0)
theater: 30% (1)
telecom: 0% (0)
brewery: 20% (1)
highways: 30% (1)
cars: 0% (0)
bank: 0% (0)
software: 0% (0)
electronics: 0% (0)

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.

Let us now have a look at the detailed solver information:

Enable the Optimizer logging output by adding the line

 setparam("XPRS_VERBOSE",true)

into the model before the call to maximize and re-run the model. There are now more rows (constraints) and columns (variables) than in the LP matrix of the previous chapters.

Figure 7.1: Solver log for MIP problem - part 1: statistics

Figure 7.2: Solver log for MIP problem - part 2: algorithm

As we have seen, it is relatively easy to turn an LP model into a MIP model by adding an integrality condition on some (or all) variables. However, the same does not hold for the solution algorithms: MIP problems are solved by repeatedly solving LP problems. Initially, the problem is solved without any integrality constraints (the LP relaxation). Then, one at a time, a discrete variable is chosen that does not satisfy the integrality condition in the current solution, and new upper or lower bounds are added for this variable to bring it to an integer value.

If we represent every LP solution as a node and connect these nodes by the bound changes or added constraints, then we obtain a tree-like structure, the Branch-and-Bound tree.

In particular, the branching information tells us how many Branch-and-Bound nodes have been needed to solve the problem: here it is just one, the enumeration did not even start.

By default, Xpress Optimizer enables certain MIP pre-treatment algorithms, among others the automated generation of cuts—i.e., additional constraints that cut off parts of the LP solution space, but no solution of the MIP (see the `Optimizer Reference Manual' for more information on algorithmic settings).

This problem is of very small size and becomes so easy through the pre-treatment that it is solved immediately.

Add the lines

 setparam("XPRS_CUTSTRATEGY",0)
 setparam("XPRS_HEUREMPHASIS",0)
 setparam("XPRS_PRESOLVE",0)

to your model before the call to maximize and re-execute it. You have now switched off the MIP pre-treatment routines for automated cut generation and MIP heuristics, and also the presolve mechanism (a treatment to the matrix that tries to reduce its size and improve its numerical properties).

It now takes several nodes to solve the problem:

Figure 7.3: Solver log for MIP problem with Branch-and-Bound