Implement Lagrangian Relaxation in UFLP $(30$ points$)$ A toy store

chain operates $100$ retail stores throughout the United States. The company currently ships

all products from a central distribution center $($DC$)$ to the stores, but it is considering closing

the central DC and instead operating multiple regional DCs that serve the retail stores. It

will use the UFLP to determine where to locate DCs$.$ Planners at the company have identified $24$ potential cities in which regional DCs may be located. The file toy$-$stores.xlsx

lists the longitude and latitude for all of the locations $($stores and DCs$),$ as well as the

annual demand $($measured in pallets$)$ at each store and the fixed annual location cost at

each potential DC location. Assume that transportation from DCs to stores costs $$1$ per

mile, as measured by the great circle distance between the two locations. In this problem, you will implement the Lagrangian Relaxation algorithm. We provide a code template

$($solve with LR template.ipynb$),$ but you are free to use any programming languages.

$($a$)(5$ points$)$ Show one step Lagrangian Relaxation iteration by relaxing constraints

yij $<=$ xj

$,$i in I, j in J$.$

Show how to calculate lower bound, upper bound and multipliers $\backslash$lambda

t$+1$

ij given $\backslash$lambda

t

ij $.($Caution: lambda must be non$-$negative or non$-$positive, depending on how you write the

inequalities, for xj $$ yij $>=0,$ the dual variables should be non$-$positive$)$

$($b$)(12$ points$)$ Do $100$ iterations using the following step length $$t

$,$

$$

t $=$

$0\mathrm{.}5$

UBt $$ zLR $(\backslash$lambda

t

$)$

P

i in I

P

j in J

$($xj $$ yij $)$

$2$

$.$

You can use the following initial conditions: $|\backslash$lambda i

$|=1,$ i in I, UB$0=1194676922($the

sign of lambda depends on how you write the inequalities$).$ Plot the upper bound and

lower bound against iterations. Report the gap.

$($c$)(8$ points$)$ Solve the toy store UFLP using Lagrangian Relaxation by relaxing $1$ P

j

yi $=0.$ Do $100$ iterations using step length

$$

t $=$

$0\mathrm{.}5$

UBt $$ zLR $(\backslash$lambda

t

$)$

P

i in I

$1$

P

j in J

yij$2$

$.$

You can use the following initial conditions: $\backslash$lambda i $=1,$ i in I, UB$0=1194676922.$ Plot

the upper bound and lower bound against iterations. Report the ga

$($d$)(5$ points$)$ Which relaxation is better? Why? This question is open$-$ended.