An algorithm for solving a structured class of linear programming problems (Q1078069)

The author presents a procedure for solving the following class of specially structured linear programs: maximize \(Z_{PN}=\sum_{j\in J}c_ jx_ j\) subject to \(\ell_ i\leq \sum_{i\in J(i)}a_ jx_ j\leq b_ i,\) \(i=1,2,...,m,\) \(d_ j\leq x_ j\leq u_ j,\) \(j\in J,\) where \(b_ i,\) \(c_ j\) and \(a_ j\) are positive and \(d_ j\) are nonnegative scalars, \(J=\cup^{m}_{i=1}J(i)\) and the sets J(i) are assumed to be nested: if \(i\neq k\) then either J(i) and J(k) are disjoint or one set is properly contained in the other. The proposed algorithm consists of solving a sequence of continuous knapsack problems each of which requires linear time to solve. The computational effort required by the procedure is proportional to the number of non-zero entries in the constant matrix.