<p>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 <span class="math-container">$b$</span> 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.</p>
<p>Since all edge capacities are integers, stndard algorithms will return an optimal solution that is integral.</p>

CC BY-SA 4.0
2020-06-25T19:52:01.997Z
Note: I think that you also need to put capacities of 1 on each row-to-column edge.

And, for those who don't know, note that with this construction the edge capacities are integers, so standard algorithms will return an optimal integer flow, i.e., a solution to the given integer LP.
Neal Young
CC BY-SA 4.0
2020-06-25T20:33:38.523Z
@NealYoung, great points, thank you!  I've edited my answer accordingly.
D.W.
CC BY-SA 4.0
2020-05-26T02:16:03.807Z
2020-06-25T20:33:29.697Z
2020-06-25T20:33:29.697Z
D.W.
<p>I would like to know if the following problem is known and has any efficient solution.</p>

<p>Given an <span class="math-container">$n\times n$</span> score matrix <span class="math-container">$S$</span>. Find the best <span class="math-container">$a$</span> elements, in terms of their sum of scores, such that no row or column is selected more than <span class="math-container">$b$</span> times.</p>

<p>This can be re-formulated as the following integer linear program:
<span class="math-container">\begin{align}
\mbox{maximize} &amp;\sum_{1\le i,j\le n} s_{ij}x_{ij},\\
\mbox{subject to} &amp; \sum_{1\le i,j\le n} x_{ij} = a,\\
&amp; \sum_{1\le i\le n} x_{ij} \le b \quad\forall 1\le j\le n,\\
&amp; \sum_{1\le j\le n} x_{ij} \le b \quad\forall 1\le i\le n,\\
&amp; x_{ij}\in\{0,1\}\quad\forall 1\le i,j\le n.
\end{align}</span></p>

<p>Thank you very much in advance for your help!</p>

<co.combinatorics><optimization><integer-programming>
Name of (and solution to) this generalization of linear assignment
f10w
# Name of (and solution to) this generalization of linear assignment

(Asked by: username_0 on 2020-05-22)

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!

**Tags:** co.combinatorics, optimization, integer-programming


---

## 1 answers

### Answer by username_1 on 2020-05-26. Score: 2

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.

> **Comments:**
> **username_2**: Note: I think that you also need to put capacities of 1 on each row-to-column edge.  And, for those who don't know, note that with this construction the edge capacities are integers, so standard algorithms will return an optimal integer flow, i.e., a solution to the given integer LP.  
> **username_1**: @NealYoung, great points, thank you!  I've edited my answer accordingly.  

---

