The p-Median Problem - Location Science - page 30

We relax constraint ( 2.2 ) to obtain the following Lagrangian problem:

D X i2 I

X j2 J

d j c ij x ij C X j2 J j 1 X

i2 I

x ij Max Min x;y L

(2.7)

D X i2 I

X j2 J

d j c ij j x ij C X j2 J

j

subject to ( 2.3 )-( 2.6 ).
For fixed values of the Lagrange multipliers, j , we compute the value of
being able to add a facility at node i 2 I . This value is given by V i D

X j2 J

min ˚ 0;d j c ij j . We then select the p sites with the p most negative V i
values, breaking ties arbitrarily. This determines the values of the location variables,
y i . The assignment variables are determined by setting x ij D 1 if (i) y i D 1 and (ii)
d j c ij j <0, and setting x ij D 0 otherwise. The resulting values can be used to
evaluate ( 2.7 ), providing a lower bound on the objective function value. To obtain an
upper bound on the objective function value, we simply assign every demand node
to the nearest candidate facility for which y i D 1 and evaluate ( 2.1 )usingthese
assignment values.
Some of constraints ( 2.2 ) are likely to be violated by the solution to the
Lagrangian problem as outlined above. In particular, some demand nodes may not
be assigned to any facility and some may be assigned to multiple facilities. This
occurs when the Lagrange multipliers are not at their optimal values. Subgradient
optimization can be used to improve the Lagrange multipliers. Daskin ( 2013 )
provides a detailed explanation of the Lagrangian algorithm for the p -median
problem.
The Lagrange multipliers coupled with the best lower and upper bounds can be
used to force candidate sites in and out of the solution at any point in the Lagrangian
procedure. Typically, it is most useful to do so when the bounds are very close to
each other but still differ by a small amount. Let LB and UB be the best-known lower
and upper bounds, respectively. Using the Lagrange multipliers associated with LB ,
sort the V i values so that V [ i ] is the i th smallest value. In other words, V [1] is the most
negative value and V [ p ] is the last value that resulted in selecting a candidate facility
site in the Lagrangian solution. Additionally, V ŒpC1 is the next largest value.
Consider a candidate site i 2 I that is in the best-known solution. Then, if UB <

LB V i C V ŒpC1 , site i 2 can be forced into the solution; in other words, we can set

y i D 1 in all subsequent Lagrangian iterations and in any branching below the node
at which this check is done (e.g., the root node of a branch-and-bound algorithm).
Similarly, if site i 2

I

I is not part of the best-known solution and UB < LB V Œp C V i ,

then site i 2 can be forced out of the solution; in other words, we can set y i D 0 in

all subsequent Lagrangian iterations and in any branching below the node at which
this check is done (e.g., the root node).

I