Consider the following formulation of the P-median problem: Inputs hi = demand at node i I dij = distance between demand node i I and candidate location j J Decision Variables Yij = fraction of the...

Consider the following formulation of the P-median problem: Inputs

h_i
= demand at node i

I

d_ij
= distance between demand node i

I and candidate location j

J

Decision Variables

Y_ij
= fraction of the demand at node i

I that is served by a facility at candidate location j

J

X_j
= 1 if we locate at candidate site j

J

0 if not

Formulation

In many cases, we not only want to minimize the sum over all demand nodes of the demand-weighted average distance between a demand node and the nearest facility, but we also want to be sure that each demand node has a facility located within at most D_c
distance units of it.

(a) Define any additional notation that you need and show how this can be handled by adding a constraint to the formulation shown above.

(b) Briefly state how you can deal with this problem by changing certain data inputs to the problem.

(c) Briefly discuss how you can solve the problem by eliminating certain variables from the formulation before you begin to solve the problem

(d) Will the new problem always have a feasible solution? If not, give an example of a case in which the new problem will not have a feasible solution. If so, prove that it will always have a feasible solution.