How to construct (0,1)-matrices with prescribed row and column sum vectors
2 visualizaciones (últimos 30 días)
Mostrar comentarios más antiguos
Yingao Zhang
el 15 de Sept. de 2020
Comentada: Yingao Zhang
el 21 de Feb. de 2021
- 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 comentarios
Ameer Hamza
el 16 de Sept. de 2020
Editada: Ameer Hamza
el 16 de Sept. de 2020
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
el 16 de Sept. de 2020
Editada: Yingao Zhang
el 16 de Sept. de 2020
Respuesta aceptada
Ameer Hamza
el 16 de Sept. de 2020
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 comentarios
Más respuestas (0)
Ver también
Categorías
Más información sobre Get Started with Optimization Toolbox en Help Center y File Exchange.
Community Treasure Hunt
Find the treasures in MATLAB Central and discover how the community can help you!
Start Hunting!