A unified approach for price directive decomposition procedures in integer programming (Q1109677): Difference between revisions
From MaRDI portal
Latest revision as of 08:22, 30 July 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | A unified approach for price directive decomposition procedures in integer programming |
scientific article |
Statements
A unified approach for price directive decomposition procedures in integer programming (English)
0 references
1988
0 references
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.
0 references
Dantzig-Wolfe decomposition principle
0 references
blockangular structure
0 references
branch and bound
0 references
cutting plane
0 references
superadditive duality
0 references
polyhedral constraint set
0 references