在 MATLAB 中通过整数规划找到最优二进制矩阵

Question

我尝试使用 Matlab 函数 intlinprog 将 optimal binary matrix 中的解决方案实现为测试输入，如下面的代码

a=[450;400;250;200]; % test input
b=[750;500]; % test input
n = 4; % length of a
m = 2; % length of b
oness=ones(m,1);
f = (kron(a,oness))'; % objective function
cont1=kron(eye(n),oness'); 
cont2=-cont1;
cont3=-kron(a',eye(m));
A=[cont1;cont2;cont3];
bb=[ones(n,1);-zeros(n,1);-b];
lb = zeros(m*n,1);
ub = [ones(m*n,1)]; % enforces binary
intcon= [1,2,3,4,5,6,7,8]; % all variable should be integers  
 Aeq = [];
 beq = [];
x = intlinprog(f,intcon,A,bb,Aeq,beq,lb,ub)

但是，我收到了消息

Intlinprog stopped because no integer points satisfy the constraints.

这个测试输入的一个明显的最佳解决方案是 x = [0;1;1;0;1;0;0;0]。

但是，如果我通过 intcon=[] 移除完整性约束，我会得到一个最优解。为什么函数找不到具有积分约束的最小解？

Answer 1

我现在已经修正了问题定义中的错误。代码现在可以正确给出输出。以下是正确的代码：

a=[450;400;250;200]; % test input
b=[750;500]; % test input
n = 4;
m = 2;
oness=ones(m,1);
f = -(kron(a,oness))';
cont1=kron(eye(n),oness');
cont2=-cont1;
cont3=kron(a',eye(m));
A=[cont1;cont2;cont3];
bb=[ones(n,1);-zeros(n,1);b];
lb = zeros(m*n,1);
ub = [ones(m*n,1)]; % enforces binary
intcon= 1:8;
 Aeq = [];
 beq = [];
x = intlinprog(f,intcon,A,bb,Aeq,beq,lb,ub)

答案：

x = [1;0;0;1;1;0;0;0] 给出与

相同的最佳结果

x = [0;1;1;0;1;0;0;0]

在 MATLAB 中通过整数规划找到最优二进制矩阵

Finding the optimal binary matrix via integer programming in MATLAB

matlab

mathematical-optimization

linear-programming

integer-programming