Linearize Objective Function

Dear All,

Given variables x_i, x_j, y_i, y_j, z_i, z_j (R^3 points) do you know
of

1. a good linear or piece-wise linear approximation for the
Euclidean metric \sqrt((x_i - x_j)^2 + (y_i - y_j)^2 + (z_i -
z_j)^2)?

2. any error bounds when the rectilinear metric |x_i - x_j|
+ |y_i - y_j| + |z_i - z_j| is used to approximate the Euclidean?

My Problem is about antenna allocation in R^3, where x_i, y_i and z_i
are given
points (location of customers) and x_j, y_j and z_j are the antenna
position
that must to be calculated. The problem is stated as:

n: number of customers
m: number of antennas
xij: binary variable that indicates which customer is server by which
antenna

Minimize sum sqrt((x_i - x_j)^2 + (y_i - y_j)^2 + (z_i - z_j)^2)xij
subject to
sum xij=1, i=1,,n and j=1,,m
xij={0,1} binary variables

So, I also would like to know how I could solve this problem using a
MILP solver
as CPLEX, using something like linearizing the objective function.

Thanks,
Marcelo.

Marcelo Lisboa wrote:

>
2. any error bounds when the rectilinear metric |x_i - x_j|
+ |y_i - y_j| + |z_i - z_j| is used to approximate the Euclidean?
>

Let |x|_e and |x|_r denote Euclidean and rectilinear norms of x
respectively; then

|x|_e <= |x|_r and |x|_r <= sqrt(d)*|x|_e

where d is the dimension of the space (d=3 in your case). These are the
tightest general bounds. You can get them by maximizing and minimizing
|x|_e over the unit "sphere" {x : |x|_r = 1} in the rectilinear norm.

/Paul