A new extended formulation of the generalized assignment problem and some associated valid inequalities

DOI10.1016/J.DAM.2019.08.015zbMATH Open1433.90082OpenAlexW2973063335MaRDI QIDQ2009013FDOQ2009013

Authors: Sam Ransbotham, Ishwar Murthy 

Publication date: 27 November 2019

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2019.08.015

Recommendations

• scientific article
• A new Lagrangian relaxation approach to the generalized assignment problem
• An efficient approximation for the generalized assignment problem
• A Survey of the Generalized Assignment Problem and Its Applications
• An approximation algorithm for the generalized assignment problem
• Solution of a class of generalized assignment problem
• An exact method with variable fixing for solving the generalized assignment problem
• An efficient algorithm for a class of generalized assignment problem
• A family of inequalities for the generalized assignment polytope

zbMATH Keywords

integer programmingvalid inequalitiesgeneralized assignmentinteger polytope

Mathematics Subject Classification ID

Linear programming (90C05) Discrete location and assignment (90B80)

Cites Work

• A survey of algorithms for the generalized assignment problem
• The generalized assignment problem: Valid inequalities and facets
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• A branch and bound algorithm for the generalized assignment problem
• A Branch-and-Price Algorithm for the Generalized Assignment Problem
• A Multiplier Adjustment Method for the Generalized Assignment Problem
• Network flow models for designing diameter‐constrained minimum‐spanning and Steiner trees
• A 2n Constraint Formulation for the Capacitated Minimal Spanning Tree Problem
• 0-1 reformulations of the multicommodity capacitated network design problem
• A very large-scale neighborhood search algorithm for the multi-resource generalized assignment problem
• Robust branch-cut-and-price for the capacitated minimum spanning tree problem over a large extended formulation
• A set partitioning heuristic for the generalized assignment problem
• A genetic algorithm for the generalised assignment problem
• Solving the generalized assignment problem: an optimizing and heuristic approach
• (1,k)-configurations and facets for packing problems
• Technical Note—An Improved Dual Based Algorithm for the Generalized Assignment Problem
• (1,k)-configuration facets for the generalized assignment problem
• Solving the generalised assignment problem using polyhedral results

Cited In (2)

• The generalized assignment problem: Valid inequalities and facets
• A three-phase matheuristic algorithm for the multi-day task assignment problem

This page was built for publication: A new extended formulation of the generalized assignment problem and some associated valid inequalities

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2009013)