Optimal set partitioning, matchings and lagrangian duality

George L. Nemhauser and Glenn M. Weber

Naval Research Logistics Quarterly, 1979, vol. 26, issue 4, 553-563

Abstract: We formulate the set partitioning problem as a matching problem with simple side constraints. As a result we obtain a Lagrangian relaxation of the set partitioning problem in which the primal problem is a matching problem. To solve the Lagrangian dual we must solve a sequence of matching problems each with different edge‐weights. We use the cyclic coordinate method to iterate the multipliers, which implies that successive matching problems differ in only two edge‐weights. This enables us to use sensitivity analysis to modify one optimal matching to obtain the next one. We give theoretical and empirical comparisons of these dual bounds with the conventional linear programming ones.

Date: 1979
References: Add references at CitEc
Citations:

Downloads: (external link)
https://doi.org/10.1002/nav.3800260401

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:wly:navlog:v:26:y:1979:i:4:p:553-563

Access Statistics for this article

More articles in Naval Research Logistics Quarterly from John Wiley & Sons
Bibliographic data for series maintained by Wiley Content Delivery ().