Facility Location

Consider the problem of locating a warehouse to serve a number of service locations. The design variable is the location of the warehouse, $x in mathbf{R}^2$ , while the service locations are given by the vector $x_i in mathbf{R}^2$ , i=1,ldots,N .

Minimizing the maximum distance

One possible objective function for this problem involves the maximum distance from the warehouse to any location. This is the problem

$min_x : max_{1 le i le N} |x-x_i|_2,$

which can be cast as the SOCP

$min_{x,t} : t ~:~ t ge |x-x_i|_2 , ;; i=1,ldots,m.$

This can be coded up with the CVX applet:

CVX syntax
% pts is a 2 x n matrix of n points
cvx_begin
    variable x(2,1);
    variable t(n,1);
    minimize( max(t) )
    subject to
        for i = 1:n,
            t(i) >= norm(x-pts(:,i));
        end
cvx_end

Minimizing the average distance

Often, the average distance is a good measure of the transportation costs involved. This leads to the problem

$min_x : frac{1}{N} sum_{i=1}^N |x-x_i|_2,$

which can be cast as the SOCP

$min_{x,y} : frac{1}{N} sum_{i=1}^N y_i ~:~ y_i ge |x-x_i|_2 , ;; i=1,ldots,m.$

This can be coded up with the CVX applet:

CVX syntax
% pts is a 2 x n matrix of n points
cvx_begin
    variable x(2,1);
    variable t(n,1);
    minimize( max(t) )
    subject to
        for i = 1:n,
            t(i) >= norm(x-pts(:,i));
        end
cvx_end