Quais programas lineares inteiros são fáceis?

Ao tentar resolver um problema, acabei expressando parte dele como o seguinte programa linear inteiro. Aqui são números inteiros positivos dados como parte da entrada. Um subconjunto especificado das variáveis x i j é definido como zero e o restante pode assumir valores integrais positivos:$\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$$x_{ij}$

Minimizar

$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$

Sujeito a:

$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$

$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$

Gostaria de saber se este programa inteiro é solucionável em tempo polinomial; meu problema original é resolvido, se for, e eu tenho que tentar outra maneira, se não for. Então, minha pergunta é:

Como faço para descobrir se um determinado programa linear inteiro pode ser resolvido em tempo polinomial? Quais programas lineares inteiros são conhecidos por serem fáceis? Em particular, o programa acima pode ser resolvido em tempo polinomial? Você poderia me indicar algumas referências sobre isso?

É um caso especial do problema de transporte (ou problema de fluxo de custo mínimo) e, portanto, pode ser resolvido em tempo polinomial. A matriz do coeficiente é totalmente unimodular, pois é a matriz de incidência de um gráfico bipartido.

Os seguintes artigos da Wikipedia podem ser úteis.

• http://en.wikipedia.org/wiki/Minimum_cost_flow_problem
• http://en.wikipedia.org/wiki/Unimodular_matrix

Em geral, é difícil dizer. Mas uma condição suficiente é que sua matriz de restrição é totalmente unimodular e o lado direito é sempre inteiro (nesse caso, o lado direito é inteiro, mas você ainda precisa verificar a unimodularidade)

Você deve dar uma olhada no seguinte: http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

Um programa inteiro com apenas igualdades pode ser resolvido por programa linear.