What is known about solutions to sparse integer linear programming problems?

Question

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.

Answer 1

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 2

If the coefficient matrix is 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, which we use at Berkeley. Here is an underused list of myths and counterexamples 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.

Answer 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 .