6.5 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 and conic quadratic problems. See the previous tutorials for an introduction to how to model these types of problems.

6.5.1 Example MILO1

We use the example

(1)\[\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)
      r = MSK_putvartype(task, j, MSK_VAR_TYPE_INT);

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

      /* Set max solution time */
      r = MSK_putdouparam(task,
                          MSK_DPAR_MIO_MAX_TIME,
                          60.0);

The complete source for the example is listed Listing 9. 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 9 Source code implementing problem (1). 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;
  MSKtask_t    task = 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. */
    r = MSK_maketask(env, 0, 0, &task);

    if ( r == MSK_RES_OK )
      r = MSK_linkfunctotaskstream(task, MSK_STREAM_LOG, NULL, printstr);

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

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

    /* Optionally add a constant term to the objective. */
    if ( r == MSK_RES_OK )
      r = MSK_putcfix(task, 0.0);
    for (j = 0; j < numvar && r == MSK_RES_OK; ++j)
    {
      /* Set the linear term c_j in the objective.*/
      if (r == MSK_RES_OK)
        r = MSK_putcj(task, j, c[j]);

      /* Set the bounds on variable j.
       blx[j] <= x_j <= bux[j] */
      if (r == MSK_RES_OK)
        r = MSK_putvarbound(task,
                            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)
        r = MSK_putacol(task,
                        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)
      r = MSK_putconbound(task,
                          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)
      r = MSK_putvartype(task, j, MSK_VAR_TYPE_INT);

    if ( r == MSK_RES_OK )
      r =  MSK_putobjsense(task,
                           MSK_OBJECTIVE_SENSE_MAXIMIZE);

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

    if ( r == MSK_RES_OK )
    {
      MSKrescodee trmcode;

      /* Run optimizer */
      r = MSK_optimizetrm(task, &trmcode);

      /* Print a summary containing information
         about the solution for debugging purposes*/
      MSK_solutionsummary (task, MSK_STREAM_MSG);

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

        MSK_getsolsta (task, MSK_SOL_ITG, &solsta);

        xx = calloc(numvar, sizeof(double));
        if ( xx )
        {
          switch (solsta)
          {
            case MSK_SOL_STA_INTEGER_OPTIMAL:
            case MSK_SOL_STA_NEAR_INTEGER_OPTIMAL :
              MSK_getxx(task,
                        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. */
              MSK_getxx(task, MSK_SOL_ITG, xx);

              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;
                MSK_getprosta(task, MSK_SOL_ITG, &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.\n");
                    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_deletetask(&task);
  }
  MSK_deleteenv(&env);

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

6.5.2 Specifying an initial solution

Solution time of can often be reduced by providing an initial solution for the solver. It is not necessary to specify the whole solution. By setting the MSK_IPAR_MIO_CONSTRUCT_SOL parameter to MSK_ON and inputting values for the integer variables only, MOSEK will be forced to compute the remaining continuous variable values. If the specified integer solution is infeasible or incomplete, MOSEK will simply ignore it.

We concentrate on a simple example below.

(2)\[\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_putxxslice and related methods.

Listing 10 Implementation of problem (2) specifying an initial solution. Click here to download.
  /* Construct an initial feasible solution from the
     values of the integer variables specified */
  if (r == MSK_RES_OK)
    r = MSK_putintparam(task, MSK_IPAR_MIO_CONSTRUCT_SOL, MSK_ON);

  if (r == MSK_RES_OK)
  {
    double xx[] = {0.0, 2.0, 0.0};

    /* Assign values 0,2,0 to integer variables */
    r = MSK_putxxslice(task, MSK_SOL_ITG, 0, 3, xx);
  }

The complete code is not very different from the first example and is available for download as mioinitsol.c. For more details about this process see Sec. 14 (The Optimizer for Mixed-integer Problems).