Improved Lagrangean decomposition: An application to the generalized assignment problem (Q922948)

The authors are concerned with specially structured pure integer programming problems: \[ (SP)\quad z=\min cx,\quad Ax\leq b,\quad Bx\leq d,\quad x\in X\subset {\mathbb{Z}}^ n, \] where for either of the two substructures special purpose methods are available. To solve this type of integer programming problems with moderate effort, they combine a lower bound improving technique with the variable splitting (copying) technique due to \textit{M. Guignard} and \textit{S. Kim} [Math. Program. 39, 215-228 (1987; Zbl 0638.90074)]: If \(d_ k\) is a known lower bound for z and \(X_ k:=\{x\in X|\) \(cx\geq d_ k\}\) then SP can be reformulated by \[ (SPR_ k)\quad z=\min (\alpha cx+\beta cy),\quad Ax\leq b,\quad By\leq d, \] and \(x=y\), \(x\in X_ k\), \(y\in Y\) with any \(Y\supset X_ k\). This formulation is valid if \(\alpha +\beta =1.\) By relaxing the equality constraint \(x=y\) and using the Lagrangean dual of \(SPR_ k\) one ``easily'' gets a monotone increasing sequence \((d_ k)\) of lower bounds, which dominates the sequence of lower bounds induced by ordinary Lagrangean methods. This procedure can be adapted very well to solve generalized assignment problems. A series of promising experimental results completes the paper.