Integer programming

YALMIP supports several mixed integer programming solvers, but also comes with built-in module for mixed integer programming, based on a simple standard branch-and-bound algorithm.

Mixed integer conic programming

Defining binary and integer variables is done with the commands binvar and intvar. The resulting objects are essentially sdpvar objects with implicit constraints.

x = intvar(n,m);
y = binvar(n,m);

Objects with integer variables are manipulated as standard sdpvar objects.

z = x + y + trace(x) + sum(sum(y));
F = set(z >= 0) + set(x <= 0);

In the code above, integrality was imposed by using integer and binary variables. An equivalent alternative is to use explicit constraints.

x = sdpvar(n,m);
y = sdpvar(n,m);
z = x + y + trace(x) + sum(sum(y));
F = set(z >= 0) + set(x <= 0) + set(integer(x)) + set(binary(y));

Note that we use non-strict inequalities. This is highly recommended when working with integer models since, see the FAQ.

The global integer solver can be applied to any kind of conic program that can be defined within the YALMIP framework, and defining integer programs is as simple as defining standard problems. The supported integer solvers are GLPK, CPLEX, XPRESS and MOSEK. In addition to these solvers, YALMIP comes with an internal branch-and-bound solver, called 'bnb', to be used together with any continuous solver. Hence, it is possible to (globally) solve mixed integer linear/quadratic/second order cone/semidefinite/geometric programs in YALMIP. Note that the internal branch-and-bound algorithm is rudimentary and useful only for small problems. See the help-text on 'bnb' for more information on this solver.

As an example, let us return to the linear regression problem. Solving the same problems, but looking for integer solutions can be done by changing one line of code

a = [1 2 3 4 5 6]';
t = (0:0.02:2*pi)';
x = [sin(t) sin(2*t) sin(3*t) sin(4*t) sin(5*t) sin(6*t)];
y = x*a+(-4+8*rand(length(x),1));

a_hat = intvar(6,1);

residuals = y-x*a_hat;
bound = sdpvar(length(residuals),1);
F = set(-bound <= residuals <= bound);
solvesdp(F,sum(bound));
a_L1 = double(a_hat);
solvesdp([],residuals'*residuals);
a_L2 = double(a_hat);
bound = sdpvar(1,1);
F = set(-bound <= residuals <= bound);
solvesdp(F,bound);
a_Linf = double(a_hat);

General mixed integer programming

The mixed integer programming solvers discussed above are all guaranteed to find a globally optimal solution, if one exists. The built-in branch-and-bound module can be applied also to general nonlinear programs with discrete data. The difference is that there is no guarantee on global optimality for these problems. It can however be a useful strategy for finding reasonably good feasible solutions to mixed integer nonlinear programs. For the following example to work, you need to have fmincon, or possibly PENBMI, installed on your system.

x = sdpvar(5,1);
A = randn(15,5);
b = rand(15,1)*10;

obj = sum(x) + sum((x-3).^4); % 4th order objective
solvesdp(set(A*x < b) + set(integer(x)),obj,sdpsettings('bnb.solver','fmincon'))

* Starting YALMIP integer branch & bound.
* Lower solver   : fmincon-standard
* Upper solver   : rounder
* Max iterations : 300

Warning : The relaxed problem may be nonconvex. This means 
that the branching process not is guaranteed to find a
globally optimal solution, since the lower bound can be
invalid. Hence, do not trust the bound or the gap...
 Node      Upper     Gap(%)     Lower     Open
    1 :  -6.400E+001    44.57    -1.155E+002   2 
    2 :  -6.400E+001    44.57    -1.155E+002   3 
    3 :  -6.400E+001    41.27    -1.090E+002   4 
    4 :  -6.400E+001    41.27    -1.090E+002   5 
    5 :  -6.400E+001    36.58    -1.009E+002   6 
    6 :  -6.400E+001    36.58    -1.009E+002   7 
    7 :  -6.400E+001    33.44    -9.615E+001   8 
    8 :  -6.400E+001    33.44    -9.615E+001   9 
    9 :  -6.400E+001    30.38    -9.193E+001   8 
   10 :  -6.400E+001    30.38    -9.193E+001   9 
   11 :  -7.800E+001    13.85    -9.054E+001   6 
   12 :  -7.800E+001    13.85    -9.054E+001   5 
   13 :  -7.800E+001    12.19    -8.883E+001   4 
   14 :  -7.800E+001    12.19    -8.883E+001   3 
   15 :  -7.800E+001    10.41    -8.706E+001   2 
   16 :  -7.800E+001    10.41    -8.706E+001   3 
   17 :  -7.800E+001     0.60    -7.847E+001   2 
   18 :  -7.800E+001     0.60    -7.847E+001   1 
   19 :  -7.800E+001     0.60    -7.847E+001   0 
+  19 Finishing.  Cost: -78
 

For an additional example, check out the mixed integer geometric programming example