A city is shaped like the following grid:
The city would like to place mailboxes at the intersections of the streets such that no-one needs to travel more than one block to reach a mailbox. To improve the budget of the city, the mayor would like to place the smallest number of mailboxes. Where should they be placed?
Solution 1. Setting up the Problem as a LOP
First, we will say let the variable \(x_{i,j}\) be 1 if there is a mailbox at the intersection of the \(i\)th street and the \(j\)th avenue. The variable will be 0 if not. The constraints for this problem is that for each intersection, there is only 1 mailbox within one block. For example, the total number of mailboxes with the upper left and the intersection to the east and the south is at least 1 or
\begin{equation*}
x_{1,1} + x_{1,2} + x_{2,1} \geq 1
\end{equation*}
and similarly for each intersection. There will be the following fifteen constraints:
\begin{align*}
x_{1,1} + x_{1,2} + x_{2,1} \amp \geq 1 \amp x_{1,1} + x_{1,2} + x_{1,3} + x_{2,2} \amp \geq 1 \\
x_{1,2} + x_{1,3} + x_{1,4} + x_{2,3} \amp \geq 1 \amp x_{1,3} + x_{1,4} + x_{1,5} + x_{2,4} \amp \geq 1 \\
x_{1,4} + x_{1,5} + x_{2,5} \amp \geq 1 \amp x_{2,1} + x_{1,1} + x_{3,1} + x_{2,2}\amp \geq 1\\
x_{2,1} + x_{2,2} + x_{2,3} + x_{1,2} + x_{3,2} \amp \geq 1 \amp x_{2,2} + x_{2,3} + x_{2,4} + x_{1,3} + x_{3,3} \amp \geq 1 \\
x_{2,3} + x_{2,4} + x_{2,5} + x_{1,4} + x_{3,4} \amp \geq 1 \amp x_{2,4} + x_{2,5} + x_{1,5} + x_{3,5} \amp \geq 1 \\
x_{3,1} + x_{2,1} + x_{3,2} \amp \geq 1 \amp x_{3,1} + x_{3,2} + x_{3,3} + x_{2,2} \amp \geq 1\\
x_{3,2} + x_{3,3} + x_{3,4} + x_{2,3} \amp \geq 1 \amp x_{3,3} + x_{3,4} + x_{3,5} + x_{2,4} \amp \geq 1 \\
x_{3,4} + x_{3,5} + x_{2,5} \amp \geq 1
\end{align*}
And the objective function is the sum of all of the \(x_{i,j}\) is it is to be minimized.
Solution 2. Solving the LOP using JuMP
We now look at the solution to this problem using JuMP. First, we can define the model in the same way as above with
m2 = Model(HiGHS.Optimizer) and then defining the variables as a matrix with @variable(m2, x[1:3, 1:5], Bin)
The constraints are put in in the following way. We can enter them in one at a time, however, below we will extend this problem and it is nicer to define them as corners, edges and interior intersections. First the 4 corners can be added as
@constraint(m2, x[1,1]+x[1,2] + x[2,1] ≥ 1)
@constraint(m2, x[1,4]+x[1,5] + x[2,5] ≥ 1)
@constraint(m2, x[3,1]+x[2,1] + x[3,2] ≥ 1)
@constraint(m2, x[3,5]+x[3,4] + x[2,5] ≥ 1)
Next, the top and bottom edges are added with
for j=2:4
@constraint(m2, x[1,j-1]+x[1,j]+x[1,j+1]+x[2,j] ≥ 1)
@constraint(m2, x[3,j-1]+x[3,j]+x[3,j+1]+x[2,j] ≥ 1)
end
Next, the left are right edges are added with
for i=2:2
@constraint(m2, x[i,1]+x[i-1,1] + x[i+1,1] + x[i,2] ≥ 1)
@constraint(m2, x[i,5] + x[i-1,5] + x[i+1,5] + x[i,4] ≥ 1)
end
where the for loop is unecessary, but will be used below. Lastly, the interior points are
for i=2:2
for j=2:4
@constraint(m2, x[i,j] + x[i,j-1] + x[i,j+1] + x[i-1,j] + x[i+1,j] ≥ 1)
end
end
and again the i for loop is unnecessary, but will be adapted below. Lastly, the objective function can be written as
@objective(m2, Min, sum(x[i,j] for i=1:3, j=1:5))
Finally, we set the output to silent and then optimize with
set_silent(m2) optimize!(m2)
and since the output has been set to silent, there is no output but checking for a solution with
is_solved_and_feasible(m2) results in true, so we have a solution and can see it with value.(x), where the . indicates broadcasting across the matrix and the output is
3×5 Matrix{Float64}:
-0.0 -0.0 1.0 -0.0 0.0
1.0 -0.0 -0.0 -0.0 1.0
-0.0 -0.0 1.0 -0.0 0.0
and note that even though the values of
x had the constraint that they are binary (therefore integers), the matrix is a matrix of floats due to the method of solution. We can make this look a little more expected with round.(Int,value.(x)) and the result is
3×5 Matrix{Int64}:
0 0 1 0 0
1 0 0 0 1
0 0 1 0 0
and the 1s indicate where the mailboxes ought to be placed and that there only need to be 4.
