Creative modeling: Variable and constraint duplicationin primal - dual decomposition methods

Kaj Holmberg

Annals of Operations Research, 1998, vol. 82, issue 0, 355-390

Abstract: In this paper, we discuss modeling with the specific purpose of solving the models withdifferent decomposition techniques. We first briefly describe the basic primal, dual andprimal - dual decomposition techniques, where a master problem is constructed by veryspecific modeling. The main part of the paper contains a discussion of variables and constraintduplication techniques, used to create a structure which can be used in decompositionmethods, i.e. enabling decomposition by modeling. We mainly treat linear mixed integerprogramming problems with several sets of variables andyor constraints. We propose severalways of incorporating variable andyor constraint duplication techniques in cross decomposition.In some cases, the constraints corresponding to the Lagrange multipliers that areneeded as input to the Lagrangian relaxation are not present in the primal subproblem.Despite this, we show how to determine these multipliers optimally. In some combinations,the input to a subproblem is not unique, and we discuss how to handle this non-uniquenessin an advantageous way. An application to the capacitated facility location problem isdescribed. Copyright Kluwer Academic Publishers 1998

Date: 1998
References: Add references at CitEc
Citations:

Downloads: (external link)
http://hdl.handle.net/10.1023/A:1018927123151 (text/html)
Access to full text is restricted to subscribers.

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:spr:annopr:v:82:y:1998:i:0:p:355-390:10.1023/a:1018927123151

Ordering information: This journal article can be ordered from
http://www.springer.com/journal/10479

DOI: 10.1023/A:1018927123151

Access Statistics for this article

Annals of Operations Research is currently edited by Endre Boros

More articles in Annals of Operations Research from Springer
Bibliographic data for series maintained by Sonal Shukla () and Springer Nature Abstracting and Indexing ().