The generalized assignment problem: Valid inequalities and facets

DOI10.1007/BF01585725zbMath0694.90071OpenAlexW2091502736MaRDI QIDQ909579

N. E. Zubov

Publication date: 1990

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01585725

zbMATH Keywords

polytopevalid inequalitiesknapsackgeneralized assignmentfacet defining inequalities

Mathematics Subject Classification ID

Linear programming (90C05) Boolean programming (90C09) Polytopes and polyhedra (52Bxx)

Related Items

Knapsack polytopes: a survey ⋮ Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem ⋮ An approach to the asymmetric multi-depot capacitated arc routing problem ⋮ Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches ⋮ Lagrangian relaxation guided problem space search heuristics for generalized assignment problems ⋮ A Survey of the Generalized Assignment Problem and Its Applications ⋮ (1,k)-configuration facets for the generalized assignment problem ⋮ On facet-inducing inequalities for combinatorial polytopes ⋮ Generalized cover facet inequalities for the generalized assignment problem ⋮ Minimization of makespan in generalized assignment problem. ⋮ A computational study of exact knapsack separation for the generalized assignment problem ⋮ A new extended formulation of the generalized assignment problem and some associated valid inequalities ⋮ A family of inequalities for the generalized assignment polytope ⋮ Good Clusterings Have Large Volume ⋮ Some integer programs arising in the design of main frame computers

Uses Software

• LOLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• (1,k)-configuration facets for the generalized assignment problem
• Optimization of a 532-city symmetric traveling salesman problem by branch and cut
• Resource constrained scheduling as generalized bin packing
• A Cutting Plane Algorithm for the Linear Ordering Problem
• On the Uncapacitated Plant Location Problem. I: Valid Inequalities and Facets
• On the Uncapacitated Plant Location Problem. II: Facets and Lifting Theorems
• Solving 0-1 Integer Programming Problems Arising from Large Scale Planning Models
• Solving Large-Scale Zero-One Linear Programming Problems
• Lifting the facets of zero–one polytopes
• (1,k)-configurations and facets for packing problems
• A branch and bound algorithm for the generalized assignment problem
• Technical Note—A Note on Zero-One Programming
• Faces for a linear inequality in 0–1 variables
• Facet of regular 0–1 polytopes
• Facets of the knapsack polytope
• Technical Note—Facets and Strong Valid Inequalities for Integer Programs
• An Integer Generalized Transportation Model for Optimal Job Assignment in Computer Networks
• Modeling Facility Location Problems as Generalized Assignment Problems
• Facets of the Knapsack Polytope From Minimal Covers
• Valid Inequalities and Superadditivity for 0–1 Integer Programs
• An all Zero-One Algorithm for a Certain Class of Transportation Problems
• On the facial structure of set packing polyhedra
• An Algorithm for Assigning Uses to Sources in a Special Class of Transportation Problems