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

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 :)

[John D'Errico]

You do understand the total number of solutions will likely be immense? And therefore, the result of this operation will be highly memory intensive? The computation of all such solutions will likely take more work than solving whatever it is that you want to solve in the first place.

The thing is, almost always when someone asks for a brute force solution like this, where ALL possible solutions are listed, this is the wrong approach. Instead, you should learn to use optimization tools to solve what you want to use this to solve.

[Yingao Zhang]

Dear John,

Thank you so much for your comment. I can't agree more with your opinion.

As you've already guessed, the aforementioned (0,1)-matrix is used for element selection with dot product. I'd like to find the optimum selection that produces the minimum sum of all the selected elements.

May I ask you for suggestions on optimization strategies?

Best regards,

Yingao Zhang

[Ameer Hamza]

What are the sizes of the row sum and column sum vectors? Is brute-force even feasible considering all the possible combination will be 2^(numel(row_sum)*numel(col_sum)). Unless there is a pattern with the selection matrix, I guess you will have to be contented with a sub-optimal solution using some heuristic-based algorithm.

[Yingao Zhang]

Dear Ameer,

Exactly, suboptimal solutions are definitely acceptable, while realtimeness is nonetheless a hard constraint.

The size of the matrix is around 200-1000 rows and less than 20 columns. It's basically a classification problem, with less than 1000 objects being classified to less than 20 destinations. Each destination accepts, however, only a fixed amount of objects. The original matrix represents the distance.

Thanks,

Yingao Zhang

[Ameer Hamza]

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]

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

Answer 1

[Ameer Hamza]

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.

[Yingao Zhang]

Thanks, Ameer,

Absolutely brilliant solution!

Cheers :)

[Ameer Hamza]

I am glad to be of help!

[Yingao Zhang]

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