13
$\begingroup$

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?

$\endgroup$
16
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ @Yoshio : Thank you, that answers my particular problem instance (once I have verified it for myself). Do you know of conditions other than total unimodularity which guarantee a polynomial-time solution? $\endgroup$ – gphilip Jan 20 '11 at 3:58
  • 2
    $\begingroup$ @gphilip : I would summarize theses questions by the term "integrality of polyhedra" and the literature on this subject is huge. The book "Combinatorial Optimization: Packing and Covering" by Gerard Cornuejols (published in 2001) describes several results along this line. $\endgroup$ – Yoshio Okamoto Jan 20 '11 at 4:37
  • $\begingroup$ @Yoshio : Could you tell me why you think that the coefficient matrix is the incidence matrix of a bipartite graph? Pardon my ignorance, but to speak of a coefficient matrix, do we not have to first convert all constraints to the standard form ($Ax\le b$)? Once we do that, the matrix will have -1 entries, and then it does not match the definition of an incidence matrix (AFAIK). Or is it the case that we can speak of the coefficient matrix without first converting the constraints to the standard form? $\endgroup$ – gphilip Jan 20 '11 at 13:15
  • 1
    $\begingroup$ @gphilip : Excuse me. I made an implicit short-cut, and I was speaking of the coefficient matrix without converting to the standard form. I used the following short-cuts. (1) If $A$ is totally unimodular (TU, for short), then $-A$ is also TU, which means that we don't have to care about the direction of inequalities. (2) If $A$ is TU, then $[A \mid -A]$ is also TU, which means that we don't have to care about equality constraints. (3) Every submatrix of a TU matrix is TU. Applying these rules to the incidence matrix of a bipartite graph should prove the property for the standard form. $\endgroup$ – Yoshio Okamoto Jan 20 '11 at 14:32
  • 1
    $\begingroup$ Let me change my short-cut rules as follows. (1) Duplication of a row maintains total unimodularity. (2) Reversal of the sign of a row maintains total unimodularity. They should do the job. $\endgroup$ – Yoshio Okamoto Jan 20 '11 at 15:07
8
$\begingroup$

In general, it's hard to say. But a sufficient condition is your constraint matrix is totally unimodular and right-hand side is always integer (in this case the right hand side is integer, but you still have to check about unimodularity)

You should take a look at this: http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns

$\endgroup$
  • $\begingroup$ I was thinking about your matrix and it looks totally unimodular. $\endgroup$ – Vinicius dos Santos Jan 20 '11 at 0:19
  • $\begingroup$ @Vinicius : Could you tell me why the matrix looks totally unimodular to you? I could not figure this out, in spite of Yoshio's comment (please see my response there). $\endgroup$ – gphilip Jan 20 '11 at 13:45
  • $\begingroup$ @gphilip: At en.wikipedia.org/wiki/Unimodular_matrix in the "Common totally unimodular matrices" section, the first item list 4 sufficient conditions for a matrix to be unimodular. I think that these conditions, together with the shortcuts Yoshio commented, are enough to show that the problem can be solved in polynomial time. $\endgroup$ – Vinicius dos Santos Jan 20 '11 at 15:16
  • $\begingroup$ @gphilip: What is the motivation for this Linear Program? $\endgroup$ – Vinicius dos Santos Jan 20 '11 at 15:17
  • $\begingroup$ @Vinicius : We are trying to solve a problem phrased in terms modifying an input matrix in a certain way to obtain another matrix with some good properties. This LP came out of one sub-problem during the process. $\endgroup$ – gphilip Jan 21 '11 at 6:52
2
$\begingroup$

An integer program with only equalities can be solved by linear program.

$\endgroup$
  • $\begingroup$ this seemed important for its own sake. $\endgroup$ – T.... Aug 19 '17 at 20:32
  • 2
    $\begingroup$ I wouldn't call that an integer program. It's a system of linear equations over the integers, solvable efficiently by computing the Hermite normal form. $\endgroup$ – Sasho Nikolov Aug 19 '17 at 22:34
  • 2
    $\begingroup$ @SashoNikolov a degenerate case but definitely a valid one though. $\endgroup$ – T.... Aug 19 '17 at 22:39
  • $\begingroup$ why negative vote? $\endgroup$ – T.... Aug 20 '17 at 0:44

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.