How to keep a specific value in binary matrix with column constraint?

2 次查看（过去 30 天）
Maria
Maria 2022-9-9
编辑： Maria 2022-9-21
Hello!
i have a binary matrix A(10*10) , i want to return '1' to '0' to get a single one in each row. I'm wondering how I can do this, knowing that I can keep a '1' in different columns except the last column, i.e. the last column cannot contain a '1'.
A [1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
1 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 1
0 1 1 1 1 1 1 1 1 0
0 0 1 1 1 1 1 1 1 1
0 0 0 1 1 1 1 1 1 1]

请先登录，再回答此问题。

采纳的回答

Fangjun Jiang
Fangjun Jiang 2022-9-9
编辑：Fangjun Jiang 2022-9-9
Ran in:
N=10;
A=eye(N);
B=A(:,randperm(N));% shuffle the Identity matrix randomly
RandCol=randi(N-1);
B(:,RandCol)=B(:,RandCol)+B(:,end);% move the 1 in last column randomly to the left
B(:,end)=0
B = 10×10
0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 1 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
% To verify
sum(B)
ans = 1×10
1 1 2 1 1 1 1 1 1 0
sum(B,2)
ans = 10×1
1 1 1 1 1 1 1 1 1 1
  27 个评论
显示 25更早的评论
Torsten
Torsten 2022-9-16
编辑：Torsten 2022-9-16
This is not done within 5 minutes.
You will have to invest some time and see how to call "intlinprog" for the problem I wrote down.
I hope you understand that this is more than I'm willing to do for you.
Maria
Maria 2022-9-16
@Torsten @Fangjun Jiang I really appreciate the effort and extra time you have contributed to help me. Thank you so much.

请先登录，再进行评论。

更多回答（1 个）

Torsten
Torsten 2022-9-17
编辑：Torsten 2022-9-17
Ran in:
@Maria
Your last question was quite interesting - so I invested some time ...
If A becomes larger, you will have to work with sparse inputs to intlinprog.
%rng('default')
% n = 100; % number of rows of A
% m = 60; % number of columns of A
n = 200; % number of rows of A
m = 120; % number of columns of A
bound_ones = 5; % bound for column sums of B
A = randi([0 1],n,m); % generate random binary matrix
%
% Usually, nothing needs to be changed after this line
if any(sum(A,2)==0)
display('Matrix A inappropriate.');
return
end
s = nnz(A);
%
% Objective function
% max: sum_ij cij = sum_ij (aij - bij)
% is equivalent to
% min: -sum_ij cij = -sum_ij (aij - bij)
f = [zeros(n*m,1);-ones(n*m,1)];
%f = zeros(2*n*m,1);
%
% Equality constraints
% cij = aij - bij
Aeq1 = zeros(n*m,2*n*m);
beq1 = zeros(n*m,1);
counter = 0;
for i = 1:n
for j = 1:m
counter = counter + 1;
Aeq1(counter,counter) = 1.0;
Aeq1(counter,counter+n*m) = 1.0;
beq1(counter) = A(i,j);
end
end
%sum_j bij = 1 (1 <= i <= n)
Aeq2 = zeros(n,2*n*m);
beq2 = zeros(n,1);
for i = 1:n
Aeq2(i,(i-1)*m+1:i*m) = 1.0;
beq2(i) = 1.0;
end
%Concatenate equality constraints
Aeq = [Aeq1;Aeq2];
beq = [beq1;beq2];
%
%Inequality constraints
%sum_i bij <= bound_ones (1 <= j <= m)
Aineq = zeros(m,2*n*m);
bineq = zeros(m,1);
for j = 1:m
Aineq(j,j:m:(n-1)*m+j) = 1.0;
bineq(j) = bound_ones;
end
%
%Integer constraints
%Define bij as integers
intcon = 1:n*m;
%
%Bound constraints
%0 <= bij <= 1 and cij = aij - bij >= 0
lb = zeros(2*n*m,1);
ub = [ones(n*m,1);Inf*ones(n*m,1)];
%
% Call intlinprog
[x,fval,exitflag,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
LP: Optimal objective value is -11707.000000. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
%
% s + fval should equal n if x is a solution
n
n = 200
s + fval
ans = 200
if exitflag == 1
B = x(1:n*m);
B = reshape(B,m,n).';
C = x(n*m+1:2*n*m);
C = reshape(C,m,n).';
% Check constraints
any(C~=A-B,'All')
any(C<0,'All')
any((0>B)|(B>1),'All')
any(sum(B,2)~=1)
any(sum(B,1)>bound_ones)
else
display('Matrix B does not exist')
end
ans = logical
0
ans = logical
0
ans = logical
0
ans = logical
0
ans = logical
0
B
B = 200×120
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
  4 个评论
显示 2更早的评论
Torsten
Torsten 2022-9-18
编辑：Torsten 2022-9-18
Ran in:
%rng('default')
% n = 100; % number of rows of A
% m = 60; % number of columns of A
n = 1500; % number of rows of A
m = 1000; % number of columns of A
bound_ones = 5; % bound for column sums of B
A = randi([0 1],n,m); % generate random binary matrix
%
% Usually, nothing needs to be changed after this line
if any(sum(A,2)==0)
display('Matrix A inappropriate.');
return
end
%
% Objective function
% min: sum_ij bij
f = ones(n*m,1);
% Alternatively:
% Only search for feasible point (objective doesn't matter)
%f = zeros(n*m,1);
%
% Equality constraints
%sum_j bij = 1 (1 <= i <= n)
ir = zeros(n*m,1);
ic = zeros(n*m,1);
v = zeros(n*m,1);
for i = 1:n
ir((i-1)*m+1:i*m) = i;
ic((i-1)*m+1:i*m) = (i-1)*m+1:i*m;
v((i-1)*m+1:i*m) = 1.0;
end
Aeq = sparse(ir,ic,v,n,n*m);
beq = ones(n,1);
%Aeq = zeros(n,n*m);
%beq = zeros(n,1);
%for i = 1:n
% Aeq(i,(i-1)*m+1:i*m) = 1.0;
% beq(i) = 1.0;
%end
%
%Inequality constraints
%sum_i bij <= bound_ones (1 <= j <= m)
ir = zeros(n*m,1);
ic = zeros(n*m,1);
v = zeros(n*m,1);
for j = 1:m
ir(j:m:(n-1)*m+j) = j;
ic(j:m:(n-1)*m+j) = j:m:(n-1)*m+j;
v(j:m:(n-1)*m+j) = 1.0;
end
Aineq = sparse(ir,ic,v,m,n*m);
bineq = bound_ones*ones(m,1);
%Aineq = zeros(m,n*m);
%bineq = zeros(m,1);
%for j = 1:m
% Aineq(j,j:m:(n-1)*m+j) = 1.0;
% bineq(j) = bound_ones;
%end
%
%Integer constraints
%Define bij as integers
intcon = 1:n*m;
%
%Bound constraints
%0 <= b_ij <= a_ij
lb = zeros(n*m,1);
ub = reshape(A.',[],1);
%
% Call intlinprog
[x,fval,exitflag,output] = intlinprog(f,intcon,Aineq,bineq,Aeq,beq,lb,ub);
LP: Optimal objective value is 1500.000000. Optimal solution found. Intlinprog stopped at the root node because the objective value is within a gap tolerance of the optimal value, options.AbsoluteGapTolerance = 0 (the default value). The intcon variables are integer within tolerance, options.IntegerTolerance = 1e-05 (the default value).
%
% fval should equal n if x is a solution
n
n = 1500
fval
fval = 1500
if exitflag == 1
B = reshape(x,m,n).';
% Check constraints
any(B>A,'All')
any((B<0)|(B>1),'All')
any(sum(B,2)~=1)
any(sum(B,1)>bound_ones)
else
display('Matrix B does not exist')
end
ans = logical
0
ans = logical
0
ans = logical
0
ans = logical
0
B
B = 1500×1000
0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0
Maria
Maria 2022-9-21
编辑：Maria 2022-9-21
@Torsten I'm sorry for my late reply, the code you contributed works well, I really appreciate your efforts. Thank you very much.

请先登录，再进行评论。

类别

在 Help Center 和 File Exchange 中查找有关 Get Started with Optimization Toolbox 的更多信息

标签

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

Translated by