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

7.6.1 Example MILO1

We use the example

(7.10)\[\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. 7.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 by modifying any existing domain with Domain.integral:

  Variable::t x = M->variable("x", 2, Domain::integral(Domain::greaterThan(0.0)));

Another way to do this is to use the method Variable.makeInteger on a selected variable.

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
  M->setSolverParam("mioMaxTime", 60.0);
  // Set max relative gap (to its default value)
  M->setSolverParam("mioTolRelGap", 1e-4);
  // Set max absolute gap (to its default value)
  M->setSolverParam("mioTolAbsGap", 0.0);

The complete source for the example is listed in Listing 7.9.

Listing 7.9 How to solve problem (7.10). Click here to download.
#include <iostream>
#include <iomanip>
#include "fusion.h"

using namespace mosek::fusion;
using namespace monty;

int main(int argc, char ** argv)
{
  auto a1 = new_array_ptr<double, 1>({ 50.0, 31.0 });
  auto a2 = new_array_ptr<double, 1>({ 3.0,  -2.0 });
  auto c  = new_array_ptr<double, 1>({  1.0, 0.64 });

  Model::t M = new Model("milo1"); auto _M = finally([&]() { M->dispose(); });
  Variable::t x = M->variable("x", 2, Domain::integral(Domain::greaterThan(0.0)));

  // Create the constraints
  //      50.0 x[0] + 31.0 x[1] <= 250.0
  //       3.0 x[0] -  2.0 x[1] >= -4.0
  M->constraint("c1", Expr::dot(a1, x), Domain::lessThan(250.0));
  M->constraint("c2", Expr::dot(a2, x), Domain::greaterThan(-4.0));

  // Set max solution time
  M->setSolverParam("mioMaxTime", 60.0);
  // Set max relative gap (to its default value)
  M->setSolverParam("mioTolRelGap", 1e-4);
  // Set max absolute gap (to its default value)
  M->setSolverParam("mioTolAbsGap", 0.0);

  // Set the objective function to (c^T * x)
  M->objective("obj", ObjectiveSense::Maximize, Expr::dot(c, x));

  // Solve the problem
  M->solve();

  // Get the solution values
  auto sol = x->level();
  std::cout << std::setiosflags(std::ios::scientific) << std::setprecision(2)
            << "x1 = " << (*sol)[0] << std::endl
            << "x2 = " << (*sol)[1] << std::endl
            << "MIP rel gap = " << M->getSolverDoubleInfo("mioObjRelGap") << " (" << M->getSolverDoubleInfo("mioObjAbsGap") << ")" << std::endl;
}

7.6.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 "mioConstructSolution" and "mioConstructSolutionObj", and via the Construct solution objective entry in the log. We concentrate on a simple example below.

(7.11)\[\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 Variable.setLevel .

Listing 7.10 Implementation of problem (7.11) specifying an initial solution. Click here to download.
  // Assign values to integer variables.
  // We only set a slice of x     
  auto init_sol = new_array_ptr<double, 1>({ 1.0, 1.0, 0.0 });
  x->slice(0,3)->setLevel( init_sol );

A more advanced application of Variable.setLevel is presented in the case study on Multiprocessor scheduling.

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 7.11 Retrieving information about usage of initial solution Click here to download.
  int constr = M->getSolverIntInfo("mioConstructSolution");
  double constrVal = M->getSolverDoubleInfo("mioConstructSolutionObj");
  std::cout << "Initial solution utilization: " << constr << std::endl;
  std::cout << "Initial solution objective: " << constrVal << std::endl;

7.6.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:

(7.12)\[\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 (7.12) suitable for Fusion API for C++ is

(7.13)\[\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 7.12 Implementation of problem (7.13). Click here to download.
#include <iostream>
#include <iomanip>
#include "fusion.h"

using namespace mosek::fusion;
using namespace monty;

int main(int argc, char ** argv)
{
  Model::t M = new Model("mico1"); auto _M = finally([&]() { M->dispose(); });

  Variable::t x = M->variable(Domain::integral(Domain::unbounded()));
  Variable::t y = M->variable(Domain::integral(Domain::unbounded()));
  Variable::t t = M->variable();
  
  M->constraint(Expr::vstack(t, x, y), Domain::inQCone());
  M->constraint(Expr::vstack(Expr::sub(x, 3.8), 1, y), Domain::inPExpCone());

  M->objective(ObjectiveSense::Minimize, t);

  M->solve();

  std::cout << std::setprecision(2)
            << "x = " << (*(x->level()))[0] << std::endl
            << "y = " << (*(y->level()))[0] << std::endl ;

  return 0;
}

Error and solution status handling were omitted for readability.