Integer 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));

Defining integer programs is as simple as standard problems. The supported integer solvers are GLPK, CPLEX, XPRESS and MOSEK. However, YALMIP comes with an internal branch-and-bound solver, called bnb, to be used together with continuous solvers. Hence, it is possible to solve mixed integer linear/quadratic/second order cone/semidefinite programs. Note though that the internal branch-and-bound algorithm is rudimentary and only useful 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);