Layering strategies for creating exploitable structure in linear and integer programs (Q1117840)

The authors describe the strategy of subdividing linear or integer programs with special structures (like network structure) into layers by splitting variables. Starting from (P) min cx\(+dy\) subject to \(Cx+Dy\leq b\), \(x\in X\), \(y\in Y\) the rows of C, D and b are partitioned into r mutually distinct classes and the equivalent problem \((P_ h)\) min cx\(+dy^ h\) subject to \(C^ kx+D^ ky^ k\leq b^ k\) for \(k=1,...,r\), \(x\in X\), \(y^ k\in Y\) and \(y^ k=y^ h\) for all \(k=h\) is obtained. Taking the equations \(y^ k=y^ h\) for \(k\neq h\) into the objective function one can get a relaxation R(w) of the form \[ \min cx+\sum^{r}_{k=1}w^ ky^ k\quad subject\quad to\quad C^ kx+D^ ky\leq b^ k \] for \(k=1,...,r\), \(x\in X_ 0(\supseteq X)\), \(y^ k\in Y_ 0(\supseteq Y)\) for \(k=1,...,r\) where \(w=(w^ 1,w^ 2,...,w^ r)\) fulfills \(\sum w^ k=d\). To strenthen R(w) simple parametrized bounds on the components of each \(y^ k\) can be included: \(L\leq y^ k\leq U\) for all \(k=1,2,...,r.\) The authors discuss a subgradient approach for solving this modified relaxation where gradually L and U are changed forcing all vectors \(y^ k\) to become equal. This approach seems also suited for parallel processing. Computational results on a class of personnel planning problems are reported.