6.7 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.7.1 Example MILO1

We use the example

(6.12)\[\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 Task.putvartype:

        for (int j = 0; j < numvar; ++j)
          task.putvartype(j, mosek.variabletype.type_int);

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 */
        task.putdouparam(mosek.dparam.mio_max_time, 60.0);

The complete source for the example is listed Listing 6.8. Please note that when Task.getsolutionslice is called, the integer solution is requested by using soltype.itg. No dual solution is defined for integer optimization problems.

Listing 6.8 Source code implementing problem (6.12). Click here to download.
using System;

namespace mosek.example
{
  public class MsgClass : mosek.Stream
  {
    public MsgClass ()
    {
      /* Construct the object */
    }

    public override void streamCB (string msg)
    {
      Console.Write ("{0}", msg);
    }
  }

  public class milo1
  {
    public static void Main ()
    {
      const int numcon = 2;
      const int numvar = 2;

      // Since the value infinity is never used, we define
      // 'infinity' symbolic purposes only
      double infinity = 0;


      mosek.boundkey[] bkc = { mosek.boundkey.up,
                               mosek.boundkey.lo
                             };
      double[] blc = { -infinity,
                       -4.0
                     };
      double[] buc = { 250.0,
                       infinity
                     };

      mosek.boundkey[] bkx = { mosek.boundkey.lo,
                               mosek.boundkey.lo
                             };
      double[] blx = { 0.0,
                       0.0
                     };
      double[] bux = { infinity,
                       infinity
                     };

      double[] c   = {1.0, 0.64 };
      int[][] asub    = { new int[]  {0,   1},  new int[] {0,    1}   };
      double[][] aval = { new double[] {50.0, 3.0}, new double[] {31.0, -2.0} };

      double[] xx  = new double[numvar];

      mosek.Env env = null;
      mosek.Task task = null;

      try
      {
        // Make mosek environment.
        env  = new mosek.Env ();
        // Create a task object linked with the environment env.
        task = new mosek.Task (env, numcon, numvar);
        // Directs the log task stream to the user specified
        // method task_msg_obj.streamCB
        MsgClass task_msg_obj = new MsgClass ();
        task.set_Stream (mosek.streamtype.log, task_msg_obj);

        /* Give MOSEK an estimate of the size of the input data.
             This is done to increase the speed of inputting data.
             However, it is optional. */
        /* Append 'numcon' empty constraints.
             The constraints will initially have no bounds. */
        task.appendcons(numcon);

        /* Append 'numvar' variables.
             The variables will initially be fixed at zero (x=0). */
        task.appendvars(numvar);

        /* Optionally add a constant term to the objective. */
        task.putcfix(0.0);

        for (int j = 0; j < numvar; ++j)
        {
          /* Set the linear term c_j in the objective.*/
          task.putcj(j, c[j]);
          /* Set the bounds on variable j.
                   blx[j] <= x_j <= bux[j] */
          task.putvarbound(j, bkx[j], blx[j], bux[j]);
          /* Input column j of A */
          task.putacol(j,                     /* Variable (column) index.*/
                       asub[j],               /* Row index of non-zeros in column j.*/
                       aval[j]);              /* Non-zero Values of column j. */
        }
        /* Set the bounds on constraints.
               for i=1, ...,numcon : blc[i] <= constraint i <= buc[i] */
        for (int i = 0; i < numcon; ++i)
          task.putconbound(i, bkc[i], blc[i], buc[i]);

        /* Specify integer variables. */
        for (int j = 0; j < numvar; ++j)
          task.putvartype(j, mosek.variabletype.type_int);
        task.putobjsense(mosek.objsense.maximize);

        /* Set max solution time */
        task.putdouparam(mosek.dparam.mio_max_time, 60.0);

        task.optimize();


        // Print a summary containing information
        //   about the solution for debugging purposes
        task.solutionsummary(mosek.streamtype.msg);

        mosek.solsta solsta;
        /* Get status information about the solution */
        task.getsolsta(mosek.soltype.itg, out solsta);
        task.getxx(mosek.soltype.itg, // Integer solution.
                   xx);

        switch (solsta)
        {
          case mosek.solsta.optimal:
            Console.WriteLine ("Optimal primal solution\n");
            for (int j = 0; j < numvar; ++j)
              Console.WriteLine ("x[{0}]:", xx[j]);
            break;
          case mosek.solsta.prim_feas:
            Console.WriteLine ("Feasible primal solution\n");
            for (int j = 0; j < numvar; ++j)
              Console.WriteLine ("x[{0}]:", xx[j]);
            break;
          case mosek.solsta.unknown:
            mosek.prosta prosta;
            task.getprosta(mosek.soltype.itg, out prosta);
            switch (prosta)
            {
              case mosek.prosta.prim_infeas_or_unbounded:
                Console.WriteLine("Problem status Infeasible or unbounded");
                break;
              case mosek.prosta.prim_infeas:
                Console.WriteLine("Problem status Infeasible.");
                break;
              case mosek.prosta.unknown:
                Console.WriteLine("Problem status unknown.");
                break;
              default:
                Console.WriteLine("Other problem status.");
                break;
            }
            break;
          default:
            Console.WriteLine("Other solution status");
            break;
        }
      }
      catch (mosek.Exception e)
      {
        Console.WriteLine (e.Code);
        Console.WriteLine (e);
        throw;
      }
      finally
      {
        if (task != null) task.Dispose ();
        if (env  != null)  env.Dispose ();
      }
    }
  }
}

6.7.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.

It is not necessary to specify the whole solution. MOSEK will attempt to use it to speed up the computation. MOSEK will first try to construct a feasible solution by fixing integer variables to the values provided by the user (rounding if necessary) and optimizing over the continuous variables. The outcome of this process can be inspected via information items iinfitem.mio_construct_solution and dinfitem.mio_construct_solution_obj, and via the Construct solution objective entry in the log. We concentrate on a simple example below.

(6.13)\[\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 Task.putsolution .

Listing 6.9 Implementation of problem (6.13) specifying an initial solution. Click here to download.
        // Assign values to integer variables.
        // We only set a slice of xx
        double[] values = {1.0, 1.0, 0.0};
        task.putxxslice(mosek.soltype.itg, 0, 3, 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.10 Retrieving information about usage of initial solution Click here to download.
        int constr = task.getintinf(mosek.iinfitem.mio_construct_solution);
        double constrVal = task.getdouinf(mosek.dinfitem.mio_construct_solution_obj);
        Console.WriteLine("Initial solution utilization: " + constr);
        Console.WriteLine("Initial solution objective: " +  constrVal);

6.7.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.14)\[\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.14) suitable for Optimizer API for .NET is

(6.15)\[\begin{split}\begin{array}{lrclr} \mbox{minimize} & x_0 & & & \\ \mbox{subject to} & (x_0,x_1,x_2)&\in&\Q^3 & (x_0\geq\sqrt{x_1^2+x_2^2}) \\ & (x_3,x_4,x_5)&\in&\EXP & (x_3\geq x_4 \exp(x_5/x_4)) \\ & -x_1 +x_3 &=& -3.8 & \\ & x_4 &=& 1 & \\ & x_2 - x_5 &=& 0 & \\ & x_1, x_2 & & \mbox{integer}. & \end{array}\end{split}\]
Listing 6.11 Implementation of problem (6.15). Click here to download.
  public class mico1
  {
    public static void Main ()
    {
      mosek.Env env  = new mosek.Env ();
      mosek.Task task = new mosek.Task(env, 0, 0);
     
      // Directs the log task stream to the user specified
      // method task_msg_obj.streamCB
      MsgClass task_msg_obj = new MsgClass ();
      task.set_Stream (mosek.streamtype.log, task_msg_obj);

      task.appendvars(6);
      task.appendcons(3);
      task.putvarboundsliceconst(0, 6, mosek.boundkey.fr, -0.0, 0.0);

      // Integrality constraints
      task.putvartypelist(new int[]{1,2}, 
                          new mosek.variabletype[]{mosek.variabletype.type_int, mosek.variabletype.type_int});

      // Set up the three auxiliary linear constraints
      task.putaijlist(new int[]{0,0,1,2,2},
                      new int[]{1,3,4,2,5},
                      new double[]{-1,1,1,1,-1});
      task.putconboundslice(0, 3, 
                            new mosek.boundkey[]{mosek.boundkey.fx, mosek.boundkey.fx, mosek.boundkey.fx},
                            new double[]{-3.8, 1, 0}, new double[]{-3.8, 1, 0});

      // Objective
      task.putobjsense(mosek.objsense.minimize);
      task.putcj(0, 1);

      // Conic part of the problem
      task.appendconeseq(mosek.conetype.quad, 0, 3, 0);
      task.appendconeseq(mosek.conetype.pexp, 0, 3, 3);

      // Optimize the task
      task.optimize();
      task.solutionsummary(mosek.streamtype.msg);

      double[] xx = {0, 0};
      task.getxxslice(mosek.soltype.itg, 1, 3, xx);
      Console.WriteLine ("x = {0}, y = {1}", xx[0], xx[1]);
    }
  }
}

Error and solution status handling were omitted for readability.