# Is there a name for this integer linear optimization problem?

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?

• All of the variables are either 0 or 1. – Nick Apr 16 '19 at 18:07
• Ahh i misread the statement. Thought it was must be in the interval of 0 to 1. my bad. – EMP Apr 16 '19 at 21:07

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.