How to construct (0,1)-matrices with prescribed row and column sum vectors

4 次查看（过去 30 天）

显示更早的评论

Yingao Zhang 2020-9-15

0
链接

此问题的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/594094-how-to-construct-0-1-matrices-with-prescribed-row-and-column-sum-vectors

评论： Yingao Zhang 2021-2-21

采纳的回答： Ameer Hamza

All matrix elements are either 1 or 0.
Both row sum vector and column sum vector are given.
Return a 3-dimensional result that stacks all possible solutions along the third dimension. (exhaustive, all possible solutions need to be included.)
Avoid looping at best due to performance, use matrix operations whenever possible.
Thank you so much for your assistance :)

6 个评论
显示 4更早的评论隐藏 4更早的评论

Ameer Hamza 2020-9-16

编辑：Ameer Hamza 2020-9-16

If rows represent objects, then does that mean that row sum for all values is 1? And the column sum should add up to the number of objects. For example, if there are 200 objects and 20 destinations, then do you have

row_sum = ones(200, 1);
col_sum = % [1x20] matrix where sum(col_sum)=200

Is this correct?

Yingao Zhang 2020-9-16

编辑：Yingao Zhang 2020-9-16

Dear Ameer,

You are perfectly correct!

row_sum = ones(200, 1);
col_sum = % [1x20] matrix where sum(col_sum)=200

Do you have any idea for this problem?

Cheers,

Yingao Zhang

请先登录，再进行评论。

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

采纳的回答

Ameer Hamza 2020-9-16

0
链接

此回答的直接链接

https://ww2.mathworks.cn/matlabcentral/answers/594094-how-to-construct-0-1-matrices-with-prescribed-row-and-column-sum-vectors#answer_495541

Since you are minimizing the dot product, the thing to realize is that this is an integer linear programming problem. Following code apply intlinprog() function.

rng(0);
M = rand(1000, 20); % distance matrix
[m, n] = size(M);
row_sum = ones(m, 1);
col_sum = [50 45 60 35 25 90 30 35 75 90 10 5 30 40 90 60 40 60 45 85];
f = reshape(M', 1, []);
x = repmat({ones(1, n)}, m, 1);
Aeq = [blkdiag(x{:}); repmat(eye(n), 1, m)];
Beq = [row_sum(:); col_sum(:)];
lb = zeros(m*n, 1);
ub = ones(m*n, 1);
sol = intlinprog(f, 1:numel(x0), [], [], Aeq, Beq, lb, ub);
sol = reshape(sol, n, []).';

If you have knowledge about integer linear programming, then the logic of this code is quite easy to follow. Let me know if there is some confusion.

3 个评论
显示 1更早的评论隐藏 1更早的评论

Ameer Hamza 2020-9-17

I am glad to be of help!

Yingao Zhang 2021-2-21

Hi, Ameer,

May I kindly ask a follow-up question?

The MILP approach that you recommended is absolutely brilliant, however, the MATLAB coder doesn't support C++ code generation for the intlinprog function. Is there any simpler alternative that allows me to deploy the algorithm on embedded targets?

Cheers!

Yingao Zhang

请先登录，再进行评论。