Optimal Set Partitioning, Matchings and Lagrangian Duality

dc.contributor.author	Nemhauser, George
dc.contributor.author	Weber, Glenn
dc.date.accessioned	2009-07-02T17:53:20Z
dc.date.available	2009-07-02T17:53:20Z
dc.date.issued	2009-07-02T17:53:20Z
dc.description.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 bonds with the conventional linear programming ones.	en_US
dc.description.sponsorship	National Science Foundation Grant ENG75-00568	en_US
dc.identifier.uri	https://hdl.handle.net/1813/13088
dc.language.iso	en_US	en_US
dc.relation.ispartofseries	399	en_US
dc.subject	Lagrangian Duality	en_US
dc.subject	Optimal Set Partitioning, Matchings	en_US
dc.title	Optimal Set Partitioning, Matchings and Lagrangian Duality	en_US
dc.type	technical report	en_US

eCommons