A path relinking approach with ejection chains for the generalized assignment problem

DOI10.1016/J.EJOR.2004.08.015zbMath1079.90119OpenAlexW2155078398MaRDI QIDQ2570155

Toshihide Ibaraki, Fred Glover, Mutsunori Yagiura

Publication date: 26 October 2005

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

Full work available at URL: https://doi.org/10.1016/j.ejor.2004.08.015

zbMATH Keywords

MetaheuristicsPath relinkingScatter searchGeneralized assignment problemEjection chains

Mathematics Subject Classification ID

Approximation methods and heuristics in mathematical programming (90C59) Combinatorial optimization (90C27) Combinatorial probability (60C05) Discrete location and assignment (90B80)

Related Items (42)

On solving the Lagrangian dual of integer programs via an incremental approach ⋮ A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem ⋮ An optimization-based heuristic for the machine reassignment problem ⋮ Fast machine reassignment ⋮ Multi-neighborhood local search optimization for machine reassignment problem ⋮ Quantum bridge analytics. II: QUBO-plus, network optimization and combinatorial chaining for asset exchange ⋮ A hybrid meta-heuristic for the batching problem in just-in-time flow shops ⋮ An LP-based heuristic procedure for the generalized assignment problem with special ordered sets ⋮ Lagrangian relaxation guided problem space search heuristics for generalized assignment problems ⋮ A note of reduced dimension optimization algorithm of assignment problem ⋮ A three-phase matheuristic algorithm for the multi-day task assignment problem ⋮ Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity ⋮ Dual-neighborhood iterated local search for routing and wavelength assignment ⋮ A game‐theoretic approach for the location of terror response facilities with both disruption risk and hidden information ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ The equilibrium generalized assignment problem and genetic algorithm ⋮ Unnamed Item ⋮ Automation and Combination of Linear-Programming Based Stabilization Techniques in Column Generation ⋮ Primal Heuristics for Branch and Price: The Assets of Diving Methods ⋮ Advanced Tabu Search Algorithms for Bipartite Boolean Quadratic Programs Guided by Strategic Oscillation and Path Relinking ⋮ An effective VNS for the capacitated \(p\)-median problem ⋮ Tabu search tutorial. A graph drawing application ⋮ Probabilistic tabu search for the cross-docking assignment problem ⋮ Solving the wire-harness design problem at a European car manufacturer ⋮ Repulsive assignment problem ⋮ An exact method with variable fixing for solving the generalized assignment problem ⋮ A computational study of exact knapsack separation for the generalized assignment problem ⋮ Convergence of the surrogate Lagrangian relaxation method ⋮ Bees algorithm for generalized assignment problem ⋮ Quantum bridge analytics II: QUBO-plus, network optimization and combinatorial chaining for asset exchange ⋮ Very large-scale variable neighborhood search for the generalized assignment problem ⋮ A hybrid tabu search/branch \& bound approach to solving the generalized assignment problem ⋮ The generalized minimum spanning tree problem: an overview of formulations, solution procedures and latest advances ⋮ Competence-based assignment of tasks to workers in factories with demand-driven manufacturing ⋮ Optimization-Based Very Large-Scale Neighborhood Search for Generalized Assignment Problems with Location/Allocation Considerations ⋮ Local search intensified: very large-scale variable neighborhood search for the multi-resource generalized assignment problem ⋮ A branching algorithm to solve binary problem in uncertain environment: an application in machine allocation problem ⋮ Scatter search --- wellsprings and challenges ⋮ A path relinking approach with ejection chains for the generalized assignment problem ⋮ Hybrid scatter search and path relinking for the capacitated \(p\)-median problem ⋮ An ejection chain approach for the generalized assignment problem ⋮ Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem

Uses Software

• Scatter Search
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Tabu search for nonlinear and parametric optimization (with links to genetic algorithms)
• A robust heuristic for the generalized assignment problem
• A genetic algorithm for the generalised assignment problem
• Tabu search for the multilevel generalized assignment problem
• A tabu search approach to the constraint satisfaction problem as a general problem solver
• Scatter search. Methodology and implementation in C. With CD-ROM.
• Ejection chains, reference structures and alternating path methods for traveling salesman problems
• A path relinking approach with ejection chains for the generalized assignment problem
• Solving the Generalized Assignment Problem: An Optimizing and Heuristic Approach
• An Ejection Chain Approach for the Generalized Assignment Problem
• The Lagrangian Relaxation Method for Solving Integer Programming Problems
• P-Complete Approximation Problems
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• A variable depth search algorithm with branching search for the generalized assignment problem
• The traveling-salesman problem and minimum spanning trees: Part II
• An Effective Lagrangian Heuristic For The Generalized Assignment Problem
• A tabu search heuristic for the generalized assignment problem

This page was built for publication: A path relinking approach with ejection chains for the generalized assignment problem