# 6.8 Integer Optimization¶

An optimization problem where one or more of the variables are constrained to integer values is called a (mixed) integer optimization problem. MOSEK supports integer variables in combination with linear, quadratic and quadratically constrtained and conic problems (except semidefinite). See the previous tutorials for an introduction to how to model these types of problems.

## 6.8.1 Example MILO1¶

We use the example

(6.27)$\begin{split}\begin{array}{lccl} \mbox{maximize} & x_0 + 0.64 x_1 & & \\ \mbox{subject to} & 50 x_0 + 31 x_1 & \leq & 250, \\ & 3 x_0 - 2 x_1 & \geq & -4, \\ & x_0, x_1 \geq 0 & & \mbox{and integer} \end{array}\end{split}$

to demonstrate how to set up and solve a problem with integer variables. It has the structure of a linear optimization problem (see Sec. 6.1 (Linear Optimization)) except for integrality constraints on the variables. Therefore, only the specification of the integer constraints requires something new compared to the linear optimization problem discussed previously.

First, the integrality constraints are imposed using the function MSK_putvartype:

    for (j = 0; j < numvar && r == MSK_RES_OK; ++j)


Next, the example demonstrates how to set various useful parameters of the mixed-integer optimizer. See Sec. 13.4 (The Optimizer for Mixed-Integer Problems) for details.

      /* Set max solution time */
MSK_DPAR_MIO_MAX_TIME,
60.0);


The complete source for the example is listed Listing 6.13. Please note that when MSK_getsolutionslice is called, the integer solution is requested by using MSK_SOL_ITG. No dual solution is defined for integer optimization problems.

Listing 6.13 Source code implementing problem (6.27). Click here to download.
#include <stdio.h>
#include "mosek.h" /* Include the MOSEK definition file. */

static void MSKAPI printstr(void *handle,
const char str[])
{
printf("%s", str);
} /* printstr */

int main(int argc, char *argv[])
{
const MSKint32t numvar = 2,
numcon = 2;

double       c[]   = {  1.0, 0.64 };
MSKboundkeye bkc[] = { MSK_BK_UP,    MSK_BK_LO };
double       blc[] = { -MSK_INFINITY, -4.0 };
double       buc[] = { 250.0,        MSK_INFINITY };

MSKboundkeye bkx[] = { MSK_BK_LO,    MSK_BK_LO };
double       blx[] = { 0.0,          0.0 };
double       bux[] = { MSK_INFINITY, MSK_INFINITY };

MSKint32t    aptrb[] = { 0, 2 },
aptre[] = { 2, 4 },
asub[] = { 0,    1,   0,    1 };
double       aval[] = { 50.0, 3.0, 31.0, -2.0 };
MSKint32t    i, j;

MSKenv_t     env = NULL;
MSKrescodee  r;

/* Create the mosek environment. */
r = MSK_makeenv(&env, NULL);

/* Check if return code is ok. */
if (r == MSK_RES_OK)
{
/* Create the optimization task. */

if (r == MSK_RES_OK)

/* Append 'numcon' empty constraints.
The constraints will initially have no bounds. */
if (r == MSK_RES_OK)

/* Append 'numvar' variables.
The variables will initially be fixed at zero (x=0). */
if (r == MSK_RES_OK)

/* Optionally add a constant term to the objective. */
if (r == MSK_RES_OK)
for (j = 0; j < numvar && r == MSK_RES_OK; ++j)
{
/* Set the linear term c_j in the objective.*/
if (r == MSK_RES_OK)

/* Set the bounds on variable j.
blx[j] <= x_j <= bux[j] */
if (r == MSK_RES_OK)
j,           /* Index of variable.*/
bkx[j],      /* Bound key.*/
blx[j],      /* Numerical value of lower bound.*/
bux[j]);     /* Numerical value of upper bound.*/

/* Input column j of A */
if (r == MSK_RES_OK)
j,                 /* Variable (column) index.*/
aptre[j] - aptrb[j], /* Number of non-zeros in column j.*/
asub + aptrb[j],   /* Pointer to row indexes of column j.*/
aval + aptrb[j]);  /* Pointer to Values of column j.*/

}

/* Set the bounds on constraints.
for i=1, ...,numcon : blc[i] <= constraint i <= buc[i] */
for (i = 0; i < numcon && r == MSK_RES_OK; ++i)
i,           /* Index of constraint.*/
bkc[i],      /* Bound key.*/
blc[i],      /* Numerical value of lower bound.*/
buc[i]);     /* Numerical value of upper bound.*/

/* Specify integer variables. */
for (j = 0; j < numvar && r == MSK_RES_OK; ++j)

if (r == MSK_RES_OK)
MSK_OBJECTIVE_SENSE_MAXIMIZE);

if (r == MSK_RES_OK)
/* Set max solution time */
MSK_DPAR_MIO_MAX_TIME,
60.0);

if (r == MSK_RES_OK)
{
MSKrescodee trmcode;

/* Run optimizer */

/* Print a summary containing information
about the solution for debugging purposes*/

if (r == MSK_RES_OK)
{
MSKint32t  j;
MSKsolstae solsta;
double     *xx = NULL;

xx = calloc(numvar, sizeof(double));
if (xx)
{
switch (solsta)
{
case MSK_SOL_STA_INTEGER_OPTIMAL:
MSK_SOL_ITG,    /* Request the integer solution. */
xx);

printf("Optimal solution.\n");
for (j = 0; j < numvar; ++j)
printf("x[%d]: %e\n", j, xx[j]);
break;
case MSK_SOL_STA_PRIM_FEAS:
/* A feasible but not necessarily optimal solution was located. */

printf("Feasible solution.\n");
for (j = 0; j < numvar; ++j)
printf("x[%d]: %e\n", j, xx[j]);
break;
case MSK_SOL_STA_UNKNOWN:
{
MSKprostae prosta;
switch (prosta)
{
case MSK_PRO_STA_PRIM_INFEAS_OR_UNBOUNDED:
printf("Problem status Infeasible or unbounded\n");
break;
case MSK_PRO_STA_PRIM_INFEAS:
printf("Problem status Infeasible.\n");
break;
case MSK_PRO_STA_UNKNOWN:
printf("Problem status unknown. Termination code %d.\n", trmcode);
break;
default:
printf("Other problem status.");
break;
}
}
break;
default:
printf("Other solution status.");
break;
}
}
else
{
r = MSK_RES_ERR_SPACE;
}
free(xx);
}
}

if (r != MSK_RES_OK)
{
/* In case of an error print error code and description. */
char symname[MSK_MAX_STR_LEN];
char desc[MSK_MAX_STR_LEN];

printf("An error occurred while optimizing.\n");
MSK_getcodedesc(r,
symname,
desc);
printf("Error %s - '%s'\n", symname, desc);
}

}
MSK_deleteenv(&env);

printf("Return code: %d.\n", r);
return (r);
} /* main */


## 6.8.2 Specifying an initial solution¶

It is a common strategy to provide a starting feasible point (if one is known in advance) to the mixed-integer solver. This can in many cases reduce solution time.

There are two modes for MOSEK to utilize an initial solution.

• A complete solution. MOSEK will first try to check if the current value of the primal variable solution is a feasible point. The solution can either come from a previous solver call or can be entered by the user, however the full solution with values for all variables (both integer and continuous) must be provided. This check is always performed and does not require any extra action from the user. The outcome of this process can be inspected via information items MSK_IINF_MIO_INITIAL_FEASIBLE_SOLUTION and MSK_DINF_MIO_INITIAL_FEASIBLE_SOLUTION_OBJ, and via the Initial feasible solution objective entry in the log.

• A partial integer solution. MOSEK can also try to construct a feasible solution by fixing integer variables to the values provided by the user (rounding if necessary) and optimizing over the remaining continuous variables. In this setup the user must provide initial values for all integer variables. This action is only performed if the parameter MSK_IPAR_MIO_CONSTRUCT_SOL is switched on. The outcome of this process can be inspected via information items MSK_IINF_MIO_CONSTRUCT_SOLUTION and MSK_DINF_MIO_CONSTRUCT_SOLUTION_OBJ, and via the Construct solution objective entry in the log.

In the following example we focus on inputting a partial integer solution.

(6.28)$\begin{split}\begin{array} {ll} \mbox{maximize} & 7 x_0 + 10 x_1 + x_2 + 5 x_3 \\ \mbox{subject to} & x_0 + x_1 + x_2 + x_3 \leq 2.5\\ & x_0,x_1,x_2 \in \integral \\ & x_0,x_1,x_2,x_3 \geq 0 \end{array}\end{split}$

Solution values can be set using MSK_putsolution .

Listing 6.14 Implementation of problem (6.28) specifying an initial solution. Click here to download.
  if (r == MSK_RES_OK)
{
/* Assign values to integer variables
(we only set a slice of xx) */
double       xxInit[] = {1.0, 1.0, 0.0};
r = MSK_putxxslice(task, MSK_SOL_ITG, 0, 3, xxInit);
}
if (r == MSK_RES_OK)
{
/* Request constructing the solution from integer variable values */
}


The log output from the optimizer will in this case indicate that the inputted values were used to construct an initial feasible solution:

Construct solution objective       : 1.950000000000e+01


The same information can be obtained from the API:

Listing 6.15 Retrieving information about usage of initial solution Click here to download.
    MSK_getintinf(task, MSK_IINF_MIO_CONSTRUCT_SOLUTION, &constr);
printf("Construct solution utilization: %d\nConstruct solution objective: %.3f\n", constr, constr_obj);


## 6.8.3 Example MICO1¶

Integer variables can also be used arbitrarily in conic problems (except semidefinite). We refer to the previous tutorials for how to set up a conic optimization problem. Here we present sample code that sets up a simple optimization problem:

(6.29)$\begin{split}\begin{array}{ll} \mbox{minimize} & x^2+y^2 \\ \mbox{subject to} & x \geq e^y+3.8, \\ & x, y \ \mbox{integer}. \end{array}\end{split}$

The canonical conic formulation of (6.29) suitable for Optimizer API for C is

(6.30)$\begin{split}\begin{array}{llr} \mbox{minimize} & t & \\ \mbox{subject to} & (t,x,y)\in\Q^3 & (t\geq\sqrt{x^2+y^2}) \\ & (x-3.8, 1, y) \in\EXP & (x-3.8\geq e^y) \\ & x, y \ \mbox{integer}, & \\ & t\in\real. \end{array}\end{split}$
Listing 6.16 Implementation of problem (6.30). Click here to download.
int main(int argc, char *argv[])
{
MSKint32t         numvar = 3;  /* x, y, t */

MSKvariabletypee  vart[] = { MSK_VAR_TYPE_INT, MSK_VAR_TYPE_INT };
MSKint32t       intsub[] = { 0, 1 };

MSKint32t    i, j;

MSKenv_t     env = NULL;
MSKrescodee  r, trm;

r = MSK_makeenv(&env, NULL);

if (r == MSK_RES_OK)
{

if (r == MSK_RES_OK)

if (r == MSK_RES_OK)
if (r == MSK_RES_OK)
r = MSK_putvarboundsliceconst(task, 0, numvar, MSK_BK_FR, -0.0, 0.0);

/* Integrality constraints */
if (r == MSK_RES_OK)
r = MSK_putvartypelist(task, 2, intsub, vart);

/* Objective */
if (r == MSK_RES_OK)
if (r == MSK_RES_OK)
r = MSK_putcj(task, 2, 1.0);    /* Minimize t */

/* Conic part of the problem */
if (r == MSK_RES_OK)
{
/* Set up the affine expressions */
/* x, x-3.8, y, t, 1.0 */
MSKint64t afeidx[] = {0, 1, 2, 3};
MSKint32t varidx[] = {0, 0, 1, 2};
MSKrealt     val[] = {1.0, 1.0, 1.0, 1.0};
MSKrealt       g[] = {0.0, -3.8, 0.0, 0.0, 1.0};
MSKint64t afeidxExp[]  = {1, 4, 2};
MSKint64t afeidxQuad[] = {3, 0, 2};

if (r == MSK_RES_OK)
if (r == MSK_RES_OK)
4,
afeidx,
varidx,
val);
if (r == MSK_RES_OK)
r = MSK_putafegslice(task, 0, 5, g);

// Add constraint (x-3.8, 1, y) \in \EXP
if (r == MSK_RES_OK)
if (r == MSK_RES_OK)
r = MSK_appendacc(task, domExp, 3, afeidxExp, NULL);

if (r == MSK_RES_OK)
if (r == MSK_RES_OK)
}

/* Optimize the problem */
if (r == MSK_RES_OK)

if (r == MSK_RES_OK)

if (r == MSK_RES_OK)
{
MSKrealt xx[] = {0, 0};

r = MSK_getxxslice(task, MSK_SOL_ITG, 0, 2, xx);

if (r == MSK_RES_OK)
printf("x = %.2f, y = %.2f\n", xx[0], xx[1]);
}