Herminia I Calvete

Concepción Domínguez

Carmen Galé

Martine Labbé

Alfredo Marín

The Rank Pricing Problem: models and branch-and-cut algorithms

Keywords: Bilevel Programming, Rank Pricing Problem, Set Packing, Integer Programming

One of the main concerns in management and economic planning is to sell the right product to the right customer for the right price. Companies in retail and manufacturing employ pricing strategies to maximize their revenues. The Rank Pricing Problem considers a unit-demand model with unlimited supply and uniform budgets in which customers have a rank-buying behavior. Under these assumptions, the problem is first analyzed from the perspective of bilevel pricing models and formulated as a non linear bilevel program with multiple independent followers. We also present a direct non linear single level formulation bearing in mind the aim of the problem. Two different linearizations of the models are carried out and two families of valid inequalities are obtained which, embedded in the formulations by implementing a branch-and-cut algorithm, allow us to tighten the upper bound given by the linear relaxation of the models. We also study the polyhedral structure of the models, taking advantage of the fact that a subset of their constraints constitutes a special case of the Set Packing Problem, and characterize all the clique facets. Besides, we develop a preprocessing procedure to reduce the size of the instances. Finally, we show the efficiency of the formulations, the branch-and-cut algorithms and the preprocessing through extensive computational experiments.

Introduction

The broad development of information and communication technologies produced over the last few decades has resulted in extensive changes in society. In particular, the data availability on customers' choice behavior has been a key factor in the increasing development of pricing strategies which also address customers' preferences. In this context, the use of revenue management strategies, traditionally attributed to airlines and hotel companies, has extended to retail and manufacturing ones ( [START_REF] Kienzler | Pricing strategy: A review of 22 years of marketing research[END_REF], [START_REF] Strauss | A review of choice-based revenue management: Theory and methods[END_REF]). Generally speaking, 1 pricing optimization problems aim at determining the prices of a series of products in order to maximize the revenue of a company. Setting a low price can lead to a loss of income if customers were willing to pay a higher price, but it can also make a product available to a greater amount of customers. On the contrary, a high price can generate greater revenue, but customers may not purchase it if it is too high. Therefore, a pricing problem is formulated as a bilevel program, in other words, has a hierarchical structure. Thus, its upper level optimization problem consists in maximizing the profit of the company, and part of the constraints force the solution to be optimal to another optimization problem designed to satisfy the customers' choice rule. For the interested reader, the references recently collected by Dempe in [START_REF] Dempe | Bilevel optimization: theory, algorithms and applications[END_REF] provide an idea of how fruitful and promising bilevel programming is, and Labbé and Violin [START_REF] Labbé | Bilevel programming and price setting problems[END_REF] present a review along with models and solution methods for pricing optimization problems that can be modeled as bilevel programs.

Pricing problems have attracted wide attention in the literature. We focus on the wellknown unit-demand pricing problem, in which each customer is willing to buy at most one product amongst several ones offered by the company, assuming an unlimited supply of each product. Unit-demand models fit multiple sectors where typically customers are only interested in purchasing one product, such as the automotive sector or companies selling electronic devices and electrical appliances (washing machines, vacuum cleaners, et cetera). In these settings, companies offer the same product with different characteristics and customers base their purchase on a selection rule that takes into account their preferences.

Regarding modelling customer's purchasing behavior, Shioda et al. [START_REF] Shioda | Maximum utility product pricing models and algorithms based on reservation price[END_REF] provide a review of different models in a reservation price framework. In this approach, each customer has a reservation price for each product which reflects how much he is willing to spend on it. Once the pricing strategy is known, the customer will purchase the product with the largest utility, that is, the largest difference between his reservation price for it and the final price of the product. Therefore, the customers' product choice is entirely based on reservation prices and aims at maximizing their utility. In the case of a limited supply of products, Guruswami et al. [START_REF] Guruswami | On profit-maximizing envy-free pricing[END_REF] study the problem of pricing to maximize the revenue while being envy-free regarding the customers' valuation for each product. In the limitedsupply setting, the envy-freeness is a fairness criterion which guarantees that customers always purchase the product that maximizes their utility among the ones they can afford. When there is unlimited supply, the company can always serve customers and therefore they purchase according to their selection rule, so any pricing is envy-free. Fernandes et al. [START_REF] Fernandes | The envyfree pricing problem, unit-demand markets and connections with the network pricing problem[END_REF] provide a state-of-art of the envy-free pricing problem. In general, the focus is on the complexity analysis of the problem in order to develop approximation algorithms with logarithmic order, as well as polynomial or pseudo-polynomial time algorithms for interesting special cases which include additional assumptions. Shioda et al. [START_REF] Shioda | Applications of deterministic optimization techniques to some probabilistic choice models for product pricing using reservation prices[END_REF] formulate mixed-integer programming problems to compare the optimal pricing strategies under several probabilistic choice models. Chen et al. [START_REF] Chen | The complexity of optimal multidimensional pricing for a unit-demand buyer[END_REF] provide a state-of-art focused on the computational aspects of the unit-demand pricing model in which the buyer's valuations of products are characterized by a probability distribution. Heilporn et al. [START_REF] Heilporn | A parallel between two classes of pricing problems in transportation and marketing[END_REF] discuss the relationship between the problems of pricing a network or a product line, with the objective of maximizing the revenue and always in the context of utility-maximizing customers. Taking into account the structure of the underlying mixed integer programming formula-tion, Myklebust et al. [START_REF] Myklebust | Efficient heuristic algorithms for maximum utility product pricing problems[END_REF] propose efficient heuristic algorithms for unit-demand pricing problems in which customer budgets and preferences are considered through reservation prices.

Rusmevichientong et al. [START_REF] Rusmevichientong | A nonparametric approach to multiproduct pricing[END_REF] address models based on data collected through an Auto Choice Advisor website. This website collected information on each customer's requirements and budget and recommended a ranked list of vehicles according to them. Thus, in the paper each customer is characterized by an ordered list of products and a budget. That means that the list of products is sorted according to the degree to which each product fulfills the requirements of the customers. The purchasing decision of a customer is determined by a choice function verifying a certain number of assumptions. Two choice functions of practical interest are analyzed. According to Min-Pricing model, the customer chooses the cheapest product from his list that meets the budget constraints without taking into account the order. If a Rank-Pricing model is assumed, the customer will buy a product under his budget if and only if the products with a higher rank in the customer list are not affordable to him. Briest and Krysta [START_REF] Briest | Buying cheap is expensive: Hardness of nonparametric multi-product pricing[END_REF] analyze the hardness of approximation of a great variety of unit-demand pricing models under different assumptions on the selection rules, the capacity of the supply and the prices of the products. In addition to rank-buying and min-buying models, these authors consider max-buying models in which the customer buys the product affordable with highest price. In the context of the envy-free pricing problem, Briest [START_REF] Briest | Uniform budgets and the envy-free pricing problem[END_REF] considers the unit-demand min-buying pricing problem on the special uniform-budget case, i.e. every customer has the same budget for all the products, which are available in unlimited supply.

In a different but related research field, Discrete Location, we also find customers whose purchase decision is based on preferences. Hanjoul and Peeters [START_REF] Hanjoul | A facility location problem with clients' preference orderings[END_REF] study the Simple (or Uncapacitated) Plant Location Problem with Order, in which they assume that a firm wants to select the number and places of a series of facilities to open so as to maximize the revenue, and the clients to be allocated have a preference order on the list of potential sites. Hansen et al. [START_REF] Hansen | Lower bounds for the uncapacitated facility location problem with user preferences[END_REF] and Cánovas et al. [START_REF] Cánovas | A strengthened formulation for the Simple Plant Location Problem with Order[END_REF] build up on the problem presented in [START_REF] Hanjoul | A facility location problem with clients' preference orderings[END_REF], the first ones deriving formulations from the bilevel perspective and the second ones introducing some valid inequalities as well as a very effective preprocessing, along with a computational study to show the efficiency of their approach. Hemmati and Smith [START_REF] Hemmati | A mixed-integer bilevel programming approach for a competitive prioritized set covering problem[END_REF] relate multi-product pricing, facility location and bilevel optimization. These authors propose a mixed-integer bilevel programming approach for a competitive prioritized set covering problem. This model can be applied to the introduction of new products in a competitive market and to the competitive facility location problem. In both cases each customer has an ordered product (facility) preference list which represents the relative utility of each product (facility).

In this work, we focus on the unit-demand rank pricing model with unlimited supply and uniform-budget. We call this problem the Rank Pricing Problem (RPP) and, to the best of our knowledge, no exact models have been proposed in the literature to deal with it so far. To address the RPP, we present a non linear bilevel formulation in which the company acts as a leader and determines the prices of the products. Once the prices are fixed, each customer, which acts as a follower, solves his own optimization problem. Besides, a non-linear single level formulation is proposed, based on the fact that a customer will purchase the highest-ranked product among all the products he can afford. We linearize the formulations by means of two types of auxiliary variables and derive new valid inequalities. These inequalities are separated and included into the models through the development of a branch-and-cut algorithm. We also take advantage of the fact that some of its constraints constitute a special case of the Set Packing Problem and other properties of the problem in order to strengthen the formulations. We develop some preprocessing techniques to be applied to the instances before solving them. Finally, we present the results of our computational analysis, in which we compare the formulations and show that the results obtained reduce the computational effort when obtaining optimal solutions. The remainder of the paper is organized as follows. Section 2 is devoted to a bilevel formulation for the RPP; in Section 3, the RPP is formulated directly as a single level non linear model; Section 4 includes two linearizations that apply to both models and the development of other valid inequalities to strengthen their linear relaxations through the implementation of branch-and-cut algorithms; in Section 5 some families of clique inequalities associated to a subset of constraints are studied attending to the formulations; Section 6 includes some preprocessing results; Section 7 is devoted to testing the performance of the models by means of a computational study; and Section 8 constitutes a conclusion of the paper.

Bilevel formulation

Let K = {1, . . . , |K|} denote the set of customers and I = {1, . . . , |I|} the set of products. Each customer k ∈ K is represented by a positive budget, a subset of products S k ⊆ I he is interested in and a preference value s k i ∈ I for each product i of this subset, i ∈ S k , where s k i > s k j if customer k prefers product i over product j. We will also assume that for each customer all preferences are strict, so that he never likes two products the same. As budgets can be equal for different customers, let

B = {b 1 , . . . , b M }, M ≤ |K|, denote the set of different budgets, where b 1 < b 2 < • • • < b M .
To describe the budget of customer k, we define a function σ : K → {1, . . . , M } such that σ(k) = if the budget of customer k is b . We will say that a customer k 1 is richer than k 2 if σ(k 1 ) > σ(k 2 ), and the richest customers will be those whose budget is b M . Without loss of generality, we assume that customers are interested in at least one product from the company, i.e., S k = ∅ ∀k ∈ K, and that each product is included in the list of preference of at least one customer, that is, for any product i ∈ I there exists k ∈ K such that i ∈ S k . Otherwise, the customer and/or the product can be removed from the optimization process. Since it will be useful in following sections, we will set b 0 = 0.

The RPP aims at establishing the prices of a set of products sold by a company so as to maximize its revenue, the sum of the prices of all items sold. Each customer purchases his most preferred product among the ones he can afford. Note that if a customer cannot afford any product, he will not purchase anything. Therefore, the company, acting as the upper level decision maker, decides on the prices of the products, p i ≥ 0, i ∈ I. At the lower level of the hierarchy, the customers decide which product to purchase. For this purpose, we introduce binary variables x k i , k ∈ K, i ∈ S k , for every customer's purchase decision, that is, x k i = 1 if and only if customer k buys product i. The bilevel formulation of the RPP is:

(BNL p ) max p k∈K i∈S k p i x k i (1a) s.t. p i ≥ 0, ∀i ∈ I, (1b)
where ∀k ∈ K, x k is an optimal solution of max

x k i∈S k s k i x k i (1c) s.t. i∈S k x k i ≤ 1 (1d) i∈S k p i x k i ≤ b σ(k) (1e) x k i ∈ {0, 1}, ∀i ∈ S k , (1f)
where constraint (1d) forces customer k to buy one product or none and (1e) establishes that customer k will only buy a product if he can afford it. (BNL p ) is a non linear bilevel problem with multiple independent followers ( [START_REF] Calvete | Linear bilevel multi-follower programming with independent followers[END_REF]). Notice that the unlimited supply assumption guarantees that each customer solves a problem involving only the upper level variables and his own variables, thus they are independent followers.

Furthemore, in bilevel programs, the existence of unique solution to the lower level problem is a fundamental assumption to have a well-posed problem. The following result proves that the BNL p is well-posed.

Proposition 2.1. The lower level optimization problems of formulation (BNL p ) have a unique optimal solution.

Proof. The objective function of the lower level problem of (BNL p ) for a given customer

k is i∈S k s k i x k i , with coefficients s k i ≥ 0, s k i = s k j ∀i, j ∈ S k , i = j.
Constraints (1d) ensure that at most one x-variable can take value one. If p i > b σ(k) ∀i ∈ S k , then the optimal solution is given by x k i = 0 ∀i ∈ S k . Otherwise, the optimal solution is x k i = 1 for the unique product i such that

s k i = max s k j : j ∈ S k , p j ≤ b σ(k) , x k j = 0 for all j ∈ S k : j = i.
It is worth noticing that, although we have focused on the unit-demand case, this formulation and the following ones also apply if a customer k is interested in purchasing c k copies of the same product and his budget represents the maximum amount he is willing to pay per copy. Indeed, without loss of generality, it suffices to replace the customer with c k customers with such budget and the same list of preferences. Alternatively, we can replace the objective function by k∈K c k i∈S k p i x k i . The following illustrative example facilitates the understanding of the RPP.

Example 2.2. Table 1 shows the preference matrix and the vector of budgets of an instance of the RPP with 10 customers and 5 products. If product i is the most preferred product for customer k, then s k i = |I| = 5; if j is the second most preferred product for = 53. Furthermore, for instance, for customer k = 7, S 7 = {1, 2, 3, 5}, and σ(7) = 2 because he has the second lowest budget. After solving this RPP, we obtain that an optimal solution is provided setting the prices indicated in the last row of Table 1. Taking into account these prices and the preferences, the customers purchase the product whose preference is marked with an asterisk in the preference matrix. For instance, customer 4 can only afford products 2, 4 and 5, and he purchases product 5 (for less than his budget) because it is his preferred one among them; whereas customer 7 purchases product 2, his least preferred one, because it is the only one in his list of preferences that he can afford.

The fact, already observed by Rusmevichientong et al. in [START_REF] Rusmevichientong | A nonparametric approach to multiproduct pricing[END_REF], that an optimal solution of (BNL p ) exists such that p i ∈ B ∀i ∈ I, suggests us to define new binary variables v i , i ∈ I, ∈ {1, . . . , M } representing the prices of products, that is, v i = 1 if and only if product i has price b . Since each product i has only one price, only one binary variable v i can take value 1 in a feasible solution ∀i ∈ I. Therefore, the price of product i can be expressed as p i = M =1 b v i . We can now reformulate the problem replacing p i variables by v i variables, replacing constraints (1b) with the following constraints in order to ensure products have at most one price:

M =1 v i ≤ 1, ∀i ∈ I, (2a)
v i ∈ {0, 1}, ∀i ∈ I, ∈ {1, . . . , M }. ( 2b
)
and replacing constraints (1e) of the lower level problem with

x k i ≤ σ(k) =1 v i , ∀k ∈ K, i ∈ S k . ( 2c
)
We call this bilevel formulation with v-variables (BNL v ).

Besides, the fact that the matrix corresponding to the feasible set of each lower level problem of (BNL v ) is totally unimodular enables us to relax the integrality constraints (1f), according to [START_REF] Wolsey | Integer Programming[END_REF]Propositions 3.2 and 3.3]. The lower level problems can be further simplified taking into account that once the leader variables v i are known, a subset of variables is determined. If we consider the subset

I(k) = {i ∈ S k : σ(k) =1 v i = 1}, variables {x k i , k ∈ K, i ∈ S k \ I(k)
} are automatically settled to 0 since customer k cannot afford to buy these products. Hence, constraints (2c) can be eliminated and the lower level problem can be formulated as max

x k i∈I(k) s k i x k i s.t. i∈I(k)
x k i ≤ 1

x k i ≥ 0, i ∈ I(k).
For each customer k, the dual problem of the lower level problem is min

u k u k s.t. u k ≥ s k i , i ∈ I(k) u k ≥ 0.
By duality theory, x k and u k are optimal solutions to the primal and dual problems, respectively, if and only if i∈I(k)

s k i x k i = u k i∈I(k) x k i ≤ 1 u k ≥ s k i ∀i ∈ I(k) x k i , u k ≥ 0.
Thus, the resultant formulation after substitution of u k is

(BNL) max v,x k∈K i∈S k   σ(k) =1 b v i   x k i (3a) s.t. M =1 v i ≤ 1, ∀i ∈ I (3b) i∈S k x k i ≤ 1, ∀k ∈ K (3c) x k i ≤ σ(k) =1 v i , ∀k ∈ K, i ∈ S k (3d) j∈S k s k j x k j ≥ s k i σ(k) =1 v i , ∀k ∈ K, i ∈ S k (3e) v i , x k i ∈ {0, 1}, ∀k ∈ K, i ∈ S k , ∈ {1, . . . , M }, (3f)
where the objective function (3a) is the same as in model (BNL v ) after replacing p i by

σ(k) =1 b v i (since for v i = 1 with > σ(k), x k i = 0). Constraints (3b
) are the upper level constraints (2a) that guarantee that products have at most one price. Constraints (3c) and (3d) are the lower level constraints (1d) and (2c), respectively. These constraints ensure that customers purchase at most one product which they can afford. Finally, constraints (3e) assure that, if customer k can afford product i, he will purchase a product j he likes the same or better than i.

Note that constraints (3e) affect

i ∈ S k instead of i ∈ I(k). If i ∈ S k \ I(k) then σ(k)
=1 v i = 0 and the constraint always holds. Otherwise, σ(k) =1 v i = 1 and the constraint applies.

Single level formulation

In this section, we formulate the problem directly as a single level optimization problem. First of all, we introduce some definitions based on the ones given by Cánovas et al. ( [START_REF] Cánovas | A strengthened formulation for the Simple Plant Location Problem with Order[END_REF]) for the plant location problem with order. Definition 3.1. Let k ∈ K be a customer and i, j ∈ S k two products. It is said that i is k-better than j if customer k prefers product i over product j, and it is denoted i > k j. The set of products k-better than i is denoted by B(k, i) = {j ∈ S k : j > k i}. Definition 3.2. Let k ∈ K be a customer and i, j ∈ S k two products. It is said that i is k-worse than j if customer k prefers product j over product i, and it is denoted i < k j. The set of products k-worse than i is denoted by B(k, i) = {j ∈ S k : j < k i}.

Since preferences are strict, for any given products i, j ∈ S k , it follows i > k j or i < k j. It is also worth noticing that a customer k buys product i if and only if i ∈ S k , its price is below the customer budget and all the products more preferred than i have a price higher than his budget. In terms of the binary variables x k i , v i previously defined:

x k i = 1 ⇔ σ(k) =1 v i = 1 and σ(k) =1 v j = 0 ∀j ∈ B(k, i).
Using this notation and decision variables x k i , v i , a single level non linear formulation is

(SLNL) max v,x k∈K i∈S k   σ(k) =1 b v i   x k i (4a) s.t. i∈S k x k i ≤ 1, ∀k ∈ K (4b) M =1 v i ≤ 1, ∀i ∈ I (4c) x k i + σ(k) =1 v j ≤ 1, ∀k ∈ K, i ∈ S k , j ∈ B(k, i) (4d)
x k i + M =σ(k)+1 v i ≤ 1, ∀k ∈ K, i ∈ S k (4e) v i , x k i ∈ {0, 1}, ∀k ∈ K, i ∈ S k , ∈ {1, . . . , M }, (4f)
where constraints (3d) have been replaced by (4e) using constraints (4c). Constraints (4d), also called preference constraints, are given by the previous reasoning and can be strengthened by means of the following result:

Proposition 3.3. The following constraints j∈B(k,i)

x k j + σ(k) =1 v i ≤ 1, ∀k ∈ K, i ∈ S k : B(k, i) = ∅, (5)
are valid for (SLNL) and dominate constraints (4d).

Proof. First of all, we shall prove the validity of (5). We have j∈B(k,i) x k j ≤ j∈I x k j ≤ 1 using (4b) and

σ(k) =1 v i ≤ M =1 v i ≤ 1 because of (4c). Furthermore, provided that product i is within k's budget, i.e., if σ(k) =1 v i = 1,
then customer k will not buy any product k-worse for him than i, so j∈B(k,i) x k j = 0, so (5) are valid.

If we change the notation of (5) and write i ∈B(k,j)

x k i + σ(k) =1 v j ≤ 1, ∀k ∈ K, j ∈ S k : B(k, j) = ∅,
and taking into account that when j is k-better than i ∈ S k then i is k-worse than j, we obtain

x k i + σ(k) =1 v j ≤ i ∈B(k,j) x k i + σ(k) =1 v j ≤ 1.
Therefore, we have proved that [START_REF] Cánovas | New facets for the set packing polytope[END_REF] are stronger than (4d).

Linearizing and strengthening formulations

Formulations (BNL) and (SLNL) are non linear because of the objective functions (3a) and (4a). Since both objective functions are the same, from now on we refer to (4a). In order to linearize it, one approach consists in introducing variables z k , k ∈ K, representing the profit obtained from customer k. Thus, the objective (4a) can be replaced by

max v,x,z k∈K z k
and the following constraints need to be added to the formulation

z k ≤ σ(k) =1 b v i + b σ(k) 1 -x k i , ∀k ∈ K, i ∈ S k (6a) z k ≤ b σ(k) i∈S k x k i , ∀k ∈ K, (6b)
where constraints (6a) ensure that if customer k buys product i,

z k = σ(k)
=1 b v i and (6b) guarantee z k ≤ 0 if customer k does not make any purchase. Constraints (6a) can be strengthened taking into account that customer k buys at most one item, obtaining

z k ≤ σ(k) =1 b v i + b σ(k) j∈S k :j =i x k j , ∀k ∈ K, i ∈ S k . (7)
Therefore, we can reformulate problem (SLNL) obtaining a linear model as follows:

(SLL 1 ) max v,x,z k∈K z k (8a) s.t. i∈S k x k i ≤ 1, ∀k ∈ K (8b) M =1 v i ≤ 1, ∀i ∈ I (8c) j∈B(k,i) x k j + σ(k) =1 v i ≤ 1, ∀k ∈ K, i ∈ S k : B(k, i) = ∅ (8d) x k i + M =σ(k)+1 v i ≤ 1, ∀k ∈ K, i ∈ S k (8e) z k ≤ σ(k) =1 b v i + b σ(k) j∈S k :j =i x k j , ∀k ∈ K, i ∈ S k (8f) z k ≤ b σ(k) i∈S k x k i , ∀k ∈ K (8g) v i , x k i ∈ {0, 1}, z k ≥ 0 ∀k ∈ K, i ∈ S k , ∈ {1, . . . , M }. ( 8h
)
The nonlinearity of the objective function (4a) can also be handled through the introduction of variables z k i , k ∈ K, i ∈ S k , representing the profit obtained from customer k associated to product i. With these variables, the objective is

max v,x,z k∈K i∈S k z k i
and the following constraints ought to be added to the model:

z k i ≤ σ(k) =1 b v i , ∀k ∈ K, i ∈ S k z k i ≤ b σ(k) x k i , ∀k ∈ K, i ∈ S k .
Thus, the resulting model is

(SLL 2 ) max v,x,z k∈K i∈S k z k i (9a) s.t. i∈S k x k i ≤ 1, ∀k ∈ K (9b) M =1 v i ≤ 1, ∀i ∈ I (9c) j∈B(k,i) x k j + σ(k) =1 v i ≤ 1, ∀k ∈ K, i ∈ S k : B(k, i) = ∅ (9d) x k i + M =σ(k)+1 v i ≤ 1, ∀k ∈ K, i ∈ S k (9e) z k i ≤ σ(k) =1 b v i , ∀k ∈ K, i ∈ S k (9f) z k i ≤ b σ(k) x k i , ∀k ∈ K, i ∈ S k (9g) v i , x k i ∈ {0, 1}, z k i ≥ 0 ∀k ∈ K, i ∈ S k , ∈ {1, . . . , M }. (9h)
In the formulations (SLL 1 ) and (SLL 2 ), the values of the z-variables associated to an assignment of prices to products (v-variables) and products to customers (x-variables) are obtained, respectively, by means of constraints (8f)-( 8g) and (9f)-(9g). Although these constraints suffice to obtain the desired values of the z-variables, they lead to weak linear relaxations. Given the shape of the objective function, this weakness is directly transmitted to the upper bounds in the branch-and-bound method. Furthermore, in (8f) (resp. (9f)), a bound for z is obtained exclusively from the v-variables, and in (8g) (resp. (9g)), from the x-variables. These two issues invite to develop stronger constraints on the z-variables.

In what follows, two families of valid inequalities for (SLL 1 ) and (SLL 2 ) are presented. As will be shown in the computational study, they produce the desired improvement in the upper bounds given by the LP relaxation, and they have the particularity of relating the z-variables with both the x-and the v-variables at a time.

Proposition 4.1. The following inequalities are valid for (SLL 1 ):

z k ≤ i∈S k   b r k i x k i + σ(k) =r k i +1 b -b r k i v i + ∈Q k i b -b r k i x k i + v i -1   , ( 10
)
∀k ∈ K, integers r k i ∈ {0, . . . , σ(k)} ∀i ∈ S k and subsets Q k i ⊆ {1, . . . , r k i -1} ∀i ∈ S k .
Proof. Notice that in the case r k i = 0, set Q k i must be empty. We aim at proving that constraints [START_REF] Guruswami | On profit-maximizing envy-free pricing[END_REF] are valid for (SLL 1 ). Let us assume x k i 0 = 1 for some i 0 ∈ S k , and prove that the sum of the addends corresponding to product i 0 in the right hand side of the constraint is greater than or equal to its price. Thus, such sum is

b r k i 0 + σ(k) =r k i 0 +1 b -b r k i 0 v i 0 + ∈Q k i 0 b -b r k i 0 v i 0 , (11)
and we know that

v 0 i 0 = 1 for some 0 ≤ σ(k). If 0 > r k i 0 , then v i 0 = 0 ∀ ∈ Q k i 0 and we get b r k i 0 + (b 0 -b r k i 0 ) = b 0 , which is exactly the price of i 0 . On the other hand, if 0 ≤ r k i 0 we have v i 0 = 0 ∀ : r k i 0 < ≤ σ(k), and therefore (11) becomes b r k i 0 + ∈Q k i 0 b -b r k i 0 v i 0 . If 0 / ∈ Q k i 0 , we obtain b r k i 0 , which is greater than or equal to b 0 because r k i 0 ≥ 0 ; otherwise, if 0 ∈ Q k i 0 , then the term becomes b r k i 0 + (b 0 -b r k i 0 ) = b 0 . Now, let us suppose x k i 0 = 0 for i 0 ∈ S k . Then the addends corresponding to product i 0 become σ(k) =r k i 0 +1 b -b r k i 0 v i 0 + ∈Q k i 0 b -b r k i 0 v i 0 -1 . Since (b -b r k i 0 ) > 0 for : r k i 0 < ≤ σ(k) and (b -b r k i 0 ) < 0 for ∈ Q k i 0
, then the sum is greater than or equal to zero. Therefore, if x k i = 0 ∀i ∈ S k , z k will be bounded from above by a sum of non-negative values. Otherwise, since, at any feasible solution, at most one x-variable can take value 1 for a fixed customer k, say x k i 0 , the upper bound will be obtained as the sum of the term corresponding to product i 0 , which has been proved to be greater than or equal to the price assigned to i 0 , plus some non-negative addends.

Remark 4.2. The family of inequalities (10) contains all of the previous upper bound constraints on z k of (SLL 1 ). Constraints (8f) are obtained by, given a customer k ∈ K and a product i ∈ S k , setting

r k i = 0, r k j = σ(k) ∀j ∈ S k \ {i} and Q k j = ∅ ∀j ∈ S k in (10); constraints (8g), by, given a customer k ∈ K, setting r k i = σ(k) and Q k i = ∅ ∀i ∈ S k .
Proposition 4.3. The inequalities of the following family are valid for (SLL 2 ):

z k i ≤ b r k i x k i + σ(k) =r k i +1 b -b r k i v i + ∈Q k i b -b r k i x k i + v i -1 , ( 12
) ∀k ∈ K, i ∈ S k , any integer r k i ∈ {0, . . . , σ(k)} and any subset Q k i ⊆ {1, . . . , r k i -1}.
Proof. First assume that

x k i = 1. This implies v 0 i = 1 for some 0 ≤ σ(k). If 0 ≤ r k i , then v i = 0 ∀ : r k i < ≤ σ(k) and (12) becomes z k i ≤ b r k i + ∈Q k i (b -b r k i )v i . If 0 ∈ Q k i , then the right hand side of the constraint is b r k i + (b 0 -b r k i ) = b 0 , which is valid as it is the exact price of product i; otherwise, the right hand side of the constraint is b r k i , valid since b r k i ≥ b 0 . If 0 > r k i , then v i = 0 ∀ ∈ Q k i and the inequality we obtain is z k i ≤ b r k i + (b 0 -b r k i ), also valid.
On the other hand, if we assume x k i = 0, then the inequality holds trivially because its right hand side is non negative and z k i = 0.

Remark 4.4. The family of inequalities (12) contains all of the previous upper bound constraints on z k i of (SLL 2 ): constraints (9f) are obtained by setting r k i = 0 and Q k i = ∅ ∀k ∈ K, i ∈ S k , whereas constraints (9g) appear as a result of setting

r k i = σ(k), Q k i = ∅ ∀k, i ∈ S k .
The number of inequalities of Propositions 4.1 and 4.3 increases exponentially as the number of customers and products grows. However, these inequalities can be efficiently separated and added dynamically to formulations (SLL 1 ) and (SLL 2 ), respectively, in a branch-and-cut mode. Thus, regarding the family of valid inequalities [START_REF] Guruswami | On profit-maximizing envy-free pricing[END_REF], and given a fractional optimal solution of the linear relaxation of (SLL 1 ), (v i , x k i , z k ), our aim is to find, for each k ∈ K, integers r k i and subsets Q k i ∀i ∈ S k such that the upper bound given by the right hand side of the resultant constraint of the family is as tight as possible. As the sum given by the right hand side of (10) can be decomposed by products and given that z is fixed, our problem reduces to

min r∈{0,...,σ(k)}, Q⊆{1,...,r-1} b r x k i + σ(k) =r+1 b -b r v i + ∈Q b -b r x k i + v i -1 , (13)
where (k, i) ∈ K × S k is fixed, and we have denoted r k i as r and Q k i as Q so as to simplify notation. It is worth noticing that this pair (r, Q) also minimizes the right hand side of the corresponding constraint of family [START_REF] Hansen | Lower bounds for the uncapacitated facility location problem with user preferences[END_REF] when given an optimal fractional solution of the linear relaxation of (SLL 2 ), (v i , x k i , z k i ), and fixed (k, i) ∈ K × S k . Thus, finding a pair (r, Q) that minimizes [START_REF] Heilporn | A parallel between two classes of pricing problems in transportation and marketing[END_REF] for a given customer k and product i not only leads to the development of an efficient separation algorithm for the set of valid inequalities [START_REF] Guruswami | On profit-maximizing envy-free pricing[END_REF], but also for the set [START_REF] Hansen | Lower bounds for the uncapacitated facility location problem with user preferences[END_REF].

The fact that (b -b r ) ≤ 0 ∀ ≤ r implies that, for a given r, Q r := { ∈ {1, . . . , r -1} : [START_REF] Heilporn | A parallel between two classes of pricing problems in transportation and marketing[END_REF]. Therefore, if W (r) is the value of the sum (13) when Q = Q r , our problem consists in minimizing W (r) for r ∈ {0, . . . , σ(k)}.

x k i +v i > 1} minimizes
To do so, we shall study the variation of W (r) as r increases. Given that

Q r+1 = Q r ∪ {r} if x k i + v r i > 1, Q r+1 = Q r otherwise, for r < σ(k) we get W (r + 1) -W (r) =   b r+1 x k i + σ(k) =r+2 b -b r+1 v i + ∈Q r+1 b -b r+1 x k i + v i -1   -   b r x k i + σ(k) =r+1 b -b r v i + ∈Q r b -b r x k i + v i -1   = (b r+1 -b r )x k i + σ(k) =r+2 b r -b r+1 v i -b r+1 -b r v r+1 i + ∈Q r+1 b r -b r+1 x k i + v i -1 = b r+1 -b r   x k i - σ(k) =r+1 v i + ∈Q r+1 1 -x k i -v i   . ( 14
)
First of all, we are going to prove that, when r increases from 0 to σ(k), W (r) first decreases and then increases. We can achieve that by proving that W (r) -

W (r -1) ≥ 0 ⇒ W (r + 1) -W (r) ≥ 0. Since b r+1 -b r > 0 ∀r < σ(k), it follows from (14) that W (r + 1) -W (r) ≥ 0 ⇔ x k i - σ(k) =r+1 v i + ∈Q r+1 1 -x k i -v i ≥ 0 ∀r < σ(k)
, and therefore demonstrating the above is equivalent to proving

x k i - σ(k) =r+1 v i + ∈Q r+1 1 -x k i -v i - x k i - σ(k) =r v i + ∈Q r 1 -x k i -v i ≥ 0. But we have x k i - σ(k) =r+1 v i + ∈Q r+1 1 -x k i -v i -   x k i - σ(k) =r v i + ∈Q r 1 -x k i -v i   = v r i + min 0, 1 -x k i -v r i = min v r i , 1 -x k i ≥ 0.
Hence, W (r) reaches its minimum value for the smallest r such that W (r)-W (r-1) ≤ 0 and W (r + 1) -W (r) > 0. Furthermore, noticing in [START_REF] Hemmati | A mixed-integer bilevel programming approach for a competitive prioritized set covering problem[END_REF] that

∈Q r+1 1 -x k i -v i ≤ 0 ∀r allows us to deduce that W (r) -W (r -1) ≤ 0 provided that x k i - σ(k) =r v i ≤ 0, i.e., if r is such that x k i ≤ σ(k)
=r v i . This fact saves us having to compute the whole sum [START_REF] Hemmati | A mixed-integer bilevel programming approach for a competitive prioritized set covering problem[END_REF] in order to know if W (r) -W (r -1) ≤ 0 whenever

x k i ≤ σ(k) =r v i .
After finding a separation for valid inequalities [START_REF] Guruswami | On profit-maximizing envy-free pricing[END_REF], the next step consists in defining a procedure to incorporate these inequalities into formulation (SLL 1 ) dynamically in a branch-and-cut framework where the starting subproblem of every child node is the final formulation of the parent node with the corresponding branching x-or v-variable fixed to either zero or one. A scheme of this procedure is depicted in Algorithm 1. Preliminary testing shows that the best strategy amounts to adding these inequalities to the formulation provided that the node depth in the branching tree is less than or equal to 4. The termination criterion is that the optimal value of the linear relaxation of that node does not improve in the last iteration. Both the algorithm and the branch-and-cut procedure used to include dynamically inequalities [START_REF] Hansen | Lower bounds for the uncapacitated facility location problem with user preferences[END_REF] into model (SLL 2 ) are analogous to these ones.

Algorithm 1 Separation of inequalities [START_REF] Guruswami | On profit-maximizing envy-free pricing[END_REF] Let (x k i , v i , z k ) be an optimal fractional solution of the linear relaxation of (SLL 1 ). For every customer k ∈ K do

Step 1. For every product i ∈ S k do

Step 1.1. Set

r k i = 0. Step 1.2. If r k i < σ(k) and k =1 v i ≤ x k i , update r k i := r k i + 1 and repeat Step 1.2. Otherwise, go to Step 1.3. Step 1.3. If r k i < σ(k) and W (r k i + 1) -W (r k i ) ≤ 0, update r k i := r k i + 1 and repeat Step 1.3.
Otherwise, go to Step 2.

Step 2. Set Q k i := { ∈ {1, . . . , r k i -1} :

x k i + v i > 1} ∀i ∈ S k . Step 3. Incorporate constraint z k ≤ i∈S k   b r k i x k i + σ(k) =r k i +1 b -b r k i v i + ∈Q k i b -b r k i x k i + v i -1   
to the formulation if and only if it is violated.

Polyhedral analysis of the set packing subproblem

In this section, we analyze the subproblem of model (SLL 1 ) (resp. model (SLL 2 )) associated to x-and v-variables and constraints (8b)-(8e) (resp. constraints (9b)-(9e)), given that it constitutes a special case of a Set Packing Problem (SPP). Since this subproblem is the same for both models (SLL 1 ) and (SLL 2 ), in the rest of the section we shall refer to the subproblem of model (SLL 1 ).

An SPP is a problem in the form of max{ct :

At ≤ 1 w , t ∈ {0, 1} u },
where c ∈ R u , A ∈ {0, 1} w×u and 1 w is a w-vector of ones.

The polyhedral structure of the SPP has been widely studied in the literature. The interested reader is referred to [START_REF] Padberg | On the facial structure of set packing polyhedra[END_REF], where the basis of this section is presented, and to [START_REF] Cánovas | New facets for the set packing polytope[END_REF], where further results are presented and the main papers on the topic are referenced. In the following paragraphs we briefly expose the notation and results necessary in the section. For details, the reader may consult [START_REF] Nemhauser | Integer and Combinatorial Optimization[END_REF].

Associated with each instance of an SPP, let the intersection graph be G = (V, E), where each node in the set V is associated to a variable of the problem and (v i , v j ) ∈ E if and only if a ki + a kj = 2 in some row of A. The neighborhood of a node v is the set of nodes adjacent to v. A non empty subset of pairwise non adjacent nodes in G is known as a packing, and the problem of obtaining an optimal solution of an SPP is equivalent to that of obtaining a packing of maximum cardinality on its intersection graph. A complete graph is that in which all the nodes are pairwise adjacent, and a clique in G is a maximal complete subgraph. The incidence vector of a subset V ⊂ V is a binary vector (t 1 , . . . , t |V | ) where t j = 1 if and only if the j th node of V belongs to V , for j ∈ {1, . . . , |V |}.

Let P (G) be the convex hull of the incidence vectors of all the packings of the intersection graph G, i.e., the convex hull of all the feasible solutions of SPP. Since facet defining inequalities are not dominated by any other valid inequality, one way of confirming that our formulation (or part of it) is tight consists in proving that its constraints are facetdefining. And, as stated in [START_REF] Padberg | On the facial structure of set packing polyhedra[END_REF], an inequality in the form v∈V x v ≤ 1, where V ⊂ V , is a facet for P (G) if and only if the subgraph induced by V is a clique in G. Clique facets are particularly interesting because they can always provide a valid formulation and their addition to a problem generally provides better results (when trying to solve it) than the addition of other types of facets which are more complex, such as lifted odd holes.

Set packing subproblem of (SLL 1 )

In order to apply the SPP properties to our problem, we begin by identifying the intersection graph GSLL associated to the previously defined subproblem of formulation (SLL 1 ). The large amount of edges of this graph makes drawing it impractical, so we will follow a different approach in order to describe the intersection graph based on the following proposition.

Proposition 5.1. Given the intersection graph GSLL associated to the subgraph of (SLL 1 ):

(1) Two nodes x k i , x k j , i = j, are adjacent ∀i, j ∈ S k .

(2) Two nodes x k i , x k i , k = k , are never adjacent.

(3) Two nodes x k i , x k j , k = k , i = j, are adjacent if and only if σ(k) ≥ σ(k ) and j ∈ B(k, i) (or, equivalently, i ∈ B(k, j)).

(4) Two nodes x k i , v i , are adjacent if and only if > σ(k).

(5) Two nodes x k i , v j , i = j are adjacent if and only if ≤ σ(k) and j ∈ B(k, i).

(6) Two nodes v i , v i , = , are adjacent ∀ , .

(7) Two nodes v i , v j , i = j, are never adjacent.

Proof.

(1) A customer k purchases at most one product.

(2) The fact that a customer k purchases a product i does not imply that another customer cannot afford it (that depends on i's price), and therefore does not allow us to determine whether another customer is going to buy it or not.

(3) Let us suppose x k i = 1, i.e., customer k purchases product i. That implies k is not able to afford any product j that is k-better than i, and therefore no customer k with σ(k ) ≤ σ(k) will be able to afford it either, hence x k j = 0. However, the fact that k purchases product i does not allow us to infer which products will not be purchased by other customers k richer that k or which customers will not purchase a product j ∈ B(k, i) ∪ {i}.

(4) If x k i = 1, k can afford product i, so there must exist 0 ≤ σ(k) such that v 0 i = 1. Since product i can have one price at most, it follows v i = 0 ∀ > σ(k).

(5) Let us suppose x k i = 1, i.e., customer k purchases product i. That implies k is not able to afford any product j that is k-better than i, i.e., v j = 0 ∀j ∈ B(k, i), ∀ ≤ σ(k). However, it does not provide any insight into the prices of products j ∈ B(k, i).

(6) A product i can have at most one price.

(7) Knowing the price of a product does not provide any insight into the price of the rest.

Having identified the intersection graph GSLL, the next subsection focuses on characterizing all its cliques.

Characterization of all the cliques in the intersection graph

We first include a lemma that will be useful when characterizing all the cliques. Lemma 5.2. Any clique in GSLL which contains nodes

v 1 i , v 2 i with 1 < 2 , contains v i ∀ such that 1 < < 2 .
Proof. Let (V , E ) be a clique in GSLL and suppose v 1 i , v 2 i ∈ V , for 1 < 2 . Let us suppose that there exists k ∈ K with x k i ∈ V . Then, x k i is adjacent to v 1 i , and thus for Prop. 5.1(4) it follows σ(k) < 1 . Therefore, for every > 1 > σ(k), the same result implies x k i is adjacent to v i . Now let us suppose that there exist k ∈ K and j ∈ S k , j = i, with x k j ∈ V . By hypothesis we have x k j adjacent to v 2 i , which for Proposition 5.1(5) implies i ∈ B(k, j) and σ(k) ≥ 2 . Thus, for every < 2 ≤ σ(k), it follows from the same result that x k j is adjacent to v i .

Finally, we know from Proposition 5.1( 6) and [START_REF] Dempe | Bilevel optimization: theory, algorithms and applications[END_REF]

that v j adjacent to v 1 i ⇔ j = i, hence v i is adjacent to v i ∀ = and v j / ∈ V for j = i.
All in all, we have proven that for such that 1 < < 2 , any variable x k j or v i ∈ V is adjacent to v i . Thus, the statement follows.

Before proving the main results of this section, we introduce some sets that generalize B(k, i).

Definition 5.3. Let k be a customer and P ⊆ S k a subset of products in which k is interested. Then we define B(k, P ) as the set {i ∈ S k : i > k j ∀j ∈ P } of products that are preferred by k to all the products in P . Similarly B(k, P ) := {i ∈ S k : i < k j ∀j ∈ P }. In the special case when P = ∅ we define B(k, ∅) := I and B(k, ∅) := I. Now we can state the two main results in this section. Note that, in order to keep a consistent notation, a set {k 2 , . . . , k n } is defined in Theorem 5.4 that will be extended to {k 1 , . . . , k n } in Theorem 5.5.

Theorem 5.4. Given a set of customers {k 2 , . . . , k n }, n ≥ 2, with σ(k 2 ) ≤ • • • ≤ σ(k n ),
and non empty pairwise disjoint sets of products P kq ⊆ S kq , q = 2, . . . , n, such that

P kq ⊆    q-1 r=2: σ(kr )<σ(kq ) B(k q , P kr )       q-1 r=2: σ(kr )=σ(kq )
B(k q , P kr ) ∪ B(k r , P kr )    ∀q ∈ {3, . . . , n}, the following inequalities are valid for (SLL 1 ):

n q=2 j∈P kq x kq j ≤ 1. ( 15
)
Valid inequalities [START_REF] Labbé | Bilevel programming and price setting problems[END_REF] are facets for the subproblem of (SLL 1 ) if and only if

(k 0 , i 0 ) ∈ K × S k 0 satisfying 1. i 0 ∈ B(k q , P kq ) ∀q ∈ {2, . . . , n} : σ(k q ) ≥ σ(k 0 ), 2. i 0 ∈ B(k 0 , P kq ) ∀q ∈ {2, . . . , n} : σ(k q ) ≤ σ(k 0 ), and
| n q=2: σ(kq )=σ(k 2 ) P kq | ≥ 2.
Furthermore, all the clique facets for the subproblem of (SLL 1 ) containing only x-variables are in family [START_REF] Labbé | Bilevel programming and price setting problems[END_REF].

Proof. Let GSLL = (V G , E G ) be the intersection graph of the subproblem of (SLL 1 ) associated to x-and v-variables and constraints (8b)-(8e), and let Q = (V , E ) be a clique of GSLL containing only x-variables.

Let k 2 be a customer with minimum budget in the clique and a subset of products P k 2 ⊆ S k 2 such that x k 2 j ∈ V ∀j ∈ P k 2 (taking into account that, by Proposition 5.1(1), x k 2 i is adjacent to x k 2 j ∀i = j). Provided that there exist customers k q , ∀q ∈ {3, . . . , n} such that σ(k 2 ) ≤ σ(k 3 ) ≤ • • • ≤ σ(k n ) and sets of products P kq ⊆ S kq , P kq = ∅ ∀q ∈ {3, . . . , n}, such that x kq j ∈ V ∀j ∈ P kq , then by Proposition 5.1(2) P k 2 , . . . , P kn are pairwise disjoint, and verify the following conditions:

• P kq ⊆ q-1 r=2 σ(kr )<σ(kq )
B(k q , P kr ), ∀q ∈ {3, . . . , n}.

Otherwise, there exist k r with σ(k r ) < σ(k q ) and products i ∈ P kr , j ∈ P kq such that x kr i , x kq j ∈ V but j / ∈ B(k q , i), and by Proposition 5.1(3) this implies x kr i , x kq j are not neighbors in the intersection graph. Therefore, V does not induce a complete graph.

• P kq ⊆ q-1 r=2 σ(kr )=σ(kq )
B(k q , P kr ) ∪ B(k r , P kr ) , ∀q ∈ {3, . . . , n}.

Otherwise, there exist k r with σ(k r ) = σ(k q ) and products i ∈ P kr , j ∈ P kq such that x kr i , x kq j ∈ V but Proposition 5.1(3) does not hold for k = k r , k = k q or for k = k q , k = k r , and hence V does not induce a complete graph. Therefore, the above conditions guarantee that the nodes corresponding with the xvariables in an inequality in the form of (15) induce a complete graph, so the family of inequalities ( 15) is valid.

In addition, if there exist (k 0 , i 0 ) ∈ K × S k 0 meeting the conditions of the statement, then x k 0 i 0 is adjacent in the intersection graph to every other node in V by Proposition 5.1(3) and conditions 1 and/or 2, and therefore the complete subgraph is not maximal. P kq | ≥ 2 holds, no v-variable can be adjacent in the intersection graph to all nodes in V . Otherwise, P k 2 = {i} and either n = 2 or σ(k 2 ) < σ(k 3 ), and hence variable v σ(k 2 )+1 i would be adjacent to every node in V and the complete subgraph would not be maximal.

On the other hand, if |

Theorem 5.5. Given a nonempty set L = { 1 , . . . , p } ⊆ {1, . . . , M }, a product i ∈ I and

• if 1 > 1, a customer k 1 such that σ(k 1 ) = 1 -1, i ∈ S k 1 , and a set P k 1 = {i}; otherwise, P k 1 = ∅; • if p < M , customers k 2 , . . . , k n , n ≥ 2, such that p = σ(k 2 ) ≤ • • • ≤ σ(k n ) (n = 1 otherwise
) and non empty pairwise disjoint sets of products P kq ⊆ S kq \ {i}, q = 2, . . . , n such that P k 2 ⊆ B(k 2 , i) and

P kq ⊆    q-1 r=1: σ(kr )<σ(kq ) B(k q , P kr )       q-1 r=1: σ(kr )=σ(kq ) B(k q , P kr ) ∪ B(k r , P kr )    ∀q ∈ {3, . . . , n},
the following inequalities are valid for (SLL 1 ):

∈L v i + n q=1 j∈P kq x kq j ≤ 1. ( 16
)
Valid inequalities (16) are facets for the previously defined subproblem of (SLL 1 ) if and only if

(k 0 , i 0 ) ∈ K × (S k 0 \ {i}): σ(k 0 ) ≥ p satisfying 1. i 0 ∈ B(k q , P kq ) ∀q ∈ {1, . . . , n} : σ(k q ) ≥ σ(k 0 ),
2. i 0 ∈ B(k 0 , P kq ) ∀q ∈ {1, . . . , n} : σ(k q ) ≤ σ(k 0 ).

Furthermore, all the clique facets for the subproblem of (SLL 1 ) containing v-variables are in family [START_REF] Myklebust | Efficient heuristic algorithms for maximum utility product pricing problems[END_REF].

Proof. Let GSLL = (V G , E G ) be the intersection graph of the previously defined subproblem of (SLL 1 ) and let Q = (V , E ) be a clique of GSLL containing v-variables. Taking into account Proposition 5.1 [START_REF] Dempe | Bilevel optimization: theory, algorithms and applications[END_REF], all v-variables in the same clique must share the subindex, and by Lemma 5.2, all v-variables in the same clique must have consecutive superindices. We represent with L = { 1 , . . . , p } this set of consecutive superindices and with i the common subindex. We thus distinguish several cases depending on L:

1. L = {1, . . . , M }.
Then by Proposition 5.1 [START_REF] Cánovas | New facets for the set packing polytope[END_REF] we know that a node x k j in the neighborhood of v 1 i , . . . , v M i must satisfy σ(k) = M and j ∈ B(k, i). However, the richest customers always purchase their most preferred product, and therefore we have removed all these x-nodes from the intersection graph, i.e., P k 2 = • • • = P kn = ∅.

Since Proposition 5.1(4) does not either provide any node adjacent to v i ∀ , we obtain P k 1 = ∅ and thus the set of nodes {v i : ∈ {1, . . . , M }} induces a maximal complete subgraph in GSLL.

2. L = { 1 , . . . , M } for some 1 > 1.

As v i / ∈ V ∀ ∈ {1, . . . , 1 -1}, a node adjacent to v i for ≥ 1 but not to v 1 -1 i must belong to the clique. Applying Lemma 5.2 and Proposition 5.1, we know this node corresponds with an x-variable, i.e., there exists a node x k j ∈ V for some customer k and product j. As in the previous case, Proposition 5.1(5) does not provide any node adjacent to v M i , thus P k 2 = • • • = P kn = ∅. Therefore, node x k j must be adjacent to v i for ≥ 1 by Proposition 5.1(4), so j = i and k = k 1 for a customer k 1 : σ(k 1 ) < 1 and P k 1 = {i}. Since x k 1 i is not adjacent to v 1 -1 i , also by Proposition 5.1(4) σ(k 1 ) ≥ 1 -1, and hence σ(k 1 ) = 1 -1.

If we suppose there exists another node x k j ∈ V , then x k j must be adjacent to v i ∀ ≥ 1 by Proposition 5.1(4), and therefore j = i. However, x k i and x k 1 i are not adjacent for any customer k = k 1 by (2), so the set {v i :

≥ 1 } ∪ {x k 1 i } induces a clique in GSLL.
3. L = {1, . . . , p } for some p < M . Since v i / ∈ V ∀ > p , applying Lemma 5.2 and Proposition 5.1 there must exist a node x k i 0 ∈ V such that x k i 0 is adjacent to v p i but not to v p+1 i . Proposition 5.1(4) does not provide any node adjacent to v 1 i , hence P k 1 = ∅ and x k i 0 has to be adjacent to v i , ≤ p , by Proposition 5.1 [START_REF] Cánovas | New facets for the set packing polytope[END_REF]. Hence, there exists a customer k 2 : σ(k 2 ) ≥ p and a subset of products

P k 2 ⊆ B(k 2 , i) such that i 0 ∈ P k 2 and x k 2 j ∈ V ∀j ∈ P k 2 (taking into account that, by Proposition 5.1(1), x k 2 j is adjacent to x k 2 j ∀j = j ). Since x k 2 i 0 is not adjacent to v p+1 i , it follows σ(k 2 ) = p .
Provided that there exist customers k q , ∀q ∈ {3, . . . , n} such that σ(k 2 ) ≤ σ(k 3 ) ≤ • • • ≤ σ(k n ) and sets of products P kq ⊆ S kq , P kq = ∅ ∀q ∈ {3, . . . , n}, such that x kq j ∈ V ∀j ∈ P kq , then by Proposition 5.1(2) P k 1 , . . . , P kn are pairwise disjoint. Moreover, P kq ⊆ S kq \ {i} ∀q ∈ {3, . . . , n}; otherwise, x kq i ∈ V for some k q : σ(k q ) ≥ p and is not adjacent to v p i (Proposition 5.1(4)), thus V does not induce a complete graph.

Applying arguments analogous to those of Theorem 5.4, the rest of the conditions stated above must hold.

4. L = { 1 , . . . , p } for some 1 > 1, p < M .

Applying arguments analogous to those of the previous items, we can conclude that there exist customers

k 1 ∈ K: σ(k 1 ) = 1 -1, i ∈ S k 1 such that P k 1 = {i} and k 2 ∈ K: σ(k 2 ) = p with P k 2 ⊆ B(k 2 , i), P k 2 = ∅.
The rest of the conditions also hold applying a reasoning analogous to that of Theorem 5.4. Now that we have established the different shapes that clique facets can adopt, we are able to determine whether constraints (8b)-(8e) always define clique facets in the corresponding subproblem of (SLL 1 ). Thus, we can conclude that constraints (8c) and (8e) always define clique facets by applying cases 1 and 2 of the proof of Theorem 5.5, respectively. By Theorem 5.4, and given that B(k, S k ) = ∅ ∀k, we know a valid inequality from the family (8b) will be a clique if and only if |S k | ≥ 2 and (k 0 , i 0 ) ∈ K×S k 0 satisfying σ(k 0 ) ≥ σ(k) and i 0 ∈ B(k 0 , S k ). As for constraints (8d), they do not necessarily define clique facets either but, like in the former case, they define clique facets in most cases.

Even though the valid inequalities given by Theorems 5.4 and 5.5 are facet defining on the subproblem of (SLL 1 ) associated to x-and v-variables and constraints (8b)-(8e), they might not define facets on the polyhedra which is obtained once we consider also z-variables and their corresponding constraints of model (SLL 1 ). Nevertheless, they are still strong valid inequalities and, as such, make the extended formulation (SLL 1 ) stronger in turn. As we have previously stated, the same applies to model (SLL 2 ). Additionally, we have incorporated some of these valid inequalities into models (SLL 1 ) and (SLL 2 ), but they do not significantly improve their performance, given that the original models are already tight since they contain mainly inequalities which are facet defining in the corresponding subproblems, as we have been able to prove through this section. Therefore, in the computational study of Section 7 we will test the performance of both models without any additional clique facet of their subproblems.

Preprocessing

In this section, our aim is to fix x-and v-variables to zero in order to reduce the size of the RPP instances before solving them.

Let us begin by recursively defining a function u : K → I as follows:

1. If σ(k) = M , then u(k) = i if and only if i ∈ S k and B(k, i) = ∅. 2. If σ(k) = M and ∃i ∈ S k such that ∀k : σ(k ) > σ(k), u(k ) = i, then u(k) = i if and only if i ∈ S k , k with σ(k ) > σ(k) such that u(k ) = i and ∀j ∈ B(k, i) ∩ S k , ∃k , σ(k ) > σ(k), such that u(k ) = j. 3. If σ(k) = M and ∀i ∈ S k , ∃k with σ(k ) > σ(k) and u(k ) = i, then u(k) = i if and only if i ∈ S k and B(k, i) = ∅.
Function u assigns, to the richest customers, their most preferred product; and to the rest of the customers, their most preferred product among the ones which have not been previously assigned to any richer customer (or their least preferred one if all of them have already been assigned).

Based on the definition of u, we are going to establish a partition of the set of customers. Thus, let C r , r ∈ {1, 2, 3}, be such that k ∈ C r if and only if u(k) has been defined for k making use of item r of the definition of u. It is clear that ∪ r∈{1,2,3} C r = K, but given this definition it is possible that both C 2 and C 3 are empty or

C 3 is. If C 2 = C 3 = ∅, then σ(k) = M ∀k ∈ K,
and the problem becomes trivial: it suffices to establish v M i = 1 ∀i ∈ I, every customer will purchase his most preferred item and the objective value will be the sum of every customer's budget, i.e., b M |K|. If C 1 = ∅ = C 2 and C 3 = ∅, then we will see in Corollary 6.7 that an optimal solution can be found by inspection.

The following result shows the usefulness of this function when fixing x-variables to zero: Proposition 6.1. There exist optimal solutions (ṽ, x) of (BNL) and (SLNL) such that

xk i = 0 ∀k ∈ K, ∀i ∈ B(k, u(k)).
Proof. Suppose we have an optimal solution (v, x) which does not satisfy the statement conditions. By slightly modifying (v, x), we aim at building another solution (ṽ, x), with the same objective value, which does satisfy them.

Let us proceed by induction on k. First consider k 0 such that σ(k 0 ) = M , i.e., one of the richest customers. Then we know k 0 is able to afford every product he is interested in, and therefore in every optimal solution he will purchase his most preferred product. Therefore, xk 0 i = 0 must hold for all k 0 such that σ(k 0 ) = M and i ∈ B(k 0 , u(k 0 )). Since (v, x) does not satisfy the statement conditions, there will exist

k 0 ∈ K such that σ(k 0 ) = 0 < M and ∀k such that σ(k) > 0 xk i = 0 ∀i ∈ B(k, u(k)) but xk 0 i 0 = 1 for a product i 0 ∈ B(k 0 , u(k 0 )). It is clear that k 0 ∈ C 2 .
The fact that k 0 buys product i 0 implies he cannot afford product u(k 0 ), i.e., 0 =1 v u(k 0 ) = 0 and xk 0 u(k 0 ) = 0. We are going to show that xk u(k 0 ) = 0 ∀k, that is to say, that product u(k 0 ) has not been sold in the considered optimal solution. On the one hand, it is clear that xk u(k 0 ) = 0 for all k such that σ(k) ≤ σ(k 0 ) because these customers cannot afford it either. On the other hand, let us prove that for all k such that σ(k

) > σ(k 0 ), it holds u(k 0 ) ∈ B(k, u(k)) or u(k 0 ) ∈ S k . First of all, we know u(k 0 ) = u(k) ∀k : σ(k) > σ(k 0 ) because k 0 ∈ C 2 . Besides, let us suppose u(k 0 ) ∈ B(k 1 , u(k 1 )) for k 1 : σ(k 1 ) > σ(k 0 ). If σ(k 1 ) = M , we have B(k 1 , u(k 1 )) = ∅, hence M > σ(k 1 ) > σ(k 0 ) and k 1 ∈ C 2 ∪ C 3 . But then, by definition of u, u(k 0 ) ∈ B(k 1 , u(k 1 )) ⇒ there exists k 2 : σ(k 2 ) > σ(k 1 ) and u(k 2 ) = u(k 0 ), which is a contradiction with k 0 ∈ C 2 .
Therefore, we have proved that customers with budget greater than k 0 do not purchase product u(k 0 ) because they buy others that prefer more, and customers k such that σ(k) ≤ σ(k 0 ) cannot afford product u(k 0 ). Hence, u(k 0 ) is not sold in this optimal solution.

Let us consider now a price vector ṽ defined by ṽ i = v i ∀ , ∀i = u(k 0 ) and ṽ 0 u(k 0 ) = 1, ṽ u(k 0 ) = 0 ∀ = 0 . If prices are settled this way, customers k with σ(k) < 0 can afford the same products as before, so they purchase the same item. Customers k with σ(k) = 0 are now able to afford product u(k 0 ). However, if they purchase it (because they prefer it over the one they were buying in the previous solution) they spend their whole budget. Therefore, the revenue does not decrease. Further, customers k with σ(k) > 0 were already buying a product more preferable than u(k 0 ) in the previous solution, so they buy the same as previously. Thus,

xk i = xk i ∀k : σ(k) = 0 , ∀i ∈ S k ; xk i = xk i ∀k : σ(k) = 0 and u k 0 ∈ B(k, j) for j : xk j = 1, ∀i ∈ S k ; and xk u(k 0 ) = 1, xk i = 0 ∀k : σ(k) = 0 and u(k 0 ) ∈ B(k, j) for j : xk j = 1
, and ∀i = u(k 0 ). Therefore, through ṽ we have built a feasible solution (ṽ, x) with the same objective value as the one given by solution (v, x) and such that xk 0 i = 0 ∀i ∈ B(k 0 , u(k 0 )). Proceeding by induction on k, we deduce that we can obtain an optimal solution satisfying the statement conditions. * To illustrate the above result, we use the Example 2.2. In Table 2, for every customer k ∈ K, s k i is circled in the preference matrix provided that u(k) = i. If x k i is fixed to i is marked with an asterisk. Now, we present how the preprocessing has been applied for some customers. Since customer 1 is the richest one, by item 1 of the definition of u we obtain that u(1) = 3, which is his most preferred product. By applying Proposition 6.1, x 1 i = 0 for i ∈ {2, 5}. Notice that u(2) = u(3) = 1 by item 2 of the definition of u. In the case of customer 2, his most preferred product has been assigned to customer 1. By applying Proposition 6.1, neither customer 2 nor customer 3 will purchase any product they like less than product 1. If we turn to customer 5, with budget 32 and S 5 = {1, 3, 5}, we remark that for each product i in his list of preferences there exists another customer k with budget greater than 32 such that u(k) = i (these are, respectively for products 1, 3 and 5, customers 2, 1 and 4). Therefore, u(5) = 3 by item 3 of the definition of u, and no x-variable related to this customer can be set to zero by Proposition 6.1. Furthermore, comparing with the optimal solution displayed in Table 1, as expected, in this optimal solution every customer k obtains a product he likes more or the same than product u(k). Remark 6.2. Besides being useful when fixing variables to zero, the proof of Proposition 6.1 derives an optimal solution (ṽ, x) from another solution (v, x) which satisfies

i∈S k s k i xk i ≥ i∈S k s k i xk i ∀k ∈ K
, that is, it allows us to obtain an optimal solution in which customers either buy the same product or buy another one they prefer more. It is also remarkable that there may be more than one optimal solution satisfying Proposition 6.1.

Function u also lets us conclude that some products will not be sold in any optimal solution that satisfies Proposition 6.1: Corollary 6.3. Let (ṽ, x) be an optimal solution of (BNL) or (SLNL) satisfying Proposition 6.1. Then for every product i ∈ I such that u -1 (i) = ∅, it follows xk i = 0 for every customer k ∈ K with i ∈ S k , i.e., product i is not sold.

Proof. Let us consider an optimal solution (ṽ, x) which meets the requirements given by Proposition 6.1, and a customer k and a product i such that xk i = 1. Then u(k) = i or i ∈ B(k, u(k)), and in the last case by definition of u there exists a customer k with σ(k ) > σ(k) and u(k ) = i. Remark 6.4. Corollary 6.3 allows us to eliminate x k i ∀k and v i ∀ for all products i we know will not be sold, thus reducing the size of the problem. Furthermore, after this procedure, and by definition of u, we will always obtain instances of the problem with |I| ≤ |K|. However, there might still remain products which will not be sold in one or more optimal solutions.

The following result, whose proof we omit for the sake of brevity, is useful to fix v-variables to zero, reducing the size of the problem. Proposition 6.5. There exists an optimal solution (ṽ, x) of (BNL) or (SLNL) such that ∀i, : k with σ(k) = and i ∈ S k , it follows v i = 0. Remark 6.6. Although optimal solutions satisfying Proposition 6.1 do not necessarily satisfy Proposition 6.5, there exist optimal solutions satisfying both propositions. Furthermore, we can assume that if a variable x k i can be fixed to zero in an optimal solution (v, x) according to Proposition 6.1, then i no longer belongs to the list of products of interest of customer k, i.e., i / ∈ S k , thus fixing more v-variables to zero when applying Proposition 6.5.

By recursively building function u and using the previous results, x k i -variables with i ∈ B(k, u(k)) can be removed from all formulations based on v-and x-variables. This will imply that x k u(k) = 1 for all richest customers k and their preferred products u(k) such that B(k, u(k)) = ∅. Variables in the conditions of Proposition 6.5 can also be removed. In some cases, as shown in the following result, an optimal solution to the problem can be directly obtained from the preprocessing phase:

Corollary 6.7. If for all customers k ∈ K with σ(k) < M an i ∈ S k exists such that ∀k : σ(k ) > σ(k), u(k ) = i, that is, if C 3 = ∅,
an optimal solution can be derived by inspection.

Proof. Let (ṽ, x) be defined as follows: for all k ∈ K, xk

u(k) = 1, xk i = 0 ∀i = u(k) and ṽσ(k) u(k) = 1, ṽ u(k) = 0 ∀ = σ(k); for all i : u -1 (i) = ∅, ṽM i = 1, ṽ i = 0 ∀ = M .
We are going to show that solution (ṽ, x) is optimal.

First of all, we know by hypothesis that u(k) = u(k ) ⇒ σ(k) = σ(k ), and therefore ṽ is well defined. Moreover, x is also well defined because for all k ∈ K, i ∈ B(k, u(k)) there exists k : σ(k ) > σ(k) with u(k ) = i, and thus ṽσ(k ) i = 1 and k cannot afford product i. Finally, since in this solution all customers k are purchasing a product for their whole budget σ(k), then the objective value is equal to the sum of the budgets of every customer (which is an upper bound), and therefore (ṽ, x) is optimal. Corollary 6.8. If |K| ≤ |I| and S k = I ∀k ∈ K, then an optimal solution can be derived by inspection.

Proof. It suffices to notice that Corollary 6.7 can be applied.

Figure 1: % of instances solved with a time limit by models (BL 1 ), (BL 2 ), (SLL 1 ), (SLL 2 ) and (SLL 1 ), (SLL 2 ) with the branch-and-cut procedure

Computational results

Computational experiments were carried out in order to compare the different models and check the performance of the valid inequalities proposed in Section 4 and the preprocessing techniques described in Section 6. The commercial IP solver used through all the testing was Xpress mosel version 4.0.3, on a computer Dell PowerEdge T110 II Server (Intel Xeon E3-1270, 3.40GHz) with 16 GB of RAM.

The reader can find all the results of the computational experiment detailed in the tables grouped in the appendix. In the rest of this section, the more relevant information of those tables will be summarized by means of several figures.

To begin with, we performed a first computational study to compare models (BNL) and (SLNL). Thus, we tested the performance of the linearization of these models by means of z k -and z k i -variables, as well as both linearizations of model (SLNL) including the branch-and-cut algorithm described in Section 4.

In this first experiment, the instances include |K| = 30 customers whose budgets have been randomly generated independently and uniformly. We consider sets of products of sizes |I| =5, |I| =15 and |I| =25, and lists of products of interest of sizes the 10, 25, 50, 75 and 100% of |I|, rounded up. The items included in the lists of products of interest and their order have also been selected independently and uniformly at random, and the number of products of interest is the same for every customer in all the instances. We generated ten instances for each combination of the three mentioned parameters, 150 in total. For the computational study, we have fixed

s k i = |I| -n + 1 if i is the n-th most preferred product for customer k, ∀k ∈ K, i ∈ S k .
Figure 2: % of solved instances depending on the number of nodes explored in the branching tree by models (BL 1 ), (BL 2 ), (SLL 1 ), (SLL 2 ) and (SLL 1 ), (SLL 2 ) with the branchand-cut procedure Figure 3: In the ordinate axis, the % of instances with an integrality gap less than or equal to that of the corresponding abscissas is represented for models (BL 1 ), (BL 2 ), (SLL 1 ), (SLL 2 ) and (SLL 1 ) and (SLL 2 ) with the branch-and-cut procedure So as to be able to compare the integrality gaps and resolution times for these models, we disabled automatic cuts and switched Xpress presolve settings off. The time limit for each instance and model was fixed to 600 seconds. The only preprocessing applied to the instances consisted in setting x k i = 1 for every richest customer k and for every product i ∈ S k such that B(k, i) = ∅. In order to check the usefulness of the valid inequalities proposed for formulations (SLL 1 ) and (SLL 2 ) in Section 4, we also implemented a branchand-cut algorithm following the separation procedure explained in Section 4. In every node of the branching tree, a fractional solution (v, x, z) was obtained after solving the linear relaxation of the corresponding subproblem, and, provided that the depth of this node in the tree was 4 or less, we checked for valid inequalities [START_REF] Guruswami | On profit-maximizing envy-free pricing[END_REF] or [START_REF] Hansen | Lower bounds for the uncapacitated facility location problem with user preferences[END_REF], respectively, and re-optimized the subproblem until no more valid inequalities were violated or the linear relaxation bound was no further improved.

Figures 1, 2 and 3 illustrate the results obtained, and refer to Table 3 of the appendix. As described in Section 4, models (BL 1 ) and (SLL 1 ) (resp. (BL 2 ) and (SLL 2 )) are the linearizations of models (BNL) and (SLNL) by means of z k -variables (resp. z k i -variables). Models (BL 1 ), (BL 2 ), (SLL 1 ), (SLL 2 ), as well as models (SLL 1 ) and (SLL 2 ) with the corresponding branch-and-cut algorithms, appear in the legend of the figures, respectively, as BL1, BL2, SLL1, SLL2, SLL1+VI and SLL2+VI. Figure 1 shows the % of instances solved within a given time limit, where the axis of abscissas has been represented using a logarithmic scale. The accumulated % of solved instances depending on the number of nodes explored in the branching tree is shown in Figure 2, also using a logarithmic scale in the axis of abscissas. And Figure 3 shows the % of instances which have an integrality gap less than or equal to that of the x-axis. For models (BL 1 ), (BL 2 ), (SLL 1 ) and (SLL 2 ), this integrality gap is equal to LRGap = 100 UB-OPT OPT %, where UB is the upper bound of the linear relaxation and OPT is the optimal value of the instance. In the case of models (SLL 1 ) and (SLL 2 ) with the corresponding branch-and-cut algorithms, the integrality gap is given by RGap = 100 UBC-OPT OPT %, where UBC represents the upper bound given by the linear relaxation in which the cuts have been added in the root node.

As we can see in Figure 1, models (BL 1 ) and (BL 2 ) were only able to solve around the 65% and the 70%, respectively, of the instances proposed within a time limit of 600 seconds. For its part, models (SLL 1 ) and (SLL 2 ) solved all the instances in 300 seconds, and this time is further improved to only a few seconds when adding the branch-and-cut procedure. In fact, we can see how the lines SLL1+VI and SLL2+VI of Figure 1 are very close to each other and reach 100% almost immediately. In Figure 2 we can observe that models (SLL 1 ), (BL 1 ) and (BL 2 ) reached the million of nodes explored in the branching tree in some of the instances, and this amount decreases in two orders of magnitude for model (SLL 2 ). Models (SLL 1 ) and (SLL 2 ) with the branch-and-cut algorithm solved the totality of the instances exploring on average less than 10 nodes, highly improving the performance of the other four models. Figure 3 shows that models (BL 1 ) and (BL 2 ) reached integrality gaps of more than 30% in some instances. The maximum gap reached by model (SLL 1 ) is of around 20%, and this gap was halved when using model (SLL 2 ) and divided by eight when adding the cuts in the root node in models (SLL 1 ) and (SLL 2 ), illustrating how these cuts have a significant importance in the reduction of the integrality gaps.

The results represented in Figures 1, 2 and3 show that, whilst the linearization of (BNL) using z k variables provides slightly better results in terms of time and nodes than Figure 4: Average time needed to solve instances with |K| = 30 by models (SLL 1 ) and (SLL 2 ), with and without the preprocessing techniques (ten instances averaged per size) the one using z k i , the opposite occurs when comparing both linearizations of formulation (SLNL), since model (SLL 2 ) performs clearly better than (SLL 1 ) in terms of both the number of nodes explored in the branching tree and the integrality gaps. The introduction of the branch-and-cut algorithm into the models leads to a considerable improvement in both models.

With the aim of testing the performance of the preprocessing proposed in Section 6, we ran the same instances after fixing x-and v-variables to zero by applying Propositions 6.1 and 6.5, respectively, with the six previous models. The results are detailed in Table 4 in the appendix, where it can be appreciated the great improvement provided by the preprocessing. The results provided by the two best previous models, (SLL 1 ) and (SLL 2 ), both with the branch-and-cut procedure, are represented in Figures 4 and5.

Figure 4 shows the average time (in seconds, using a logarithmic scale) needed to optimally solve the ten instances previously generated for each number of products (|I| = 5, |I| = 15 and |I| = 25) and each size of the list of products of interest of every customer

(|S k | = 0.1|I| , |S k | = 0.25|I| , |S k | = 0.5|I| , |S k | = 0.75|I| and |S k | = |I|).
The size of the set of products is included after the letter i in the notation of the instances, and the number of products of interest of every customer appears after the letter s. Regarding the instances, it is noticeable from the results of Figure 4 that the difficulty to solve them increases when the number of products in which every customer is interested grows. It is also remarkable that the preprocessing techniques are more efficient in the reduction of the times when the number of products increases: for the instances with 25 products and complete list of products of interest, fixing x-and v-variables to zero according to Propositions 6.1 and 6.5 leads to a reduction in the average resolution times of two and one orders of magnitude for models (SLL 1 ) and (SLL 2 ), respectively. This is due to the fact that instances with more products (with respect to the number of customers) lead to the fixing of a greater number of x-variables, which results in the elimination of more The average integrality gaps of the linear relaxation LRGap are represented in Figure 5. The greatest integrality gaps are reached when the size of the set of products is small, which may be because these instances have a smaller optimal value. It is noticeable the improvement of the gaps when adding the preprocessing to the model (SLL 1 ), regardless of the number of products and the size of the list of products of interest. Probably due to the small size of the instances, the preprocessing applied to model (SLL 2 ) with the branchand-cut algorithm does not result in any reduction on the integrality gaps. However, as it will be stated in the second computational study, the preprocessing techniques applied to (SLL 2 ) improve the results when the instances have a bigger size.

Regarding the number of nodes explored in the branching tree, in the majority of the instances only one node is explored, and the average number does not exceed six nodes. Furthermore, the average integrality gaps are reduced to zero in all cases after the cuts in the root node.

Considering the results of the first computational experiment, we generated instances of bigger and more varied sizes and discarded the models derived from (BNL). We extended the time limit for each instance and model to 1200 seconds as well. In order to generate the instances of our second computational study, we designed a model based on the Characteristics Model proposed by Fernandes et al. in [8]. This model has an economic interpretation, and focuses on the idea that each product has a profile of characteristics, and each customer is interested in several of them. In this way, a product will be more preferred by a customer than another provided that more of its characteristics, or the most important ones, are among the ones he desires. Let C be the set of characteristics, o the number of options for any characteristic and p the number of options in which a customer is interested for any characteristic. The characteristics of every product i are represented by means of a vector of options E i = (e i c ), c ∈ C, whose entries are in the set {1, 2, . . . , o}, chosen independently and uniformly at random. The set of characteristics in which a customer k is interested is represented by a matrix A k |C|×o = (a k cv ) where, for every row, p positions are set independently and uniformly at random to 1 (the ones in which k is interested) and o -p positions to 0. The relevance of each characteristic c is determined by its weight w(c), so that w(c) > w(c ) if characteristic c is considered (for every customer) more important than c . In this way, the score each customer k gives to a product i is defined as the sum of the weights of the characteristics of i in which k is interested, i.e., score k i := c∈C w(c)a k ce i c . The preferences of a customer are based on the score he has given to each product, since customer k will prefer product i over product j if and only if score k i > score k j . Each customer is interested in s ∈ {1, . . . , |I|} products; therefore, if s < |I|, the set of products of interest of every customer will only include the s products with the greatest scores for each of them. Note that the lists of products of interest have equal size s for all the customers in all the instances.

The instances for the computational experiment were generated fixing the number of options of each characteristic as o = 8; the number of options preferred by each customer as p = 7; the number of characteristics as |C| = 50|I|; and the budgets of the customers are integers randomly selected between 1 and 2|K|. With the aim of testing the performance of the models (SLL 1 ) and (SLL 2 ) with the branch-and-cut procedure, with and without preprocessing, using instances of different sizes and densities, we generated instances of |K| =50, |K| =100 and |K| =150 customers and 0.1|K|, 0.5|K| and |K| products. We generated 10 instances of each size, 360 in total. Once the customers (including their budgets and scores for each product) and products were randomly generated following the previously described procedure, we generated four different instances by modifying s, that is, considering s = 1, s = 0.2|I| , s = 0.5|I| and s = |I|.

Figures 6, 7 and 8 illustrate the results obtained. We have included a detailed description of the results in which these figures are based in Tables 5 and6 of the appendix for the interested reader.

Figure 6 shows the % of instances solved within a given time limit. In this figure we can observe how model (SLL 1 ) performed clearly worse than the rest of the models, not reaching the 60% of solved instances. Models (SLL 2 ) and (SLL 1 ) and (SLL 2 ) with the preprocessing techniques had a similar behavior, the three of them solving more than the 80% of instances in less than 1200 seconds. Model (SLL 2 ) with the preprocessing techniques offered the best results, reaching the 89%. We can also notice that model (SLL 1 ) with the preprocessing outperformed model (SLL 2 ) without it at the beginning, but it performed worse after approximately 800 seconds. As we had noted in the first computational study, the difficulty of the instances grows when the size of S k increases. In particular, instances with complete list of products of interest are the most difficult ones, and none of them was solved in less than 1200 seconds for |K| = 150 and 15 and 75 products. For the instances with the same number of customers and products, the preprocessing makes a great improvement. This is specially noticeable when |K| = |I| = |S k | = 150, where adding the preprocessing led to the resolution of all the instances, taking into account that none of them had been solved without it.

Figure 8 shows the integrality gaps for both models with the preprocessing techniques. The LRGap is calculated using the objective value of the best solution found by any of the models (OV): LRGap = 100 UB-OV OV %, and RGap = 100 UBC-OV OV %, where UBC represents the upper bound given by the linear relaxation in which the cuts have been added in the root node. The notation used to express the size of the instances is the same as the notation of Figure 7. It can be observed how, even though there were sizes of instances for which the average LRGap was smaller for model (SLL 1 ) than for (SLL 2 ), the cuts in the root node were more effective in the reduction of the upper bound for model (SLL 2 ) regardless of the case, since the RGap is smaller in this model. In most cases, the reduction of the integrality gap by the branch-and-cut procedure was crucial in the resolution of the instances. It is also remarkable that, for |K| = |I|, the LRGap did not reach the 3%, and the inclusion of the cuts reduced it to zero.

Conclusions

We have studied the Rank Pricing Problem, proposing for the first time two exact formulations and two different linearizations. We have also carried out a characterisation of all the families of clique inequalities of a subproblem of both linearizations which constitutes a special case of the SPP. As a result, we have been able to determine which of them are part of our model. In order to improve the bound provided by the linear relaxation of the models, we have derived some families of valid inequalities by making an in-depth analysis of its structure and developed a separation procedure to embed them into the formulations. Some preprocessing techniques have also been applied so as to reduce the size of the instances before solving them. The different models and results have been tested through the development of a branch-and-cut algorithm and by means of computational experiments which show how these techniques lead to the resolution of instances of greater size with reduced running times and integrality gaps.

A challenging future line of research consists in generalizing the RPP by considering limited supply. Adding capacity constraints on product supply would require the development of new formulations, since a decision must be taken about how to allocate the available units of each product to the customers. In particular, the development of models which provide an envy-free solution, i.e., a solution in which no customer can afford any other product more preferable for him than his own, or not, would lead to different solution strategies. All instances have |K| = 30 customers, and the table shows the number of products (|I|) and the number of products in which every customer is interested (|S k |). Depending on the model, it also includes the number of cuts in the branching tree (Cuts), the number of nodes of the branching tree (Nodes), the integrality gap of the linear relaxation (LRGap), the integrality gap of the linear relaxation after the cuts in the root node (RGap), the execution time in seconds taking into account that the time limit was settled to 600 seconds (t(s)), and the number of instances solved within that time period for the models for which not every instance was solved (Sol) Table 5: Results obtained for model (SLL 1 ) strengthened with valid inequalities, without and with the preprocessing described in Section 6, for instances of 50, 100 and 150 customers (10 instances averaged per line). The table includes the number of customers of the instance (|K|), the number of products (|I|) and the number of products in which every customer is interested (|S k |) and, in the model which includes preprocessing, it also shows the average % of x-and v-variables fixed to zero during the preprocessing ((%X) and (%V), respectively). For each model, the table shows the average number of cuts in the branching tree (Cuts), the number of nodes of the branching tree (Nodes), the average integrality gap of the linear relaxation (LRGap), the average integrality gap of the linear relaxation after the cuts in the root node (RGap), the execution time in seconds taking into account that the time limit was settled to 1200 seconds (t(s)) and the number of instances solved within that time period (Sol)

k, s k j = 4 ,

 4 et cetera. In this example, M = 7 and b 1 = 16, b 2 = 25, b 3 = 31, . . . , b 7

Figure 5 :

 5 Figure 5: Average integrality gaps of the linear relaxation, LRGap, for instances with |K| = 30 by models (SLL 1 ) and (SLL 2 ), with and without the preprocessing techniques (ten instances averaged per size)

Figure 6 :

 6 Figure 6: % of instances solved with a time limit by models (SLL 1 ) and (SLL 2 ), with and without the preprocessing techniques detailed in Section 6

Figure 7 :

 7 Figure 7: % of solved instances depending on their size. Instances with |K| = 100 are shown in the graphic of the left hand side, and instances with |K| = 150, in the graphic of the right hand side. The size of the set of products is included after the letter i in the notation of the instances, and the number of products of interest of every customer appears after the letter s

Figure 7

 7 Figure 7 represents the % of instances solved attending to their size. The graphic of the left hand size shows the instances with |K| = 100, and the graphic of the right hand side, the instances with |K| = 150, given that models (SLL 1 ) with the preprocessing techniques and (SLL 2 ) with and without the preprocessing techniques solved all the instances of 50 customers. The size of the set of products (|I|) is indicated by the number that follows letter i in the notation of the instances; the size of the set of products in which

Figure 8 :

 8 Figure 8: Average integrality gaps for models (SLL 1 ) and (SLL 2 ) with the preprocessing techniques. Instances with |K| = 100 are shown in the graphic of the left hand side, and instances with |K| = 150, in the graphic of the right hand side

Table 3 :

 3 Results of the first computational study without the preprocessing techniques. Comparison of models (BL 1 ) and (BL2 ) with models (SLL 1 ) and (SLL 2 ), as well as models (SLL 1 ) and (SLL 2 ) strengthened with valid inequalities (10 instances averaged per line).

Table 1 :

 1 Preference matrix, vector of budgets and an optimal solution to an instance of the RPP with 10 customers and 5 products

		Product 1 Product 2 Product 3 Product 4 Product 5 Budgets
	Customer 1	-*	3*	5*	-*	4*	53
	Customer 2	4*	-*	5*	-*	-*	40
	Customer 3	5*	-*	4*	2*	3*	40
	Customer 4	2*	3*	1*	4*	5*	38
	Customer 5	5*	-*	3*	-*	4*	32
	Customer 6	2*	3*	5*	1*	4*	31
	Customer 7	5*	2*	4*	-*	3*	25
	Customer 8	5*	-*	3*	4*	-*	25
	Customer 9	-*	-*	4*	5*	-*	25
	Customer 10	4*	5*	-*	2*	3*	16
	Optimal prices	40*	16*	53*	25*	31*

Table 2 :

 2 Preprocessing of the x-variables of Example 2.2 0 by Proposition 6.1, then s k i appears in gray. If customer k purchases product i in the optimal solution from Table 1, s k

Acknowledgements

The research of Herminia Calvete and Carmen Galé has been funded by the Spanish Ministry of Economy, Industry and Competitiveness under grant ECO2016-76567-C4-3-R. Concepción Domínguez and Alfredo Marín have been partially supported by the research project MTM2015-65915-R (MINECO, Spain). Alfredo Marín has also been partially supported by projects 19320/PI/14 (Fundación Séneca) and "Cost-sensitive classification. A mathematical optimization approach" (Fundación BBVA). Martine Labbé has been partially supported by the Fonds de la Recherche Scientifique -FNRS under Grant(s) n o PDR T0098.18.

Appendix. Tables with the computational results

|I| |S

) and (SLL 2 ) strengthened with valid inequalities, applying the preprocessing described in Section 6 to all the instances (10 instances averaged per line). All instances have |K| = 30 customers, and the table shows the number of products (|I|), the number of products in which every customer is interested (|S k |) and the average % of x-and v-variables fixed to zero during the preprocessing ((%X) and (%V), respectively). Depending on the model, it also includes the number of cuts in the branching tree (Cuts), the number of nodes of the branching tree (Nodes), the integrality gap of the linear relaxation (LRGap), the integrality gap of the linear relaxation after the cuts in the root node (RGap) and the average time needed to optimally solve the instances (t(s)) shows the average % of x-and v-variables fixed to zero during the preprocessing ((%X) and (%V), respectively). For each model, the table shows the average number of cuts in the branching tree (Cuts), the number of nodes of the branching tree (Nodes), the average integrality gap of the linear relaxation (LRGap), the average integrality gap of the linear relaxation after the cuts in the root node (RGap), the execution time in seconds taking into account that the time limit was settled to 1200 seconds (t(s)) and the number of instances solved within that time period (Sol)