<p>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)</p>

<p>You should take a look at this:
<a href="http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns">http://en.wikipedia.org/wiki/Linear_program#Integer_unknowns</a></p>

CC BY-SA 2.5
2011-01-20T00:19:56.980Z
I was thinking about your matrix and it looks totally unimodular.
Vinicius dos Santos
CC BY-SA 2.5
2011-01-20T13:45:21.157Z
@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).
gphilip
CC BY-SA 2.5
2011-01-20T15:16:59.193Z
@gphilip: At http://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.
Vinicius dos Santos
CC BY-SA 2.5
2011-01-20T15:17:43.093Z
@gphilip: What is the motivation for this Linear Program?
Vinicius dos Santos
CC BY-SA 2.5
2011-01-21T06:52:59.190Z
@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.
gphilip
CC BY-SA 2.5
2011-01-20T00:05:56.853Z
2011-01-20T00:05:56.853Z
Vinicius dos Santos
<p>An integer program with only equalities can be solved by linear program.</p>

CC BY-SA 3.0
2017-08-19T20:32:39.937Z
this seemed important for its own sake.
Turbo
CC BY-SA 3.0
2017-08-19T22:34:08.233Z
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.
Sasho Nikolov
CC BY-SA 3.0
2017-08-19T22:39:00.643Z
@SashoNikolov a degenerate case but definitely a valid one though.
Turbo
CC BY-SA 3.0
2017-08-20T00:44:52.283Z
why negative vote?
Turbo
CC BY-SA 3.0
2017-08-19T18:58:52.750Z
2017-08-19T18:58:52.750Z
Turbo
<p>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.</p>

<p>The following Wikipedia articles could be useful.</p>

<ul>
<li><a href="http://en.wikipedia.org/wiki/Minimum_cost_flow_problem">http://en.wikipedia.org/wiki/Minimum_cost_flow_problem</a></li>
<li><a href="http://en.wikipedia.org/wiki/Unimodular_matrix">http://en.wikipedia.org/wiki/Unimodular_matrix</a></li>
</ul>

CC BY-SA 2.5
2011-01-20T03:58:31.483Z
@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?
gphilip
CC BY-SA 2.5
2011-01-20T04:37:02.233Z
@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.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-20T13:15:23.310Z
@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?
gphilip
CC BY-SA 2.5
2011-01-20T14:32:18.330Z
@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.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-20T14:40:19.393Z
@Yoshio : Thank you, let me chew on that!
gphilip
CC BY-SA 2.5
2011-01-20T14:55:21.447Z
Hmm... my short-cut rules don't look enough to give a proof that the coefficient matrix in the standard form is TU.  Let me think.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-20T15:07:50.543Z
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.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-21T07:52:35.067Z
@Yoshio : Yes, these rule do the job! Thanks for all the help. 

The fastest algorithm for solving an LP for which I can find a reference is Karmarkar's algorithm(http://en.wikipedia.org/wiki/Karmarkar%27s_algorithm), which in this case would run in roughly $O(l^{11})$ time (with some simplifying assumptions). Is this the best that I can hope for, or are there faster algorithms known for the totally unimodular case? Straightforward googling doesn't seem to turn up anything useful.
gphilip
CC BY-SA 2.5
2011-01-21T12:04:23.363Z
@gphilip : Thank you.  For faster algorithms, I don't have an immediate answer.  Probably it's better to cast it as a new question.
Yoshio Okamoto
CC BY-SA 2.5
2011-01-21T12:23:29.743Z
@Yoshio : Thanks, I have done that : http://cstheory.stackexchange.com/q/4454/148
gphilip
CC BY-SA 2.5
2011-01-20T01:04:22.980Z
2011-01-20T01:04:22.980Z
Yoshio Okamoto
<p>While trying to solve a problem, I ended up expressing part of it as the following integer linear program. Here <span class="math-container">$\ell,m,n_{1},n_{2},\ldots,n_{\ell},c_{1},c_{2},\ldots,c_{m},w$</span> are all positive integers given as part of the input. A specified subset of the variables <span class="math-container">$x_{ij}$</span> is set to zero, and the rest can take positive integral values:</p>
<blockquote>
<p>Minimize</p>
<p><span class="math-container">$\sum_{j=1}^{m}c_{j}\sum_{i=1}^{\ell}x_{ij}$</span></p>
<p>Subject to:</p>
<p><span class="math-container">$\sum_{j=1}^{m}x_{ij}=n_{i}\,\,\forall i$</span></p>
<p><span class="math-container">$\sum_{i=1}^{\ell}x_{ij}\ge w\,\,\forall j$</span></p>
</blockquote>
<p>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:</p>
<blockquote>
<p>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?</p>
</blockquote>

<reference-request><linear-programming><polynomial-time><integer-programming><integrality-gap>
Which Integer Linear Programs are easy?
gphilip
# Which Integer Linear Programs are easy?

(Asked by: username_0 on 2011-01-19)

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?

**Tags:** reference-request, linear-programming, polynomial-time, integer-programming, integrality-gap

---

## 3 answers

### Answer by username_4 on 2011-01-20. Score: 16 | Accepted answer

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_problem>
* <http://en.wikipedia.org/wiki/Unimodular_matrix>

> **Comments:**
> **username_0**: @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?  
> **username_4**: @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.  
> **username_0**: @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?  
> **username_4**: @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.  
> **username_0**: @Yoshio : Thank you, let me chew on that!  
> **username_4**: Hmm... my short-cut rules don't look enough to give a proof that the coefficient matrix in the standard form is TU.  Let me think.  
> **username_4**: 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.  
> **username_0**: @Yoshio : Yes, these rule do the job! Thanks for all the help.   The fastest algorithm for solving an LP for which I can find a reference is Karmarkar's algorithm(http://en.wikipedia.org/wiki/Karmarkar%27s_algorithm), which in this case would run in roughly $O(l^{11})$ time (with some simplifying assumptions). Is this the best that I can hope for, or are there faster algorithms known for the totally unimodular case? Straightforward googling doesn't seem to turn up anything useful.  
> **username_4**: @gphilip : Thank you.  For faster algorithms, I don't have an immediate answer.  Probably it's better to cast it as a new question.  
> **username_0**: @Yoshio : Thanks, I have done that : http://cstheory.stackexchange.com/q/4454/148  

---

### Answer by username_1 on 2011-01-20. Score: 9

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>

> **Comments:**
> **username_1**: I was thinking about your matrix and it looks totally unimodular.  
> **username_0**: @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).  
> **username_1**: @gphilip: At http://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.  
> **username_1**: @gphilip: What is the motivation for this Linear Program?  
> **username_0**: @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.  

---

### Answer by username_2 on 2017-08-19. Score: 2

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

> **Comments:**
> **username_2**: this seemed important for its own sake.  
> **username_3**: 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.  
> **username_2**: @SashoNikolov a degenerate case but definitely a valid one though.  
> **username_2**: why negative vote?  

---

