Problem 2 - Location

2230 days ago by rklaube

This Location problem will determine the optimal location for a central unit in a ceiling sensor so that the maximum wire length to the central unit from three other units are minimized.

There are already three existing sensors, and if the ceiling were a coordinate system, the existing sensors are already located at (10,3), (5,15), and (20,25). Wires can only run along horizontal and vertical tracks in the ceiling, and a wire must run from each existing sensors to the central unit.

The linear programming model will determine the shortest length of total wire needed to connect each sensor to the central unit, and the desirable location of that unit.

The problem can be modeled as the following:

$minimize\quad max\big\{|x-5| + |y-15|, |x-10| + |y-3|, |x-20| + |y-25|\big\}$

$subject\, to\; x,y\geq0$

However, this model is nonlinear due to the absolute values and the maximizing operation. As seen in class, we can rearrange this problem into the linear form

$minimize\quad f=f^{+}-f^{-}$

$subject\, to\quad \begin{gather*}f\geq(x_1^{+}+x_1^{-}) + (y_1^{+}+y_1^{-}) \\ f\geq(x_2^{+}+x_2^{-}) + (y_2^{+}+y_2^{-}) \\ f\geq(x_3^{+}+x_3^{-}) + (y_3^{+}+y_3^{-}) \\ x-5=x_1^{+}-x_1^{-}, y-15=y_1^{+}-y_1^{-} \\ x-10=x_2^{+}-x_2^{-}, y-3=y_2^{+}-y_2^{-} \\ x-20=x_3^{+}-x_3^{-}, y-25=y_3^{+}-y_3^{-} \\ x,y,x_1^{+},x_1^{-},y_1^{+},y_1^{-},x_2^{+},x_2^{-},y_2^{+},y_2^{-},x_3^{+},x_3^{-},y_3^{+},y_3^{-},f^{+},f^{-}\geq0 \end{gather*}$

Below is the coding in SAGE to find the optimal solution.

LocationProblem=MixedIntegerLinearProgram(maximization=False, solver="GLPK") v = LocationProblem.new_variable(real=True, nonnegative=True) # Decision Variables f_p,f_n = v['f_p'], v['f_n'] #the location of the central unit x,y = v['x'], v['y'] #location of existing unit 1 x_1p, x_1n, y_1p, y_1n = v['x_1p'], v['x_1n'], v['y_1p'], v['y_1n'] #location of existing unit 2 x_2p, x_2n, y_2p, y_2n = v['x_2p'], v['x_2n'], v['y_2p'], v['y_2n'] #location of existing unit 3 x_3p, x_3n, y_3p, y_3n = v['x_3p'], v['x_3n'], v['y_3p'], v['y_3n']
#Set Objective Function (we introduce free variable f to minimize the maximum #length of wire between the existing units and the central unit LocationProblem.set_objective(f_p - f_n)
#the optimal value gives us to the total wire length between all #existing units and the central unit OptimalValue = int(round(LocationProblem.solve()))
#Compute all values of each optimal x,y as rounded integer values F_p = int(round(LocationProblem.get_values(f_p))) F_n = int(round(LocationProblem.get_values(f_n))) X = int(round(LocationProblem.get_values(x))) Y = int(round(LocationProblem.get_values(y))) X_1p = int(round(LocationProblem.get_values(x_1p))) X_1n = int(round(LocationProblem.get_values(x_1n))) Y_1p = int(round(LocationProblem.get_values(y_1p))) Y_1n = int(round(LocationProblem.get_values(y_1n))) X_2p = int(round(LocationProblem.get_values(x_2p))) X_2n = int(round(LocationProblem.get_values(x_2n))) Y_2p = int(round(LocationProblem.get_values(y_2p))) Y_2n = int(round(LocationProblem.get_values(y_2n))) X_3p = int(round(LocationProblem.get_values(x_3p))) X_3n = int(round(LocationProblem.get_values(x_3n))) Y_3p = int(round(LocationProblem.get_values(y_3p))) Y_3n = int(round(LocationProblem.get_values(y_3n))) #Display of the solution of the LP in the form we wouuld have gotten as a result of a tableau InitialObjectiveSolution = (F_p,F_n,X,Y,X_1p,X_1n,Y_1p,Y_1n,X_2p,X_2n,Y_2p,Y_2n,X_3p,X_3n,Y_3p,Y_3n) print("The optimal objective value for the LP is {}".format(InitialObjectiveSolution))
 The optimal objective value for the LP is (16, 0, 10, 19, 5, 0, 4, 0, 0, 0, 16, 0, 0, 10, 0, 6) The optimal objective value for the LP is (16, 0, 10, 19, 5, 0, 4, 0, 0, 0, 16, 0, 0, 10, 0, 6)
#The final objective solution is our problem is just the location #of the central unit, which are only the values of X and Y FinalObjectiveSolution = (X,Y) print("The optimal objective solution for (x,y) is {} with an optimal value of {}".format(FinalObjectiveSolution,OptimalValue))
 The optimal objective solution for (x,y) is (10, 19) with an optimal value of 16 The optimal objective solution for (x,y) is (10, 19) with an optimal value of 16

In conclusion, we can use our optimal $x$ and $y$ values to see how what they do to the objective function. When $x=10$ and $y=19$,

$|x-5|+|y-15|=|10-5|+|19-15|=5+4=9$

$|x-10|+|y-3|=|10-10|+|19-3|=0+16=16$

$|x-20|+|y-25|=|10-20|+|19-25|=10+6=16$

Then the minimization of the maximum operation is $16$, which is our optimal objective value.