A Family of Facets for the p-Median Polytope

Ismael R. de Farias (defariasbuffalo.edu)

Abstract: We present a nontrivial family of facet-defining inequalities for the p-median polytope. We incorporate the inequalities in a branch-and-cut scheme, and we report computational results that demonstrate their effectiveness.

Keywords: mixed-integer programming, p-median, facility location, cardinality constrained programming, branch-and-cut

Category 1: Integer Programming ((Mixed) Integer Linear Programming )

Category 2: Combinatorial Optimization (Branch and Cut Algorithms )

Category 3: Applications -- OR and Management Sciences (Transportation )

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

Download: [Postscript]

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

Modify/Update this entry