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.24)\[\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 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.

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

Listing 6.13 How to solve problem (6.24). Click here to download.

function milo1()
clear prob       
prob.c        = [1 0.64];
prob.a        = [[50 31];[3 -2]];
prob.blc      = [-inf -4];
prob.buc      = [250 inf];
prob.blx      = [0 0];
prob.bux      = [inf inf];

% Specify indexes of variables that are integer
% constrained.

prob.ints.sub = [1 2];

% Optimize the problem.
[r,res] = mosekopt('maximize',prob);

try 
  % Display the optimal solution.
  res.sol.int
  res.sol.int.xx'
catch
  fprintf('MSKERROR: Could not get solution')
end

Please note that compared to a linear optimization problem with no integer-constrained variables:

• The prob.ints.sub field is used to specify the indexes of the variables that are integer-constrained.

• The optimal integer solution is returned in the res.sol.int MATLAB structure.

MOSEK also provides a wrapper for the intlinprog function found in the MATLAB optimization toolbox. This function solves linear problems wth integer variables; see the reference section for details.

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.25)\[\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 the appropriate fields in the problem structure .

Listing 6.14 Implementation of problem (6.25) specifying an initial solution. Click here to download.

% Specify start guess for the integer variables.
prob.sol.int.xx  = [1 1 0 nan]';

% Request constructing the solution from integer variable values
param.MSK_IPAR_MIO_CONSTRUCT_SOL = 1;

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.

  res.info.MSK_IINF_MIO_CONSTRUCT_SOLUTION
  res.info.MSK_DINF_MIO_CONSTRUCT_SOLUTION_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.26)\[\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.26) suitable for Optimization Toolbox for MATLAB is

(6.27)\[\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.27). Click here to download.

[rcode, res] = mosekopt('symbcon echo(0)');
symbcon = res.symbcon;
clear prob       

% The full variable is [t; x; y]
prob.c        = [1 0 0];
prob.a        = sparse(0,3);   % No constraints

% Conic part of the problem
prob.f = sparse([ eye(3); 
                  0 1 0; 
                  0 0 0; 
                  0 0 1 ]);
prob.g = [0 0 0 -3.8 1 0]';
prob.accs = [symbcon.MSK_DOMAIN_QUADRATIC_CONE 3 symbcon.MSK_DOMAIN_PRIMAL_EXP_CONE 3];

% Specify indexes of variables that are integers
prob.ints.sub = [2 3];

% It is as always possible (but not required) to input an initial solution
% to start the mixed-integer solver. 
prob.sol.int.xx = [100, 9, -1];

% Optimize the problem.
[r,res] = mosekopt('minimize info',prob);

% The integer solution (x,y) 
res.sol.int.xx(2:3)

Error and solution status handling were omitted for readability.