Fixed-Charge Facility Location Problems

Abstract

Fixed-Charge Facility Location Problems are among core problems in Location Science. There is a finite set of users with demand of service and a finite set of potential locations for the facilities that will offer service to users. Two types of decisions must be made: Location decisions determine where to establish the facilities whereas allocation decisions dictate how to satisfy the users demand from the established facilities. Potential applications of various types arise in many different contexts. We provide an overview of the main elements that may intervene in the modeling and the solution process of Fixed-Charge Facility Location Problems, namely, modeling hypotheses and their implications, characteristics of formulations and their relation to other formulations, properties of the domains, and appropriate solution techniques.

1 Introduction

Fixed-Charge Facility Location Problems (FLPs) are among core problems in Location Science. In FLPs there is a finite set of users with demand of service and a finite set of potential locations for the facilities that will offer service to users. Two types of decisions must be made. Location decisions determine where to establish the facilities whereas allocation decisions dictate how to satisfy the users demand from the established facilities. Each possible decision incurs fixed-charge costs for the facilities that are established and assignment costs for the allocation decisions. In FLPs the aim is to make optimal decisions with respect to the considered costs.

Applications of FLPs arise in an wide variety of contexts. The book by Drezner and Hamacher (2002) surveys different applications of fixed-charge facility location in such diverse areas as the public sector, software for GIS or robotics. Furthermore, fixed-charge facility location also plays a critical role in many other areas like supply chain management, distributed systems, humanitarian relief, emergency systems, location-routing problems or freight transportation. Melo et al. (2009) survey facility location models in the context of supply chain management until 2009. Klose and Drexl (2005) summarize applications of FLPs within distributed system design. The paper by Balcik and Beamon (2008) is a recent sign of the interest of the combination of both humanitarian relief analysis and facility location models. Further examples of applications can be found in Owen and Daskin (1998), Daskin et al. (2002), Nagy and Salhi (2007) and Jiaa et al. (2007). In fact, the applicability of fixed-charge facility location models goes beyond the area of Location Analysis. Some fixed-charge facility location models are also valid within other fields like machine scheduling, cluster analysis or combinatorial auctions (Escudero et al. 2009; Klose and Drexl 2005; Singh 2008).

It has been traditionally assumed that in FLPs location decisions are strategic, whereas allocation decisions are tactical or operational. There are potential applications, however, in which location and allocation decisions are at the same hierarchy level in the decision making process. One example of application in which both decisions are strategic can be found in the design of a backbone network in telecommunications. An example of application in which both decisions are operational can be faced by some logistic companies which, at each time period, have to solve a FLP to determine the warehouses locations and the distribution pattern to be applied within the corresponding period.

Because FLPs are difficult optimization problems with many potential applications the study of their properties and efficient solution methods is of interest on its own. A further motivation for this study is that it sets the basis for the analysis of more complex models related to FLP extensions. In some cases, these extensions can, in turn, be modeled as some basic FLP. For example, some multi-period facility location problems (see Chap.11) or some hub-arc location problems (see Chap.12) can be can be reduced to the FLPs studied here (see, for instance Albareda-Sambola et al. 2009a; Contreras and Fernández 2013).

There are indeed a number of issues that define the characteristics of FLPs. These will be discussed in this chapter and include the possibility of satisfying the demand of each of the users from more than one facility, or capacity limits on the maximum demand that can be served from any selected facility, among others. Furthermore, several alternative formulations can be valid for a given FLP. Usually, none of these alternatives has a clear advantage over the others although, as it often happens with other discrete optimization problems, each of them is better suited for a certain solution technique. We aim to give the reader a broad overview of the main elements that may intervene in the solution process of FLPs, namely, modeling assumptions and their implications, characteristics of formulations and their relation to other formulations, properties of the domains, and appropriate solution techniques. However, in order to keep the length of the chapter within a reasonable limit, it has been impossible to address all relevant variants and extensions of the problem. As a consequence, we have selected some topics which, in our opinion, cover most of the major issues related to fixed-charge facility location. Diversity among the selected topics has been a major guideline as well.

The material presented in this chapter is the result of the research carried out by many authors in this area over the last 60 years. Most of it has been published but occasionally we present and prove some unpublished results which are either adaptations of well-known results for other cases, or simple results that can be easily derived from the existing state of knowledge.

The remainder of this chapter is structured as follows. In Sect. 3.2 we introduce our notation and we provide an overview of the problems we study. Section 3.2 also discusses modeling issues leading to standard formulations or to alternative Set Partitioning formulations and properties of the domains. A sample of possible solution methods, namely Lagrangean relaxation and column generation is presented in Sect. 3.3. Some of the major difficulties of FLPs that will offer service to users derive from the assumption that individual facilities do not have enough capacity to satisfy the demand of all customers. Releasing this assumption yields a particular FLP known as the Uncapacitated Facility Location Problem (UFLP), which is studied in Sects. 3.4 and 3.5. The UFLP satisfies some specific properties that do not hold for general FLPs. These properties can be exploited for modeling purposes or for deriving specific solution techniques. In particular, Sect. 3.4.1 studies some properties derived from Linear Programming duality, whereas Sect. 3.4.2 presents a formulation for the UFLP based on its supermodular property and relates it with the so-called radius based formulations. Finally, Sect. 3.5 gives some polyhedral results related to the UFLP. The chapter closes in Sect. 3.6 with some comments.

2 Overview and Modeling Issues

In this chapter we will use indistinctively the term service center when referring to a facility, and customer or demand point when referring to a user. Let I = { 1, …, i, …, m} denote the index set for the potential locations for the facilities and J = { 1, …, j, …, n} the index set for the users. We will refer to potential locations by their indices, so we will say that a facility is open at location i, or simply that facility i is open, if the decision to establish a service center at the potential location i is made. We will also denote users by their indices and simply refer to user j. Associated with each i ∈ I, q _i denotes the maximum capacity of facility i, if it is opened. The service demand of user j ∈ J is denoted by d _j . As mentioned, there are two types of costs. The decision to establish a facility at i ∈ I incurs a fixed-charge (setup) cost f _i . For i ∈ I and j ∈ J, $c_{\mathit{ij}}$ is the cost for serving all the demand of customer j from facility i.

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 ∈ I we define

$$\displaystyle{y_{i} = \left \{\begin{array}{rl} 1&\mbox{ if a facility is open at location }i\\ 0 &\mbox{ otherwise.}\\ \end{array} \right.}$$

For the allocation decisions, associated with i ∈ I, j ∈ J we define

$$\displaystyle{x_{\mathit{ij}} = \left \{\begin{array}{rl} 1&\mbox{ if the demand at user }j\mbox{ is served by facility }i\\ 0 &\mbox{ otherwise.}\\ \end{array} \right.}$$

A standard integer programming formulation for the FLP is as follows:

$$\displaystyle\begin{array}{rcl} \mbox{ minimize }z =\sum _{i\in I}f_{i}y_{i} +\sum _{i\in I}\sum _{j\in J}c_{\mathit{ij}}x_{\mathit{ij}}& &{}\end{array}$$

(3.1)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\sum _{i\in I}x_{\mathit{ij}} = 1\qquad \qquad \!j \in J& &{}\end{array}$$

(3.2)

$$\displaystyle\begin{array}{rcl} \sum _{j\in J}d_{j}x_{\mathit{ij}} \leq q_{i}y_{i}\quad \,\,\,\,i \in I& &{}\end{array}$$

(3.3)

$$\displaystyle\begin{array}{rcl} y_{i} \in \{ 0,1\}\qquad \qquad \, i \in I& &{}\end{array}$$

(3.4)

$$\displaystyle\begin{array}{rcl} x_{\mathit{ij}} \in \{ 0,1\}\qquad \qquad \!i \in I,\,j \in J.& &{}\end{array}$$

(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:

$$\displaystyle\begin{array}{rcl} \sum _{j\in J}d_{j}x_{\mathit{ij}} \leq q_{i}\qquad i \in I& &{}\end{array}$$

(3.6)

$$\displaystyle\begin{array}{rcl} x_{\mathit{ij}} \leq y_{i}i \in I,j \in J.& &{}\end{array}$$

(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 ∈ 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 where the demand of each customer represents a physical object that cannot be split. This case is known as the single allocation FLP (SFLP). Equations (3.1)–(3.5) is a valid formulation for the SFLP. Many FLP models, however, allow splitting the demand at users among several open facilities. Such models, which are referred to as multiple allocation FLPs (MFLPs), arise, for instance, when customers represent population areas and not all the individuals in a given area need to be served from the same service center. In MFLPs allocating customer j to facility i means that some positive fraction of d _j is served from facility i. Hence, for i ∈ I, j ∈ J the allocation decision variables x _ij are defined as the fraction of demand of user j served by facility i, and the domain for the x variables is thus substituted by its continuous relaxation

$$\displaystyle{ 0 \leq x_{\mathit{ij}} \leq 1,\qquad i \in I,j \in J. }$$

(3.8)

With the above definition of the allocation decision variables, constraints (3.2) have a slightly more general interpretation than in the single allocation case. Since they impose that the sum of all the fractions served from the different facilities be one, they also guarantee that the total demand at each user is satisfied. Therefore, in order to obtain a valid formulation for the MFLP, in formulation (3.1)–(3.5) we “only” have to change the domain of the allocation variables x. It then follows that (3.1)–(3.4) together with (3.8) is a valid formulation for the MFLP.

The FLP is $\mathcal{N}\mathcal{P}$-hard since a polynomial transformation can be used to reduce the node cover problem, which is known to be $\mathcal{N}\mathcal{P}$-hard (Garey and Johnson 1979), into the FLP (see, for instance, Cornuéjols et al. 1990).

The reader may note that the “difficult” decision in FLPs is the selection of the facilities to open. This is readily seen in the multiple allocation case where, if the set of facilities to open is given, S ⊂ I, the best allocation of customers within S can easily be obtained by solving the following transportation problem:

$$\displaystyle\begin{array}{rcl} \mathit{TP}(S)\quad \mbox{ minimize }z =\sum _{i\in S}\sum _{j\in J}(c_{\mathit{ij}}/d_{j})s_{\mathit{ij}}& &{}\end{array}$$

(3.9)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\sum _{i\in S}s_{\mathit{ij}} \geq d_{j}\qquad \!j \in J& &{}\end{array}$$

(3.10)

$$\displaystyle\begin{array}{rcl} \sum _{j\in J}s_{\mathit{ij}} \leq q_{i}\qquad i \in S& &{}\end{array}$$

(3.11)

$$\displaystyle\begin{array}{rcl} s_{\mathit{ij}} \geq 0\qquad \quad \quad \!i \in S,\,j \in J.& &{}\end{array}$$

(3.12)

In formulation (3.9)–(3.12) above the continuous decision variable s _ij denotes the amount of demand of customer j which is served from facility i. Hence we have the relation, $x_{\mathit{ij}} = s_{\mathit{ij}}/d_{j}$.

In the single allocation case, finding an optimal allocation of customers to a given set of open facilities S ⊂ I is still a difficult problem, namely a Generalized Assignment Problem, which is also $\mathcal{N}\mathcal{P}$-hard (Fisher et al. 1986). Now, a formulation for finding the best allocation of customers within the set of facilities S is given by:

$$\displaystyle\begin{array}{rcl} \mathit{GAP}(S)\quad \mbox{ minimize }z =\sum _{i\in S}\sum _{j\in J}c_{\mathit{ij}}x_{\mathit{ij}}& &{}\end{array}$$

(3.13)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\sum _{i\in S}x_{\mathit{ij}} = 1\qquad \quad j \in J& &{}\end{array}$$

(3.14)

$$\displaystyle\begin{array}{rcl} \sum _{j\in J}d_{j}x_{\mathit{ij}} \leq q_{i}\quad \,\,\,\,i \in S& &{}\end{array}$$

(3.15)

$$\displaystyle\begin{array}{rcl} x_{\mathit{ij}} \in \{ 0,1\}\qquad \,\,\,\,\,\,i \in S,\,j \in J.& &{}\end{array}$$

(3.16)

So far we have presented FLPs as a minimization problems in which both types of decisions incur costs. However, the type of objective function depends on the decision maker. Minimization FLPs usually appear in the public sector when locating facilities for essential services: public hospitals or schools, dumps for garbage collection, etc. In the private sector, however, service to customers produces a profit to companies so that the objective of companies facing location decisions for their service centers is to maximize the net profit, defined as the difference between the revenue derived from the serviced customers and the cost for the location of the selected facilities. There is indeed an essential difference between these two models: while minimization FLPs impose that all customers be served (no demand point can be excluded from an essential service), in maximization FLPs not all users necessarily have to be served. The company may not have enough incentive for servicing all customers and only those generating a profit in an optimal location setting will be served. However, as we will next see, from a mathematical programming point of view the maximization and minimization versions of the FLP are equivalent.

Consider a maximization FLP where b _ij denotes the profit for servicing customer j ∈ J from facility i ∈ I. As indicated in Cornuéjols et al. (1990), typically, b _ij is a function of the unit production costs at facility i (h _i ), the unit transportation costs from facility i to customer j (t _ij ), and the service price for customer j (s _j ). That is, $b_{\mathit{ij}} = d_{j}(s_{j} - h_{i} - t_{\mathit{ij}})$. Then, the objective function for a maximization FLP is

$$\displaystyle\begin{array}{rcl} \mbox{ maximize }z =& -\sum _{i\in I}f_{i}y_{i} +\sum _{i\in I}\sum _{j\in J}b_{\mathit{ij}}x_{\mathit{ij}}.&{}\end{array}$$

(3.17)

In principle, if not all customers have to be served, allocation constraints should be stated as inequalities, i.e. $\sum _{i\in I}x_{\mathit{ij}} \leq 1$, j ∈ J. However, such constraints are easily transformed into equalities by simply defining a fictitious potential facility 0, representing the facility to which all unserved demand is allocated. To this end, we assume a sufficiently large capacity for the fictitious facility, q ₀ = ∑ _j ∈ J d _j , and set to zero, both the fixed-charge cost of the fictitious facility (f ₀ = 0) and the allocation profits of all customers (b _0j  = 0, j ∈ J). Thus, without loss of generality we can assume that in the maximization FLP allocation constraints must also be satisfied as equality.

Taking into account the expression of the coefficients b _ij and because of the equality allocation constraints, the second term in (3.17) can be rewritten as

$$\displaystyle\begin{array}{rcl} \sum _{i\in I}\sum _{j\in J}b_{\mathit{ij}}x_{\mathit{ij}}& =& \sum _{i\in I}\sum _{j\in J}d_{j}(s_{j} - h_{i} - t_{\mathit{ij}})x_{\mathit{ij}} {}\\ & =& \sum _{i\in I}\sum _{j\in J}d_{j}s_{j}x_{\mathit{ij}} -\sum _{i\in I}\sum _{j\in J}d_{j}(h_{i} + t_{\mathit{ij}})x_{\mathit{ij}} {}\\ & =& \sum _{j\in J}d_{j}s_{j} -\sum _{i\in I}\sum _{j\in J}c'_{\mathit{ij}}x_{\mathit{ij}}. {}\\ \end{array}$$

Hence objective (3.17) reduces to

$$\displaystyle\begin{array}{rcl} \sum _{j\in J}d_{j}s_{j} -\mbox{ min }\left [\sum _{i\in I}f_{i}y_{i} +\sum _{i\in I}\sum _{j\in J}c'_{\mathit{ij}}x_{\mathit{ij}}\right ].& &{}\end{array}$$

(3.18)

Since the first term in (3.18) is a constant, the maximization FLP is equivalent to a minimization FLP.

2.1 Set Partitioning Formulation of FLPs

Below we present alternative formulations for FLPs which use decision variables to model the overall customers demand allocated to open facilities. Consider for the moment the single allocation case and note that feasible assignments to a given facility i ∈ I are associated with subsets of customers T ⊂ J such that ∑ _j ∈ T d _j  ≤ q _i . We will use the notation K _i to denote the index set of feasible assignment subsets for facility i ∈ I, T _k  ⊂ J the index set of the customers served in feasible assignment k ∈ K _i , and p _ki for the fixed-charge cost of facility i plus the cost for assigning to i all the customers indexed in T _k , i.e. $p_{\mathit{ki}} = f_{i} +\sum _{j\in T_{k}}c_{\mathit{ij}}$. Also, for i ∈ I, k ∈ K _i , j ∈ J, let a _ijk  = 1 if j ∈ T _k and 0 otherwise. Consider now the following decision variables:

$$\displaystyle{z_{\mathit{ki}} = \left \{\begin{array}{cl} 1&\mbox{ if the subset of customers $T_{k}$ is assigned to facility $i$}\\ 0 &\mbox{ otherwise.} \end{array} \right.}$$

Then, a set partitioning formulation for the SFLP is

$$\displaystyle\begin{array}{rcl} \mathit{SPSFLP}\qquad \mbox{ minimize}\sum \limits _{i\in I}\sum \limits _{k\in K_{i}}p_{\mathit{ki}}z_{\mathit{ki}}& &{}\end{array}$$

(3.19)

$$\displaystyle\begin{array}{rcl} \qquad \mbox{ subject to}\sum \limits _{i\in I}\sum \limits _{k\in K_{i}}a_{\mathit{ijk}}z_{\mathit{ki}} = 1\quad j \in J& &{}\end{array}$$

(3.20)

$$\displaystyle\begin{array}{rcl} \quad \sum \limits _{k\in K_{i}}z_{\mathit{ki}} = y_{i}\qquad \quad \,\,\,i \in I& &{}\end{array}$$

(3.21)

$$\displaystyle\begin{array}{rcl} y_{i} \in \{ 0,1\}\qquad \qquad \,\,i \in I& &{}\end{array}$$

(3.22)

$$\displaystyle\begin{array}{rcl} z_{\mathit{ki}} \in \{ 0,1\}\qquad \qquad \,\,i \in I,\,k \in K_{i}.& &{}\end{array}$$

(3.23)

Constraints (3.20) ensure that each customer is assigned to exactly one facility. Constraints (3.21) guarantee that no assignment is selected for a non-open facility and also that one feasible assignment is selected for each open facility. Observe that, because of (3.20), constraints (3.21) can be written as ≤ inequalities and will still be satisfied as equalities. Constraints (3.22) and (3.23) define the domain of the decision variables. The above a formulation will be referred to as SPSFLP.

A set partitioning formulation for the multiple allocation case can be obtained from the above formulation by simple relaxing the integrality conditions on the z variables to 0 ≤ z _ki  ≤ 1, i ∈ I, k ∈ K _i . It is now necessary to use the ≤ expression for constraints (3.21), since optimal solutions may exist with some open facility only serving fractions of demand of the allocated customers. This formulation will be referred to as SPMFLP.

The large number of variables both in SPSFLP and in SPMFLP make these formulations suitable for column generation.

3 Solution Algorithms for Fixed-Charge Facility Location

In this section we overview solution methods for FLPs. Several heuristic and exact algorithms have been proposed for FLPs and an exhaustive survey on the related literature is outside the scope of this chapter. Branch-and-bound methods proposed in the early papers (Sá 1969; Davis and Ray 1969; Ellwein and Gray 1977; Akinc and Khumawala 1977; Nauss 1978; Neebe and Rao 1983) were followed by many algorithms based on Lagrangean relaxation (Geoffrion and McBride 1978; Christofides and Beasley 1983; Guignard and Kim 1983; Barceló and Casanovas 1984; Klincewicz and Luss 1986; Pirkul 1987; Beasley 1988; Guignard and Opaswongkarn 1990; Barceló et al. 1990, 1991; Cornuéjols et al. 1991; Beasley 1993; Sridharan 1993, 1995; Holmberg et al. 1999). Some of the first works on approximation algorithms are those of Shetty (1990), Shmoys et al. (1997) and Chudak and Shmoys (1999). Algorithms based on Benders and cross decomposition have been respectively proposed in Wentges (1996) and Van Roy (1986), whereas branch-and-price has been applied by Díaz and Fernández (2002) and Klose and Görtz (2007). Some recent works are Barahona and Chudak (2005), Sankaran (2007), Sharma and Berry (2007), Ghiani et al. (2012), and Zhen et al. (2012). For an overview of heuristics for FLPs the interested reader is addressed to Jacobsen (1983), Filho and Galvão (1998), Delmaire et al. (1999a,b), Hindi and Pienkosz (1999), Cortinhal and Captivo (2003), Ahuja et al. (2004) and references therein.

The most obvious strategy for solving an FLP instance to optimality is to use a standard mixed integer programming (MIP) solver with formulation SFLP or MFLP, depending on the case. This approach may, however, fail on large instances, especially for the single source case. Some alternatives are presented below, which somehow exploit the structure of the problem and lead either to an exact algorithm or to methods that can be embedded within an exact algorithm. First we study Lagrangean relaxation, which has been used by a number of authors both for the single and multiple allocation cases. Then we address the pricing problem for the set partitioning formulation SPSFLP, which is one of the main ingredients of the branch-and-price algorithm of Díaz and Fernández (2002).

3.1 Lagrangean Relaxation

We next present a Lagrangean relaxation of model SFLP in which the assignment constraints (3.2) are relaxed. This relaxation has been used by a number of authors (see, for instance, Pirkul 1987; Barceló et al. 1990, 1991; Beasley 1993; Holmberg et al. 1999). The Lagrangean subproblem associated with a given set of multipliers $\pi \in \mathbf{R}^{n}$, is

$$\displaystyle\begin{array}{rcl} L_{\mathit{SFLP}}(\pi ) = \quad \mbox{ minimize}\;\sum \limits _{i\in I}\left (f_{i}y_{i} +\sum \limits _{j\in J}c_{\mathit{ij}}x_{\mathit{ij}}\right ) +\sum \limits _{j\in J}u_{j}\left (1 -\sum \limits _{i\in I}x_{\mathit{ij}}\right )& &{}\end{array}$$

(3.24)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\sum \limits _{j\in J}d_{j}x_{\mathit{ij}} \leq q_{i}y_{i}\qquad i \in I& &{}\end{array}$$

(3.25)

$$\displaystyle\begin{array}{rcl} x_{\mathit{ij}} \in \{ 0,1\}\qquad \qquad \, i \in I,j \in J& &{}\end{array}$$

(3.26)

$$\displaystyle\begin{array}{rcl} y_{i} \in \{ 0,1\}\qquad \qquad \,\,i \in I.& &{}\end{array}$$

(3.27)

After rearranging its terms the objective function can be rewritten as

$$\displaystyle{\sum \limits _{j\in J}\pi _{j} +\min \quad \sum \limits _{i\in I}\left (f_{i}y_{i} +\sum \limits _{j\in J}\left (c_{\mathit{ij}} -\pi _{j}\right )x_{\mathit{ij}}\right ).}$$

A solution to L _SFLP (π) can be obtained applying the following two steps:

• (1) For each i ∈ I solve the knapsack problem

  $$\displaystyle\begin{array}{rcl} \mathit{KP}(i): \qquad \mbox{ maximize}\sum \limits _{j\in J}\left (c_{\mathit{ij}} -\pi _{j}\right )x_{\mathit{ij}}& & {}\end{array}$$

  (3.28)
  $$\displaystyle\begin{array}{rcl} \qquad \mbox{ subject to}& & \sum \limits _{j\in J}d_{j}x_{\mathit{ij}} \leq q_{i} {}\end{array}$$

  (3.29)
  $$\displaystyle\begin{array}{rcl} x_{\mathit{ij}} \in \{ 0,1\}\quad j \in J.& & {}\end{array}$$

  (3.30)

  Let J(i) denote the index set of variables at value 1 in an optimal solution to KP(i) and $v(i) =\sum \limits _{j\in J(i)}(c_{\mathit{ij}} -\pi _{j})$ its associated optimal value.

• (2) For each i ∈ I, with f _i + v(i) < 0 then y _i  = 1, and x _ij  = 1, for j ∈ J(i).

The Lagrangean dual associated with L _SFLP (π) is

$$\displaystyle{D_{\mathit{SFLP}}\quad \max \limits _{\pi \in \mathbf{R}^{n}}L_{\mathit{SFLP}}(\pi ).}$$

Proposition 3.1

The optimal value of the Lagrangean dual D _SFLP coincides with the value of the linear programming (LP) relaxation of program SPSFLP.

Proof

Consider the following Lagrangean function resulting from relaxing constraints (3.20) in SPSFLP in a Lagrangean fashion:

$$\displaystyle\begin{array}{rcl} L_{\mathit{SPSFLP}}(\pi ) = \mbox{ minimize}\quad \sum \limits _{i\in I}\sum \limits _{k\in K}p_{\mathit{ki}}z_{\mathit{ki}} +\sum \limits _{j\in J}\pi _{j}\left (1 -\sum \limits _{i\in I}\sum \limits _{k\in K_{i}}a_{\mathit{ijk}}z_{\mathit{ki}}\right )\quad & &{}\end{array}$$

(3.31)

$$\displaystyle\begin{array}{rcl} \qquad \mbox{ subject to}\quad \sum \limits _{k\in K_{i}}z_{\mathit{ki}} \leq y_{i}\quad \,\,\,\,i \in I& &{}\end{array}$$

(3.32)

$$\displaystyle\begin{array}{rcl} z_{\mathit{ki}} \geq 0\qquad \qquad i \in I,\,k \in K_{i}& &{}\end{array}$$

(3.33)

$$\displaystyle\begin{array}{rcl} y_{i} \in \{ 0,1\}\qquad \,\,i \in I.& &{}\end{array}$$

(3.34)

The objective function (3.31) can be expressed as

$$\displaystyle\begin{array}{rcl} \sum \limits _{j\in J}\pi _{j} +\min \left [\sum \limits _{i\in I}\sum \limits _{k\in K_{i}}p_{\mathit{ki}}z_{\mathit{ki}} -\sum \limits _{i\in I}\sum \limits _{k\in K_{i}}\sum \limits _{j\in J}\pi _{j}a_{\mathit{ijk}}z_{\mathit{ki}}\right ] = & & {}\\ \sum \limits _{j\in J}\pi _{j} +\min \left [\sum \limits _{i\in I}\sum \limits _{k\in K_{i}}(p_{\mathit{ki}} -\sum \limits _{j\in T_{k}}\pi _{j})z_{\mathit{ki}}\right ].& & {}\\ \end{array}$$

Thus, for a given vector π, the solution to L _SPSFLP (π) can be obtained as follows:

• For i ∈ I, do

  • Find $k(i) \in \arg \max _{k\in K_{i}}\{p_{\mathit{ki}} -\sum \limits _{j\in T_{k}}\pi _{j}\}$.

  • If $p_{k(i)i} -\sum \limits _{j\in T_{k(i)}}\pi _{j} < 0$ then y _i  = 1, z _k(i)i  = 1, z _ki  = 0,  k ∈ K _i ∖{k(i)}.If $p_{k(i)i} -\sum \limits _{j\in T_{k(i)}}\pi _{j} \geq 0$ then y _i  = 0, z _ki  = 0, k ∈ K _i .

Note that, for each feasible solution $(\hat{z},\hat{y})$ to (3.32)–(3.34), for each i ∈ I there exists a one-to-one correspondence between $(\hat{y}_{i},(\hat{z}_{\mathit{ki}})_{k\in K_{i}})$, and a vector $(\hat{y}_{i},(\hat{x}_{\mathit{ij}})_{j\in J})$, that satisfies constraints (3.25). In particular, $\hat{x}_{\mathit{ij}} =\sum _{k\in K_{i}}a_{\mathit{ijk}}\hat{z}_{\mathit{ki}}$ for all i ∈ I, j ∈ J. Note that the above solution is well defined since for i ∈ I there is at most one k ∈ K _i with $\hat{z}_{\mathit{ki}} = 1$. Furthermore, by definition of the z variables, for i ∈ I, $(\hat{x}_{\mathit{ij}})_{j\in J}$ represents a feasible assignment to facility i, i.e. $\sum _{j\in J}d_{j}\hat{x}_{\mathit{ij}} \leq q_{i}\hat{y}_{i}$. Finally, the objective function values of the two solutions coincide since for i ∈ I fixed, $\sum _{k\in K_{i}}p_{\mathit{ki}}\hat{z}_{\mathit{ki}} = f_{i}\hat{y}_{i} +\sum \limits _{j\in J}c_{\mathit{ij}}\hat{x}_{\mathit{ij}}$. Therefore, taking into account the above considerations, L _SPSFLP (π) can be rewritten as

$$\displaystyle\begin{array}{rcl} \sum \limits _{i\in I}\pi _{i} + \mbox{ minimize}& & \sum \limits _{j\in J}\left (f_{i}y_{i} +\sum \limits _{j\in J}c_{\mathit{ij}}x_{\mathit{ij}}\right ) -\sum \limits _{j\in J}\sum \limits _{i\in I}\pi _{j}x_{\mathit{ij}} \\ \mbox{ subject to}& & \sum \limits _{j\in J}d_{j}x_{\mathit{ij}} \leq q_{i}y_{i}\quad i \in I \\ & & x_{\mathit{ij}} \in \{ 0,1\}\qquad \quad \,i \in I,j \in J \\ & & y_{i} \in \{ 0,1\}\qquad \quad \,i \in I, {}\end{array}$$

(3.35)

which is indeed L _SFLP (π). □ 

The reader will immediately conclude that a similar result holds for the MFLP.

Proposition 3.1 establishes that D _SFLP and the LP relaxation of SPSFLP are equally tight in terms of the lower bounds they produce (the same is true for D _MFLP and the LP relaxation of SPMFLP). Now, the question that arises naturally is how to compare both types of formulations from an algorithmic point of view.

As we have seen, the Lagrangean subproblem L _SFLP (π) is rather easy to solve and subgradients are easy to compute at each point. For a given vector π, let (y(π), x(π)) denote an optimal solution to L _SFLP (π). Then, a subgradient of L _SFLP (π) is given by $\varphi = (\varphi _{j})_{j\in J}$, where $\varphi _{j} = 1 -\sum _{i\in I}x_{\mathit{ij}}(\pi )$. Therefore, D _SFLP can be efficiently solved with subgradient optimization. However, when looking for an exact algorithm, the Lagrangean dual D _MFLP may not be very handy within an enumeration scheme. In contrast the LP relaxation of SPSFLP may be more demanding than D _SFLP from a computational point of view (the pricing subproblem must be solved repeatedly to generate all the needed columns), but it can be very well integrated within a branch-and-price scheme. For this reason, the next section studies the pricing problem for generating columns for SPSFLP, which is the main component of an exact branch-and-price algorithm for the SFLP based on this formulation (Díaz and Fernández 2002).

3.2 The Pricing Problem for SPSFLP

Suppose we have solved the LP relaxation of the subproblem of SPSFLP associated with a subset of columns $\overline{K} = (\overline{K}_{i})_{i\in I}$. Let π, and λ denote the optimal values of the dual variables associated with constraints (3.20) and (3.21), respectively. Then in order to know whether there exists a z variable of the overall formulation that, if added to the current set of columns, would improve the current LP solution, we must find the column of the coefficient matrix of SPSFLP with the smallest reduced cost. The reduced cost of variable z _ki , i ∈ I, k ∈ K _i , is given by $r_{\mathit{ki}} = p_{\mathit{ki}} -\sum _{j\in J}\pi _{j}a_{\mathit{ijk}} -\lambda _{i}$. Thus, in order to find the column that yields the smallest reduced cost we must solve the following pricing problem:

$$\displaystyle\begin{array}{rcl} (\mathit{PP})\quad \min \limits _{i\in I,\;k\in K_{i}}\quad r_{\mathit{ki}} = p_{\mathit{ki}} -\sum \limits _{j\in J}\pi _{j}a_{\mathit{ijk}} -\lambda _{i}.& & {}\\ \end{array}$$

Since $p_{\mathit{ki}} = f_{i} +\sum _{j\in T_{k}}c_{\mathit{ij}}$, then $r_{\mathit{ki}} = f_{i} +\sum _{j\in J}\left (c_{\mathit{ij}} -\pi _{j}\right )a_{\mathit{ijk}} -\lambda _{i}$. Note also that feasible columns a _ik , k ∈ K _i , i ∈ I, are characterized by the condition $\sum \nolimits _{j\in J}d_{j}a_{\mathit{ijk}} \leq q_{i}$. Thus, the solution to PP can be obtained by solving a series of independent problems, one for each i ∈ I. Since, for a given i ∈ I, the value f _i −λ _i is fixed, then the corresponding problem reduces to

$$\displaystyle\begin{array}{rcl} \mathit{PP}_{i}\qquad \mbox{ minimize}\quad & & \sum _{j\in J}\left (c_{\mathit{ij}} -\pi _{j}\right )a_{\mathit{ijk}} {}\\ \qquad \mbox{ subject to}\quad & & \sum \limits _{j\in J}d_{j}a_{\mathit{ijk}} \leq q_{i} {}\\ & & a_{\mathit{ijk}} \in \{ 0,1\}\quad j \in J. {}\\ \end{array}$$

4 The Uncapacitated Facility Location Problem

An important particular case of the FLP arises under the assumption that the capacity of any open facility is sufficient to satisfy the demand of all customers, i.e. q _i  ≥ ∑ _j ∈ J d _j , i ∈ I, so that the capacity constraints (3.3) are not needed. This particular case is known as the Uncapacitated Facility Location Problem (UFLP) and has received a considerable amount of attention. Next we focus on the UFLP and study some of its properties. The interested reader is addressed to Cornuéjols et al. (1990) for a deeper analysis and further details.

A first observation is that the UFLP basically involves one main decision: finding the set of facilities to open. Note that an optimal allocation of customers within a given set of open facilities, say S, is trivial, and consists of serving all the demand of each customer from a facility in S with minimum allocation cost, with ties broken arbitrarily. That is, for j ∈ J, let $i(j) \in \arg \min \{ c_{\mathit{ij}}\mid i \in S\}$ be arbitrarily chosen, then x _i(j)j  = 1, x _ij  = 0, i ∈ I ∖ i(j) is an optimal allocation of customers within the set of facilities S. Thus, a closed expression for the objective function value for a set of facilities S ⊆ I is $z(S) =\sum _{i\in S}f_{i} +\sum _{j\in J}\min _{i\in S}c_{\mathit{ij}}$. The main implication of this observation is that the UFLP can be stated as the minimization of a known set function. Before addressing this issue, we study some properties and algorithmic alternatives, derived from a standard MIP formulation for the UFLP.

Indeed a MIP formulation for the UFLP can be obtained with the y and x decision variables of the previous sections. Now it is no longer necessary to impose the binary condition on the allocation variables, even if single allocation is imposed. The argument is simple: if some customer is allocated to more than one facility in an optimal solution, the allocation costs of that customer to all its allocated facilities must be equal (otherwise the solution would not be optimal). Thus the customer can be fully served from any arbitrarily selected open facility of minimum allocation cost. On the other hand, even if capacity constraints are no longer needed, it is still necessary to impose that no customer is assigned to a non-open facility. Thus, by replacing constraints (3.3) by (3.7) we obtain the following valid formulation for the UFLP:

$$\displaystyle\begin{array}{rcl} \mathit{UFLP}\quad \mbox{ minimize }\sum _{i\in I}f_{i}y_{i} +\sum _{i\in I}\sum _{j\in J}c_{\mathit{ij}}x_{\mathit{ij}}& &{}\end{array}$$

(3.36)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\sum _{i\in I}x_{\mathit{ij}} = 1\quad \,\,\,\,\,j \in J& &{}\end{array}$$

(3.37)

$$\displaystyle\begin{array}{rcl} x_{\mathit{ij}} \leq y_{i}\qquad \quad \,i \in I,j \in J& &{}\end{array}$$

(3.38)

$$\displaystyle\begin{array}{rcl} 0 \leq x_{\mathit{ij}}\qquad \quad \,\,\,i \in I,\,j \in J& &{}\end{array}$$

(3.39)

$$\displaystyle\begin{array}{rcl} y_{i} \in \{ 0,1\}\qquad i \in I.& &{}\end{array}$$

(3.40)

A broad literature exists on the UFLP. From seminal papers (Kuehn and Hamburger 1963; Stollsteimer 1963; Manne 1964; Balinski 1966; Efroymson 1966; Spielberg 1969a,b; Khumawala 1972; Bilde and Krarup 1977; Cornuéjols et al. 1977; Guignard and Spielberg 1977; Nemhauser et al. 1978) and other early contributions (Guignard 1980; Cornuéjols and Thizy 1982; Guignard 1988; Beasley 1988; Körkel 1989; Beasley 1993; Aardal 1998), to more recent works (Goldengorin et al. 2004; Klose and Drexl 2005; Mladenović et al. 2006; Janacek and Buzna 2008; Beltran-Royo et al. 2012; Letchford and Miller 2012, 2014), virtually any type of solution algorithm has been proposed for it. As with the general facility location problem, an extensive literature review is outside the scope of this chapter. The interested reader is referred to Krarup and Pruzan (1983), Cornuéjols et al. (1990), Labbé et al. (1995), ReVelle and Laporte (1996) or Verter (2011) for overviews of the main contributions.

4.1 Bounds for UFLP Derived from LP Duality

Consider the LP relaxation of UFLP, in which constraints (3.38) have been written as $y_{i} - x_{\mathit{ij}} \geq 0$, and the upper bound constraints on the y variables as $-y_{i} \geq -1$, i ∈ I. Let u, w and t denote the vectors of dual variables of appropriate dimensions associated with constraints (3.37), (3.38) and the upper bound constraints, respectively. Then, the dual of the LP relaxation of UFLP is

$$\displaystyle\begin{array}{rcl} \mathit{DUFLP}\quad \mbox{ maximize }\sum _{j\in J}u_{j} -\sum _{i\in I}t_{i}& &{}\end{array}$$

(3.41)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\sum _{j\in J}w_{\mathit{ij}} - t_{i} \leq f_{i}\,\,\,i \in I& &{}\end{array}$$

(3.42)

$$\displaystyle\begin{array}{rcl} u_{j} - w_{\mathit{ij}} \leq c_{\mathit{ij}}\quad \,\,\,\,i \in I,j \in J& &{}\end{array}$$

(3.43)

$$\displaystyle\begin{array}{rcl} w_{\mathit{ij}} \geq 0\qquad \qquad \,i \in I,\,j \in J& &{}\end{array}$$

(3.44)

$$\displaystyle\begin{array}{rcl} t_{i} \geq 0\qquad \qquad \,\,\,\,i \in I.& &{}\end{array}$$

(3.45)

The optimal values for the t variables can be determined from the optimal w values as $t_{i} = \left (\sum _{j\in J}w_{\mathit{ij}} - f_{i}\right )^{+}$, i ∈ I, where $(a)^{+} =\max \{ 0,a\}$. In turn, the optimal w values can be determined from the optimal u values as $w_{\mathit{ij}} = \left (u_{j} - c_{\mathit{ij}}\right )^{+}$, i ∈ I, j ∈ J. Therefore, DUFLP can be expressed in terms of only u variables as

$$\displaystyle\begin{array}{rcl} \mathit{DUFLP}\quad \mbox{ max }D(u) =\sum \limits _{j\in J}u_{j} -\sum _{i\in I}\left (\sum \limits _{j\in J}\left (u_{j} - c_{\mathit{ij}}\right )^{+} - f_{ i}\right )^{+}.& & {}\\ \end{array}$$

Furthermore, the following optimality conditions hold:

• (a) There exists an optimal DUFLP solution where u _j  ≥ min _i ∈ I c _ij for all j ∈ J.

  If u _j  < min _i ∈ I c _ij for some j ∈ J, then we can increase the value of u _j without decreasing the objective function value.

• (b) There exists an optimal DUFLP solution where $\sum _{j\in J}\left (u_{j} - c_{\mathit{ij}}\right )^{+} - f_{i} \leq 0$ for all i ∈ I.

  If $\sum _{j\in J}\left (u_{j} - c_{\mathit{ij}}\right )^{+} - f_{i} > 0$ for some i ∈ I, we can decrease the value of some component u _j (with u _j  > c _ij ) without decreasing the objective function value.

Condition (b) means that the objective function value of an optimal dual solution reduces to ∑ _j ∈ J u _j . In other words, an optimal dual solution exists with t _i  = 0 for all i ∈ I. Hence, the complementarity slackness conditions for constraints (3.42) are

$$\displaystyle{ \left (f_{i} -\sum \limits _{j\in J}\left (u_{j} - c_{\mathit{ij}}\right )^{+}\right )y_{ i} = 0\qquad \qquad i \in I. }$$

(3.46)

These conditions, which apply to any primal-dual optimal pair to the LP relaxation of UFLP, hold trivially for all i ∈ I with y _i  = 0. When y _i  > 0, (3.46) holds provided that $\sum _{j\in J}\left (u_{j} - c_{\mathit{ij}}\right )^{+} = f_{i}$. For the integer UFLP the complementarity slackness conditions (3.46) give the guidelines for primal-dual heuristics. Two alternative strategies may be applied: (1) the primal solution is obtained first and then a vector u is built to satisfy $\sum _{j\in J}\left (u_{j} - c_{\mathit{ij}}\right )^{+} = f_{i}$ for all i ∈ I with y _i  = 1; or (2) the dual solution u is first obtained and then the primal solution sets y _i  = 1 for all i ∈ I with $\sum _{j\in J}\left (u_{j} - c_{\mathit{ij}}\right )^{+} = f_{i}$. The first strategy can be applied starting from any set of open facilities S (which can be obtained, for instance, with a greedy heuristic). The associated dual solution u(S) can be obtained by setting $u_{j}(S) =\min _{i\in S}c_{\mathit{ij}}$ for all j ∈ J (note that this solution need not satisfy condition (b)). The DUFLP objective function value for u _j (S) is

$$\displaystyle\begin{array}{rcl} D(u(S))& =& \sum \limits _{j\in J}u_{j}(S) -\sum \limits _{i\in I}\left (\sum \limits _{j\in J}\left (u_{j}(S) - c_{\mathit{ij}}\right )^{+} - f_{ i}\right )^{+} = {}\\ & & \sum \limits _{j\in J}\min _{i'\in S}c_{i'j} -\sum \limits _{i\in I}\left (\sum \limits _{j\in J}\left (\min _{i'\in S}c_{i'j} - c_{\mathit{ij}}\right )^{+} - f_{ i}\right )^{+} = {}\\ & & \sum \limits _{j\in J}\min _{i'\in S}c_{i'j} -\sum \limits _{i\notin S}\left (\sum \limits _{j\in J}\left (\min _{i'\in S}c_{i'j} - c_{\mathit{ij}}\right )^{+} - f_{ i}\right )^{+}. {}\\ \end{array}$$

Since the value of the primal solution associated with S is $Z(S) =\sum _{i\in S}f_{i} +\sum _{j\in J}\min _{i\in S}c_{\mathit{ij}}$, the deviation between the primal/dual values of S and u(S) is

$$\displaystyle{Z(S) - D(u(S)) =\sum _{i\in S}f_{i} +\sum _{i\notin S}\left (\sum \limits _{j\in J}\left (\min _{i'\in S}c_{i'j} - c_{\mathit{ij}}\right )^{+} - f_{ i}\right )^{+}.}$$

The above expression for the deviation suggests choosing S in order to satisfy $\sum _{j\in J}\left (\min _{i'\in S}c_{i'j} - c_{\mathit{ij}}\right )^{+} - f_{i} \leq 0$ for all $i\notin S$, since in this case the above deviation reduces to ∑ _i ∈ S f _i .

To illustrate the second strategy let u be a dual solution satisfying the optimality condition (b) above and define $I(u) =\{ i \in I\mid \sum _{j\in J}(c_{\mathit{ij}} - u_{j})^{+} - f_{i} = 0\}$. Assume further that $u_{j} \geq \mbox{ min}_{i\in I(u)}c_{\mathit{ij}}$. Consider now a set of facilities S(u) ⊆ I(u) satisfying $\max _{i\in I(u)}c_{\mathit{ij}} =\max _{i\in S(u)}c_{\mathit{ij}}$, for all i ∈ I and let $s_{j} =\{ i \in S(u)\mid c_{\mathit{ij}} < u_{j}\}$, j ∈ J. Then, D(u) = Z(S(u)) (see Proposition 3.2. in Cornuéjols et al. 1990). This means that under the above assumptions, S(u) is an optimal UFLP solution.

Note that D(u) = Z(S(u)) means that the optimal UFLP value coincides with that of its LP relaxation. Thus, in general, one should not expect to find a solution u that together with S(u) satisfies the conditions stated above. However the DUALOC heuristic (see Erlenkotter 1978; Bilde and Krarup 1977), which follows this spirit has proved to be extremely effective for finding optimal or near-optimal solutions for the UFLP. The basic idea is to start with $u = (u_{j})_{j\in J} = (\min _{i\in I}c_{\mathit{ij}})_{j\in J}$, and then progressively attempt to increase each component u _j while satisfying condition (b). If u _j can be increased, then its next value is $\min \{c_{\mathit{ij}}\mid c_{\mathit{ij}} > u_{j}\}$, provided that this value satisfies (b). If not, u _j is increased to the maximum possible value. Indeed, the outcome of the above heuristic depends on the order in which the indices in j ∈ J are considered. Necessary and sufficient conditions for the duality LP gap to be zero, which may lead to tighter bounds have been proposed in Mladenović et al. (2006). Heuristics in the same spirit have been proposed for other discrete facility location problems, like the one for the stochastic version of the FLP proposed in Louveaux and Peeters (1992).

4.2 The UFLP as the Optimization of a Supermodular Set Function

As mentioned, the UFLP can be stated as the minimization of a set function. In this section we see that an alternative formulation for the UFLP can be obtained by exploiting the supermodularity property of this set function, which has been observed by several authors, namely Spielberg (1969a), Frieze (1974), Babayev (1974), Fisher et al. (1978), and we relate such a formulation with a radius based formulation. We start by recalling some well-known results on supermodular set functions (see, e.g., Section III.3.1 in Nemhauser and Wolsey 1988) and introduce some additional notation.

Definition 3.1

Let N be a finite set, and Z a real-valued function on the subsets of N. The function Z is supermodular if $Z(S) + Z(T) \leq Z(S \cup T) + Z(S \cap T),\ \quad \forall S,T \subseteq N$.

For i ∈ N let $\rho _{i}(S) = Z(S \cup \{ i\}) - Z(S)$ be the incremental value of adding element i to the set S.

Lemma 3.1

Each of the following statements is equivalent and defines a supermodular set function.

• (a) $Z(S) + Z(T) \leq Z(S \cup T) + Z(S \cap T),\ \quad \forall S,T \subseteq N$ .

• (b) $Z(S \cup \{ i\}) - Z(S) \leq Z(T \cup \{ i\}) - Z(T),\ \quad \forall S \subset T \subset N$ and i ∈ N.

• (c) If, in addition, Z is non-increasing, then $Z(T) \geq Z(S) +\sum \limits _{i\in T\setminus S}\rho _{i}(S)$ , $\quad \forall S,T \subset I$ .

In the following we suppose that N is the set of potential facilities, i.e. N = I, and we consider as set function Z the cost function of UFLP solutions. That is $Z(S) =\sum _{i\in S}f_{i} +\sum _{j\in J}\min _{i\in I}c_{\mathit{ij}}$. To see that Z(. ) is supermodular we recall that a positive linear combination of supermodular functions is supermodular and we observe that $Z(S) = f(S) + c(S)$ with $f(S) =\sum _{i\in S}f_{i}$ and $c(S) =\sum _{j\in J}\min _{i\in I}c_{\mathit{ij}}$. Thus, it is enough to see that both f(. ) and c(. ) are supermodular. Because f(S) is linear, it is clear that it is supermodular. We next see that c(. ) is also supermodular.

Proposition 3.2

c(.) is supermodular and non-increasing.

Proof

We will use the characterization of supermodular functions of Lemma 3.1b. For $S \subset T \subset I$, and $i \in I\setminus T$,

$$\displaystyle\begin{array}{rcl} c(S \cup \{ i\}) - c(S)& =& \sum \limits _{j\in J}\left [\min _{i'\in S\cup \left \{i\right \}}c_{i'j} -\min _{i'\in S}c_{i'j}\right ] =\sum \limits _{j\in J}\min \left \{0,c_{\mathit{ij}} -\min _{i'\in S}c_{i'j}\right \} \leq {}\\ & &\sum \limits _{j\in J}\min \left \{0,c_{\mathit{ij}} -\min _{i'\in T}c_{i'j}\right \} =\sum \limits _{j\in J}\left [\min _{i'\in T\cup \left \{i\right \}}c_{i'j} -\min _{i'\in T}c_{i'j}\right ] = {}\\ & & c(T \cup \{ i\}) - c(T), {}\\ \end{array}$$

where the inequality follows since $\min _{i'\in S}c_{i'j} \geq \min _{i'\in T}c_{i'j}$ for all j ∈ J. Furthermore, c is non-increasing since

$$c(S \cup \{ i\}) - c(S) =\sum \limits _{j\in J}\left [\min _{i'\in S\cup \left \{i\right \}}c_{i'j} -\min _{i'\in S}c_{i'j}\right ] \leq 0.\qquad \qquad \qquad \square $$

For the function c(. ) the incremental value of adding element i to the set S is c(S ∪{ i}) − c(S). Hence, statement (b) of Lemma 3.1 can be rewritten as

$$\displaystyle{ c(T) \geq c(S)+\sum \limits _{i\in T\setminus S}\left [c(S \cup \{ i\}) - c(S)\right ] = c(S)+\sum \limits _{i\in T\setminus S}\left [c(S \cup \{ i\}) - c(S)\right ],\forall S,T \subset I. }$$

(3.47)

The UFLP formulation below exploits the supermodular property of z(. ) and c(. ) as well as the non-increasing property of c(. ). Consider the polyhedron

$$\displaystyle{P_{\mathit{SF}} = \left \{(\eta,x,y) \in \mathbb{R} \times \mathbb{B}^{\vert I\vert \times \vert J\vert }\times B^{\vert I\vert }:\eta \geq \sum \limits _{ i\in S}f_{i}y_{i} + c(S) +\sum \limits _{i\notin S}\rho _{i}(S)y_{i},\forall S \subseteq I\right \},}$$

where η is a continuous variable and $\mathbb{B}^{\vert I\vert \times \vert J\vert }$ and $\mathbb{B}^{\vert J\vert }$ are the domains of the binary vectors associated with the location and allocation variables x and y, respectively.

Theorem 3.1

Let T ⊂ I and $(\eta,x^{T},y^{T}) \in \mathbb{R} \times \mathbb{B}^{\vert I\vert \times \vert J\vert }\times \mathbb{B}^{\vert I\vert }$ , with x and y the incidence vectors of the UFLP solution associated with subset T. Then, $(\eta,x^{T},y^{T}) \in P_{\mathit{SF}}$ if and only if η ≥ Z(T).

Proof

If $(\eta,x^{T},y^{T}) \in P_{\mathit{SF}}$ then

$$\displaystyle{\eta \geq \sum \limits _{i\in T}f_{i}y_{i}^{T} + c(T) +\sum \limits _{ i\notin T}\rho _{i}(T)y_{i}^{T} =\sum \limits _{ i\in T}f_{i} + c(T) = Z(T).}$$

Suppose now that η ≥ Z(T). We have

$$\displaystyle\begin{array}{rcl} f(T)& =& \sum \limits _{i\in T}f_{i}y_{i}^{T} =\sum \limits _{ i\in T\cap S}f_{i}y_{i}^{T} +\sum \limits _{ i\in T\setminus S}f_{i}y_{i}^{T} {}\\ & =& \sum \limits _{i\in S}f_{i}y_{i}^{T} +\sum \limits _{ i\in T\setminus S}f_{i}y_{i}^{T},\qquad \mbox{ for all }S \subseteq I. {}\\ \end{array}$$

Since c is non-increasing supermodular, by (3.47), we also have

$$\displaystyle\begin{array}{rcl} c(T) \geq c(S) +\sum \limits _{i\in T\setminus S}\Big[c(S \cup \{ i\}) - c(S)\Big]& =& c(S) +\sum \limits _{i\notin S}\Big[c(S \cup \{ i\}) - c(S)\Big]y_{i}^{T}, {}\\ & & \mbox{ for all }S \subseteq I. {}\\ \end{array}$$

Thus, for all S ⊆ I

$$\displaystyle\begin{array}{rcl} Z(T) = f(T) + c(T) \geq \sum \limits _{i\in S}f_{i}y_{i}^{T} +\sum \limits _{ i\in T\setminus S}f_{i}y_{i}^{T} + c(S) +\sum \limits _{ i\notin S}\Big[c(S \cup \{ i\}) - c(S)\Big]y_{i}^{T}.& & {}\\ \end{array}$$

Hence, $\eta \geq Z(T) \geq \sum \limits _{i\in S}f_{i}y_{i}^{T} + c(S) +\sum \limits _{ i\notin S}\rho _{i}(S)y_{i}^{T},\mbox{ for all }S \subseteq I$.

Therefore, (η, y ^T, x ^T) ∈ P _SF and the result follows. □ 

As a consequence of Theorem 3.1, the UFLP can be stated as the following MIP (see Nemhauser and Wolsey 1981):

$$\displaystyle\begin{array}{rcl} \mbox{ minimize}\qquad \eta & &{}\end{array}$$

(3.48)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\quad \;\;\;\eta \geq \sum \limits _{i\in I}f_{i}y_{i} + c(S) +\sum \limits _{e\notin S}\rho _{i}(S)y_{i}\qquad \forall S \subseteq I^{{\ast}}& &{}\end{array}$$

(3.49)

$$\displaystyle\begin{array}{rcl} \qquad \qquad \quad \,\,\,\,\eta \geq 0\quad & &{}\end{array}$$

(3.50)

$$\displaystyle\begin{array}{rcl} \qquad \qquad \quad \,\,\,\,y_{i} \in \{ 0,1\}\qquad \qquad \qquad \qquad \qquad \qquad \,i \in I,& &{}\end{array}$$

(3.51)

where $I^{{\ast}} = I \cup \{ i^{{\ast}}\}$ and i ^∗ is a fictitious facility such that (1)$\ c_{i^{{\ast}}k} >\max _{i\in I}c_{\mathit{ij}}$, for all j ∈ J; and (2)$\ \sum _{j\in J}c_{i{\ast}j} >\max _{i\in I}(f_{i} +\sum _{j\in J}c_{\mathit{ij}})$. This assumption guarantees that at least one variable y _i is at value one in any optimal solution to the above formulation.

Taking into account the supermodularity of c(. ) we can obtain a tighter formulation by respectively substituting objective (3.48) and constraints (3.49) by

$$\displaystyle\begin{array}{rcl} \mbox{ minimize}\quad \sum \limits _{i\in I}f_{i}y_{i} +\sum \limits _{j\in J}\eta ^{j},& &{}\end{array}$$

(3.52)

$$\displaystyle\begin{array}{rcl} \mbox{ and}\quad \qquad & \eta ^{j} \geq \min _{i\in S}c_{\mathit{ij}} +\sum \limits _{i\notin S}\left [\min _{i'\in S\cup \left \{i\right \}}c_{i'j} -\min _{i'\in S}c_{i'j}\right ]y_{i},& \quad \forall S \subseteq I^{{\ast}},j \in J.{}\end{array}$$

(3.53)

The following observation indicates that only a polynomial number of constraints (3.53) is required to obtain a valid formulation for the UFLP.

Remark 3.1

For S ⊂ I and j ∈ J given, the right-hand side of their associated constraint (3.53) does not change if the summation is taken over all i ∈ I, since $\min _{i'\in S\cup \left \{i\right \}}c_{i'j} -\min _{i'\in S}c_{i'j} = 0$, for i ∈ S. Moreover, for any S ⊂ I, the value of min _i ∈ S c _ij will be one of the values c _ij , with i ∈ S. That is, for any S its associated constraint (3.53) can be written as

$$\displaystyle{\eta ^{j} \geq c_{\mathit{ sj}} +\sum \limits _{i\in I}(c_{\mathit{ij}} - c_{\mathit{sj}})^{-}y_{ i},\qquad \mbox{ for some }s \in S.}$$

To apply the above remark and obtain a formulation with a polynomial number of constraints, for each j ∈ J, we order the elements of I in non-decreasing values of their coefficients c _ij , and we denote by i _r the rth index according to that ordering. That is, $c_{i_{1}j} \leq c_{i_{2}j} \leq \ldots \leq c_{i_{m}j} \leq c_{i_{m+1}j}$, where $c_{i_{m+1}j} = c_{i^{{\ast}}j}$ is the allocation cost of customer j to the fictitious facility i ^∗.

Theorem 3.2

The UFLP can be formulated as

$$\displaystyle\begin{array}{rcl} (\mathit{SUFLP}) v_{S} = \mbox{ minimize}\quad \sum \limits _{i\in I}f_{i}y_{i} +\sum \limits _{j\in J}\eta ^{j}& &{}\end{array}$$

(3.54)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\quad \eta ^{j} \geq c_{ i_{r}j} +\sum \limits _{i\in I}(c_{\mathit{ij}} - c_{i_{r}j})^{\bar{}}\;y_{ i}\quad r = 1,\ldots,m + 1,\ j \in J& &{}\end{array}$$

(3.55)

$$\displaystyle\begin{array}{rcl} \eta ^{j} \geq 0j \in J& &{}\end{array}$$

(3.56)

$$\displaystyle\begin{array}{rcl} \quad y_{i} \in \{ 0,1\}i \in I.& &{}\end{array}$$

(3.57)

The proof which is based on Remark 3.1 is left to the reader. Formulation (3.54)–(3.57) involves | m | binary variables y and | J | continuous variables η. Its total number of constraints is (m + 1) | J | .

The reader familiar with Benders type reformulations (Benders 1962) will immediately observe that, in fact, constraints (3.55) are nothing but Benders cuts. Thus formulation (3.54)–(3.57) admits an alternative interpretation as a Benders type reformulation for the UFLP. The interested reader is addressed to the inspiring chapter by Magnanti and Wong (1990) for an extensive description of the application of Benders reformulations to the UFLP.

We close this section by interpreting SUFLP as a radius-based formulation. Such formulations have been broadly used in recent years for different types of location and hub location problems, after the work by Elloumi et al. (2004). Their main characteristic is the use of decision variables to model the service cost for customers. Using the above notation, in which, for j ∈ J, $c_{i_{r}j}$ denotes the rth smallest allocation cost for customer j, we define a new set of binary decision variables z _rj , r = 1, …, m, where z _rj  = 1 if and only if the allocation cost of customer j is at least $c_{i_{r}j}$. With these decision variables, the allocation cost of customer j can be written as the telescopic sum $c_{i_{1}j} +\sum _{ r=2}^{m}(c_{i_{r}j} - c_{i_{r-1}j})z_{\mathit{rj}}$, so that an alternative UFLP formulation is

$$\displaystyle\begin{array}{rcl} (\mathit{RUFLP}) v_{R} = \mbox{ minimize}\quad \sum \limits _{i\in I}f_{i}y_{i} +\sum \limits _{j\in J}\Bigg(c_{i_{1}j} +\sum _{ r=2}^{m}(c_{ i_{r}j} - c_{i_{r-1}j})z_{\mathit{rj}}\Bigg)& &{}\end{array}$$

(3.58)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\quad z_{\mathit{rj}} +\sum \limits _{\begin{array}{c}i\in I \\ c_{\mathit{ij}}<c_{i_{r}j}\end{array}}y_{i} \geq 1\quad \!r\,=\,1,\ldots,m + 1,\ j \in J& &{}\end{array}$$

(3.59)

$$\displaystyle\begin{array}{rcl} z_{\mathit{rj}} \in \{ 0,1\}\qquad \qquad \qquad \!j \in J,r = 1,\ldots,m + 1& &{}\end{array}$$

(3.60)

$$\displaystyle\begin{array}{rcl} \quad y_{i} \in \{ 0,1\}\qquad \qquad \qquad \!i \in I.& &{}\end{array}$$

(3.61)

The equivalence between both formulations can be established by observing that feasible solutions to SUFLP define feasible solutions to RUFLP and vice versa. Indeed, if (η, y) is feasible for SUFLP we obtain a feasible RUFLP solution by setting, for each j ∈ J, z _rj  = 0 for all r with $c_{i_{r}j} \geq \eta ^{j}$, and zero otherwise. Constraints (3.55) guarantee that (z, y) satisfies constraints (3.59) and is feasible for RUFLP. Conversely, we can also check that a feasible SUFLP solution can be obtained from a feasible RUFLP solution by setting for, j ∈ J, $\eta ^{j} = c_{i_{r^{{\ast}}}j}$ with $r^{{\ast}} =\arg \min \{ c_{i_{r}j}: y_{i_{r}} = 1\}$.

5 Polyhedral Analysis of the UFLP

This section concentrates on the polyhedral analysis of the UFLP. We assume the reader is familiar with the basic polyhedral concepts (an exposition can be found, for instance in Nemhauser and Wolsey 1988). Although any UFLP formulation can be analyzed from a polyhedral perspective, we focus on the set packing formulation for the UFLP, because it is the one that has received more attention from a polyhedral point of view. An alternative analysis to the one we develop next, based on a set partitioning UFLP formulation, can be found in Guignard (1980).

As indicated in Sect. 3.2 facility location problems can also be modeled as maximization problems in which the expression of the objective function is (3.17). In the case of the UFLP such a formulation can be easily transformed into a set packing one by doing the change of variables $\bar{y}_{i} = 1 - y_{i}$, i ∈ I; i.e. $\bar{y}_{i} = 1$ if and only if facility i is not opened. The objective function can be rewritten in terms of the new variables as $-\sum _{i\in I}f_{i} +\sum _{i\in I}f_{i}\bar{y}_{i} +\sum _{i\in I}\sum _{j\in J}p_{\mathit{ij}}x_{\mathit{ij}}$, whose maximization reduces to maximizing the objective $\sum _{i\in I}f_{i}\bar{y}_{i} +\sum _{i\in I}\sum _{j\in J}p_{\mathit{ij}}x_{\mathit{ij}}$ within the appropriate domain. Hence, a set packing formulation for the UFLP is

$$\displaystyle\begin{array}{rcl} (\mathit{KUFLP})\quad \mbox{ maximize }z =\sum _{i\in I}f_{i}\bar{y}_{i} +\sum _{i\in I}\sum _{j\in J}p_{\mathit{ij}}x_{\mathit{ij}}& &{}\end{array}$$

(3.62)

$$\displaystyle\begin{array}{rcl} \mbox{ subject to}\sum _{i\in I}x_{\mathit{ij}} \leq 1\qquad j \in J& &{}\end{array}$$

(3.63)

$$\displaystyle\begin{array}{rcl} x_{\mathit{ij}} +\bar{ y}_{i} \leq 1\quad \,\,\,i \in I,\forall j \in J\quad & &{}\end{array}$$

(3.64)

$$\displaystyle\begin{array}{rcl} x_{\mathit{ij}} \in \{ 0,1\}\qquad i \in I,\,\forall j \in J\quad & &{}\end{array}$$

(3.65)

$$\displaystyle\begin{array}{rcl} y_{i} \in \{ 0,1\}\qquad i \in I.& &{}\end{array}$$

(3.66)

Formulation KUFLP can be viewed as a set packing formulation and thus its set packing properties are inherited. For this we will consider the intersection graph, that we denote by G(m, n), with a node for each variable of KUFLP and with an edge for each pair of variables sharing a constraint in KUFLP.

In the following P ^mn and F ^mn denote the convex hull of the feasible solutions of KUFLP and its LP relaxation, LKUFLP, respectively. For m ^∗ ≤ m and n ^∗ ≤ n, we call m ^∗× n ^∗ adjacency matrix S to any m ^∗× n ^∗, 0-1 matrix with no zero row and no zero column. Given an adjacency matrix S and two ordered sets I ^S ⊆ I and J ^S ⊆ J, we denote by G ^S = (V ^S, E ^S) the subgraph of G(m, n) given by $V ^{S} =\{ x_{\mathit{ij}}:\ i \in I^{S},j \in J^{S},s_{\mathit{ij}}\neq 0\} \cup \{\bar{ y}_{i}:\ i \in I^{S}\}$, $E^{S} =\{ (x_{\mathit{ij}},x_{\mathit{kj}}):\ i,k \in I^{S},i < k,j \in J^{S},s_{\mathit{ij}} = s_{\mathit{kj}} = 1\}\cup \{(\bar{y}_{i},x_{\mathit{ij}}):\ i \in I^{S},j \in J^{S},s_{\mathit{ij}} = 1\}$. Finally, α(G) denotes the independence number of graph G, i.e., the maximal cardinality of a packing of nodes in G, and B denotes a cyclic matrix of type (k, t), i.e. its size is k × k and its rows are 0-1 vectors with t adjacent 1’s, which move one position to the right in each row.

Some relevant contributions on the polyhedral analysis of KUFLP are (in chronological order): Cornuéjols et al. (1977), Guignard (1980), Cornuéjols and Thizy (1982), Cho et al. (1983a,b), Myung and Tcha (1996), Cánovas et al. (2000, 2001, 2002, 2003), Baiou and Barahona (2009a) and Chen et al. (2012). New trends in this area relate to the study of how to adapt the known polyhedral properties of the UFLP to problems generalizing it. Nice examples are the papers by Hamacher et al. (2004) and by Baiou and Barahona (2009b). In both cases the authors give results allowing to directly adapt any valid inequality of the UFLP to the Hub Location Problem and the Two-Level Facility Location Problem, respectively. Next we summarize the main results in this area.

First of all, P ^mn is full-dimensional, i.e., dim$(P^{\mathit{mn}}) = \mathit{mn} + p$. Thus, two different facets of P ^mn always define two different sets of feasible solutions for KUFLP.

Cho et al. (1983a) have proven that for m ≤ 2 or n ≤ 2 the coefficients matrix of KUFLP is totally unimodular, so the polyhedral analysis is of little interest. They have also given a complete description of the facets of P ^mn when m = 3 or n = 3. Recently, Baiou and Barahona (2009a) and Chen et al. (2012) have presented new conditions for F ^mn to be integral, i.e., to have all its extreme points integral. Both papers define a particular type of odd cycles in the intersection graph of KUFLP without which the extreme points of the polyhedron F ^mn are integral.

The remainder of this section is divided in three parts: extreme points of F ^mn, valid inequalities and facets of P ^mn, and lifting procedures.

5.1 Extreme Points

We are aware of two papers dealing with the characterization of the fractional extreme points. Cornuéjols et al. (1977) give a characterization for the extreme points of F ^mn. Let $I_{f} =\{ i \in I: 0 <\bar{ y}_{i} < 1\},\ J_{0} =\{ j \in J: x_{\mathit{ij}} \in \{ 0,1 -\bar{ y}_{i}\}$ for all i and x _ij non-integer for some i} and let U be the | I _f  | × | J ₀ | matrix whose elements are

$$\displaystyle{u_{\mathit{ij}} = \left \{\begin{array}{ll} 1&\mbox{ if }x_{\mathit{ij}} > 0, \\ 0&\mbox{ if }x_{\mathit{ij}} = 0. \end{array} \right.}$$

Theorem 3.3 (Cornuéjols et al. 1977)

The fractional feasible solution (x,y) of LKUFLP is an extreme point of F ^mn if and only if

• (a) $1 -\bar{ y}_{i} =\max _{j}\{x_{\mathit{ij}}\}$ for all i ∈ I _f ,

• (b) for each j ∈ J, there is at most one i with $0 < x_{\mathit{ij}} < 1 -\bar{ y}_{i},$

• (c) the rank of U equals |I _f |.

Cánovas et al. (2001) have later provided a characterization for the extreme points of a more general polyhedron and proved that condition (a) of Theorem 3.3 follows from conditions (b) and (c). Cho et al. (1983a) make use of this characterization to prove that a certain family of valid inequalities can cut fractional solutions of LKUFLP. The results of Cánovas et al. (2001) also characterize the extreme points of the polyhedra associated with the FLP formulation in Leung and Magnanti (1989) and of other related problems.

5.2 Valid Inequalities and Facets

Next we present several families of valid inequalities of P ^mn. Further details and results can be found in Cho et al. (1983a) and Cánovas et al. (2002).

Cornuéjols et al. (1977) presented the first polyhedral study of the KUFLP. They proposed, without proof, the following family of valid inequalities of P ^mn

$$\displaystyle{ \sum _{i\in I^{C}}b_{\mathit{ij}}x_{\mathit{ij}} +\sum _{i\in I^{C}}\bar{y}_{i} \leq 2k -\lceil k/t\rceil, }$$

(3.67)

where k and t are integers such that $k = \mathit{tp} + 1$ for some integer p, B is a cyclic matrix of type (k, t) and I ^B ⊆ I,  J ^B ⊆ J are subsets of cardinality k. Later, Cornuéjols and Thizy (1982) proved that (3.67) is a facet.

Several well-known families of facets for the KUFLP with binary coefficients are discussed below:

Theorem 3.4 (Cho et al. 1983b)

Consider I ^S ⊆ I and J ^S ⊆ J. Then, the inequality

$$\displaystyle{\sum _{i\in I^{S}}\sum _{j\in J^{S}}s_{\mathit{ij}}x_{\mathit{ij}} +\sum _{i\in I^{S}}\bar{y}_{i} \leq \alpha (G^{S}),}$$

where s _ij = 0 or 1, is facet-defining for P ^mn (and different from a clique facet) if and only if S is a |I ^S |×|J ^S |, maximal mn-adjacency matrix.

A characterization of maximal mn-adjacency matrices can be found in Cho et al. (1983b). A special case of maximal mn-adjacency matrix gives rise to a concrete family of facet-defining inequalities of P ^mn:

Theorem 3.5 (Cornuéjols and Thizy 1982)

Consider ℓ and t such that 2 ≤ t < ℓ ≤ m and subsets P ⊆ I, D ⊆ J, such that $\vert D\vert = \left (\begin{array}{l} \ell\\ t \end{array} \right )$ , |P| = ℓ. Let A ^ℓt be the matrix whose columns are all vectors 0-1 with t ones and ℓ − t zeros. Then,

$$\displaystyle{\sum _{i\in I}\sum _{j\in J}a_{\mathit{ij}}^{\ell t}x_{\mathit{ ij}}+\sum _{i\in I}\bar{y}_{i} \leq \left (\begin{array}{l} \ell\\ t \end{array} \right )+t-1}$$

is a facet-defining inequality of P ^mn .

By exploiting the set packing structure of KUFLP, the odd holes in the intersection graph of KUFLP allow to define two new families of valid inequalities.

Theorem 3.6 (Cornuéjols and Thizy 1982)

The inequality

$$\displaystyle{ \sum _{i=1}^{3}x_{\mathit{ ii}} +\sum _{ i=1}^{3}x_{ (i+1)\ \bmod \ 3,i} +\sum _{ i=1}^{3}\bar{y}_{ i} \leq 4 }$$

is facet-defining for P ³³ .

Theorem 3.7 (Cornuéjols and Thizy 1982)

The inequality

$$\displaystyle{ x_{13} + x_{41} +\sum _{ i=1}^{5}x_{\mathit{ ii}} +\sum _{ i=1}^{5}x_{ (i+1)\ \bmod \ 5,i} +\sum _{ i=1}^{5}\bar{y}_{ i} \leq 7 }$$

is facet-defining for P ⁵⁵ .

Families of facet defining inequalities for KUFLP with general integer coefficients are also known.

Theorem 3.8 (Cánovas et al. 2000)

Let S be an r × c adjacency matrix satisfying

• (i) $\forall i_{1},i_{2} \in I^{S}\ \exists j \in J^{S}$ such that $s_{i_{1}j}s_{i_{2}j} = 1$ and

• (ii) $\forall (i,j) \in I^{S} \times J^{S}$ with $s_{\mathit{ij}} = 1\ \exists \ell\in I^{S}$ , ℓ ≠ i, such that s _ℓj = 1 and s _ih s _ℓh = 0 ∀h ≠ j.

Then,

$$\displaystyle{\sum _{i\in I^{S}}\sum _{j\in J^{S}}s_{\mathit{ij}}x_{\mathit{ij}} +\sum _{i\in I^{S}}\left (\sum _{j\in J^{S}}s_{\mathit{ij}} - 1\right )\bar{y}_{i} \leq \sum _{i\in I^{S}}\sum _{j\in J^{S}}s_{\mathit{ij}} -\vert I^{S}\vert + 1}$$

is a facet-defining inequality of P ^rc .

Theorem 3.9 (Cánovas et al. 2002)

Let S be the k × k adjacency matrix, k ≥ 3, given by

$$\displaystyle{S = \left (\begin{array}{cc} 0 & \mathbf{1}_{1\times (k-1)} \\ \mathbf{1}_{(k-1)\times 1} & I_{(k-1)\times (k-1)} \end{array} \right )}$$

Then,

$$\displaystyle{ \sum _{i\in I^{S}}\sum _{j\in J^{S}}s_{\mathit{ij}}x_{\mathit{ij}} + (k - 2)\bar{y}_{1} +\sum _{ i=2}^{k}\bar{y}_{ i} \leq 2k - 2 }$$

is a facet-defining inequality of P ^kk .

Theorem 3.10 (Cánovas et al. 2002)

Consider three numbers, k ≥ 5, 1 ≤ a < k − 3 and $b = k - 3 - a$ and let S be the k × k adjacency matrix given by

$$\displaystyle{S = \left (\begin{array}{ccccc} I_{a\times a}&\mathbf{0}_{a\times b}&\mathbf{0}_{a\times 1} & \mathbf{0}_{a\times 1} & \mathbf{1}_{a\times 1} \\ \mathbf{0}_{b\times a} & I_{b\times b} & \mathbf{1}_{b\times 1} & \mathbf{0}_{b\times 1} & \mathbf{1}_{b\times 1} \\ \mathbf{1}_{1\times a}& \mathbf{0}_{1\times b} & 1 & 0 & 0 \\ \mathbf{0}_{1\times a}& \mathbf{1}_{1\times b} & 0 & 1 & 0 \\ \mathbf{0}_{1\times a}& \mathbf{0}_{1\times b} & 1 & 1 & 1 \end{array} \right ).}$$

Then,

$$\displaystyle{\sum _{i\in I^{S}}\sum _{j\in J^{S}}s_{\mathit{ij}}x_{\mathit{ij}} +\sum _{i\in I^{S}\setminus \{k-2,k-1\}}\bar{y}_{i} + a\bar{y}_{k-2} + b\bar{y}_{k-1} \leq 2k - 3}$$

is a facet-defining inequality of P ^kk .

Theorem 3.11 (Cánovas et al. 2002)

Let B be the cyclic (2k + 1,2) matrix, k ≥ 1, and let S be the $(2k + 2) \times (4k + 2)$ adjacency matrix given by

$$\displaystyle{S = \left (\begin{array}{cc} B_{(2k+1)\times (2k+1)} & I_{(2k+1)\times (2k+1)} \\ \mathbf{0}_{1\times (2k+1)} & \mathbf{1}_{1\times (2k+1)} \end{array} \right ).}$$

Then,

$$\displaystyle{ \sum _{i\in I^{S}}\sum _{j\in J^{S}}s_{\mathit{ij}}x_{\mathit{ij}} +\sum _{ i=1}^{2k+1}2\bar{y}_{ i} + (k + 1)\bar{y}_{2k+2} \leq 6k + 3 }$$

is a facet-defining inequality of $P^{(2k+2)(4k+2)}$ .

Other types of inequalities have been suggested. For instance, Myung and Tcha (1996) develop a family of inequalities that may cutoff feasible solutions but not optimal ones. In particular, they propose a method for generating inequalities for a constrained KUFLP which considers its feasible domain and the objective function value, as well. For the sake of brevity, details are omitted here.

5.3 Lifting Procedures

The procedures that transform a valid inequality (facet) of a polyhedron $P^{m^{{\ast}}n^{{\ast}} }$ into a valid inequality (facet) of an higher polyhedron P ^mn,  m ≥ m ^∗ or n ≥ n ^∗, are called lifting procedures. Such results invite the study of small polyhedra. The following result indicates how to lift all the facets in the previous section.

Theorem 3.12 (Cho et al. 1983b)

Let

$$\displaystyle{ \sum _{i\in P}\sum _{j\in D}\pi _{\mathit{ij}}x_{\mathit{ij}} +\sum _{i\in P}\mu _{i}\bar{y}_{i} \leq \pi _{0} }$$

(3.68)

be a facet-defining inequality of $P^{m^{{\ast}}n^{{\ast}} }$. Then, (3.68) is also a facet-defining inequality of P ^mn for m ≥ m ^∗ , n ≥ n ^∗ .

Cho et al. (1983b) also give a constructive procedure for obtaining facets of P ^mn from cyclic adjacency matrices which do not define facets themselves.

Theorem 3.13 (Cho et al. 1983b)

Consider P ⊆ I, D ⊆ J, such that $\vert P\vert = \vert D\vert = q$ , q ≥ 3. Consider the facet-defining inequality of P ^qq given by

$$\displaystyle{\sum _{i\in P}\sum _{j\in D_{i}}x_{\mathit{ij}} +\sum _{i\in P}\bar{y}_{i} \leq 2q - 2}$$

where the sets D _i are all the different subsets of D with $\vert D_{i}\vert = q - 1$ . Suppose we add |S| + |T| facilities of I to P in such a way that each facility in S covers q − 1 destinations and each facility in T covers all the q destinations. Let |S| = s and |T| = t. Then,

$$\displaystyle{\sum _{i\in I\cup S\cup T}\sum _{j\in D_{i}}\pi _{\mathit{ij}}x_{\mathit{ij}} +\sum _{i\in I\cup S\cup T}\mu _{i}\bar{y}_{i} \leq (2q + s - 2)(q - 1) + t(q - 2)}$$

is a facet-defining inequality of $P^{(q+s+t)q}$ , where

• I. $\pi _{\mathit{ij}} =\mu _{i} = q - 1,\ \ i \in P \cup S,j \in D_{i}$ ,

• II. $\pi _{\mathit{ij}} =\mu _{i} = q - 2,\ \ i \in T,j \in D_{i}$ .

6 Conclusions

Fixed-Charge Facility Location Problems capture the main issues arising in fixed-charge location, so they are an excellent workbench for reviewing relevant aspects in this field. This was the aim of this chapter where we have covered a broad range of possibilities related to the modeling and the solution process of FLPs. Indeed the problems studied in this chapter can be seen as simplifications of more realistic models that take into account additional issues. We have studied deterministic static problems, without taking uncertainty into account (see, for instance, Lin 2009; Albareda-Sambola et al. 2011, 2013; Gao 2012) or temporal aspects (see, for instance, Albareda-Sambola et al. 2009a, 2010, 2012). Also, the way we have considered capacity constraints on the facilities may seem simplistic, since modular capacities (incurring their corresponding costs) can be more realistic (see, for instance, Gouveia and Saldanha da Gama 2006; Gourdin and Klopfenstein 2008; Correia et al. 2010). FLPs can be extended in various ways: One can consider more involved objective functions or multiple objectives (Fernández and Puerto 2003; Boland et al. 2006; Wu et al. 2006; Zanjirani Farahani et al. 2010), problems combining FLP decisions with network design (Melkote and Daskin 2011; Contreras et al. 2012), additional constraints (Albareda-Sambola et al. 2009b; Gendron and Semet 2009; Marín 2011), or the possibility of installing several facilities at the same site (Ghiani et al. 2002), to mention just a few possibilities. Some of these extensions are addressed in other chapters of this book.