Mathematical Programming Formulations of the Planar Facility Location Problem

facility location;semidefinite programming;Combinatorics and Optimization

Zvereva, Margarita

University of Waterloo

关键词: facility location;    semidefinite programming;    Combinatorics and Optimization;   

Others  :  https://uwspace.uwaterloo.ca/bitstream/10012/3283/1/myThesis.pdf

瑞士|英语

来源: UWSPACE Waterloo Institutional Repository

【 摘 要 】

The facility location problem is the task of optimally placing agiven number of facilities in a certain subset of the plane.Inthis thesis, we presentvarious mathematical programmingformulations of the planar facility location problem, wherepotential facility locations are not specified. We first considermixed-integer programming formulations of the planar facilitylocations problems with squared Euclidean and rectangular distancemetrics to solve this problem to provable optimality. We alsoinvestigate a heuristic approach to solving the problem by extendingthe $K$-means clustering algorithm and formulating the facilitylocation problem as a variant of a semidefinite programming problem,leading to a relaxation algorithm. We present computational resultsfor the mixed-integer formulations, as well as compare the objectivevalues resulting from the relaxation algorithm and the modified$K$-means heuristic.In addition, we briefly discuss some of thepractical issues related to the facility location model under thecontinuous customer distribution.