Mixed Integer Programming
This chapter extends the LP problem from Chapter 2 to a Mixed Integer Programming (MIP) problem. It describes how to
- transform a MIP model into matrix format,
- input MIP problems with different types of discrete variables into Xpress Optimizer,
- solve MIP problems and output the solution.
Chapter 6 shows how to formulate and solve this example with Mosel and in Chapter 11 the same is done with BCL.
Extended problem description
The investor is unwilling to have small share holdings. He looks at the following two possibilities to formulate this constraint:
- Limiting the number of different shares taken into the portfolio to 4.
- If a share is bought, at least a minimum amount 10% of the budget is spent on the share.
We are going to deal with these two constraints in two separate models.
MIP model 1: limiting the number of different shares
To be able to count the number of different values we are investing in, we introduce a second set of variables buys in the LP model developed in Chapter 2. These variables are indicator variables or binary variables. A variable buys 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 4 different ones. It expresses the constraint that at most 4 of the variables buys may take the value 1 at the same time.
We now still need to link the new binary variables buys with the variables fracs, 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 fracs > 0 then buys = 1'. The following inequality formulates this implication:
If, for some s, fracs is non-zero, then buys must be greater than 0 and hence 1. Conversely, if buys is at 0, then fracs 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 buys is at 1 and fracs 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, buys and fracs, at 0.
Matrix representation
The mathematical model can be transformed into the following table. Compared to the LP matrix of the previous chapter, we now have ten additional columns for the variables buys and ten additional rows for the constraints linking the two types of variables. Notice that we have to transform the linking constraints so that all terms involving decision variables are on the left hand side of the operator sign.
| frac1 | ... | frac10 | buy1 | ... | buy10 | ||||||||||||||||||
|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|---|
| 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | 12 | 13 | 14 | 15 | 16 | 17 | 18 | 19 | Op. | RHS | ||
| Risk | 0 | 13 | 17 | 111 | 123 | 126 | ≤ | 1/3 | |||||||||||||||
| MinNA | 1 | 10 | 14 | 18 | 112 | ≥ | 0.5 | ||||||||||||||||
| Allfrac | 2 | 11 | 15 | 19 | 113 | 115 | 117 | 119 | 121 | 124 | 127 | = | 1 | ||||||||||
| Maxnum | 3 | 129 | 131 | 133 | 135 | 137 | 139 | 141 | 143 | 145 | 147 | ≤ | 4 | ||||||||||
| Linking | 4 | 12 | -130 | ≤ | 0 | ||||||||||||||||||
| 5 | 16 | -132 | ≤ | 0 | |||||||||||||||||||
| 6 | 110 | -134 | ≤ | 0 | |||||||||||||||||||
| 7 | 114 | -136 | ≤ | 0 | |||||||||||||||||||
| 8 | 116 | -138 | ≤ | 0 | |||||||||||||||||||
| 9 | 118 | -140 | ≤ | 0 | |||||||||||||||||||
| 10 | 120 | -142 | ≤ | 0 | |||||||||||||||||||
| 11 | 122 | -144 | ≤ | 0 | |||||||||||||||||||
| 12 | 125 | -146 | ≤ | 0 | |||||||||||||||||||
| 13 | 128 | -148 | ≤ | 0 | |||||||||||||||||||
| ↑ | ↑ | ||||||||||||||||||||||
| rowidx | matval | ||||||||||||||||||||||
| colbeg | 0 | 3 | 7 | 11 | 15 | 17 | 19 | 21 | 23 | 26 | 29 | 31 | 33 | 35 | 37 | 39 | 41 | 43 | 45 | 47 | 49 | ||
The superscripts for the matrix coefficients indicate again the order of the entries in the arrays rowidx and matval, the first three entries of which are highlighted (printed in italics).
Implementation with Xpress Optimizer
In addition to the structures related to the matrix coefficients that are in common with LP problems, we now also need to specify the MIP-specific information, namely the types of the MIP variables (here all marked 'B' for binary variable) in the array miptype and the corresponding column indices in the array mipcol.
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. These variables are defined with the type 'I'. In the following section (MIP model 2) we shall see yet another example of discrete variables, namely semi-continuous variables.
#include <stdio.h>
#include <stdlib.h>
#include "xprs.h"
int main(int argc, char **argv)
{
XPRSprob prob;
int s, status;
double objval, *sol;
/* Problem parameters */
int ncol = 20;
int nrow = 14;
int nmip = 10;
/* Row data */
char rowtype[]= { 'L','G','E','L','L','L','L','L','L','L','L','L','L','L'};
double rhs[] = {1.0/3,0.5, 1, 4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
/* Column data */
double obj[]= { 5, 17, 26, 12, 8, 9, 7, 6, 31, 21,0,0,0,0,0,0,0,0,0,0};
double lb[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,0,0,0,0,0,0,0,0,0,0};
double ub[] = {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,1,1,1,1,1,1,1,1,1,1};
/* Matrix coefficient data */
int colbeg[] = {0,3,7,11,15,17,19,21,23,26,29,31,33,35,37,39,41,43,45,47,49};
int rowidx[] = {1,2,4,0,1,2,5,0,1,2,6,0,1,2,7,2,8,2,9,2,10,2,11,0,2,12,0,2,
13,3,4,3,5,3,6,3,7,3,8,3,9,3,10,3,11,3,12,3,13};
double matval[] = {1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,
1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1,1,-1};
/* MIP problem data */
char miptype[] = {'B','B','B','B','B','B','B','B','B','B'};
int mipcol[] = { 10, 11, 12, 13, 14, 15, 16, 17, 18, 19};
XPRSinit(NULL); /* Initialize Xpress Optimizer */
XPRScreateprob(&prob); /* Create a new problem */
/* Load the problem matrix */
XPRSloadglobal(prob, "FolioMIP1", ncol, nrow, rowtype, rhs, NULL,
obj, colbeg, NULL, rowidx, matval, lb, ub,
nmip, 0, miptype, mipcol, NULL, NULL, NULL, NULL, NULL);
XPRSchgobjsense(prob, XPRS_OBJ_MAXIMIZE); /* Set sense to maximization */
XPRSmipoptimize(prob, ""); /* Solve the problem */
XPRSgetintattrib(prob, XPRS_MIPSTATUS, &status); /* Get MIP sol. status */
if((status == XPRS_MIP_OPTIMAL) || (status == XPRS_MIP_SOLUTION))
{
XPRSgetdblattrib(prob, XPRS_MIPOBJVAL, &objval); /* Get objective value */
printf("Total return: %g\n", objval);
sol = (double *)malloc(ncol*sizeof(double));
XPRSgetmipsol(prob, sol, NULL); /* Get primal solution */
for(s=0;s<ncol/2;s++)
printf("%d: %g%% (%g)\n", s, sol[s]*100, sol[ncol/2+s]);
}
XPRSdestroyprob(prob); /* Delete the problem */
XPRSfree(); /* Terminate Xpress */
return 0;
}To load the problem into Xpress Optimizer we now use the function XPRSloadglobal. The first 14 arguments of this function are the same as for XPRSloadlp. The use of the 19th argument will be discussed in the next section; the remaining four arguments are related to the definition of SOS (Special Ordered Sets)—the value 0 for the 16th argument indicates that there are none in our problem.
In this program, not only the function for loading the problem but also those for solving and solution access have been adapted to the problem type: we now solve a MIP problem via a Branch-and-Bound search (the second argument "" of the optimization function XPRSmipoptimize stands for 'default MIP algorithm'). We then retrieve the MIP solution status and if an integer feasible solution has been found we print out the objective value of the best integer solution found and the corresponding solution values of the decision variables.
Running this program produces the following solution output. 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:
Total return: 13.1 0: 20% (1) 1: 0% (0) 2: 30% (1) 3: 0% (0) 4: 20% (1) 5: 30% (1) 6: 0% (0) 7: 0% (0) 8: 0% (0) 9: 0% (0)
MIP model 2: imposing a minimum investment in each share
To formulate the second MIP model, we start again with the LP model from Chapters 2 and 15. The new constraint we wish to formulate is `if a share is bought, at least a minimum amount 10% of the budget is spent on the share.' Instead of simply constraining every variable fracs to take a value between 0 and 0.3, it now must either lie in the interval between 0.1 and 0.3 or take the value 0. This type of variable is known as semi-continuous variable. In the new model, we replace the bounds on the variables fracs by the following constraint:
Matrix representation
This problem has the same matrix as the LP problem in the previous chapter, and so we do not repeat it here. The only changes are in the specification of the MIP-related column data.
Implementation with Xpress Optimizer
The following program foliomip2.c loads the MIP model 2 into the Optimizer. We have the same matrix data as for the LP problem in the previous chapter, but the variables are now semi-continuous, defined by the type marker 'S'. By default, Xpress Optimizer assumes a continuous limit of 1, we therefore specify the value 0.1 in the array sclim. Please note in this context that limits for semi-continuous and semi-continuous integer variables given in the array sclim are overwritten by the value in the array lb if the latter is different from 0.
Other available composite variable types are semi-continuous integer variables that take either the value 0 or an integer value between a given limit and their upper bound (marked by 'R') and partial integers that take integer values from their lower bound to a given limit value and are continuous beyond this value (marked by 'P').
#include <stdio.h>
#include <stdlib.h>
#include "xprs.h"
int main(int argc, char **argv)
{
XPRSprob prob;
int s, status;
double objval, *sol;
/* Problem parameters */
int ncol = 10;
int nrow = 3;
int nmip = 10;
/* Row data */
char rowtype[] = { 'L','G','E'};
double rhs[] = {1.0/3,0.5, 1};
/* Column data */
double obj[] = { 5, 17, 26, 12, 8, 9, 7, 6, 31, 21};
double lb[] = { 0, 0, 0, 0, 0, 0, 0, 0, 0, 0};
double ub[] = {0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3,0.3};
/* Matrix coefficient data */
int colbeg[] = {0, 2, 5, 8, 11,12,13,14,15, 17, 19};
int rowidx[] = {1,2,0,1,2,0,1,2,0,1,2, 2, 2, 2, 2, 0,2, 0,2};
double matval[] = {1,1,1,1,1,1,1,1,1,1,1, 1, 1, 1, 1, 1,1, 1,1};
/* MIP problem data */
char miptype[] = {'S','S','S','S','S','S','S','S','S','S'};
int mipcol[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 9};
double sclim[] = {0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1,0.1};
XPRSinit(NULL); /* Initialize Xpress Optimizer */
XPRScreateprob(&prob); /* Create a new problem */
/* Load the problem matrix */
XPRSloadglobal(prob, "FolioSC", ncol, nrow, rowtype, rhs, NULL,
obj, colbeg, NULL, rowidx, matval, lb, ub,
nmip, 0, miptype, mipcol, sclim, NULL, NULL, NULL, NULL);
XPRSchgobjsense(prob, XPRS_OBJ_MAXIMIZE); /* Set sense to maximization */
XPRSmipoptimize(prob, ""); /* Solve the problem */
XPRSgetintattrib(prob, XPRS_MIPSTATUS, &status); /* Get MIP sol. status */
if((status == XPRS_MIP_OPTIMAL) || (status == XPRS_MIP_SOLUTION))
{
XPRSgetdblattrib(prob, XPRS_MIPOBJVAL, &objval); /* Get objective value */
printf("Total return: %g\n", objval);
sol = (double *)malloc(ncol*sizeof(double));
XPRSgetmipsol(prob, sol, NULL); /* Get primal solution */
for(s=0;s<ncol;s++) printf("%d: %g%%\n", s, sol[s]*100);
}
XPRSdestroyprob(prob); /* Delete the problem */
XPRSfree(); /* Terminate Xpress */
return 0;
}When executing this program we obtain the following output:
Total return: 14.0333 0: 30% 1: 0% 2: 20% 3: 0% 4: 10% 5: 26.6667% 6: 0% 7: 0% 8: 13.3333% 9: 0%
Now five securities are chosen for the portfolio, each forming at least 10% and at most 30% of the total investment. Due to the additional constraint, the optimal MIP solution value is again lower than the initial LP solution value.