On the boolean-quadric packing uncapacitated facility-location polytope

On the boolean-quadric packing uncapacitated facility-location polytope

0.00 Avg rating0 Votes
Article ID: iaor19991090
Country: Netherlands
Volume: 83
Issue: 1
Start Page Number: 77
End Page Number: 94
Publication Date: Oct 1998
Journal: Annals of Operations Research
Authors: , ,
Keywords: programming: integer
Abstract:

We introduce and study the boolean-quadric uncapacitated packing facility-location polytope BQPUFLP(m, n), which is a model for uncapacitated facility-location problems, with m facilities and n customers, in which there are fixed costs associated with the operation of pairs of facilities. This problem arises in the design of two-level telecommunication networks in which the embedded backbone network is full-meshed and the local networks are of star type. We study the facial structure of BQPUFLP(m, n); in particular, we demonstrate that every facet of the boolean-quadric polytope BQP(m) is a facet of BQPUFLP(m, n), we introduce some facets of BQPUFLP(m, n) that are not related to BQP(m), and we provide a complete description of the facets of BQPUFLP(m, n) when m = 3. Finally, we describe a cutting-plane algorithm based on our results, and we report on the results of computational experiments on problems with m = 50 facilities and n = 1000 customers.

Reviews

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