A new Lagrangian relaxation approach to the generalized assignment problem

DOI10.1016/0377-2217(86)90328-0zbMath0617.90068MaRDI QIDQ1088908

Kurt O. Jørnsten, Mikael Näsberg

Publication date: 1986

Published in: European Journal of Operational Research (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/0377-2217(86)90328-0

zbMATH Keywords

Lagrangian relaxation; coupling constraints; auxiliary variables; generalized assignment

Mathematics Subject Classification ID

65K05: Numerical mathematical programming methods

90C10: Integer programming

90B35: Deterministic scheduling theory in operations research

Related Items

Heuristics for the multi-resource generalized assignment problem, A tabu search heuristic for the generalized assignment problem, Solving large scale generalized assignment problems. --- An aggregation/disaggregation approach, Improved Lagrangean decomposition: An application to the generalized assignment problem, An algorithm for the generalized quadratic assignment problem, A decentralized coordination mechanism for integrated production-transportation-inventory problem in the supply chain using Lagrangian relaxation, A new Lagrangian relaxation approach to the generalized assignment problem, A survey of algorithms for the generalized assignment problem, Heuristic sensitivity analysis in a combinatoric environment: An exposition and case study, Application of the scenario aggregation approach to a two-stage, stochastic, common component, inventory problem with a budget constraint, A technique for speeding up the solution of the Lagrangean dual, A set partitioning heuristic for the generalized assignment problem, Optimizing single-terminal dispatch of large volume trips to trucks, A Lagrangean heuristic for the capacitated concave minimum cost network flow problem, The bottleneck generalized assignment problem, Tabu search for the multilevel generalized assignment problem, Effective algorithm and heuristic for the generalized assignment problem., Lagrangean heuristics for location problems, Lagrangian-relaxation-based solution procedures for a multiproduct capacitated facility location problem with choice of facility type, Lagrangean/surrogate relaxation for generalized assignment problems, Maximal covering code multiplexing access telecommunication networks, Lagrangean relaxation. (With comments and rejoinder)., Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches, Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan, Designing a minimal spanning tree network subject to a budget constraint

Cites Work

• An O(n) algorithm for the linear multiple choice knapsack problem and related problems
• A new Lagrangian relaxation approach to the generalized assignment problem
• A note on the knapsack problem with special ordered sets
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• An O(n) algorithm for the multiple-choice knapsack linear program
• Generalized Lagrange Multiplier Method for Solving Problems of Optimum Allocation of Resources
• Some relationships between lagrangian and surrogate duality in integer programming
• The Linear Multiple Choice Knapsack Problem
• Surrogate duality in a branch-and-bound procedure
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• A branch and bound algorithm for the generalized assignment problem
• The Multiple-Choice Knapsack Problem
• Validation of subgradient optimization
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item