A new Lagrangian relaxation approach to the generalized assignment problem

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

Mikael Näsberg, Kurt O. Jørnsten

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 relaxationcoupling constraintsauxiliary variablesgeneralized assignment

Mathematics Subject Classification ID

Numerical mathematical programming methods (65K05) Integer programming (90C10) Deterministic scheduling theory in operations research (90B35)

Related Items (31)

Maximal covering code multiplexing access telecommunication networks ⋮ Lagrangean relaxation. (With comments and rejoinder). ⋮ Optimizing single-terminal dispatch of large volume trips to trucks ⋮ A new Lagrangian relaxation approach to the generalized assignment problem ⋮ The fixed charge transportation problem: a strong formulation based on Lagrangian decomposition and column generation ⋮ A Lagrangean heuristic for the capacitated concave minimum cost network flow problem ⋮ Heuristics for the multi-resource generalized assignment problem ⋮ Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches ⋮ The bottleneck generalized assignment problem ⋮ Tabu search for the multilevel generalized assignment problem ⋮ Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity ⋮ Matheuristics: survey and synthesis ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ A Lagrangian relaxation approach to an electricity system investment model with a high temporal resolution ⋮ Effective algorithm and heuristic for the generalized assignment problem. ⋮ Improved Lagrangean decomposition: An application to the generalized assignment problem ⋮ Designing a minimal spanning tree network subject to a budget constraint ⋮ Scheduling jobs with release dates and tails on two unrelated parallel machines to minimize the makespan ⋮ Solving large scale generalized assignment problems. --- An aggregation/disaggregation approach ⋮ A survey of algorithms for the generalized assignment problem ⋮ A stochastic production planning problem with nonlinear cost ⋮ A tabu search heuristic for 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 ⋮ 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 ⋮ 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

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• 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

This page was built for publication: A new Lagrangian relaxation approach to the generalized assignment problem