Gravity location problem locates a warehouse at $(x,y)$ to serve $N$ retailers. Retailer $n$ is already located at $(a_n,b_n).$ The objective in the gravity location problem is

$mi{n}_{x,y}{\displaystyle \underset{n=1}{\overset{N}{}}}\sqrt[\phantom{2}]{(a_n-x{)}^2+(b_n-y{)}^2}.$

When we measure the distances in terms of rectilinear distances as opposed to Euclidean distances, we arrive at the new rectilinear objective

$mi{n}_{x,y}{\displaystyle \underset{n=1}{\overset{N}{}}}|a_n-x|+|b_n-y|$

where $|*|$ denotes the absolute value. In comparison to the gravity location objective, the rectilinear objective seems more "linear". The rectilinear objective is not totally linear, because absolute value function is not; draw $f(x)=|x|$ to convince yourself. Despite this, it is possible to provide an LP formulation.

Towards an LP formulation, first let $d_n^x$ and $d_n^y$ be new decision variables denoting the rectilinear distance from the warehouse to retailer $n$ respectively in $x-$ and $y-$axis directions. Then we can write the following formulation

$mi{n}_{x,y}{\displaystyle \underset{n=1}{\overset{N}{}}}{d}_n^x+d_n^y$