导航

Integer programminginteger and binary variablesmixed integer conic programminggeneral mixed integer programmingReferences

Integer programming

YALMIP内置了BNB求解器可以处理整数规划问题

integer and binary variables

定义二元变量binvar和整型变量intvar如下

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

设置目标函数

z=x+y+trace(x)+sum(sum(y)); F=[z>=0, x<=0]

也可以声明变量的类型

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

mixed integer conic programming

内置的BNB求解器的算法为基础算法，只有当问题规模较小的时候才可以起作用，考虑线性回归的问题，加上变量的整型约束

%% x = [1 2 3 4 5 6]'; t = (0:0.02:2*pi)'; a = [sin(t) sin(2*t) sin(3*t) sin(4*t) sin(5*t) sin(6*t)]; y = a*x+(-4+8*rand(length(a),1)); x_hat = intvar(6,1); % 整型变量 residuals = y-a*x_hat; bound = sdpvar(length(residuals),1); % 变量上下界 F = [-bound <= residuals <= bound]; optimize(F,sum(bound)); % L1 norm x_L1 = value(x_hat); optimize([],residuals'*residuals); % L2 norm x_L2 = value(x_hat); bound = sdpvar(1,1); % L_inf norm F = [-bound <= residuals <= bound]; optimize(F,bound); x_Linf = value(x_hat);

BNB同样支持半正定混合整数规划，可以设置半正定约束

%% semidefinited constraint F = [toeplitz(x_hat) >= 0]; ops=sdpsettings('solver', 'BNB'); optimize(F, residuals'*residuals, ops); x_L2_toep = value(x_hat)

general mixed integer programming

在非线性混合整数规划中未必可以找到全局最优解，但是可以找到近似可行的局部最优解也是合理的

%% general MIP x = sdpvar(5, 1); A = randn(15, 5); b = rand(15, 1)*10; obj = sum(x)+sum((x-3).^4); % 目标函数为四阶矩 ops=sdpsettings('solver', 'bnb', 'bnb.solver', 'fmincon'); optimize([A*x<=b, integer(x)], obj, ops)

使用BMIBNB可以求出全局最优解，但是适合变量较少的情况，并且求解速度较慢

% ops = sdpsettings('solver','bmibnb', 'bnb.upper', 'fmincon'); % ops=sdpsettings('solver', 'bmibnb'); ops = sdpsettings('solver','bmibnb', 'bmibnb.uppersolver', 'fmincon'); optimize([A*x <= b, integer(x)],obj,ops)

References

Integer programming