I want to find solutions for the following problem. It seems to be a classic problem in integer programmimg and logistics, but I don't know its name.
Find a matrix of m rows and n columns, with non-negative entries, such that the sum of the entries in each row are, respectively, m given integers and the sum of the entries in each column are, also respectively, another n given integers.
Also, the entries will be limited to given maximum integers, and in some cases those entries will be 0.
In reality, I am interested in an algorithm for extracting all solutions (maybe I should ask in the Programming StackExchange if this is not the correct place). In the end, my goal is to find a solution which makes the maximum possible number of entries equal to zero.
This problem comes from allocating teachers (columns) for classes on days (rows) so that they come to work the least possible number of days (the non-zero entries).
Just to have a better idea of the sizes of each parameter: m=5, n=100, entries are bounded to 5 or 6, when not set to 0 from the beginning.
Best Answer
Let $r_i$ be the required sum for row $i$, and let $c_j$ be the required sum for column $j$. Let nonnegative integer variable $x_{i,j}$ with upper bound $M_{i,j}$ be the entry in cell $(i,j)$, and let binary variable $y_{i,j}$ indicate whether $x_{i,j}>0$. The problem is to maximize $\sum_{i,j} (1 - y_{i,j})$ subject to: \begin{align} \sum_j x_{i,j} &= r_i &&\text{for all $i$}\\ \sum_i x_{i,j} &= c_j &&\text{for all $j$}\\ x_{i,j} &\le M_{i,j} y_{i,j} &&\text{for all $i$ and $j$} \end{align}
If you think of the equivalent objective of minimizing $\sum_{i,j} y_{i,j}$, this is the fixed-charge transportation problem in a complete bipartite network with a supply node for each $i$, a demand node for each $j$, and arcs $(i,j)$ with capacity $M_{i,j}$. In this formulation, "set to $0$ from the beginning" means $M_{i,j}=0$, but it is more efficient to just omit that arc.