Problem 2 - Location

2050 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) 
       
#minimizing the maximum length between existing unit 1 to the central unit LocationProblem.add_constraint(x_1p + x_1n + y_1p + y_1n - f_p + f_n <= 0) #minimizing the maximum length between existing unit 2 to the central unit LocationProblem.add_constraint(x_2p + x_2n + y_2p + y_2n - f_p + f_n <= 0) #minimizing the maximum length between existing unit 3 to the central unit LocationProblem.add_constraint(x_3p + x_3n + y_3p + y_3n - f_p + f_n <= 0) #setting the location of existing unit 1 at (x,y)=(5,15) LocationProblem.add_constraint(x_1p - x_1n - x <= -5) LocationProblem.add_constraint(x_1p - x_1n - x >= -5) LocationProblem.add_constraint(y_1p - y_1n - y <= -15) LocationProblem.add_constraint(y_1p - y_1n - y >= -15) #setting the location of existing unit 2 at (x,y)=(10,3) LocationProblem.add_constraint(x_2p - x_2n - x <= -10) LocationProblem.add_constraint(x_2p - x_2n - x >= -10) LocationProblem.add_constraint(y_2p - y_2n - y <= -3) LocationProblem.add_constraint(y_2p - y_2n - y >= -3) #setting the location of existing unit 3 at (x,y)=(20,25) LocationProblem.add_constraint(x_3p - x_3n - x <= -20) LocationProblem.add_constraint(x_3p - x_3n - x >= -20) LocationProblem.add_constraint(y_3p - y_3n - y <= -25) LocationProblem.add_constraint(y_3p - y_3n - y >= -25) #Nonnegativity constraints (all values are constrained to the positive x-y plane) LocationProblem.add_constraint(f_p >= 0) LocationProblem.add_constraint(f_n >= 0) LocationProblem.add_constraint(x >= 0) LocationProblem.add_constraint(y >= 0) LocationProblem.add_constraint(x_1p >= 0) LocationProblem.add_constraint(x_1n >= 0) LocationProblem.add_constraint(y_1p >= 0) LocationProblem.add_constraint(y_1n >= 0) LocationProblem.add_constraint(x_2p >= 0) LocationProblem.add_constraint(x_2n >= 0) LocationProblem.add_constraint(y_2p >= 0) LocationProblem.add_constraint(y_2n >= 0) LocationProblem.add_constraint(x_3p >= 0) LocationProblem.add_constraint(x_3n >= 0) LocationProblem.add_constraint(y_3p >= 0) LocationProblem.add_constraint(y_3n >= 0) 
       
#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.