ISSN:
1572-9338
Quelle:
Springer Online Journal Archives 1860-2000
Thema:
Mathematik
,
Wirtschaftswissenschaften
Notizen:
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.
Materialart:
Digitale Medien
URL:
http://dx.doi.org/10.1023/A:1018972400378
Permalink