Article ID: | iaor20081162 |
Country: | United Kingdom |
Volume: | 17 |
Issue: | 4 |
Start Page Number: | 397 |
End Page Number: | 412 |
Publication Date: | Oct 2006 |
Journal: | IMA Journal of Management Mathematics (Print) |
Authors: | Drezner Zvi, Salhi S., Welch S.B. |
Keywords: | programming: branch and bound |
Two branch-and-bound algorithms are proposed to optimally solve the maximin formulation for locating p facilities in the plane. Tight upper and lower bounds are constructed and suitable methods of guiding the search developed. To enhance the method, efficient measures for identifying specific squares for subdivision are suggested. The proposed algorithms are evaluated on a set of randomly generated problems of up to five facilities and 120 nodes.