A unified approach for price directive decomposition procedures in integer programming (Q1109677)

The subject of this paper is a generalization of the Dantzig-Wolfe decomposition principle to integer programming. The following decomposed optimization problem is considered: \[ \max \quad cx,\quad s.t.\quad A_ 1x\leq b_ 1,\quad A_ 2x\leq b_ 2,\quad x\in Z\quad n_+ \] where \(c\in {\mathbb{Z}}^ n,\) \(A_ 1\in {\mathbb{Z}}^{m_ 1\times n}\), \(A_ 2\in {\mathbb{Z}}^{m_ 2\times n}\), \(b_ 1\in {\mathbb{Z}}^{m_ 1}\) and \(b_ 2\in {\mathbb{Z}}^{m_ 2}\). Typically, \(A_ 2\) has a blockangular structure consisting of several blocks, where each block corresponds to a subunit and thus defines the local constraints for each subunit. The decomposition procedure may be built on one of the two basic solution methods in integer programming: branch and bound (this case is treated in Section 3 of the paper) or cutting plane (treated in Section 5). The necessary background for the application of cutting plane is given in Section 4 which deals with the superadditive duality for mixed integer programming. The following basic result of the paper is derived in Section 6: The subproblems of both solution methods are of the same kind with a convex, polyhedral objective function to be maximized over a polyhedral constraint set. In Section 7 the important case with blockangular constraints is described and in the last section a small numerical example for illustration is solved.