Parametric integer programming

When analysing computer programs (especially numerical programs in which arrays are used extensively), one is often confronted with integer programming problems. These problems have three peculiarities: (a) feasible points are ranked according to lexicographic order rather than by the usual linear economic function; (b) the feasible set depends on integer parameters; (c) one is interested only in exact solutions. The difficulty is somewhat alleviated by the fact that problem sizes are usually quite small. This paper shows that: (1) the classical simplex algorithm has no difficulty in handling lexicographic ordering; (2) the algorithm may be executed in symbolic mode, thus giving the solution of continuous parametric problems; (3) the method may be extended to problems in integers. It proves that the resulting algorithm always terminate and give an estimate of its complexity.