An exact method with variable fixing for solving the generalized assignment problem

DOI10.1007/s10589-011-9432-0zbMath1259.90062OpenAlexW2061568192MaRDI QIDQ694523

Jacques A. Ferland, Marius Posta, Philippe Yves Paul Michelon

Publication date: 12 December 2012

Published in: Computational Optimization and Applications (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10589-011-9432-0

zbMATH Keywords

Lagrangian relaxationdynamic programminggeneralized assignment problembranch and bound

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Discrete location and assignment (90B80)

Related Items

An implementation of exact knapsack separation, Exact makespan minimization of unrelated parallel machines, 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, An integer programming column generation principle for heuristic search methods, A generic exact solver for vehicle routing and related problems, Primal Heuristics for Branch and Price: The Assets of Diving Methods, Improved Lagrangian bounds and heuristics for the generalized assignment problem, Convergence of the surrogate Lagrangian relaxation method, Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem

Uses Software

• Knapsack

Cites Work

• Unnamed Item
• Integer-programming software systems
• A computational study of exact knapsack separation for the generalized assignment problem
• Effective algorithm and heuristic for the generalized assignment problem.
• Solving semidefinite quadratic problems within nonsmooth optimization algorithms
• 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
• A branch and bound algorithm for the generalized assignment problem
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• A Minimal Algorithm for the 0-1 Knapsack Problem
• A tabu search heuristic for the generalized assignment problem