A Lagrangean relaxation method for the constrained assignment problem
This paper addresses the problem of finding a minimal weight assignment subject to a knapsack-type constraint. It develops a two-stage algorithm based on the Lagrangean relaxation formulation of this problem. The first stage obtains the optimal Lagrange multiplier in a polynominal effort by generating the efficient frontier in a bicriteria framework. The second stage uses this information very effectively to zero in on the optimal solution in a relatively lower depth of search in the ordered-generation- of-assignments framework. The algorithm is supported by a numerical example and its advantages over other schemes are shown.
- The singly constrained assignment problem: A Lagrangian relaxation heuristic algorithm
- A lagrangean relaxation algorithm for the constrained matrix problem
- An improved bounding procedure for the constrained assignment problem
- A truncated exponential algorithm for the lightly constrained assignment problem
- Lagrangean/surrogate relaxation for generalized assignment problems
- A new algorithm for the assignment problem
- scientific article; zbMATH DE number 3558962 (Why is no real title available?)
- scientific article; zbMATH DE number 3793772 (Why is no real title available?)
- scientific article; zbMATH DE number 3365044 (Why is no real title available?)
- Letter to the Editor—An Algorithm for Ranking all the Assignments in Order of Increasing Cost
- Minimal ratio spanning trees
- Shortest chain subject to side constraints
- Solving the Assignment Problem by Relaxation
- The alternating basis algorithm for assignment problems
- The assignment problem under categorized jobs
- The Lagrangian Relaxation Method for Solving Integer Programming Problems
- Network flow problems with one side constraint: A comparison of three solution methods
- Solution of a tinned iron purchasing problem by Lagrangean relaxation
- Applications of the parametric programming procedure
- An improved bounding procedure for the constrained assignment problem
- Resource constrained assignment problems
- The singly constrained assignment problem: A Lagrangian relaxation heuristic algorithm
- Algorithms for finding a \(K\)th best valued assignment
- The \(k\)-cardinality assignment problem
- Critical objective function values in linear sum assignment problems
- Lagrangian relaxation and constraint generation for allocation and advanced scheduling
- Lagrangean/surrogate relaxation for generalized assignment problems
- Parametric programming and Lagrangian relaxation: The case of the network problem with a single side-constraint
- Constraint programming based Lagrangian relaxation for the automatic recording problem
- A constrained matching problem
- The singly constrained assignment problem: An AP basis algorithm
- Some heuristic methods for solving p-median problems with a coverage constraint
- Multipurpose machine scheduling with rejection and identical job processing times
- Adaptive CP-based Lagrangian relaxation for TSP solving
- A parametric programming methodology to solve the Lagrangian dual for network problems with multiple side-constraints
- A branch-and-bound algorithm for the singly constrained assignment problem
- scientific article; zbMATH DE number 4199945 (Why is no real title available?)
- A lagrangean relaxation algorithm for the constrained matrix problem
- A Lagrangian Relaxation Approach To The Classroom Assignment Problem*
- scientific article; zbMATH DE number 30946 (Why is no real title available?)
- A Lagrange relaxation method for solving weapon-target assignment problem
- scientific article; zbMATH DE number 1487886 (Why is no real title available?)
- A comprehensive simplex-like algorithm for network optimization and perturbation analysis
- A Lagrangean Relaxation Approach for a Turbine Design Quadratic Assignment Problem
- Relajacion lagrangeana para el problema de particionamiento de áreas geográficas
- A facet generation and relaxation technique applied to an assignment problem with side constraints
This page was built for publication: A Lagrangean relaxation method for the constrained assignment problem
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1086162)
