A computational study of exact knapsack separation for the generalized assignment problem

DOI10.1007/s10589-008-9183-8zbMath1190.90153OpenAlexW2054299720MaRDI QIDQ967219

Pasquale Avella, Maurizio Boccia, Igor' Leonidovich Vasilyev

Publication date: 28 April 2010

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

Full work available at URL: https://doi.org/10.1007/s10589-008-9183-8

zbMATH Keywords

generalized assignment problemexact separationcutting plane algorithm

Mathematics Subject Classification ID

Combinatorial optimization (90C27) Discrete location and assignment (90B80)

Related Items

Knapsack polytopes: a survey ⋮ Branch-and-cut and hybrid local search for the multi-level capacitated minimum spanning tree problem ⋮ An implementation of exact knapsack separation ⋮ A Lagrangian heuristic for sprint planning in agile software development ⋮ A cutting plane method for knapsack polytope ⋮ Analysis of a local search heuristic for the generalized assignment problem with resource-independent task profits and identical resource capacity ⋮ A generic exact solver for vehicle routing and related problems ⋮ The equilibrium generalized assignment problem and genetic algorithm ⋮ An exact method with variable fixing for solving the generalized assignment problem ⋮ Strong bounds with cut and column generation for class-teacher timetabling ⋮ On the exact separation of mixed integer knapsack cuts ⋮ Convergence of the surrogate Lagrangian relaxation method ⋮ Computational Testing of a Separation Procedure for the Knapsack Set with a Single Continuous Variable ⋮ An exact separation algorithm for unsplittable flow capacitated network design arc-set polyhedron ⋮ Variable-fixing then subgradient optimization guided very large scale neighborhood search for the generalized assignment problem ⋮ On the exact separation of cover inequalities of maximum-depth

Uses Software

• OR-Library
• Knapsack
• Tabu search

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• The generalized assignment problem: Valid inequalities and facets
• (1,k)-configuration facets for the generalized assignment problem
• A genetic algorithm for the generalised assignment problem
• Tabu search for the multilevel generalized assignment problem
• Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches
• A convex-analysis perspective on disjunctive cuts
• 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
• Technical Note—Facets and Strong Valid Inequalities for Integer Programs
• Generating Fenchel Cutting Planes for Knapsack Polyhedra
• Fenchel Cutting Planes for Integer Programs
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• A Minimal Algorithm for the 0-1 Knapsack Problem
• A branch‐and‐price algorithm for the capacitated p‐median problem
• On the Convergence of Fenchel Cutting Planes in Mixed-Integer Programming
• A variable depth search algorithm with branching search for the generalized assignment problem
• On the facial structure of set packing polyhedra
• On the Exact Separation of Mixed Integer Knapsack Cuts
• A family of inequalities for the generalized assignment polytope