Valid inequalities and facets of the capacitated plant location problem

Valid inequalities and facets of the capacitated plant location problem

0.00 Avg rating0 Votes
Article ID: iaor1989709
Country: Netherlands
Volume: 44
Issue: 3
Start Page Number: 271
End Page Number: 291
Publication Date: Nov 1989
Journal: Mathematical Programming (Series A)
Authors: ,
Keywords: location
Abstract:

Recently, several successful applications of strong cutting plane methods to combinatorial optimization problems have renewed interest in cutting plane methods, and polyhedral characterizations, of integer programming problems. In this paper, the authors investigate the polyhedral structure of the capacitated plant location problem. The present purpose is to identify facets and valid inequalities for a wide range of capacitated fixed charge problems that contain this prototype problem as a substructure. The first part of the paper introduces a family of facets for a version of the capacitated plant location problem with a constant capacity for all plants. These facet inequalities depend on the capacity and thus differ fundamentally from the valid inequalities for the uncapacited version of the problem. The authors also introduce a second formulation for a model with indivisible customer demand and show that it is equivalent to a vertex packing problem on a derived graph. They identify facets and valid inequalities for this version of the problem by applying known results for the vertex packing polytope.

Reviews

Required fields are marked *. Your email address will not be published.