Name of (and solution to) this generalization of linear assignment

Question

I would like to know if the following problem is known and has any efficient solution.

Given an $n\times n$ score matrix $S$. Find the best $a$ elements, in terms of their sum of scores, such that no row or column is selected more than $b$ times.

This can be re-formulated as the following integer linear program: \begin{align} \mbox{maximize} &\sum_{1\le i,j\le n} s_{ij}x_{ij},\\ \mbox{subject to} & \sum_{1\le i,j\le n} x_{ij} = a,\\ & \sum_{1\le i\le n} x_{ij} \le b \quad\forall 1\le j\le n,\\ & \sum_{1\le j\le n} x_{ij} \le b \quad\forall 1\le i\le n,\\ & x_{ij}\in\{0,1\}\quad\forall 1\le i,j\le n. \end{align}

Thank you very much in advance for your help!

Answer 1

It looks to me like this is a special case of minimum cost flow; introduce one vertex per row and one per column, with an edge for each entry whose cost is the negative of the value of that entry and whose capacity is 1. Then add an edge of capacity $b$ from the source to each row, with cost 0, and similarly for the columns, and solve the resulting minimum cost flow problem -- which can be done in polynomial time.

Since all edge capacities are integers, stndard algorithms will return an optimal solution that is integral.