Relaxation heuristics for a generalized assignment problem

DOI10.1016/0377-2217(95)00041-0zbMath0924.90119OpenAlexW2038841623MaRDI QIDQ1278258

Luiz Antonio Nogueira Lorena, Marcelo Gonçalves Narciso

Publication date: 10 November 1999

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

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

zbMATH Keywords

heuristicsgeneralized assignment problemLagrangian and surrogate relaxation

Mathematics Subject Classification ID

Combinatorial optimization (90C27)

Related Items (22)

A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem ⋮ Elitist genetic algorithm for assignment problem with imprecise goal ⋮ Lagrangian heuristic for a class of the generalized assignment problems ⋮ Matheuristics: survey and synthesis ⋮ Two stage decision making approach for Sensor Mission Assignment Problem ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ Logic cuts for multilevel generalized assignment problems. ⋮ A column generation approach to capacitated \(p\)-median problems ⋮ A dual bounding scheme for a territory design problem ⋮ A genetic algorithm for the project assignment problem ⋮ A tabu search heuristic for the generalized assignment problem ⋮ A Lagrangian bound for many-to-many assignment problems ⋮ Studying properties of Lagrangian bounds for many-to-many assignment problems ⋮ A dynamic tabu search for large-scale generalized assignment problems ⋮ Very large-scale variable neighborhood search for the generalized assignment problem ⋮ Optimal ABC inventory classification using interval programming ⋮ Optimizing cane supply decisions within a sugar mill region ⋮ Lagrangean/surrogate relaxation for generalized assignment problems ⋮ Local search intensified: very large-scale variable neighborhood search for the multi-resource generalized assignment problem ⋮ A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem ⋮ An ejection chain approach for the generalized assignment problem ⋮ Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems

Uses Software

• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• A fast algorithm for the linear multiple-choice knapsack problem
• Exact methods for the knapsack problem and its generalizations
• A survey of algorithms for the generalized assignment problem
• A surrogate heuristic for set covering problems
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• An O(n) algorithm for the multiple-choice knapsack linear program
• Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem
• Some relationships between lagrangian and surrogate duality in integer programming
• Note—On the Maximal Covering Location Problem and the Generalized Assignment Problem
• Calculating surrogate constraints
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• An Integer Generalized Transportation Model for Optimal Job Assignment in Computer Networks
• An all Zero-One Algorithm for a Certain Class of Transportation Problems
• Surrogate Constraints
• The traveling-salesman problem and minimum spanning trees: Part II

This page was built for publication: Relaxation heuristics for a generalized assignment problem