Is there a name for this integer linear optimization problem?

Question

I have an integer linear programming problem of the form:

$$\DeclareMathOperator{\tr}{tr} \min \tr WX$$ subject to:

$$\begin{align} \sum_j X_{ij} < c_i && \forall i \\ \sum_i X_{ij} = 1 && \forall j \\ X_{ij} \in \{0,1\} && \forall i,j \end{align}$$

I'm sure this is probably a common problem that's been well studied, but I can't find the name for it. Does anyone know?

Answer 1

This is a minimum cost network flow problem. Construct the network as follows. You haven't specified the ranges for $i$ and $j$, but I'll assume that we $i=1, 2, \ldots, m$ and $j=1, 2, \ldots, n$.

• A source node $s$ sourcing $n$ units of flow.
• $m$ nodes $u_{i}$, $i=1, 2, \ldots, m$.
• Arcs from $s$ to $u_{i}$ with capacity $c_{i}$ for $i=1, 2, \ldots m$.
• $n$ nodes $v_{j}$, $j=1, 2, \ldots, n$.
• Arcs $(u_{i},v_{j})$, for all $i,j$, each with capacity 1.
• A node $t$ that is a sink for $n$ units of flow.
• Arcs from $v_{j}$ to $t$ with capcity one for $j=1, 2, \ldots, n$.
• Weights $W_{j,i}$ on the arcs from $u_{i}$ to $v_{j}$. Weights of 0 on the remaining arcs.

Any feasible flow on this graph corresponds to a solution of the LP relaxation of the above problem. Since the constraint matrix of the LP is totally-unimodular, any optimal BFS has integer values for all of the variables $X_{i,j}$.

You can solve this problem using the simplex method or by using a specialized algorithm for the minimum cost network flow problem.