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

7.4.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. 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 x = M.variable("x", 2, Domain.integral(Domain.greaterThan(0.0)));

Next, the example demonstrates how to set various useful parameters of the mixed-integer optimizer. See Sec. 13 (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 6.

Listing 6 How to solve problem (1). Click here to download.
package com.mosek.fusion.examples;
import mosek.fusion.*;

public class milo1 {
  public static void main(String[] args)
  throws SolutionError {
    double[][] A = {
      { 50.0, 31.0 },
      { 3.0,  -2.0 }
    };
    double[] c = { 1.0, 0.64 };

    Model M = new Model("milo1");
    try {
      Variable 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(A[0], x), Domain.lessThan(250.0));
      M.constraint("c2", Expr.dot(A[1], 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
      double[] sol = x.level();
      System.out.printf("x1,x2 = %e, %e\n", sol[0], sol[1]);
      System.out.printf("MIP rel gap = %.2f (%f)\n",
                        M.getSolverDoubleInfo("mioObjRelGap"),
                        M.getSolverDoubleInfo("mioObjAbsGap"));
    } finally {
      M.dispose();
    }
  }
}

7.4.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 mioConstructSol parameter to "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}\]

We initialize the mixed-integer optimizer with a feasible starting point \((x_0,x_1,x_2,x_3)=(0,2,0,0)\) using the method Variable.setLevel:

Listing 7 Fusion implementation of problem (2) specifying an initial solution. Click here to download.
      double[] init_sol = { 0.0, 2.0, 0.0, 0.0 };      
      x.setLevel( init_sol );

The complete code is not very different from the first example and is available for download as mioinitsol.java. For more details about this process see Sec. 13 (The Optimizer for Mixed-integer Problems). An more advanced application of Variable.setLevel is presented in the case study on Multiprocessor scheduling.