1
$\begingroup$

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?

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

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.