<p>If the coefficient matrix is <a href="https://secure.wikimedia.org/wikipedia/en/wiki/Unimodular_matrix#Totally_unimodular">totally unimodular</a>, then an efficient solution exists via ordinary linear programming.  This holds for any ILP, not just sparse ones -- though you're more likely to be able to exploit this property for a sparse ILP such as yours.</p>

<p>I suspect you may know this already, so let me try and give you a better answer.  Before thinking about the specifics too deeply, the answer to your concrete question is "yes", a bound exists. The the intersection of n inequalities in m variables defines a polytope.  Because the coefficients are so well-behaved, we can work out an upper bound on the dimension of the coordinates of its vertices with a little arithmetic.  This gives you a very easy upper bound on the dimension of any integer point within the polytope, and thus on a solution to your integer program. Have you tried this already?</p>

<p>Your problem in particular has quite a bit of structure (I'm curious, where does it come from?) so I'm confident that we can be much more precise than this if we discuss it further.  </p>

<p>Now, for the more general question about finding information on this topic.  This is the sort of problem that traditionally falls in the theory of linear and integer programming, a subset of mathematical programming.  </p>

<p>It's quite an active area of research, but much of the work takes place in operations research departments under the headings of "optimization" and "mathematical programming" instead of computer science.  There are many textbooks available covering the topic.  You might consider the one by <a href="http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471283665.html">Wolsey</a>, which we use at Berkeley.  Here is an underused list of <a href="http://glossary.computing.society.informs.org/index.php?page=myths.html">myths and counterexamples</a> by Greenberg, including integer and linear programming, which may give you a sense of what things people consider in analyzing such problems.  Wolsey is dense, but a reasonably good place to start -- there are a bevy of techniques for analyzing ILPs and improving problem formulations to the point of efficiency.</p>

<p>Let me add that if you do pursue the naive approach I suggest, by analyzing the geometry of the polytope, the terms to search for would concern bounding the size of the coordinates of the polytope's vertices. These terms come up more often in the mathematical literature about polytopes.</p>

CC BY-SA 2.5
2010-11-06T14:37:12.260Z
@Dave Doty: there is a stackexchange site for operations research http://www.or-exchange.com.
Mohammad Alaggan
CC BY-SA 2.5
2010-08-18T05:48:01.510Z
2010-08-18T06:10:37.737Z
2010-08-18T06:10:37.737Z
Anand Kulkarni
<p>You may find this account of interest: </p>

<p><a href="http://en.wikipedia.org/wiki/Polyhedral_combinatorics" rel="nofollow">http://en.wikipedia.org/wiki/Polyhedral_combinatorics</a></p>

<p>and in particular the article by G. Ziegler:</p>

<p>Lectures on 0-1 polytopes </p>

<p>in:</p>

<p>Kalai, Gil; Ziegler, Günter M. (2000), Polytopes: Combinatorics and Computation, DMV Seminar, 29, Birkhäuser, ISBN 9783764363512 .</p>

CC BY-SA 2.5
2010-11-09T18:22:31.420Z
Thank you!  That looks like exactly the kind of field that would study these sorts of results.
Dave Doty
CC BY-SA 2.5
2010-11-06T13:30:30.517Z
2010-11-06T13:30:30.517Z
Joseph Malkevitch
<p>The answer to this (at least to the concrete question about linearly bounding the solution) is no.  This is part of the following paper: <a href="http://arxiv.org/abs/1011.3493" rel="nofollow">http://arxiv.org/abs/1011.3493</a>.  Theorem 5.1 was the motivation for this question.</p>

<p>The counterexample is this:</p>

<p>base case:</p>

<pre>
a_1'  + b_1'  - t &ge; 0
a_1'' + b_1'' - t &ge; 0
a_1   + b_1'  - t &le; -1
a_1 ' + b_1'' - t &le; -1
</pre>

<p>recursive case:</p>

<pre>
a_n'  + b_n'  + a_{n-1}   - t &ge; 0
a_n'' + b_n'' + a_{n-1}   - t &ge; 0
a_n   + b_n'  + a_{n-1}'' - t &le; -1
a_n'  + b_n'  + a_{n-1}'' - t &le; -1
</pre>

<p>along with requiring them all to be nonnegative.</p>

<p>You can prove by induction that any real solution must satisfy a_n'' >= a_n + 2^n.  We change the "&lt; 0"-inequalities into "&le; -1" because any integer solution satisfies "&le; -1" if and only if it satisfies "&lt; 0".</p>

<p>So, the moral is that n inequalities of this form can have the property that all integer solutions have at least one integer at least exponential in n, certainly not linearly bounded as we originally suspected.</p>

CC BY-SA 3.0
2010-11-05T17:15:40.910Z
2012-02-28T22:10:38.230Z
2012-02-28T22:10:38.230Z
Dave Doty
<p>If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what is known about the solution space?  I am less concerned with an efficient solution (although please indicate if one is known) than with knowing how small the minimum of the objective function can be, as a function of the number of variables and number of constraints, and the number of variables per constraint.  </p>

<p>More concretely, the program is something like</p>

<p>minimize t<br>
&nbsp;&nbsp;subject to<br>
for all i, x_i is a positive integer<br>
x1 + x2 + x3 - t &lt; 0<br>
x1 + x4 + x5 - t &lt; 0<br>
...<br>
x3 + x6 - t     &ge; 0<br>
x1 + x2 + x7 - t &ge; 0<br>
...  </p>

<p>If a concrete question is needed, then is it the case that the minimum solution obeys t &lt;= O(max{# of variables, # of constraints}), with the constant in the O() depending on the sparseness?  But even if the answer is no, I am more interested in knowing what kind of textbook or paper to study for a discussion of such issues, and if there is an area of study devoted to this kind of thing but I just don't know the terms to search for.  Thank you.</p>

<p><b>Update:</b> With further reflection (and thinking through the rather simple reduction of 3SAT to ILP, which uses constraints with three variables), I realize that the issue of coefficients is critical (if there is going to be an efficient algorithm).  More precisely, all x_i variables have 0 or 1 coefficients (with at most three 1 coefficients in any one constraint), and all t variables have -1 coefficients, and all comparisons have variables on the left and 0 on the right.  I updated the above example to clarify.</p>

CC BY-SA 2.5
2010-08-18T23:53:29.767Z
You have the constraints x_i ≥ 1 for all i, but do you also require that t ≥ 1?
Anand Kulkarni
CC BY-SA 2.5
2010-08-19T18:35:11.547Z
Not explicitly, but since there are constraints of the form x_i + ... < t, it is the case that t >= 1 will be enforced.
Dave Doty
CC BY-SA 2.5
2010-09-23T10:17:45.243Z
You may want to check out a paper by D. Chakrabarty and myself http://dx.doi.org/10.1007/s00453-010-9431-z (it's also on the arXiv) where we survey and improve results on approximability of sparse integer programming, some of which were then improved by N. Bansal et al (http://www.springerlink.com/content/e705157852700g23/ or arXiv)
daveagp
CC BY-SA 2.5
2010-08-17T14:50:16.207Z
Can you phrase your question more precisely? I am unsure whether the variable t is the one that counts as having a negative coefficient.
Chandra Chekuri
CC BY-SA 2.5
2010-08-17T15:03:40.837Z
Yes, t is the variable with a negative coefficient, if all variables are required to be on the left side. Or, if you like, all coefficients are {0,1} but all x_i's appear on the left side and t appears on the right side of each constraint.
Dave Doty
<co.combinatorics><integer-programming>
What is known about solutions to sparse integer linear programming problems?
Dave Doty
# What is known about solutions to sparse integer linear programming problems?

(Asked by: username_0 on 2010-08-17)

If I have a set of linear constraints in which each constraint has at most (say) 4 variables (all nonnegative and with {0,1} coefficients except for one variable that can have a -1 coefficient), what is known about the solution space? I am less concerned with an efficient solution (although please indicate if one is known) than with knowing how small the minimum of the objective function can be, as a function of the number of variables and number of constraints, and the number of variables per constraint.

More concretely, the program is something like

minimize t  
  subject to  
for all i, x\_i is a positive integer  
x1 + x2 + x3 - t < 0  
x1 + x4 + x5 - t < 0  
...  
x3 + x6 - t ≥ 0  
x1 + x2 + x7 - t ≥ 0  
...

If a concrete question is needed, then is it the case that the minimum solution obeys t <= O(max{# of variables, # of constraints}), with the constant in the O() depending on the sparseness? But even if the answer is no, I am more interested in knowing what kind of textbook or paper to study for a discussion of such issues, and if there is an area of study devoted to this kind of thing but I just don't know the terms to search for. Thank you.

**Update:** With further reflection (and thinking through the rather simple reduction of 3SAT to ILP, which uses constraints with three variables), I realize that the issue of coefficients is critical (if there is going to be an efficient algorithm). More precisely, all x\_i variables have 0 or 1 coefficients (with at most three 1 coefficients in any one constraint), and all t variables have -1 coefficients, and all comparisons have variables on the left and 0 on the right. I updated the above example to clarify.

**Tags:** co.combinatorics, integer-programming

> **Comments:**
> **username_3**: Can you phrase your question more precisely? I am unsure whether the variable t is the one that counts as having a negative coefficient.  
> **username_0**: Yes, t is the variable with a negative coefficient, if all variables are required to be on the left side. Or, if you like, all coefficients are {0,1} but all x_i's appear on the left side and t appears on the right side of each constraint.  
> **username_1**: You have the constraints x_i ≥ 1 for all i, but do you also require that t ≥ 1?  
> **username_0**: Not explicitly, but since there are constraints of the form x_i + ... < t, it is the case that t >= 1 will be enforced.  
> **username_2**: You may want to check out a paper by D. Chakrabarty and myself http://dx.doi.org/10.1007/s00453-010-9431-z (it's also on the arXiv) where we survey and improve results on approximability of sparse integer programming, some of which were then improved by N. Bansal et al (http://www.springerlink.com/content/e705157852700g23/ or arXiv)  

---

## 3 answers

### Answer by username_0 on 2010-11-05. Score: 12 | Accepted answer

The answer to this (at least to the concrete question about linearly bounding the solution) is no.  This is part of the following paper: http://arxiv.org/abs/1011.3493.  Theorem 5.1 was the motivation for this question.
The counterexample is this:
base case:

a_1'  + b_1'  - t ≥ 0
a_1'' + b_1'' - t ≥ 0
a_1   + b_1'  - t ≤ -1
a_1 ' + b_1'' - t ≤ -1

recursive case:

a_n'  + b_n'  + a_{n-1}   - t ≥ 0
a_n'' + b_n'' + a_{n-1}   - t ≥ 0
a_n   + b_n'  + a_{n-1}'' - t ≤ -1
a_n'  + b_n'  + a_{n-1}'' - t ≤ -1

along with requiring them all to be nonnegative.
You can prove by induction that any real solution must satisfy a_n'' >= a_n + 2^n.  We change the "< 0"-inequalities into "≤ -1" because any integer solution satisfies "≤ -1" if and only if it satisfies "< 0".
So, the moral is that n inequalities of this form can have the property that all integer solutions have at least one integer at least exponential in n, certainly not linearly bounded as we originally suspected.


---

### Answer by username_1 on 2010-08-18. Score: 9

If the coefficient matrix is [totally unimodular](https://secure.wikimedia.org/wikipedia/en/wiki/Unimodular_matrix#Totally_unimodular), then an efficient solution exists via ordinary linear programming. This holds for any ILP, not just sparse ones -- though you're more likely to be able to exploit this property for a sparse ILP such as yours.

I suspect you may know this already, so let me try and give you a better answer. Before thinking about the specifics too deeply, the answer to your concrete question is "yes", a bound exists. The the intersection of n inequalities in m variables defines a polytope. Because the coefficients are so well-behaved, we can work out an upper bound on the dimension of the coordinates of its vertices with a little arithmetic. This gives you a very easy upper bound on the dimension of any integer point within the polytope, and thus on a solution to your integer program. Have you tried this already?

Your problem in particular has quite a bit of structure (I'm curious, where does it come from?) so I'm confident that we can be much more precise than this if we discuss it further.

Now, for the more general question about finding information on this topic. This is the sort of problem that traditionally falls in the theory of linear and integer programming, a subset of mathematical programming.

It's quite an active area of research, but much of the work takes place in operations research departments under the headings of "optimization" and "mathematical programming" instead of computer science. There are many textbooks available covering the topic. You might consider the one by [Wolsey](http://www.wiley.com/WileyCDA/WileyTitle/productCd-0471283665.html), which we use at Berkeley. Here is an underused list of [myths and counterexamples](http://glossary.computing.society.informs.org/index.php?page=myths.html) by Greenberg, including integer and linear programming, which may give you a sense of what things people consider in analyzing such problems. Wolsey is dense, but a reasonably good place to start -- there are a bevy of techniques for analyzing ILPs and improving problem formulations to the point of efficiency.

Let me add that if you do pursue the naive approach I suggest, by analyzing the geometry of the polytope, the terms to search for would concern bounding the size of the coordinates of the polytope's vertices. These terms come up more often in the mathematical literature about polytopes.

> **Comments:**
> **username_4**: @username_0: there is a stackexchange site for operations research http://www.or-exchange.com.  

---

### Answer by username_5 on 2010-11-06. Score: 3

You may find this account of interest:

<http://en.wikipedia.org/wiki/Polyhedral_combinatorics>

and in particular the article by G. Ziegler:

Lectures on 0-1 polytopes

in:

Kalai, Gil; Ziegler, Günter M. (2000), Polytopes: Combinatorics and Computation, DMV Seminar, 29, Birkhäuser, ISBN 9783764363512 .

> **Comments:**
> **username_0**: Thank you!  That looks like exactly the kind of field that would study these sorts of results.  

---

