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

MATLAB

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

Best Answer

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.
Related Question