Geoscience Reference
In-Depth Information
Classical formulations for FLPs use two sets of decision variables: one set for the
selection of the facilities to open and another set for the allocation of users demand
to open facilities. For the location decisions, associated with each i
2
I we define
y
i
D
1 if a facility is open at location i
0 otherwise.
For the allocation decisions, associated with i
2
I, j
2
J we define
x
ij
D
1 if the demand at user j is served by facility i
0 otherwise.
A standard integer programming formulation for the FLP is as follows:
minimize
z
D
X
i2I
f
i
y
i
C
X
i2I
X
c
ij
x
ij
(3.1)
j2J
subject to
X
i2I
x
ij
D
1
j
2
J
(3.2)
X
d
j
x
ij
q
i
y
i
i
2
I
(3.3)
j2J
y
i
2f
0;1
g
i
2
I
(3.4)
x
ij
2f
0;1
g
i
2
I; j
2
J:
(3.5)
Constraints (
3.2
) guarantee that each customer is served from one facility, while
constraints (
3.3
) play a double role: (1) they ensure that the capacity of facilities is
not exceeded; and (2) they prevent users from being allocated to non-open facilities.
Constraints (
3.4
)and(
3.5
) define the domains of the decision variables. In the above
formulation inequalities (
3.3
) can be substituted by the two sets:
X
d
j
x
ij
q
i
i
2
I
(3.6)
j2J
x
ij
y
i
i
2
I;j
2
J:
(3.7)
Now the set of knapsack constraints (
3.6
) enforce that facility capacities are not
violated, whereas inequalities (
3.7
) relate the two sets of decision variables. While
constraints (
3.3
) are equivalent to (
3.6
)and(
3.7
) when the binary condition of the
y variables (
3.4
) is enforced, the compact set of constraints (
3.3
) dominates (
3.6
)
and (
3.7
) when the integrality of the location variables is relaxed to 0
y
i
1,
i
2
I.
Formulation (
3.1
)-(
3.5
) is appropriate for models requiring that the total
demand of each customer be served from the same facility. A number of situations
exist where such a requirement is justified, the most obvious one being the case
