Relaxation heuristics for a generalized assignment problem

DOI10.1016/0377-2217(95)00041-0zbMath0924.90119MaRDI 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

heuristics; generalized assignment problem; Lagrangian and surrogate relaxation

Mathematics Subject Classification ID

90C27: Combinatorial optimization

Related Items

A tabu search heuristic for the generalized assignment problem, A dynamic tabu search for large-scale generalized assignment problems, Elitist genetic algorithm for assignment problem with imprecise goal, A Lagrangian bound for many-to-many assignment problems, Local search intensified: very large-scale variable neighborhood search for the multi-resource generalized assignment problem, Logic cuts for multilevel generalized assignment problems., A column generation approach to capacitated \(p\)-median problems, A comparison of Lagrangean and surrogate relaxations for the maximal covering location problem, Using logical surrogate information in Lagrangean relaxation: An application to symmetric traveling salesman problems, Optimizing cane supply decisions within a sugar mill region, Lagrangean/surrogate relaxation for generalized assignment problems, A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem, A genetic algorithm for the project assignment problem, An ejection chain approach for the generalized assignment problem, Very large-scale variable neighborhood search for the generalized assignment problem

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