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