What is known about solutions to sparse integer linear programming problems?
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.