Data aggregation for p-median problems

作者：AlBdaiwi Bader F^*; Ghosh Diptesh; Goldengorin Boris

来源：Journal of Combinatorial Optimization, 2011, 21(3): 348-363.

DOI：10.1007/s10878-009-9251-8

• p-Median problem
• Pseudo-Boolean polynomial
• Data aggregation
• Equivalent instances

In this paper, we use a pseudo-Boolean formulation of the p-median problem and using data aggregation, provide a compact representation of p-median problem instances. We provide computational results to demonstrate this compactification in benchmark instances. We then use our representation to explain why some p-median problem instances are more difficult to solve to optimality than other instances of the same size. We also derive a preprocessing rule based on our formulation, and describe equivalent p-median problem instances, which are identical sized instances which are guaranteed to have identical optimal solutions.

• 出版日期2011-4