Parameterisation algorithms for the integer linear programs in binary variables (Q795729)

In this paper problems of parametric integer linear programming (ILP) are discussed. Consider the problem: (ILP) minimize \(z(x)=\sum_{j\in J}c_ jx_ j\) subject to A\(X\leq b\), \(x_ j=0\), 1. Due to Roodman's well-known postoptimality analysis scheme a modified version of Balas' additive algorithm is used and each of the fathomed partial solutions (FPS) is attributed to the constraint which caused the fathoming. The set \(\Lambda\) of FPS is partitioned into \(m+1\) disjoint sets. In this paper a parametric function \(z^*(\xi(\lambda))\) for any single parameter \(\xi \in \{c_ j,a_{ij},b_ i:i\in I\), \(j\in J\}\), \(\xi(\lambda)=\xi +\lambda\) is constructed. The function \(z^*(\xi(\lambda))\) matches nonoverlapping intervals of \(\lambda\) with optimal solutions and their associated objective function values. Contrasted to Roodman's collection and classification scheme the proposed algorithm employs additional bounding tests which result in a substantial reduction in the number of FPS necessary for the construction of \(z^*(\xi(\lambda))\). Computational experience was conducted on a UNIVAC 1106, computer programs were written in FORTRAN V and tested on more than 1000 randomly generated problems.