A Family of Inequalities for the Generalized Assignment Polytope

Ismael R. de Farias (defariasbuffalo.edu)
George L. Nemhauser (george.nemhauserisye.gatech.edu)

Abstract: We present a family of inequalities that are valid for the generalized assignment polytope. Although the inequalities are not facet-defining in general, they define facets of a polytope of a relaxation. We report computational results on the use of the inequalities in a branch-and-cut scheme that demonstrate their effectiveness.

Keywords: integer programming, generalized assignment, branch-and-cut

Category 1: Integer Programming (0-1 Programming )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Citation: Department of Industrial Engineering, State University of New York at Buffalo, under review

Download: [Postscript]

Entry Submitted: 12/12/2000
Entry Accepted: 12/13/2000
Entry Last Modified: 12/12/2000

Modify/Update this entry