Layering strategies for creating exploitable structure in linear and integer programs (Q1117840): Difference between revisions

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.