What is known about solutions to sparse integer linear programming problems? 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
&nbsp;&nbsp;subject to
for all i, x_i is a positive integer
x1 + x2 + x3 - t &lt; 0
x1 + x4 + x5 - t &lt; 0
...
x3 + x6 - t     &ge; 0
x1 + x2 + x7 - t &ge; 0
...  

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.

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.
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 &ge; 0
a_1'' + b_1'' - t &ge; 0
a_1   + b_1'  - t &le; -1
a_1 ' + b_1'' - t &le; -1


recursive case:


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


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 "&lt; 0"-inequalities into "&le; -1" because any integer solution satisfies "&le; -1" if and only if it satisfies "&lt; 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.