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

DOI10.1016/J.DAM.2019.08.015MaRDI QIDQ2009013zbMATH OpenOpenAlexFDO

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

zbMATH Keywords

integer programmingvalid inequalitiesgeneralized assignmentinteger polytope

Mathematics Subject Classification ID

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

Recommendations

• scientific article; zbMATH DE number 4199971
• 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

Cites work

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

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)