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

From MaRDI portal
Revision as of 13:08, 13 July 2023 by Importer (talk | contribs) (‎Created a new Item)
(diff) ← Older revision | Latest revision (diff) | Newer revision → (diff)
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
    0 references
    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

    Identifiers