While trying to solve a problem, I ended up expressing part of it as the following integer linear program. Here $\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$ are all positive integers given as part of the input. A specified subset of the variables $x_{ij}$ is set to zero, and the rest can take positive integral values:Minimize$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$Subject to: $\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$I would like to know if this integer program is solvable in polynomial time; my original problem is solved if it is, and I have to try some other way if it isn't. So my question is:How do I figure out if a certain integer linear program can be solved in polynomial time? Which integer linear programs are known to be easy? In particular, can the above program be solved in polynomial time? Could you point me to some references on this?
Which Integer Linear Programs are easy?
reference request;linear programming;polynomial time;integer programming;integrality gap
It is a special case of the transportation problem (or the minimum-cost flow problem), and so can be solved in polynomial time.  The coefficient matrix is totally unimodular since it is the incidence matrix of a bipartite graph.The following Wikipedia articles could be useful.http://en.wikipedia.org/wiki/Minimum_cost_flow_problemhttp://en.wikipedia.org/wiki/Unimodular_matrix