Jose Gentile
email: josegentile@terra.com.br

Artur Alves Pessoa

Marcos Costa Roboredo

Michael Poss
email: michael.poss@lirmm.fr

Integer programming formulations for three sequential discrete competitive location problems with foresight

Keywords: Maximal Covering Location Problem, Competitive Location, Integer Programming, Stackelberg problem

We deal with three competitive location problems based on the classical Maximal Covering Location Problem. The environment of these problems consists of an open market with two non-cooperative firms (leader and follower), several customers and locations where facilities can be located. In order to capture the demand of the customers, the leader enters the market by locating a set of facilities knowing the potential locations where the follower can locate her facilities after the leader's decision. We consider here three pairs of objective functions for the leader/follower previously studied in the literature: maximizing/minimizing the demand captured by the leader, minimizing/maximizing the regret of the leader, maximizing the demand

Introduction

Location decision is a crucial issue in the strategic planning of a firm. A large part of research about location theory does not consider a potential competitor offering the same service or goods. In many real situations, it is vital to consider competition in the location decisions which leads to the competitive location problems (CLP). In these problems, two or more noncooperative firms compete to capture customers from a given market. The demand of each customer is partially or totally served by the facilities located by the firms according to some given rule. Various types of CLP have been studied, which are often classified according to the structure of the decision space (discrete or continuous) and the temporal relations among the decisions (sequential or simultaneous). Different objective functions can be pursued by each firm when they decide where to locate its facilities. For example, they might seek to maximize their own market share, their own profit, their own number of customers served, among others. A review of competitive location problems can be found in [START_REF] Eiselt | Competitive spatial models[END_REF]; [START_REF] Friesz | Competitive network facility location models: a survey[END_REF]; [START_REF] Eiselt | Competitive location models: A framework and bibliography[END_REF]; [START_REF] Eiselt | Sequential location problems[END_REF]; [START_REF] Kress | Sequential competitive location on networks[END_REF].

This paper deals with three CLP variants that adds competition to the classical maximal covering location problem (MCLP) proposed by [START_REF] Church | The maximal covering location problem[END_REF]. In MCLP, a firm should decide where to locate its facilities. After this decision, the demand of each customer in this market is said covered if there is a facility located by the firm within a threshold distance from the customer. In this context, the firm wishes to maximize the total covered demand.

In order to add competition to the MCLP, we consider two non-cooperative firms named leader and follower. The leader enters the market by locating her facilities knowing that the follower will react by doing the same. After the location decisions, each customer demand is covered by the closest facility that is located within a threshold distance from the customer. We consider three pair of objective functions for the leader and the follower, following [START_REF] Plastria | Discrete models for competitive location with foresight[END_REF]: the leader maximizes her covered demand and the follower minimize that value (worst case criterion), the leader minimizes her regret while the follower maximizes that value (regret criterion), and both the leader and the follower maximize their respective covered demands (stackelberg criterion). We refer to those three problems as WC-CMCLP, RE-CMCLP and ST-CMCLP, respectively. The WC-CMCLP and the RE-CMCLP were proposed by [START_REF] Serra | The maximum capture problem with uncertainty[END_REF] where the authors proposed an Integer Linear Programming (ILP) formulation for each problem considering a small number of possibilities for the follower's responses. The ST-CMCLP was proposed by [START_REF] Serra | Market capture by two competitors: The preemptive location problem[END_REF] where a simple heuristic was proposed for the problem. The three problems were revisited in [START_REF] Plastria | Discrete models for competitive location with foresight[END_REF] where a MILP formulation was proposed for each problem for the particular case where the follower is restricted to locating a unique facility. Recently, [START_REF] Seyhan | Network design under competitionTheses and Dissertations[END_REF] proposed a heuristic for the ST-CMCLP for the case where the decision space of the follower is constrained by linear constraints, refereed to as the general case hereafter.

Contributions. To the best of our knowledge, no exact algorithm had been proposed for any of the three problems in the general case, prior to the current manuscript. Hence, our main contributions lie in presenting MILP-based algorithms that can solve these problems for the general case. Specifically, we propose for each variant a MILP formulation with a polynomial number of variables and an exponential number of constraints. The constraints are then generated on demand in the course of branch-and-cut algorithms by solving MILP separation problems. While the MILP formulations derived for WC-CMCLP extend rather naturally the previous work from [START_REF] Roboredo | A branch-and-cut algorithm for the discrete (r| p)-centroid problem[END_REF], those presented for RE-CMCLP and ST-CMCLP require new insights on the problems studied. We provide numerical experiments assessing the efficiency of our algorithms on instances generated similarly to the procedure described in [START_REF] Plastria | Discrete models for competitive location with foresight[END_REF]. We also compare our method with the formulations proposed in [START_REF] Plastria | Discrete models for competitive location with foresight[END_REF] for the particular case where the follower locates a single facility and we also compare our algorithm for the general case of ST-CMCLP with the heuristic proposed in [START_REF] Seyhan | Network design under competitionTheses and Dissertations[END_REF].

Structure of the paper. We present in the next section a formal definition of the three variants considered in the paper, including a numerical toy example. Section 3 complements the above literature review. Section 4 contains the main contributions of the paper, namely, the MILP formulations for the three problems as well as for the separation problems. The algorithmic details are provided in Section 5 and thorough numerical experiments are presented in Section 6, and in the supplementary material available online. The paper is finally concluded in Section 7.

The problems

We define next the three problems formally. We consider three sets: the set of customers, denoted J, the set of leader potential facilities, denoted L, and the set of follower potential facilities, denoted F . Let x l ∈ {0, 1} |L| and x f ∈ {0, 1} |F | be binary decision variables indicating which facilities are located by the leader and the follower, respectively. We restrain the sets of facilities that can be located by the leader and the follower by X l ⊆ {0, 1} |L| and X f ⊆ {0, 1} |F | , respectively. Sets X l and X f can, for instance, be defined by one ore more budget constraints. Specifically, locating facility i ∈ L ∪ F would incur a cost of κ i and the leader and the follower would dispose of budgets B l and B f , respectively. We could also suppose that X l (resp. X f ) contains incompatibility constraints, forbidding the leader (resp. the follower) to simultaneously locate pairs of given facilities. For each pair (i, j) ∈ (L ∪ F ) × J, we denote by d ij the distance between facility i and customer j. Finally, each facility i ∈ L ∪ F has a radius of δ i that restrains the customers that it can attend. Each customer's demand w j is totally served by the closest facility i ∈ L ∪ F that satisfies δ i ≥ d ij . Ties are broken in favor of the follower's facilities, and ties between facilities of the same firm are broken arbitrarily.

The difference among the problems lie in the objective functions of the leader and the follower. In the WC-CMCLP, the leader aims to maximize its market share while the follower aims to minimize the leader market share. In the RE-CMCLP, the leader aims to minimize its maximum regret while the follower aims to maximize the leader's maximum regret. The regret of the leader is given by the difference between the maximum demand served by the leader, if the follower's decision were previously known, and the demand actually served by this firm. Finally, in the ST-CMCLP both the leader and the follower aim to maximize their own market share.

The three problems can be cast as special cases of the following Bilevel Integer Programming Problem (BIP). Let us denote the objective functions of the leader and the follower by g l (x l , x f ) and g f (x l , x f ), respectively.

max g l (x l , x f ) (1) s.t. x l ∈ X l (2) x f ∈ arg max g f (x l , x f ) (3) s.t. x f ∈ X f . (4)
To ease the definition of the functions g l and g f used in each of the three variants studied in the paper, we introduce sets J l (x l , x f ) ⊆ J and J f (x l , x f ) ⊆ J that denote the sets of customers that are served by the leader and the follower, for the locating (x l , x f ), respectively. We consider the following specific functions g l and g f :

WC-CMCLP: g l (x l , x f ) = j∈J l (x l ,x f ) w j and g f (x l , x f ) = -g l (x l , x f ).
RE-CMCLP: Let x * (x f ) ⊆ {0, 1} |L| denote the leader best response knowing that the follower will locate the facilities indicated by x f . Hence, the regret of the pair (x l , x f ) is given by

Regret(x l , x f ) = j∈J l (x * (x f ),x f ) w j - j∈J l (x l ,x f ) w j , (5)
yielding the objective functions g l (x l , x f ) = -Regret(x l , x f ) and

g f (x l , x f ) = -g l (x l , x f ). ST-CMCLP: g l (x l , x f ) = j∈J l (x l ,x f ) w j and g f (x l , x f ) = j∈J f (x l ,x f ) w j .
Let us make some observations on the structure of the three variants of CMCLP defined above. First, when each pre-specified distances δ i is large enough to cover all customers, we have that J l ∪ J f = J so that the WC-CMCLP and ST-CMCLP are equivalent. In general however, we have that J l ∪ J f ⊂ J and these problems are different, see the toy examples below. Second, for WC-CMCLP and RE-CMCLP, we have g f (x l , x f ) = -g l (x l , x f ) so that both problems can be reformulated as max Reformulation ( 6) better sheds light on the names worst-case and regret used to refer to these problems. Notice also that while (6) resembles robust min max optimization, the integrality restriction in X f make the problem fundamentally different from robust optimization wherein the inner optimization problem is defined over real variables. The integrality of the optimization vector x f also implies that the algorithms described in this paper, based on constraint generation with MILP separation problems, are not related to Benders' decomposition, which relies on LP separation problems. Differently from Benders' decomposition, our approaches crucially rely on the fact that the feasibility set X l (resp. X f ) does not depend on x f (resp. x l ), which allows us to propose in Section 4 models containing specific constraints for each vector in X f . We illustrate below the above formal definition on a toy example in which J l ∪ J f ⊂ J. The example contains twelve customers (|J| = 12), each having a demand of one unit, two potential facilities for the leader (L = {L 1 , L 2 }) and three potential facilities for the follower (F = {F 1 , F 2 , F 3 }). Sets X l and X f are characterized by the fixed costs κ i and the budgets B l and B f are unitary. In other words, both the leader and follower can locate a unique facility. The distances d ij between the potential facilities and the customers, the radius δ i and the demands w j are given by Table 1 implicitly. That table shows the total demand served by the leader and the follower in this order for each possible pair of strategies of the leader and the follower.

x l ∈X l min x f ∈X f g l (x l , x f ). ( 6
)
According to table 1 if the leader locates the facility L 2 and the follower locates F 1 then the leader serves a total demand of three units while the follower serves a total of seven units. Note that in the worst case, the leader serves at least four and three units when she locates L 1 and L 2 , respectively. Hence, when we consider the WC-CMCLP, the leader locates the facility associated to the maximum of these two numbers, L 1 . In the ST-CMCLP the leader's location decision is made in the following way. On the one hand, if the leader locates L 1 then the follower locates F 3 , which is the facility that maximizes her market share. Hence, the leader would serve four units. On the other hand, if the leader locates L 2 then the follower locates F 1 . Consequently, the leader would serve three units. Observing the two cases, the leader locates L 1 . Note that, while the leader locates L 1 in the optimal solutions to WC-CMCLP and ST-CMLP, the decisions of the follower are different, locating F 2 in the former and F 3 in the latter.

To identify which strategy would be used by the leader in the RE-CMCLP, we first construct Table 2 containing the values of Regret for each pair of strategies of the leader and the follower. The table is filled in the following way. Suppose that the leader locates the facility L 2 and the follower locates F 1 . Hence, the leader serves a total demand of three units but she could have served five units if she had located L 1 . Hence the leader's regret is 5 -3 = 2 units for the pair (L 2 , F 1 ). The purpose of the leader is to minimize her maximal regret. If the leader locates L 1 , the greatest regret is 3 (follower locates F 2 ). If the leader locates L 2 , the greatest regret is 2 (follower locates F 1 ). Therefore the leader should locate L 2 , remaining with a regret of at most 2.

Review of the literature

The WC-CMCLP, the RE-CMCLP and the ST-CMCLP can be seen as special Bilevel Integer Programming Problems where the first level decision consists of choosing where the leader locates her facilities while the second level is associated with the follower's location decisions. Yet, the WC-CMCLP and the RE-CMCLP are very special cases of BIP since they can be rewritten as min max optimization problems. The literature is rather scarce when it comes to exact methods for general BIPs. Branch-and-bound algorithms for linear BIP were proposed by [START_REF] Moore | The mixed integer linear bilevel programming problem[END_REF] and [START_REF] Bard | An algorithm for the discrete bilevel programming problem[END_REF]. However, these are able to solve only instances with up to 10 general integer variables and 35 binary variables for the first level problem. Other approaches are based on specific characteristics of the optimization problem under study such as a decomposition method based on super valid inequalities, see [START_REF] Israeli | Shortest-path network interdiction[END_REF]; O'Hanley and [START_REF] O'hanley | Designing robust coverage networks to hedge against worst-case facility losses[END_REF], cutting plane algorithms [START_REF] Taşkın | Cutting plane algorithms for solving a stochastic edge-partition problem[END_REF], among others. Recently, Fischetti et al. ( 2016) have proposed generic algorithms to solve larger BIP to optimality, relying on intersection cuts.

Coming back to the CMLP, [START_REF] Plastria | Discrete models for competitive location with foresight[END_REF] revisited the three aforementioned variants and proposed a MILP formulation for each of them considering the particular case where the follower locates a unique facility. In order to show the robustness of the formulations, the authors presented several numerical results for randomly generated instances. Although the results are able to solve instance of moderate size efficiently, it does not seem possible to extend their formulations to the more general problems considered herein. Recently, [START_REF] Seyhan | Network design under competitionTheses and Dissertations[END_REF] considered the general case of the ST-CMCLP and propose a greedy heuristic for the problem. That heuristic is based on a MILP formulation where a set of variables and linear constraints are used to compute the follower response in a greedy heuristic way.

A closely related problem is the discrete (r|p)-centroid problem, proposed by [START_REF] Hakimi | On locating new facilities in a competitive environment[END_REF]. In the (r|p)-centroid problem, the coverage radii are infinite, δ i = +∞, and all fixed costs κ i are unitary. In other words, each customer is covered by one of the facilities and there is a fixed number of facilities to be located by the leader and the follower. Since [START_REF] Noltemeier | Multiple voting location and single voting location on trees[END_REF] proved that the (r|p)-centroid problem is Σ p 2 -hard, the previous observation implies that both the WC-CMCLP and the ST-CMCLP are Σ p 2hard. Moreover, some techniques used for the (r|p)-centroid problem can be adapted for the WC-CMCLP and ST-CMCLP. Specifically, the algorithm used in this paper for the WC-CMCLP is an adaptation of the branch-andcut algorithm proposed by [START_REF] Roboredo | A branch-and-cut algorithm for the discrete (r| p)-centroid problem[END_REF] for the (r|p)-centroid problem.

MILP Formulations for the problems

In this section, we present for each of the three problems a MILP formulation with a polynomial number of variables and a exponential number of constraints together with a compact MILP formulation for separating the exponential number of constraints.

We use the following notations in the formulations: let S f be the set that contains the ground sets of all vectors in X f , that is, the set of feasible strategies for the follower. Formally, each S 0 ∈ S f represents a subset of F such that the vector x f defined by x f i = 1 for i ∈ S 0 and x f i = 0 otherwise belongs to X l . Furthermore, for each customer j ∈ J and for each S 0 ∈ S f , we define d(S 0 , j) = min {d kj |k ∈ S 0 }. Finally, for each customer j ∈ J, the sets

L (j) = {i ∈ L|d ij ≤ δ i } and F (j) = {i ∈ F |d ij ≤ δ i }
contain the facilities of the leader and the follower that can potentially cover customer j.

MILP formulation for the WC-CMCLP

Let z wc be a non-negative continuous variable indicating the total demand served by the leader after the follower's response. For each j ∈ J and i ∈ L, the binary first level variable y l ij is equal one if and only if the facility i is located by the leader to try to serve customer j. The formulation follows. max z wc (7)

s.t. y l ij ≤ x l i , ∀j ∈ J, ∀i ∈ L (8) i∈L y l ij = 1, ∀j ∈ J (9) z wc ≤ j∈J i∈L (j) d ij <d(S 0 ,j) w j y l ij ∀S 0 ∈ S f (10) y l ij ∈ {0, 1} , ∀i ∈ L, ∀j ∈ J (11) z wc ≥ 0, (12)
x l ∈ X l . ( 13
)
The objective function (7) maximizes the total demand served by the leader after the follower's response. Constraints (8) ensure the consistency between variables x l and y l . Constraints (9) indicate that for each customer j, the leader locates exactly one facility to try to serve customer j. To explain constraints (10), consider a given set S 0 ∈ S f and a customer j ∈ J. Then, i∈L (j) d ij <d(S 0 ,j) w j y l ij is equal to w j only if the facility chosen by the leader is closer than the closest admissible facility of the follower in strategy S 0 . Hence, summing up over j yields the revenue of the leader for the follower strategy S 0 and writing the constraint for each S 0 ∈ S f yields the worst-case among all strategies possible for the follower. Note that ( 10) is composed of an exponential number of constraints. Hence, it is necessary to solve the separation problem associated to (10) in order to include in the formulation only the necessary constraints.

Given a relaxed leader solution (z wc , x l , y

l ) ∈ R + × [0, 1] |I| × [0, 1]
|I|×|J| possibly violating some of the constraints in (10), the separation problem for the constraints (10) consists of finding the follower's strategy that minimizes the total demand served by the leader. That strategy can be found by solving the integer programming model described below.

Recall that, for each k ∈ F , x f i is a binary variable indicating whether the follower locates facility k. Similarly, for each j ∈ J and k ∈ F , let the binary variable y f kj indicate if the facility k is the closest facility of the follower to customer j. The formulation follows.

min j∈J k∈F (j)     w j i∈L (j) d ij <d kj y l ij     y f kj (14) s.t. y f kj ≤ x f k , ∀j ∈ J, ∀k ∈ F (15) k∈F y f kj = 1, ∀j ∈ J (16) y f kj ∈ {0, 1} , ∀k ∈ F, ∀j ∈ J (17) x f ∈ X f . ( 18
)
The objective function ( 14) minimizes the total demand served by the leader. Constraints (15) ensure the consistency between the variables y f and x f . Constraints ( 16) indicate that for each customer j, the follower locates exactly one facility to try to serve customer j.

The formulation ( 7) -( 12) for the leader problem and the formulation ( 14) -( 18) for the separation problem were adapted from the formulations presented by [START_REF] Roboredo | A branch-and-cut algorithm for the discrete (r| p)-centroid problem[END_REF] for the (r|p)-centroid problem.

MILP formulation for the RE-CMCLP

We present below a MILP formulation for the RE-CMCLP. The variables x f , y f used below have the same meaning as in ( 7) -( 12). Let z re be a nonnegative continuous variable indicating the worst regret for the leader. For each S 0 ∈ S f we define z * (S 0 ) as the largest demand served by the leader if she knows that the follower strategy is S 0 . Recalling the definition (5) from Section 2, we can define z * (S 0 ) formally as

z * (S 0 ) = j∈J l (x * (x f 0 ),x f 0 ) w j ,
where

x f 0i = 1 for i ∈ S 0 and x f 0i = 0 for i ∈ F \ S 0 . The formulation follows. min z re (19) s.t. y l ij ≤ x l i , ∀j ∈ J, ∀i ∈ L (20) i∈L y l ij = 1, ∀j ∈ J (21) z re ≥ z * (S 0 ) - j∈J i∈L (j) d ij <d(S 0 ,j) w j y l ij ∀S 0 ∈ S f (22) y l ij ∈ {0, 1} , ∀i ∈ L, ∀j ∈ J (23) z re ≥ 0, ( 24
)
x l ∈ X l . ( 25
)
The above formulation is similar to the formulation provided in the previous section, with the following differences. First, the objective function ( 19) minimizes the worst regret z re , while objective function (7) maximizes the worst revenue. Second, and more importantly, constraints (22) involve a constant term, z * (S 0 ), that is not present in (10). Again, the number of constraints in ( 22) is typically exponential so that the constraints are generated on demand in a branch-and-cut algorithm. The separation problem associated to ( 22) is defined in the following way. Given a relaxed leader solution (z re , x l , y l ) ∈ R + × [0, 1] |I| × [0, 1] |I|×|J| possibly violating some of the constraints in ( 22), the separation problem for the constraints (22) consists of finding the feasible follower strategy that maximizes the regret of the leader. That strategy can be found by solving the a MILP model introduced next.

Recall that the regret of the leader is given by a difference of two terms where the first one is associated to the best leader strategy given a feasible follower strategy. From now on, we refer to that leader as the virtual leader. According to the notations introduced before, for each i ∈ L, the binary variable x * i is equal one if and only if the virtual leader locates facility i. For each j ∈ J and i ∈ L, the binary variable y * ij is equal one if and only if facility i is used by the virtual leader to serve customer j. Before proceeding with the definitions used in the formulation, let us make a simple, yet crucial, observation. In the separation problem, variables x * and x f purse the same objective, that is, maximizing the regret. Hence, although the separation problem involves decision variables for the (virtual) leader and the follower, it is not a BIP. As we show below, the separation problem can in fact be modeled quite naturally as a MILP with polynomial numbers of variables and constraints.

For each j ∈ J and k ∈ F , the binary variable v f kj is equal to is equal to 1 if and only if the follower does not locate facility k (x f k = 0) and there is no facility located by the follower closer to customer j than k (x f k = 0, ∀k ∈ F |d k j < d kj ), otherwise the variable is equal to 0. Finally the separation model also relies on variables x f and y f already defined for the formulation (7) -( 12). In the formulation below, we also use the constant θ(k, j) to denote the k-th potential facility of the follower closer to customer j, for each customer j ∈ J and each follower potential facility k ∈ F . max j∈J i∈L (j)

w j y * ij - j∈J k∈F (j)   w j i∈L (j)|d ij <d kj y l ij   y f kj (26) s.t. y f kj ≤ x f k , ∀j ∈ J, ∀k ∈ F (27) k∈F y f kj = 1, ∀j ∈ J (28) y * ij ≤ x * i , ∀j ∈ J, ∀i ∈ L (29) i∈L y * ij = 1, ∀j ∈ J (30) y * ij + k∈F (j)|d kj ≤d ij y f kj ≤ 1, ∀j ∈ J, ∀i ∈ L (j) (31) v f θ(1,j)j = 1 -x f θ(1,j) , ∀j ∈ J (32) v f kj ≤ 1 -x f k , ∀k ∈ F, ∀j ∈ J (33) v f θ(k,j)j ≥ v f θ(k+1,j)j , ∀k ∈ {1, ..., |F | -1} , ∀j ∈ J (34) y f θ(1,j)j = 1 -v f θ(1,j)j , ∀j ∈ J (35) y f θ(k,j)j = v f θ(k-1,j)j -v f θ(k,j)j , ∀k ∈ {2, ..., |F |} , ∀j ∈ J (36) y f kj ∈ {0, 1} , ∀j ∈ J, ∀k ∈ F (j) (37) y * kj ∈ {0, 1} , ∀j ∈ J, ∀i ∈ L (j) (38) x f ∈ X f , (39)
x * ∈ X l .

(40)

The objective function (26) maximizes the leader regret. Constraints (31) ensure that if y * ij is equal 1, all facilities located by the follower are further from j than facility i. Consider then constraints (32) -( 36) and suppose that these constraints are removed from the formulation. Then, the virtual leader and the follower can falsely increase the optimal solution cost by letting the follower try to capture the customer by a distant facility instead of assigning her closest facility. This increases the profit of the virtual leader and reduces the profit of the follower, thus falsely increasing the optimal solution cost. Constraints (32) ensure that if the follower locates her closest facility from customer j, then the corresponding component of v is equal to 0. Otherwise, the component of v is equal to 1. Constraints (33) ensure that if the follower locates facility k, v f kj is equal to 0, for each customer j. Constraints (34) ensure that if the variable v f kj corresponding to the k-th closest facility from customer j is equal to 0, then the subsequent (from k + 1 until |F |) variables are also equal to 0. Constraints ( 35) and ( 36) ensure the consistency between the variables y f and v. Constraints (35) ensure that if follower locates the closest facility from customer j, then y f kj is equal to 1 and v f kj is equal to 0. Otherwise, y f kj is equal to 0 and v f kj is equal to 1. Constraints (36) ensure that if the k-th potential facility closest from customer j is the facility located by the follower closest to customer j, then y f θ(k,j)j is equal to 1, v f θ(k-1,j)j is equal to 1 and v f θ(k, j)j is equal to 0.

It is worth noting that constraints (32) -( 36) can be relocated by

y f kj + x f k ≤ 1, ∀j ∈ J, ∀k ∈ F (j), ∀k ∈ F (j)|d k j < d kj , (41)
eliminating the variables v from the formulation. However, despite having a simpler description than the previous ones, constraints (41) corresponds to O(|J||F | 2 ) inequalities. Unreported results showed that constraints (32) -( 36) are numerically more efficient than constraints (41) for the large instances.

MILP formulation for the ST-CMCLP

We present next a MILP formulation for the ST-CMCLP. Differently from the formulations proposed for the previous two problems, the formulation proposed here for the ST-CMCLP contains variables related to both the leader and the follower strategies. As before, these variables are respectively denoted by x l and y l , and x f and y f , respectively. In addition, we introduce binary variable z l j (resp. z f j ) that is equal to one if and only if costumer j is served by the leader (resp. follower). We also define the vector of optimization variables v l and the constants λ, which are the counterpart of v and θ for the leader's strategy. The variables ensure that y l is set to 1 for the closest facility. The formulation follows. max j∈J w j z l j (42) subject to:

y l ij ≤ x l i ∀j ∈ J, ∀i ∈ L (43) y f kj ≤ x f k ∀j ∈ J, ∀k ∈ F (44) i∈L y l ij = 1 ∀j ∈ J (45) k∈F y f kj = 1 ∀j ∈ J (46) z l j + z f j ≤ 1 ∀j ∈ J (47) z l j ≤ i∈L (j) y l ij ∀j ∈ J (48) z f j ≤ k∈F (j) y f kj ∀j ∈ J (49) z l j ≥ k∈L (j)|d kj ≤d ij y l kj - k∈F (j)|d kj ≤d ij y f kj ∀j ∈ J, ∀i ∈ L (j) (50) z f j ≥ k∈F (j)|d kj ≤d ij y f kj - k∈L (j)|d kj ≤d ij y l kj ∀j ∈ J, ∀i ∈ F (j) (51) v l λ(1,j)j = 1 -x l λ(1,j) ∀j ∈ J (52) v l ij ≤ 1 -x l i ∀j ∈ J, ∀i ∈ L (53) v l λ(i,j)j ≥ v l λ(i+1,j)j ∀j ∈ J, ∀i = 1, ..., L -1 (54) y l λ(1,j)j = 1 -v l λ(1,j)j ∀j ∈ J (55) y l λ(i,j)j = v l λ(i-1,j)j -v l λ(i,j)j ∀j ∈ J, ∀i = 2, ..., L (56)
j∈J

w j z f j ≥ j∈J: S 0 ∩F (j) =∅ w j 1 - i∈L (j): d ij <min{d kj |k∈S 0 } y l ij ∀S 0 ∈ S f (57) y l ij , y f kj , z l j , z f j ∈ {0, 1} ∀j ∈ J, ∀i ∈ L, ∀k ∈ F, (58)
x l ∈ X l , (59)

x f ∈ X f . ( 60
)
The objective function (42) maximizes the leader market share. The constraints ( 43)-( 46) are identical to those introduced in the previous formulations. Constraints (47) ensure that each costumer j be served either by the leader or the follower. Constraints (48) (resp. ( 49)) ensure that if a costumer is served by the leader (resp. follower), the nearest facility from this costumer located by the leader (resp. follower) is within the coverage radius. Constraints (50) ensure that if costumer j is not covered by the leader (resp. follower), the nearest facility from this costumer, located within coverage by the leader, is not closer to those located within coverage by the follower (resp. leader). Constraints ( 52) -( 56) are the counterparts of constraints ( 32) -(36) for the leaders variables. As in the RE-CMCLP, these 5 group of constraints could be relocated by a single one which corresponds to O(|J||F | 2 ) inequalities. Again, unreported experimental results showed that the use of constraints ( 52) -( 56) obtained better results for large instances. There was also a quick explosion of the constraint number in the case where a single group of constraints is used.

Finally, constraints (57) ensure that the follower chooses her best location. In other words, the constraints ensure that, given the strategy taken by the leader, the follower will pick up the one which maximizes her covered demand. Note that the right-hand side of constraints (57) shows the demand served by the follower, given her strategy S 0 and the leader strategy defined by variables y l . More explicitly, this demand is the difference between all demand that the follower could cover and the demand taken by the leader due to her closer facilities. There is a constraint (57) for each feasible strategy for the follower S 0 . As this number of constraints tends to be exponential, the constraints are added on demand during a branch-and-cut algorithm. We propose below an exact ILP formulation problem to separate the cuts (57) in the line of those proposed in for the other two variants.

Given a relaxed leader solution (x l , y l , z

l ) ∈ [0, 1] |I| × [0, 1] |I|×|J| × [0, 1] |J|
for the model ( 42) -( 58) possibly violating some of the constraints (57), the separation problem amounts to find the follower strategy that maximizes the violation of the constraint, which is to maximize the right side of (57).

max

j∈J k∈F   w j i∈L (j)|d kj ≤d ij y l ij   y f kj (61) s.t. y f kj ≤ x f k , ∀j ∈ J, ∀k ∈ F (62) k∈F y f kj = 1, ∀j ∈ J (63) y f kj ∈ {0, 1} , ∀k ∈ F, ∀j ∈ J (64)
x f ∈ X f . (65)

Details of the branch-and-cut algorithms

The exact algorithms for the WC-CMCLP, the RE-CMCLP and the ST-CMCLP are built on the top of the branch-and-cut algorithms that solve the models given by, respectively, ( 7) -( 12), ( 19) -( 25) and ( 42) -( 58) using commercial solvers. Constraints (10), ( 22) and ( 57) are added through cut callbacks by solving, respectively, the separation problems ( 14) -( 18), ( 26) -( 40) and ( 61) -( 64). Notice that our separation algorithms can be used to separate cuts over fractional solutions along the branch-and-bound tree. We did it only for the ST-CMCLP where it improved the results significantly. More specifically, we separate cuts over fractional solutions at the root node until the relative difference between the current relaxation and the best integer solution found so far drops below a given threshold . We also limited the number of separations over fractional solutions to 200.

For the three problems, we also used the following technique to obtain quickly feasible integer solutions. Every time we reach an integer branchand-bound node that violates some of the missing constraints, the algorithm inserts the following incumbent solution: the leader variables are set to their values in the current node, while the follower variables are set to their values in the optimal solution of the separation problem. Note that the time spent by this strategy is negligible.

For the ST-CMCLP, we observed that it takes too much time to find good integer solutions even using the previous technique. Therefore, we propose the following procedure able to transform fractional solutions into feasible integer ones. Whenever a fractional relaxed solution does not violate any missing inequality, we take the solution of the follower obtained from solving the separation problem and compute the leader strategy that maximizes her covered demand. This amounts to solve a MILP very close to formulation ( 61) -( 64), exchanging the roles of the leader and the follower. In a second step, we find a new follower solution running model ( 61) -( 64) based on the leader solution from the previous step. The strategies of the leader and follower found in the previous two steps form a feasible integer solution to the problem, which is fed to the algorithm. Note that the computational time of this procedure require solving two MILP formulations.

Computational Results

In this section, we present our computational results. The tests were coded in C++, using CPLEX 12.5.1, and the experiments were conducted on a computer with an Intel core i7-4790 3.60GHz CPU and 16 GB of memory running the windows 8 operating system. A single thread was used for the tests. All instances used in this paper are available in www.logis.uff.br/ ~roboredo/instances.

We tested our three methods on randomly instances generated similarly to [START_REF] Plastria | Discrete models for competitive location with foresight[END_REF]. Specifically, the coordinates of the customers and facilities are randomly distributed on square grids, where each grid cell has integer positive coordinates. There are not common potential facilities for the leader and for the follower (L ∩ F = ∅). The potential facilities for the follower (set F ) are those cells for which sum of the coordinates is a multiple of 3 while the potential facilities for the leader (set L) consists of all other cells, so approximately |L| ≈ 2|F |. We considered the euclidean distances between customers and facilities. Customer demands w j and fixed costs κ i were integers uniformly generated in [50, 250] and [5, 10], respectively. The instance types and their characteristics are summarized in Table 3.

For each type of instance, we considered the following covering radii, identical for all facilities: 1, √ 2, 2, √ 5, √ 8, 3, √ 10, √ 13 and 4. Sets X l and X f are defined by binary restrictions and single budget constraints, defined by the budgets B l = B f ranging in {15, 25, 35}.

In sections 6.1, 6.2 and 6.3 we respectively present average statistics considering all covering radii for the WC-CMCLP, the RE-CMCLP and the ST- CMCLP. We provide detailed results in the supplementary material available online. Section 1 therein presents the comparison between our methods and the one proposed in [START_REF] Plastria | Discrete models for competitive location with foresight[END_REF] for the particular case where the follower places just one facility. Section 2 therein presents detailed statistics of the branch-and-cut algorithms for each one of the instances tested. Finally,

Results for the WC-CMCLP

Table 4 presents several statistics of our method for the WC-CMCLP. Specifically, for each type of instance and each budget, the table shows average results considering all covering radii. The following headers are used for the columns. Column Budget indicates the budget of the firms. Column Type indicates the type of the instance (according Table 3). Obj indicates the total demand covered by the leader at the optimal solution, Gap Root(%) indicates the percentage of the relative difference between the best upper bound obtained at the root node and the optimal solution, Time Root(s) indicates the CPU times in seconds spent at the root node, #Nodes indicates the total number of nodes of the B&B tree, #Sep indicates the number of separation problems solved, #Cuts indicates the total number of cuts generated by separation problems, #Time Sep(s) and Time total(s) indicate, respectively, the total CPU time in seconds spent by the separation problems and the complete branch-and-cut algorithm. If the optimal solution was not found after 21600 seconds of execution we stopped the algorithm and report the best feasible solution found.

Observing Table 4 we note that the branch-and-cut algorithm found the optimal solution for almost all instances in reasonable computational time.

The exception was the large instance with budgets B l = B f = 35, grid 20×20 and δ i = √ 5 where the optimal solution was not found after 21600 seconds of execution time.

Results for the RE-CMCLP

For the RE-CMCLPC we did not test instances with grid 20 × 20 or instances with budgets B l = B f = 35. First, we compare our formulation with a brute-force algorithm, testing all possible solutions, in order to compare with the model and prove its accuracy. The algorithm constructs all possible combinations for leader, follower and virtual leader strategies. Some techniques to speed up the process were used, such as quickly discarding the budgets solutions and follower strategies which produce greater regret than the minimum obtained so far. We tested the algorithm only for B l = B f = 15, given that for B l = B f = 25 there would be a combinatorial explosion, due to the possibility to place four or even five facilities. Table 5 displays the comparison, where each cell indicates the average time in seconds for all coverage radii tested (1, √ 2, 2, √ 5, √ 8, 3, √ 10, √ 13 and 4). We marked in bold the smallest average time for each type of grid. In addition, we stopped the brute force algorithm after 21600 seconds of execution for instances with grid 15 × 15 because the algorithm did not reached the optimal solution. The results presented in Table 5 indicate that for instances with grids greater than or equal to 10 × 10 our model surpasses brute-force performance.

Table 6 shows for each type of instance and each budget, average results for RE-CMCLPC considering all covering radii. This table has two columns different from Table 4: the columns Virt w j and Real w j indicating, respectively, the total demand served by the virtual leader and the leader for the best solutions found. Although the latter values could be different if the instance had more than one optimal solution, this did not happen in our experiments. The solution for the instance with B l = B f = 25, grid 10 × 10 and radius √ 10 are just feasible because the algorithm could not find the optimal solution after 21600 seconds of execution. The final gap for that instance was 32.81%. Besides, our reported means do not consider instances with coverage radii greater than or equal to √ 10 for types P12, P15 or P17 with B l = B f = 25 because no good feasible solution could be found after 21600 seconds of execution.

In Table 6, we observe that the number of separations problems solved as well as the number of generated cuts are small. Nevertheless, even with few separations, the running time for some instances was really high. When we compare the separation time with the total time, we conclude that almost all of the time is spent solving the MILP separations problems. This is due to the complex model of the separations, its large number of constraints and the fact that the objective function is a difference between two terms. We also observe that the number of cuts is close to the number of separations problems solved, indicating that for almost all separation problems solved, a cut is added to the main problem. The average difference between the separation number and the cut number is three, indicating a feasible solution was obtained in those cases. This is due to the fact that the separation problem is only solved for integer relaxed solutions.

Results for the ST-CMCLP

Comparison with the heuristic from [START_REF] Seyhan | Network design under competitionTheses and Dissertations[END_REF]. As mentioned before, [START_REF] Seyhan | Network design under competitionTheses and Dissertations[END_REF] proposed a heuristic for the ST-CMCLP. The authors proposed a MILP formulation for the general case of the problem. That follower response is based on a greedy heuristic. The authors proposed two additional equivalent formulations to try to improve the relaxation. We implemented the three heuristic variants in order to compare in a fair way our exact method with the heuristic proposed by [START_REF] Seyhan | Network design under competitionTheses and Dissertations[END_REF].

The instances used for the comparison are generated similarly to [START_REF] Seyhan | Network design under competitionTheses and Dissertations[END_REF]. The instances rely on two data sets from [START_REF] Daskin | Network and discrete location: models, algorithms, and applications[END_REF]. Both sets are based on the US 1990 census. The first set includes the geographical coordinates and populations of 88 cities. These are the 50 largest US cities 7 shows the comparison. In the table, we present the results associated only to the heuristic 1 because that heuristic presented the best results for the instances tested. The column #opt shows the number of optimal solutions found by the heuristic among the 50 instances generated. In addition, the table presents statistics of the percentage gap for the heuristic and statistics of the CPU time in seconds for both methods. Observing Table 7, we note that the heuristic found a large number of optimal solutions for all types of instances tested. Moreover, the average percentage gap was less than 1%. However, our method was faster for instances with higher values of the follower budget B f . In the heuristic, the larger the B f , the greater is the number of constraints. In our formulation, increasing this parameter makes harder the separation problem (61) -(64). Although the increase of B f affects both methods, our method was less sensitive to that parameter.

Instances from [START_REF] Plastria | Discrete models for competitive location with foresight[END_REF]. For the ST-CMCLPC, Table 8 presents for each type of instance and each budget, average results for ST-CMCLPC considering all covering radii. These tables have tree columns that are different from Table 4: the columns Follower, #Sols Calc, #Sols Ins and #Time Heur(s) indicating, respectively, the total demand served by the follower, the number of calculated solutions, the number of solutions included and the total time spent by the heuristic that transforms fractional solutions into feasible integer ones described in section 5. For the budget B l = B f = 15, we set = 0.05 while for the budgets B l = B f = 25 and B l = B f = 35, we set = 0.03. We stopped the method when it reached 21600s of execution. The time limit was reached for instances of the type P15 with B l = B f = 35 and coverage radii greater than or equal √ 8. For that reason, we did not test any instance of type P20 and B l = B f = 25 and any instance of types P17 or P20 with B l = B f = 35.

Observing Table 8, we reach the following conclusions. First, we observe that the method was able to solve almost all instances in reasonable computational time. The hardest instances were in the type P15 with B l = B f = 35, where we were not able to obtain the optimal solution in 21600s of execution for five instances. Another point is that the average root gap was not low in some instances. This indicates that the total computational time could be reduced by improving the strength of the formulation. Another important observation is the low average cumulative time spent by solving the separation problems, which was small compared to the average total time for most instances. One last observation concerns the use of the heuristic. Despite the low number of inserted solutions, those were essential to the speed up our method. Several instances were not solved within 3 hours of execution before applying such strategies.

Conclusions

This paper presents for the first time ILP formulations for three variants the competitive location problems that are valid for general sets of facilities for the leader and the follower. As the formulations typically contain exponentially many constraints, we generated them on the fly in the course of branch-and-cut algorithms. To show the robustness of the formulations, we compared each formulation proposed here with the one from the literature for particular cases of the problems. The results showed that our algorithms are competitive. Besides we presented results for instances in the general .44 16.52 26.29 53.43 P12 8470.56 6789.44 7.32 40.76 184.11 35.11 36.78 6.11 7.00 29.89 1.67 41.68 74.29 151.19 P15 10348.33 9297.33 5.43 189.60 260.67 36.33 37.89 5.67 6.33 31.33 1.22 130.75 206.06 579.17 P17 11483.11 10245.67 2.47 323.36 63.11 3.33 6.33 2.00 4.11 3.44 0.67 10.57 26.65 505.73 P20 12524.78 11911.67 2.36 1016.07 175.22 2.44 7.33 2.00 5.89 4.33 0.78 7.68 43.22 2147.19 25 P5 1440.56 2101.44 6.60 0.76 40.33 13.33 16.11 4.56 6.78 11.00 2.33 0.36 0.72 1.39 P7 2350.11 3842.89 9.41 6.58 153.11 53.11 56.00 4.56 5.56 49.56 2.33 8.63 12.55 19.44 P10 5828.44 7457.00 13.06 34.99 2122.67 123.44 127.78 20.33 22.67 105.44 3.89 78.37 136.26 374.61 P12 9286.00 9063.89 8.91 79.58 2477.22 130.78 138.00 29.56 32.44 104.11 3.11 152.24 265.15 1422.12 P15 13385.89 12061.56 7.94 231.22 3814.22 57.67 64.44 19.22 24.67 43.89 2.44 217.06 383.94 4146.96 P17 15523.67 14305.56 5.14 436.71 2180.00 35.89 40.00 12.78 16.00 26.33 2.22 200.03 .33 220.67 48.89 51.33 10.56 11.78 39.56 3.89 5.72 10.21 17.29 P10 6210.33 7797.56 9.04 27.25 3057.78 76.33 84.00 27.56 34.11 55.33 4.11 29.48 70.96 333.30 P12 9369.22 10162.78 7.35 84.03 6741.00 131.78 140.89 46.11 51.89 91.44 4.78 129.07 240.82 2425.77 P15 14178.00 14341.78 10.01 380.85 9175.22 96.00 103.33 53.00 59.22 49.22 3.67 216.36 468.33 12717.50 case with several sizes, where the formulations could optimally solve large instances in a reasonable amount of time. For future papers, we intend to improve the algorithms performance through two ways: proposing metaheuristics and finding cuts for both the original and the separation problems. In addition, it could be very interesting to see how our approaches generalize to more general bi-level optimization problems, more particularly for the regret and the Stackelberg variants.

Follower

Table 1 :

 1 Total demand served by the leader and the follower for each pair of strategies of the leader and the follower.

			Follower
		F1	F2	F3
	Leader	L1 (5, 4) (4, 5) (5, 6) L2 (3, 7) (7, 2) (5, 6)

Table 2 :

 2 Regret of the leader for each pair of strategies of the leader and the follower.

Table 3 :

 3 Instance types and their characteristics

	Type Grid |J| |L| |F |	w j
	P5	5x5	25 16	9	3542
	P7	7x7	49 33 16 6531
	P10 10x10 100 67 33 15247
	P12 12x12 144 96 48 22977
	P15 15x15 225 150 75 31354
	P17 17x17 289 192 97 43999
	P20 20x20 400 134 266 61910

Table 4 :

 4 WC-CMCLPC: average results considering all covering radii

	Instance Root node B&B Tree	Budget Type Obj Gap(%) Time(s) #Nodes #Sep #Cuts Sep Time(s) Total Time(s)	P5 1815.56 0.47 0.25 0.22 9.11 5.44 0.17 0.24	P7 2270.67 9.30 1.23 14.33 32.67 9.67 1.28 1.92	P10 4697.44 6.08 7.78 19.44 39.78 13.44 7.25 10.48	15 P12 6516.44 9.00 7.04 29.33 57.00 16.00 13.42 20.72	P15 8028.89 10.33 59.11 85.22 158.67 42.44 96.15 139.36	P17 8374.44 21.65 24.95 104.67 244.11 86.33 411.76 590.15	P20 8815.89 16.41 557.42 270.22 545.11 170.56 2124.70 2840.08	P5 1406.89 5.89 0.52 16.33 37.11 9.44 0.37 0.54	P7 2263.89 7.13 2.34 35.78 75.44 20.33 4.32 5.19	P10 5229.56 12.12 14.90 181.11 300.67 61.00 49.06 60.91	25 P12 8042.22 5.04 13.28 65.78 111.11 20.44 12.23 20.97	P15 10725.56 8.70 76.68 286.00 470.11 103.00 257.40 366.90	P17 11503.89 24.04 38.20 464.33 799.22 212.67 724.13 1112.91	P20 13092.78 13.86 710.86 1288.89 2255.78 621.89 6245.35 8675.24	P5 1299.00 1.23 0.19 6.33 21.00 4.56 0.15 0.25	P7 2383.00 4.77 2.27 46.44 93.56 21.78 3.37 4.40	P10 5757.67 6.70 15.19 152.44 245.44 43.11 23.69 32.75	35 P12 8487.67 6.18 30.55 327.44 488.33 59.78 68.04 98.10	P15 12175.11 8.64 149.32 881.11 1464.56 326.56 1176.48 1518.99	P17 13584.22 10.51 242.40 1477.67 2469.44 586.78 2300.48 3278.06	P20 ≤ 16394.44 11.26 1025.31 ≥2516.78 ≥4152.33 ≥1034.00 ≥9896.07 ≥14092.73

Table 5 :

 5 RE-CMCLPC: comparison between smart brute force and our formulation for instance with B l = B f = 15

	Grid	Smart	Our
	Size	B.F. Formulation
	5 × 5	0.13	4.52
	7 × 7	1.16	18.53
	10 × 10	629.5	260.28
	12 × 12	10716.7	168.54
	15 × 15	-	1197.99

Table 6 :

 6 RE-CMCLPC: average results considering all covering radii

	Objective Function Root node Branch and Bound Tree	Obj Virt. Real Gap(%) Time(s) #Nodes #Sep #Cuts Sep Total	w j w j Time(s) Time(s)
	Instance	Type δ j

Table 7 :

 7 ST-CMCLPC: comparison between our method and the heuristic 1 proposed in[START_REF] Seyhan | Network design under competitionTheses and Dissertations[END_REF] continental state capitals, avoiding to count twice any city. The second set includes the geographical coordinates of the 150 largest US cities. The customers are represented by the 88 cities of the first data set where theirs populations represent the customer demands. We considered |L| = 40 and |F | = 20. Those potential facilities are randomly selected among the 150 cities from the second data set in a way that L ∩ F = ∅. For all instances generated, all fixed costs to open a facility are unitary. We created five group of instances by varying the values of budgets B l and B f . For each group, we generated 50 instances. Table

	Instance Heuristic 1 proposed in Seyhan (2012) Our exact method
	Budgets #opt Gap(%)	Time (s)	Time (s)
	B l B f	Avg. Max. Avg. Min. Max. Avg. Min. Max.
	8 4	39 0.42 3.20 6.42 0.84 41.10 41.78 8.48 141.75
	8 5	35 0.55 5.30 20.12 2.11 121.72 69.77 4.00 335.25
	8 6	34 0.68 7.31 54.39 4.50 350.42 62.45 2.75 253.14
	8 7	32 0.74 6.28 114.84 7.16 475.69 57.22 2.41 339.97
	8 8	33 0.68 4.63 219.54 8.47 1495.13 39.36 2.06 278.28
	and the 48

Table 8 :

 8 ST-CMCLPC: results for B l Leader Follower Gap(%) Time(s) #nodes #Sep #Sep #Cuts #Cuts #Sols #Sols Time Time

	= 15 and small grids
	= B f

j


Déborah Caucheteur

Gautier Robin

Vincent Parez

Pierre Martineau
email: pierre.martineau@inserm.fr

Construction of a Synthetic Antibody Gene Library for the Selection of Intrabodies and Antibodies

Keywords: Kunkel mutagenesis, antibody fragment, single-chain Fv, phage-display, synthetic library -2 -

  L'archive ouverte pluridisciplinaire

Introduction

With more than fifty molecules already registered, human monoclonal antibodies (mAbs) have proved their value as therapeutic molecules in numerous pathologies (1-3). These mAbs are usually obtained through three main technologies (4, 5): mice immunization followed by hybridoma generation, and then in vitro humanization; transgenic mice genetically engineered for producing human antibodies (6); in vitro methods such as phage, ribosome or yeast-display (7). The displaybased methods present several advantages over the animal-based ones, in particular their low cost, high flexibility, and high speed, and for therapeutic applications, their ability to directly generate human antibodies and human-mouse cross-reacting mAbs for the pre-clinical characterizations in rodent models.

Among the display methods, phage-display is currently the most widely used approach and has proved to be a cheap and robust technology. This is particularly the case when a naive library is used, since a single antibody source is used for all the projects. For simple selections, antibodies against any target can be identified in about two weeks and the method can be automated and run in parallel with several antigens (8). However, few naive and diverse phage-display libraries are publicly available and the first step is thus to develop your own antibody source. For this critical step, you can rely on the natural diversity of human-recombined antibodies by cloning them from a collection of healthy human donors, or you can design the library using structural and sequence informations and build it in vitro using molecular biology techniques (9-12). The former has the advantage of using natural genes but requires many steps and human donors, whereas the latter only uses in vitro techniques but requires a careful design to obtain efficient libraries.

Most of the phage-displayed libraries use antibody fragments like scFv, Fab or VHH fused to the g3p filamentous phage capsid protein. In addition, most authors use a phagemid since it is easier to manipulate than phages and essentially results in a monovalent display of the antibody fragment, allowing a more stringent selection than the multivalent display obtained when using phage vectors.

Since the pioneering work of Dr. Kabat (13), it is well known that most of the diversity of the antibody molecule is found in the six complementarity-determining regions (CDRs), three being located in each chain. Because of their critical role in the antibody-antigen interaction, these six regions are the main target for randomization in most synthetic library designs. However, the average contribution of the six CDRs to the binding energy is very variable, the heavy chain CDR2 and CDR3 being the main contributors, and the light chain CDR2 only rarely interacting with the antigen. In addition, there is also a strong bias in the amino-acid distribution in the natural antibody paratopes with a high abundance of tyrosine residues. Using these informations may lead to more clever library designs but this requires a flexible mutagenesis method to construct them (11).

In this protocol, we will describe the construction of a synthetic library, based on a unique framework. We will add diversity in the 6 CDR loops and length variations in the VH CDR3. The protocol is based on the well known site-directed mutagenesis method developed by Dr. Kunkel (14). The main interest of this approach is that the library is constructed in a single step using a pool of randomized oligonucleotides, and can address any antibody format. We will introduce diversity in the six CDRs but the protocol can be easily adapted to also introduce diversity to framework regions, to a more restricted number of positions, or using a restrained amino-acid code.

Materials

All buffers must be prepared with ultra-pure water and ACS grade chemicals, and stored at room temperature unless otherwise indicated.

Common Materials

1. Ampicillin and/or Carbenicillin stock at 100 mg/mL (see Note 1). Store at -20 °C.

2. Chloramphenicol stock at 30 mg/mL in ethanol. Store at -20 °C.

3. Kanamycin stock at 25 mg/mL in H 2 O. Sterilize by filtration and store at -20 °C.

4. 2xYT medium. In 900 mL of H 2 O, dissolve 16 g of Tryptone (Peptone), 10 g of yeast extract, and 5 g of NaCl, adjust pH to 7.0 with 5 Ν NaOH, and then the volume to 1 liter.

Autoclave and store at RT. 11. 50 mL conical centrifuge tubes (see Note 5) and a refrigerated centrifuge.

12. 1.5 mL microcentrifuge tubes and a refrigerated bench-top centrifuge (see Note 6).

Preparation of Uracil-Containing Single-Stranded DNA Template

1. E. Coli K J 6: Δ(HindIII)::cat (Tra + Pil + Cam R )/ ung-1 relA1 dut-1 thi-1 spoT1 mcrA (see Note 7).

2. A phage or phagemid containing your antibody gene (see Note 8). In the protocol below we will use pHEN1 phagemid vector (17) containing the scFv13R4 (18).

3. Uridine stock. 6 mg/mL in H 2 O, sterilize by filtration, and store at -20 °C.

Synthesis of the Mutagenized Complementary Strand

T7 D A P ym ( B /μL).

Preparation of Electrocompetent Bacteria

1. E. Coli TG1 (see Note 10).

2. 500 mL centrifuge bottles. 6. Glycerol/HEPES: Weight 10 g of glycerol, make up to 1 liter with water, autoclave. Add 1 mL of sterile HEPES 1M, store at 4 °C.

7. H 2 O/HEPES: Add 1 mL of sterile HEPES 1M to 1 liter of autoclaved ultra-pure water, store at 4 °C.

Electroporation and Phage Production

1. SOC medium. In 950 mL of H 2 O, dissolve 20 g of tryptone (peptone), 5 g of yeast extract, 0.5 g of NaCl, 10 mL of 250 mM KCl (18.6 g/l). Make up to 1 liter with water, adjust pH to 7.0 with 5 N NaOH, autoclave. Before use, add 5 mL of sterile 2 M MgCl 2 (190.4 g/l, autoclaved) and 9 mL of sterile 40% glucose (20 mM).

2. 14 ml sterile polypropylene round-bottom culture tubes (17 mm x 100 mm).

3. Biorad GENE PULSER II and 0.2 cm gap cuvettes (see Note 11).

4. Sterile Pasteur pipettes.

Methods

Preparation of Uracil-Containing Single-Stranded DNA Template

In this protocol, we will first infect a dut ung strain with our phagemid, we then make a stock of phages using KM13 helper phage, and finally purify the single stranded DNA (ssDNA) encapsided in the phage particles. This ssDNA will contain uracil instead of thymine and will be used in the next protocol.

1. Pick a single fresh colony of CJ236 in 2 mL of 2xYT and grow overnight (ON) at 37 °C with shaking.

A μL f

-culture in 2 mL of 2xYT.

3. Grow with vigorous agitation at 37 °C until the OD 600nm reaches 0.5.

4.

A μL f H -13R4 phage stock diluted to 10 6 cfu/mL (see Note 12).

5.

Incubate 1 h at 37 °C without or with a slow shaking (0 -100 rpm). 28. Store the purified ssDNA at -20 °C.

Synthesis of the Mutagenized Complementary Strand

Diversity in the library is introduced using degenerate oligonucleotides. The pool of phosphorylated oligonucleotides is first hybridized to the single-stranded template prepared in section 3.1, then theses oligonucleotides are used as primers and elongated using T7 polymerase, and finally the gaps closed using T4 DNA ligase. This results in a double-stranded circular DNA with a uracil-containing strand coding a wild-type scFv gene and a thymine-containing strand coding for the scFv library. Each reaction prepared in this section will be used in a single electroporation experiment (section 3.4) and should generate between 5x10 8 and 5x10 9 clones. We usually make the following reaction independently for each VH-CDR3 loop length (5-10 lengths) to generate a large library of at least 5x10 9 clones.

1. Annealing of the mutagenic primers to the ssDNA template

 Prepare a primer mix in H 2 O m μ f (see Note 20): μL f m f m f μL f H 2 O.
 Prepare an oligonucleotide:template mix with a 6:1 molar ratio:  Run the gel for 1 h at 5 V/cm.

 Incubate the gel for 30-6 m f TA w μ /mL f YB f DNA Gel Stain (see Note 27). A typical result is shown in Figure 2.

Preparation of Electrocompetent Bacteria

Use freshly-prepared electrocompetent cells following the protocol below in order to obtain the high transformation efficiency (typically 5.10 9 -2.10 10 f m /μ f C18 plasmid) required for the final library transformation (see Note 28).

E. Coli Electroporation and Phage Production

If you prepared your own electrocompetent cells in section 3.3, you must immediately proceed and electroporate your DNA since transformation efficiency will decrease if cells are frozen. Each mutagenesis prepared in step 5 of section 5 will generate, in a single electroporation experiment, between 5 x 10 8 and 5 x 10 9 clones. In this protocol, we directly make the stock of phages that can be then used in phage display experiments. With the volumes used below, we typically obtain enough aliquots for 1500 selections.

1. Prepare one sterile 50 mL centrifuge tube for each DNA preparation (section 5) containing 12 mL of SOC and two 14 mL sterile polypropylene culture tubes containing 0.95 mL of SOC.

2. Warm these tubes to 37 °C for at least 1 h. 8. Immediately transfer the tube to a 37 °C incubator and shake vigorously (220 rpm) for 1 h. but resuspend in 0.95 mL of SOC using the second 14 pre-warmed tube.

12. P LB/GA : μL f μL f -1 and 10 -2 dilutions of μL f -2, , 10 -3 , 10 -4 and 10 -5 dilutions of each 50 mL conical tube (containing 12 mL of SOC and transformed bacteria).

13. Transfer the content of each 50 mL centrifuge tube (12 mL of SOC with transformed cells) in a f k mL f xTY w % μ /mL b (see Note 1).

14. Incubate at 37 °C with shaking (220 rpm) until OD 600nm reaches 0.5.

15.

A μL f KM13 helper phage at 10 14 pfu/mL (20-fold excess).

16. Incubate for 30 min at 37 °C without or with a slow shaking (0 -100 rpm).

17. Centrifuge at 3,000 g for 20 min at 4 °C.

18. 5 mL f xTY w 5 μ /mL K my μ /mL Carbenicillin.

19. Incubate ON in a 2 liter flask at 37 °C with agitation (220 -240 rpm).

20. Calculate the size of the library and the transformation efficiency using the series of dilutions plated in step 12 (see Note 33).

21. Pool all the flasks and centrifuge for 30 min at 10,000 g at 4 °C.

22. Recover the supernatant and add 1/5 th of the volume of PEG/NaCl (200 mL per liter of supernatant). High quality oligonucleotides must be used. The best is to order cloning-q y 5'phosphorylated oligonucleotides. 12 cfu: colony-forming unit. We use a large excess of bacteria to ensure that all the phages can infect a bacterium. [START_REF] Johnson | Kabat Database and its applications: 30 years after the first variability plot[END_REF] We use glucose in all the plates because the scFv is under the control of the lac promoter in pHEN1. This ensures a strong repression of the gene and avoid toxicity. You should get 100-1000 colonies.

14 At an OD 600nm of 0.5, you should have around 5 x 10 8 bacteria/mL. To infect all the bacteria, a 20-fold excess of phages is used, that is 10 10 KM13 per mL of culture.

15 Avoid vigorous shaking but a slow shaking (100 rpm) is also possible.

16 Empty the supernatant into a liquid trash by inverting the tube, then, without reverting it,

place the tube open upside down on a piece of paper towel to absorb the remaining liquid.

17 Clean the hood with phagospray and use filtered pipette tips to prevent contaminations with filamentous phages.

18 The pellet may be absent since it is essentially due to bacteria that were not fully eliminated by the first centrifugation step. 32 The period between applying the pulse and transferring the cells to the outgrowth medium is critical for efficient recovering of E. coli transformants. Delaying this transfer by even one minute causes a threefold drop in transformation efficiency.

33 If the library is not large enough and the transformation efficiency lower than 5 x 10 9 you must improve electrocompetent cell preparation or use commercial ones. If the cells are competent enough, the problem comes presumably from the dsDNA preparation (section 2.3).

Check the efficiency of this step by analyzing your sample on an agarose gel: no ssDNA but a strong dsDNA band should be visible (Figure 2). 35 The formula depends on the phage/phagemid size (19). Phages/mL = (A 269nm -A 320nm ) x 6 x 10 13 / (number of bases of the phage ssDNA). It is better to also titer the infectious phages using serial dilutions, infection of mid-log TG1, then plating on LB/GA (cfu/mL). In general, infectious phages represent 10-50% of the UV-determined particles; e.g., in one of the library made in the group, we obtained at this step 2.2 x 10 14 phages/ml using UV and 3 x 10 13 cfu/mL by titration.

36 Each aliquot should be a hundred times larger than the library size measured by titration. For most libraries this means around 10 12 phages. It is convenient to aliquot into strips of 8 x 0.2 μL P b .

  phosphorylated mutagenenic primers in Tris-HCl pH 8 / EDTA 1 mM (Figure1) (see Note 9). Store at -20 °C.2. NEB2 x10 buffer (1x: 10 mM Tris-HCl pH7.9@25 °C, 50 mM NaCl, 10 mM MgCl 2 , 1 mM DTT). Store at -20 °C. 3. dNTPs (25 mM each). Store at -20 °C. 4. T D A L (5 /μL) x b ff ( m T -HCl, 100 mM MgCl 2 , 100 mM DTT, 5 mM ATP, pH 7.8 at 25°C; Thermofisher).

3. Sterile magnetic stir bars. 4 .

 4 Magnetic stirrer. 5. HEPES 1M: weight 2.38 g of HEPES, add 8 mL of H 2 O, adjust pH to 7.0 and the volume to 10 mL. Sterilize by filtration. Store at 4 °C.

6 .

 6 see Note 21).  Transfer to a thermal cycler at 90 °C for 2 min, 4 °C 10 s, 45 °C for 20 min, and 20 °C for 10 min (see Note 22). Store at 4 °C. Optional. Run an agarose gel to check the efficiency of the second-strand synthesis. Pour a 1% agarose gel without any intercalating agent using TAE buffer (see Note 26).

3 . 4 . 5 . 6 . 7 .

 34567 Cool on ice: 1 electroporation cuvette for each DNA preparation, and 1 for the positive control; the same number of sterile microcentrifuge tubes; and the slide that holds the cuvette in the electroporator (see Note 31). In a pre-m f b m x 5 μL f m lls and the purified ligation (35-μL 5 of section 5). Do not pipet up and down to mix since this will warm the cells. Transfer the mix in a pre-chilled electroporation cuvette. Be sure to put the sample at the bottom of the cuvette by gently taping the bottom of the cuvette on a flat surface, and avoid introducing bubbles. Quickly wet the cuvette and the cuvette slide with absorbent paper, then assemble them in the electroporator. Apply an electric pulse using the following conditions: 2,500 V, 25 µF, Ω. Immediately transfer the cells to one of the pre-warmed sterile 50 mL centrifuge tube containing 12 mL of SOC by washing the sample with 1 mL of outgrowth medium using a Pasteur pipette. (see Note 32).

Figure 1 .

 1 Figure 1. Schematic view of the experiment. The main steps of the protocol are depicted in the figure. (A) Production of uracil-containing

Figure 2 .

 2 Figure 2. Quality control of the dsDNA synthesis.Efficacy of second-strand synthesis is analyzed by agarose gel electrophoresis. The ssDNA

9

 9

10 TG1:

 10 supE thi-1 ∆(lac-proAB) ∆(mcrB-hsdSM)5 without proline (proAB), for instance M9 plates with glucose and thiamine (thi-1). Use a recently streaked plate of less than 1 week. 11 BioRad 0.2 cm gap cuvettes al w f μL f . O b possible but check the size of the cuvette.

  use a single mutagenic oligonucleotide for the CDR1s, CDR2s and the VL-CDR3, and a series of oligonucleotides of lengths for the VH CDR3. We prepare one mix for eachVH-D ( μL f de) to ensure an equal representation of the CDR3 lengths in the library. You can however mix together all the oligonucleotides if you need a library of a more limited size. 21 pHEN1-13R4 vector is 5229 bases long. If your phagemid contains N bases, 15 pmoles of ssDNA represents (15 x 330 x N x 10 -6 ) ~ / μ . 22 It is extremely important to cool down very quickly from 90 °C to 4 °C to avoid a hybridization bias due to a partial matching between the degenerated oligonucleotide and the original CDR sequence. You can use a thermal cycler or simply boil your sample and transfer it directly into an ice bucket. The third step at 45 °C is to remove wrongly hybridized oligonucleotides with a low Tm. 23 This is a very high dNTP concentration, much higher that what is used in most protocols (0.1 -0.6 mM). With the classical dNTP concentrations, we only get few dsDNA. For the ssDNA given in this protocol, at least 1.25 mM is required. 24 This is page 23 of the current manual. You can also heat-inactivate the reaction and purify change the DNA supercoiling state and the migration speed. Resolution of single and double-stranded DNA is much better in their absence. For 1 liter of TAE x50: Tris 242 g, 57.1 mL acetic acid, 100 mL EDTA 0.5 M, pH 8.0 (NaOH). 27 SYBR Safe DNA Gel Stain (Thermofisher). Any DNA stain can be used, e.g. Ethidium Bromide. 28 Alternatively you can use electrocompetent TG1 from Lucigen. You can contact them to get b k q ( x 5 μL). 29 Do not use ice but an ice/water mix to optimize temperature exchange. 30 We use a 10 mL pipette to avoid stressing the bacteria by shearing. You can use a 1 mL micropipette by cutting the tip at around 5 mm from the extremity. With the volume of competent cells prepared here you can perform up to six large electroporation experiments. 31 See figure 7 in the Biorad technical note MC1652101C (http://www.biorad.com/cmc_upload/Literature/12864/M1652101C.pdf).

34

  This volume is suitable if you have pooled 5-10 transformations. You can scale it down or up depending on the anticipated results (see Notes 35 and 36).

phage (15) stock at 10 14 pfu/mL (see Note 2

	5. 40% glucose solution. Sterilize by autoclaving. Store at RT.
	6. LB plates. In 900 mL of H 2 O, dissolve 10 g of Tryptone (Peptone), 5 g of yeast extract, and
	10 g of NaCl, adjust pH to 7.0 with 5 Ν NaOH, and then the volume to 1 liter. Add 15 g of
	agar and autoclave. Allow the solution to cool to 55-60 °C before adding supplements, and
	then pour the plates. LB/GA plates, add 50 mL of 40% glucose solution and 1 mL of
	ampic	(	μ /mL) LB/	5	μL f	m	( 5 μ /m )
	LB/GA		5 mL f %		mL f m	5 μL f
	Chloramphenicol.
	7. KM13 helper ). Store at -70 °C.
	8. PEG/NaCl solution: 20% (w/v) PEG, 2.5 M NaCl in H 2 O. Autoclave and store at 4 °C (see
	Note 3).
	9. PBS x10. In 900 mL of H 2 O, dissolve 80 g of NaCl (1370 mM), 2 g of KCl (27 mM), 11.5
	g of Na 2 HPO 4 .7H 2 O (43 mM), 2 g of KH 2 PO 4 (15 mM), adjust volume to 1 liter, autoclave
	and store at RT.
	10. Macherey Nagel NucleoSpin plasmid kit and NT2 buffer (see Note 4).

  Centrifuge at 4 °C for 5 min at 16,000 g in a bench-top centrifuge to pellet any insoluble material (see Note 18).[START_REF]Spin briefly and eliminate any remaining drop of PEG/NaCl. 26. Resuspend all the pellets in a total volume of 300 mL of cold PBS with 15% glycerol[END_REF]. Purify the ssDNA from the supernatant using Macherey Nagel NucleoSpin plasmid kit using the supplementary protocol for the isolation of M13 DNA (see Note 4).

	7. Pick a colony in 2 mL of 2xYT w at 37 °C with agitation. 8. A μL f -mL f xYT w % and grow with vigorous agitation until OD 600nm reaches 0.5. μ /mL Am % 9. A μL f / th dilution of the KM13 helper phage (10 12 pfu/mL) (see Note 14). w O μ /mL Am 24. 26. D A μL f 5 m T -HCl, pH 8.5 (kit AE buffer).
	10. Incubate without shaking for 30 min at 37 °C (see Note 15). 27. Quantify the ssDNA in a spectrophotometer (see Note 19).
	11. Centrifuge at 4 °C for 15 min at 3,000 g.
	12. Discard the supernatant.
	13.			mL f xYT w	5 μ /mL f K my		μ /mL f
	Am	m	w	. 5 μ /mL f	( . 5 μL f	k	).
	22. Spin briefly and remove the remaining liquid with a pipette and using absorbent paper as in
	the previous step.
	23. Resuspend the phage pellet in 0.5 mL of PBS using an aerosol-free tip (see Note 17) and
	transfer it in a 1.5 mL microcentrifuge tube.
	6. P	μL LB/GA		b O	7 ° (see Note 13).

14. Grow ON with vigorous agitation (220-240 rpm) at 37 °C in a 150 mL flask.

[START_REF] Kristensen | Proteolytic selection for protein folding using filamentous bacteriophages[END_REF]

. Transfer in a 50 mL conical centrifuge tube.

[START_REF]Supplementary protocols plasmid DNA[END_REF]

. Centrifuge for 10 min at 12,000 g at 2 °C (see Note 5). 17. Transfer the 30 mL of supernatant containing the phages into a 50 mL centrifuge tube. 18. Add 8 mL of cold PEG/NaCl solution and mix thoroughly by inverting the tube several times. 19. Incubate for 30 min at 4 °C on ice with regular mixing. 20. Centrifuge for 10 min at 12,000 g at 2 °C. 21. Remove the supernatant by inverting the tube with caution and put it gently upside down on absorbent paper to remove excess liquid (see Note 16).

Notes

Carbenicillin and Ampicillin can be alternatively used. However, since it is more stable, we prefer to use Carbenicillin for the last step of the library production (section 3.4). To make a stock solution of Carbenicillin or Ampicillin at 100 mg/mL final: dissolve 1 g of powder in 9 mL of H 2 O, adjust to 10 mL with H 2 O, sterilize by filtration, and store in aliquots at -20 °C.

2

We use here KM13 helper phage that confers resistance to kanamycin. M13KO7 or another helper phage can be alternatively used.

3

The quality of the PEG is critical (e.g., PEG 8000 for molecular biology from Sigma #81268).

4

Nucleospin plasmid kit can be used to purify single-stranded M13 DNA. Macherey Nagel provides an additional protocol for this application that can be downloaded from their web site (16) or obtained on request. This protocol requires a buffer not present in the kit (NT2, #740597). Alternatively, phenol extraction and ethanol precipitation can be used (14).

5

Be sure that the tubes are resistant enough. Falcon (#352070) and Corning (#430290) branded 50 mL polypropylene conical centrifuge tubes are resistant to 16,000 g.

6

If not refrigerated, put the centrifuge in a cold room. Phages are very stable even at high temperature but the expressed scFv are heat-sensitive. VHH, etc.), but requires a phage or phagemid vector. The mutagenic oligonucleotides must be complementary to the encapsided (+) strand that can be either the coding or the non-coding strand depending on the cloning orientation.