Consider the following integer$-$linear program which is used to decide which warehouses to open

from a set of n potential warehouses, and how to assign m retail stores to the opened warehouses

$($for receiving supplies$).$ Note that each retail store must be assigned to exactly one warehouse.

Each warehouse can serve all the retail stores. Associated with each assignment is a transportation

cost cij $,$ i $=1,...,$ n$,$ j $=1,...,$ m$,$ and associated with opening each warehouse is a fixed cost

fi

$,$ i $=1,...,$ n$.$ We seek to minimize the total cost. This is known as a location$-$allocation model.

Let

xij $=$

$($

$1,$ if store j is assigned to warehouse i$,$

$0,$ o$/$w$,$

i $=1,...,$ n$,$ j $=1,...,$ m$,$and

yi $=$

$($

$1,$ if warehouse i is opened,

$0,$ o$/$w$,$

i $=1,...,$ n$.$

Then, the location$-$allocation model is:

min z $=$

Xn

i$=1$

Xm

j$=1$

cijxij $+$

Xn

i$=1$

fiyi

s$.$t$.$ Xn

i$=1$

xij $=1,$ j $=1,...,$ m$,$

Xm

j$=1$

xij $<=$ myi i $=1,...,$ n$,$

xij in $\{0,1\},$ i $=1,...,$ n$,$ j $=1,...,$ m$,$

yi in $\{0,1\},$ i $=1,...,$ n$.$

$(5)$

Assume that n $=4,$ m $=5,$ and that the fixed cost for opening a warehouse is $$20,000$ for each

of four warehouses. The transportation costs for all pairs of warehouses and stores $($in thousands$)$

are provided in the table below:

Stores

$12345$

$1101520940$

$21217152010$

$31814103516$

$4912332819$

Questions:$2.$ Run Tabu Search for five iterations with tenure period $\backslash$tau $=2,$ and starting with the solution

$[1,0,0,1].$ A neighborhood here is defined as a solution in which the status of only one

warehouse is flipped, i$.$e$.,$ you can flip one warehouse from being open to being closed or vice

versa to generate a neighbor $($except if that warehouse is on the Tabu list$).$ If a warehouse

is flipped from open to closed or vice versa, that warehouse $($not the entire solution$)$ should

then go on the Tabu list. Use random$-$walk selection for neighbors. For this part, use the

random numbers from seed $(1,1),$ and use them in this order! Show detailed work for every

iteration, then at the end of the algorithm, report the best solution found.