$(50$ pts$.)$ Facility Location

A paper products manufacturer has enough capital to build and manage some additional

manufacturing plants in the United States in order to meet increased demand in three cities:

New York City, NY; Los Angeles, CA; and Topeka, KS$.$ The company is considering building

in Denver, CO$,$ Seattle, WA and St$.$ Louis, MO$.$

Figure $1$: Graphical representation of the given data

Due to geographic constraints, plants in Denver, Seattle and St$.$ Louis would have

a maximum operating capacity $k_i$ of $400$ tons$/$day$,700$ tons$/$day$,$ and $600$ tons$/$day$,$

respectively.

The cost $f_i$ of building plants in these cities is $f_1=$$$5,000,000$ in Denver, $f_2=$

$$10,000,000$ in Seattle. and $f_2=$$$8,000,000$ in St$.$ Louis.

The cost $c_{ij}$ per ton of transporting paper from city $i$ to city $j$ is outlined in Figure $1.$

The unmet demand $d_j$ for Los Angeles, Topeka, and New York City are $300$ tons$/$day$,$

$100$ tons$/$day$,$ and $500$ tons$/$day$,$ respectively.

The problem is to decide which plants to build, how much paper to produce in each plant,

and how best to ship paper from the plants to the customers in the way which minimizes

total expense. $($a$)$ Model this problem as an Integer Program. Let $w_i$ represent the binary choice of whether

or not to build plant i and $x_{ij}$ represent the amount of paper to be sent from plant $i$ to

customer $j$ for iin$\{1,2,3\}$ and jin$\{1,2,3\}.$

$($b$)$ The first step of solving an Integer Program is to solve its Continuous Relaxation. This

is the linear program formed by simply ignoring the integer constraints in the original

IP$.$

Solve the IP from part $($a$),$ and its continuous relaxation, in Excel Solver. Report the

optimal objective function values in your written submission and upload the excel sheets

in a workbook.

Hint: a binary constraint can be decomposed into $0,1,$ and Integer, before linearizing

it$.$

$($c$)$ If we cannot $($with our current knowledge$)$ prove that the excel solution to our IP is

optimal, we certainly know that there is no integer$-$feasible solution to the primal with

objective function value $($OFV$)$ better than the optimal continuous relaxation solution

we have found.

If $P$ is the OFV of the best known integer$-$feasible solution and $D$ is the OFV of the

optimal continuous relaxation, we can define the Integrality Gap to be

$\frac{P-D}{P}.$

Report the integrality gap of the solutions to the facility location problem that you found

in part $($b$).(15$ pts$.)($Bonus Problem$)$

$($e$)$ Ignoring any integer constraints, derive the dual of the IP you found in part $($a$)$ and

solve it using Excel Solver. Report its optimal solution in your written submission and

upload the excel sheets in a workbook.