9 views (last 30 days)

Hi everyone,

Please assume that I have a matrix as follows:

A = [0 1 0 0

1 1 0 0

0 0 1 0

0 0 0 1

1 0 1 1]

I would like to identify and selcet the minimum number of rows that have value of one in all columns (altoghether). For example, rows 2 and 5 are the best choice for matrix A. Do you have any suggestion?

Regards,

Amir

Matt J
on 8 Jul 2020

Edited: Matt J
on 8 Jul 2020

This solution uses the Optimization Toolbox, although I am still only half certain what row-selection rule you are looking for (see my question here).

[m,n]=size(A);

irp=1:m;

rp=randperm(m); %row permutation

irp(rp)=irp; %inverse permutation

Ap=A(rp,:);

x=optimvar('x',[1,m],'LowerBound',0,'UpperBound',1,'Type','integer');

prob=optimproblem('Objective',sum(x));

prob.Constraints=(x*Ap>=ones(1,n));

sol=solve(prob);

selection=find(round(sol.x(irp)));

Matt J
on 8 Jul 2020

2) Just randomly pre-permute the rows of A (see my edited version above).

1) I find that my version is faster than yours for larger problems even when adding in the above permutation. For example, with A = randi([0,1],40,100), I find

Elapsed time is 0.193646 seconds.%Matt J

Elapsed time is 0.367822 seconds.%Amir

madhan ravi
on 8 Jul 2020

Edited: madhan ravi
on 8 Jul 2020

According to what I understood, see if this does what you want to do:

[a, b] = unique(A, 'rows', 'stable');

s = sum(a, 2);

rows = b(s > 1)

Amirhossein Moosavi
on 8 Jul 2020

Matt J
on 8 Jul 2020

My method is faster for larger problems. For this matrix,

A = randi([0,1],40,100);

I obtain these timings,

Elapsed time is 0.193646 seconds.%Matt J

Elapsed time is 0.367822 seconds.%Amir

Opportunities for recent engineering grads.

Apply Today
## 2 Comments

## Direct link to this comment

https://nl.mathworks.com/matlabcentral/answers/561275-identify-the-minimum-number-of-rows-in-a-matrix-meeting-a-condition#comment_928862

⋮## Direct link to this comment

https://nl.mathworks.com/matlabcentral/answers/561275-identify-the-minimum-number-of-rows-in-a-matrix-meeting-a-condition#comment_928862

## Direct link to this comment

https://nl.mathworks.com/matlabcentral/answers/561275-identify-the-minimum-number-of-rows-in-a-matrix-meeting-a-condition#comment_928943

⋮## Direct link to this comment

https://nl.mathworks.com/matlabcentral/answers/561275-identify-the-minimum-number-of-rows-in-a-matrix-meeting-a-condition#comment_928943

Sign in to comment.