14
$\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?

Improve this question
$\endgroup$

3 Answers 3

Reset to default
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.

Improve this answer
$\endgroup$
10
  • 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
    Commented Jan 20, 2011 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
    Commented Jan 20, 2011 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
    Commented Jan 20, 2011 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
    Commented Jan 20, 2011 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
    Commented Jan 20, 2011 at 15:07
9
$\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

Improve this answer
$\endgroup$
5
  • $\begingroup$ I was thinking about your matrix and it looks totally unimodular. $\endgroup$
    – Vinicius dos Santos
    Commented Jan 20, 2011 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
    Commented Jan 20, 2011 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
    Commented Jan 20, 2011 at 15:16
  • $\begingroup$ @gphilip: What is the motivation for this Linear Program? $\endgroup$
    – Vinicius dos Santos
    Commented Jan 20, 2011 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
    Commented Jan 21, 2011 at 6:52
2
$\begingroup$

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

Improve this answer
$\endgroup$
4
  • $\begingroup$ this seemed important for its own sake. $\endgroup$
    – Turbo
    Commented Aug 19, 2017 at 20:32
  • 3
    $\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
    Commented Aug 19, 2017 at 22:34
  • 3
    $\begingroup$ @SashoNikolov a degenerate case but definitely a valid one though. $\endgroup$
    – Turbo
    Commented Aug 19, 2017 at 22:39
  • $\begingroup$ why negative vote? $\endgroup$
    – Turbo
    Commented Aug 20, 2017 at 0:44

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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