A Lagrangean relaxation method for the constrained assignment problem

DOI10.1016/0305-0548(85)90011-5zbMath0608.90079OpenAlexW2054516211MaRDI QIDQ1086162

Vijay Aggarwal

Publication date: 1985

Published in: Computers \& Operations Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0305-0548(85)90011-5

zbMATH Keywords

Lagrangean relaxationtwo-stage algorithmknapsack-type constraintminimal weight assignment

Mathematics Subject Classification ID

Analysis of algorithms and problem complexity (68Q25) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Combinatorial optimization (90C27)

Related Items (15)

Algorithms for finding a \(K\)th best valued assignment ⋮ A parametric programming methodology to solve the Lagrangian dual for network problems with multiple side-constraints ⋮ A constrained matching problem ⋮ Network flow problems with one side constraint: A comparison of three solution methods ⋮ The \(k\)-cardinality assignment problem ⋮ The singly constrained assignment problem: An AP basis algorithm ⋮ Some heuristic methods for solving \(p\)-median problems with a coverage constraint ⋮ A branch-and-bound algorithm for the singly constrained assignment problem ⋮ Applications of the parametric programming procedure ⋮ An improved bounding procedure for the constrained assignment problem ⋮ Multipurpose machine scheduling with rejection and identical job processing times ⋮ Resource constrained assignment problems ⋮ Parametric programming and Lagrangian relaxation: The case of the network problem with a single side-constraint ⋮ A comprehensive simplex-like algorithm for network optimization and perturbation analysis ⋮ The singly constrained assignment problem: A Lagrangian relaxation heuristic algorithm

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The assignment problem under categorized jobs
• Shortest chain subject to side constraints
• Solving the Assignment Problem by Relaxation
• A new algorithm for the assignment problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• Minimal ratio spanning trees
• The alternating basis algorithm for assignment problems
• Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost

This page was built for publication: A Lagrangean relaxation method for the constrained assignment problem