Integer-friendly formulations for the r-separation problem

Integer-friendly formulations for the r-separation problem

0.00 Avg rating0 Votes
Article ID: iaor1999403
Country: Netherlands
Volume: 92
Issue: 2
Start Page Number: 342
End Page Number: 351
Publication Date: Jul 1996
Journal: European Journal of Operational Research
Authors: , ,
Keywords: location
Abstract:

In this paper, we consider different formulations for the r-separation problem, where the objective is to choose as many points as possible from a given set of points subject to the constraint that no two selected points can be closer than r units to one another. Our goal is to devise a mathematical programming formulation with an LP-relaxation which yields integer solutions with great frequency. We consider six different formulations of the r-separation problem. We show that the LP-relaxations of the most obvious formulations will yield fractional results in all instances of the problem if an optimal solution contains fewer than half of the given points. To build computationally effective formulations for the r-separation problem, we write dense constraints with unit right-hand-sides. The LP formulation that performs the best in our computational tests almost always finds 0–1 solutions to the problem.

Reviews

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