(1,k)-configuration facets for the generalized assignment problem

DOI10.1007/BF01585726MaRDI QIDQ914550zbMATH OpenFDO

Authors N. E. Zubov, Elsie Sterbin Gottlieb

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/BF01585726

zbMATH Keywords

generalized assignment problemknapsack constraintspolytopevalid inequalities

Mathematics Subject Classification ID

Combinatorial properties of polytopes and polyhedra (number of faces, shortest paths, etc.) (52B05) (n)-dimensional polytopes (52B11) Special problems of linear programming (transportation, multi-index, data envelopment analysis, etc.) (90C08) Boolean programming (90C09)

Review text

In a previous paper [ibid., 31-52 (1990; Zbl 0694.90071)] the authors described various classes of valid inequalities for the generalized assignment problem. Continuing this work they derive here a family of facets for the polytope associated to this problem. The facet defining inequalities are based upon multiple knapsack constraints and are derived from (1,k)-configuration inequalities discussed in the paper mentioned above.

Recommendations

• The generalized assignment problem: Valid inequalities and facets
• A family of inequalities for the generalized assignment polytope
• Generalized cover facet inequalities for the generalized assignment problem
• A generalized assignment problem with special ordered sets: a polyhedral approach.
• Facets of the knapsack polytope derived from disjoint and overlapping index configurations

Cites work

• Bottleneck extrema
• Technical Note—A Note on Zero-One Programming
• The generalized assignment problem: Valid inequalities and facets

Cited in

(15)

• Facets of the knapsack polytope derived from disjoint and overlapping index configurations
• Unrelated machine scheduling with time-window and machine downtime constraints: An application to a naval battle-group problem
• Heuristics for the generalised assignment problem: Simulated annealing and tabu search approaches
• A new extended formulation of the generalized assignment problem and some associated valid inequalities
• Minimization of makespan in generalized assignment problem.
• Some integer programs arising in the design of main frame computers
• Generalized cover facet inequalities for the generalized assignment problem
• scientific article; zbMATH DE number 4087427 (Why is no real title available?)
• Coupled and k-Sided Placements: Generalizing Generalized Assignment
• A generalized assignment problem with special ordered sets: a polyhedral approach.
• A family of inequalities for the generalized assignment polytope
• A Survey of the Generalized Assignment Problem and Its Applications
• Knapsack polytopes: a survey
• The generalized assignment problem: Valid inequalities and facets
• A computational study of exact knapsack separation for the generalized assignment problem

This page was built for publication: (1,k)-configuration facets for the generalized assignment problem

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