Optimal set partitioning, matchings and lagrangian duality

DOI10.1002/nav.3800260401zbMath0496.90057OpenAlexW1959130699MaRDI QIDQ3960468

Nemhauser, George I., Glenn M. Weber

Publication date: 1979

Published in: Naval Research Logistics Quarterly (Search for Journal in Brave)

Full work available at URL: https://hdl.handle.net/1813/13088

zbMATH Keywords

Lagrangian relaxationsensitivity analysismatching problemcyclic coordinate methodLagrangian dualset partitioning problemsimple side constraints

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Boolean programming (90C09)

Related Items

The matching relaxation for a class of generalized set partitioning problems, Matching problems with generalized upper bound side constraints, Tighter representations for set partitioning problems, A network relaxation based enumeration algorithm for set partitioning, Graph theoretic relaxations of set covering and set partitioning problems, Use of hidden network structure in the set partitioning problem, A matching-based approach for solving a delivery/pick-up vehicle routing problem with time constraints, Dynamic matchings and quasidynamic fractional matchings. I, Using dual network bounds in algorithms for solving generalized set packing/partitioning problems, Efficient automated pallet loading, Sensitivity analysis of optimal matchings, An analysis of alternative strategies for implementing matching algorithms, Experiments with parallel branch-and-bound algorithms for the set covering problem

Cites Work

• A survey of various tactics for generating Lagrangian multipliers in the context of Lagrangian duality
• Sensitivity analysis of optimal matchings
• An Algorithm for Large Set Partitioning Problems
• Validation of subgradient optimization
• Paths, Trees, and Flowers
• Maximum matching and a polyhedron with 0,1-vertices
• The traveling-salesman problem and minimum spanning trees: Part II
• Unnamed Item
• Unnamed Item
• Unnamed Item