{'fraction_non_alphanumeric': 0.03908402203856749, 'fraction_numerical': 0.015861742424242424, 'mean_word_length': 4.461330512458862, 'pattern_counts': {'":': 0, '<': 1, '<?xml version=': 0, '>': 3, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 17, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Joint Location and Cost Planning in Maximum Capture Facility Location under Multiplicative Random Utility Maximization

We study a joint facility location and budget planning problem in a competitive market under random utility maximization (RUM) models. The objective is to locate new facilities and make decisions on the budgets (or costs) to spend on the new facilities, aiming to maximize an expected captured customer demand, assuming that customers choose a facility among all available facilities according to a RUM model. We examine two RUM frameworks in the discrete choice literature, namely, the additive and multiplicative RUM. While the former has been widely used in facility location problems, we are the first to explore the latter in the context. We show that, under the additive RUM framework, the resulting cost optimization problem becomes highly non-convex and may have several local optimum solutions. In contrast, the use of the multiplicative RUM brings several advantages to the competitive facility location problem. More precisely, we show that the cost optimization problem under the multiplicative RUM can be solved efficiently by a general convex optimization solver or can be reformulated as a conic quadratic program and handled by a conic solver available in some optimization tools such as CPLEX or GUROBI. Furthermore, we consider a joint location and cost optimization problem and propose three approaches to solve the problem, namely, an equivalent conic reformulation, a multi-cut outer-approximation algorithm, and a local search heuristic. We provide numerical experiments based on synthetic instances of various sizes to evaluate the performances of the proposed algorithms in solving the cost optimization and joint location and cost optimization problems.


Introduction
Facility location has been one of the most fundamental problems in decision-making for modern transportation and logistics systems. In the most classical setting, this is the problem of determining a subset of locations from a given set of location candidates to set up new facilities, aiming at maximizing a profit function (e.g. expected customer demand, or expected revenue) or minimizing a cost function (e.g., operational or transportation cost). Customer demand plays a critical role in facility location problems as it is a driving factor in determining where to open facilities. In this work, we focus on a class of competitive facility location problems where customers' demand is predicted by a random utility maximization (RUM) model (Benati and Hansen, 2002a, Dam et al., 2021, Ljubić and Moreno, 2018, Mai and Lodi, 2020. In this class of problems, it is assumed that customers choose among different facilities by maximizing utilities that they assign to the available facilities. Such utilities are typically functions of facility attributes/features, e.g., quality of services and infrastructure of the facilities, and transportation costs. The use of the RUM framework in the context is well supported by the popularity and usefulness of RUM models in modeling and predicting people's choice behavior (Ben-Akiva and Lerman, 1985). To the best of our knowledge, existing RUM-based facility location studies only focus on making location decisions, ignoring the fact that customers' demand would be significantly affected by other factors such as the opening/operating costs spent on the new facilities.
We address this limitation in this paper.
It is well-known that facility location and cost decisions would significantly impact customer demand, thus determining the success of the business, especially in a competitive market where other players are competing for the market share. For instance, in the context of car-sharing businesses where customers have the options of using their own vehicles or renting cars from different car-sharing services, Ciari et al. (2014), Jorge and Correia (2013) show that customer demand is mainly affected by the distance to the car-rental stations and the service availability at these stations, and Shaheen et al. (1998) indicate that when customers observe more vehicle availability and usage conveniences in the newly opened rental stations, their demand for the service would increase. Intuitively, customer demand would be critically affected by both the service availability within their neighborhood (i.e. locations of the service) and the quality of the service, which is generally dependent on the costs spent on the facilities. This is our main motivation to jointly consider the location and cost planning in the context of competitive facility location.
In our joint problem, the objective is to maximize an expected customer demand by making decisions on choosing locations to open new facilities and distributing the available budget to the new facilities. To model the impact of the costs on customer behavior, we include the costs into the customers' utility functions, taking into consideration the fact that giving a higher cost to a facility would make this facility more attractive to customers and increase the probability that the facility will be chosen. We then formulate the problem as an optimization problem with binary (for the choices of locations) and continuous (for the costs) variables. Due to the nonlinear structures of the RUM models, the resulting location and cost optimization problem becomes highly nonlinear and challenging to handle. We then focus on the question of how to efficiently solve the proposed problems under large-scale settings. We will state our main contributions in the following, but before that, we note that, throughout the paper, when we say "choice-based decision-making problem", we are referring to a decision-making problem where customer/user behavior is predicted by a discrete choice model, e.g., facility location or assortment optimization under a RUM model.

Contributions:
We consider both the additive RUM (ARUM) (McFadden, 1978) and multiplicative RUM (MRUM) (Fosgerau and Bierlaire, 2009) frameworks, where the former assumes that a random utility is a sum of a deterministic and a random error terms, the latter framework relies on the setting that the random utilities have a multiplicative structure, i.e., a random utility is a product of a deterministic and a random error term. While the former has been popularly used in facility location (any other choice-based decision-making problems), we are the first to consider the latter in the context. We show that while the cost optimization problem under ARUM is highly non-convex and may have several local optimal solutions, the cost optimization problem under the MRUM framework can be solved efficiently by convex optimization. Furthermore, we show that the cost optimization problem under MRUM can be reformulated as a conic program, which can be efficiently handled by a conic solver such as CPLEX or GUROBI. These indicate the fact that the MRUM framework would bring great advantages into the context of choice-based facility location, as compared to the classical ARUM framework.
We then consider the joint location and cost optimization problem under MRUM and propose three solution approaches to solve the problem. First, we propose an equivalent conic reformulation that allows us to exactly solve the problem by a mixed-integer conic program solver available in some popular optimization tools such as CPLEX or GUROBI (see Bonami and Tramontani, 2015, for instance). Second, we show that the joint problem can be also handled exactly by a multicut outer-approximation algorithm (Bonami et al., 2011, Hijazi et al., 2014, Mai and Lodi, 2020. Third, motivated by the fact that some recent studies have shown that a local search heuristic would achieve state-of-the-art performance in the context (Dam et al., 2021), we develop such a local search procedure to solve our joint problem.
We provide numerical experiments based on generated instances of various sizes to validate the performances of our approaches, for both the cost optimization and the joint location and cost optimization problem under the MRUM framework. Our numerical results clearly demonstrate the superiority of the conic reformulation approach for the cost optimization problem, and the multicut outer-approximation algorithm for the joint location and cost optimization problem, especially for large-scale problem instances.
It should be noted that, in this paper, we focus on multinomial logit (MNL) based models (i.e., the random terms are independent and identically distributed) (Train, 2003). This is the most popular model in the discrete choice modeling and choice-based decision-making literature.
Other choice models taking into consideration the correlation between choice alternatives exist, e.g., the nested or mixed logit models (McFadden andTrain, 2000, Train, 2003) but we will keep them for future work.
Literature review: Our work contributes to the line of research on the maximum capture facility location problem under random utilities. In this context, Benati and Hansen (2002a) seems to be the first to formulate the maximum capture problem (MCP) under the ARUM-based multinomial logit model (MNL) and propose methods based on mixed-integer linear programming (MILP) and variable neighborhood search. Afterward, some alternative MILP reformulations have been proposed by Zhang et al. (2012) and Hasse (2009). Haase and Müller (2014) provide a comparison of existing MILP reformulation models and conclude that the MILP model from Hasse (2009) gives the best performance. Freire et al. (2016) strengthen the MILP reformulation of Hasse (2009) using a branch-and-bound algorithm with some tight inequalities. Lin and Tian (2021a,b) further improve the MILP approach using Benders decomposition. Ljubić and Moreno (2018) propose a branch-and-cut method combining outer-approximation and submodular cuts, and Mai and Lodi (2020) propose a multicut outer-approximation algorithm to efficiently solve large-scale instances. Recently, (Dam et al., 2021) study the MCP under the generalized extreme value (GEV) family of models and propose a local search algorithm with guarantees. To the best of our knowledge, existing works in the context of the MCP only focus on the selection of locations, thus the original optimization problems only involve binary variables. In contrast, our joint location and cost optimization problem involves both binary and continuous variables, thus existing combinatorial optimization algorithms do not directly apply.
The literature on random utility maximization models covers both the ARUM and MRUM frameworks. While the ARUM framework has been widely studied since the 1908s and already has as many successful applications (McFadden, 1978, 1981, Train, 2003. The MRUM framework appears in the literature since the 2000s and seems to be less popular. Brilon and Dette (2002) seem to be the first to mention the multiplicative structure and since then this framework has been studied and applied by various researchers (Börjesson and Eliasson, 2014, Börjesson et al., 2012, De Jong et al., 2014, Fosgerau, 2006, Fosgerau and Bierlaire, 2009, Hess et al., 2018. In particular, it has been shown that changing from the additive to the multiplicative structure (i.e, from ARUM to MRUM) would lead to a large improvement in model fit, sometimes larger than that gained from introducing random coefficients in the deterministic terms of the utilities (i.e., the mixed MNL model (McFadden and Train, 2000)) (see Fosgerau and Bierlaire, 2009, for instance). As far as we know, in the context of the choice-based facility location and other choice-based decision-making problems such as assortment optimization (Rusmevichientong et al., 2010, Talluri and Van Ryzin, 2004, this is the first time the MRUM framework is exploited.
Since we study a joint location and cost optimization problem, our work closely relates to joint assortment and pricing optimization problems (Chen and Jiang, 2020, Miao and Chao, 2021, Wang, 2012, where the relation to the MCP problem stems from the analogy of set of products to set of locations and of continuous prices to continuous costs to spend on the new facilities. In particular, the objective function in the MCP is a sum of ratios, thus our problem share a similar structure with a joint assortment and price optimization problem under the mixed MNL model (McFadden and Train, 2000), for which Li et al. (2019) show that the price optimization itself is highly non-convex and challenging to solve. Later on in the paper, we will also show that the cost optimization MCP under ARUM is also highly non-convex and may have several local optimums. Again, we highlight the fact that, as far as we know, existing assortment and/or price optimization work only employs the ARUM framework. Thus, our work here would encourage the use of the MRUM counterpart in assortment and/or price optimization problems.
Paper outline: Our paper is organized as follows. Section 2 presents the problem formulations where we introduce the formulations of the joint location and cost optimization problems under both ARUM and MRUM frameworks. Section 3 presents the cost optimization problems under the ARUM and MRUM frameworks where we investigate issues associated with the ARUMbased problem and develop solution methods for the MRUM-based one. Section 4 presents our solution methods to deal with the joint location and cost optimization problem under MRUM.
Section 5 provide our numerical experiments, and Section 6 concludes.
Notation: Boldface characters represent matrices (or vectors), and a i denotes the i-th element of vector a. We use [m], for any m ∈ N, to denote the set {1, . . . , m}.

Problem Formulations
In this section, we present the additive and multiplicative RUM models and introduce the formulations of the joint facility location and cost optimization problems under these frameworks.

Additive and Multiplicative RUM models
The discrete choice framework (Train, 2003) assumes that each individual (decision-maker) n associates an utility U ni with each alternative i in a choice set S n . It is then assumed that each utility U ni consists of two parts: a deterministic part V ni that contains some observed attributes of the corresponding alternative and the individual n, and a random term ni that is unknown to the analyst. Different assumptions can be made on the random terms, leading to different types of discrete choice models. In general, a linear-in-parameters formula is used for the deterministic part of the utility, i.e, V ni = β β β T a ni , where β β β is a vector of parameters that can be estimated using historical observations and a ni is a vector of attributes of alternative i as observed by individual n. Under the RUM framework, the probability that individual n selects item i ∈ S n can be computed as P (U ni ≥ U ni , ∀j ∈ S n ), i.e., the individual chooses an item of the highest utility.
Under the additive RUM (ARUM) assumption (McFadden, 1978, Train, 2003, the deterministic parts and random terms have additive form, U in = V ni + ni . Under the popular multinomial logit (MNL) model where ni are i.i.d and follow the standard Gumbel distribution, the choice probabilities have the following form The MNL is widely used in both demand modeling and decision-making (Talluri andVan Ryzin, 2004, Train, 2003) due to its simple structure. The model however retains the independence from irrelevant alternatives (IIA) property which may be not hols in many situations. Efforts have been made to overcome this shortcoming, resulting in several discrete choice models, i.e., the nested logit (Ben-Akiva, 1973), cross nested logit (Vovsha and Bekhor, 1998), network multivariate extreme value (MEV) (Daly and Bierlaire, 2006), or mixed logit (McFadden, 1981) models.
The multiplicative RUM framework (Börjesson et al., 2012, Brilon and Dette, 2002, Fosgerau and Bierlaire, 2009) replaces the additive assumption in the ARUM framework by its multiplicative couter part, i.e., U ni = V ni ni , where V ni and the random terms ni are additionally assumed to be positive to made log V ni and log ni valid to derive the choice probabilities. The choice probability that individual n selects item i becomes P (V ni ni ≥ V nj ni ∀j ∈ S n ). Since the logarithm is a strictly increasing function, the choice probabilities can be further written as We then can impose some similar assumptions on the random terms log nj , as in the ARUM framework, to get closed form choice probabilities. For instance, if log ni are i.i.d and follow the standard Gumbel distribution, the choice probabilities become Here, we note that it is only necessary to assume that the signs of V ni are the same over i ∈ S n .
In the case that V ni are negative, we can write the choice probabilities as P the assumption that − ni are positive. One then can assume that log(− ni ) are i.i.d Gumbel distributed to obtained a MNL-based model P (i|S n ) = (−V ni )/ j∈Sn (−V nj ) . Similarly to the ARUM framework, other assumptions can be made for the random terms (log ni or log(− ni )) to obtain models with nested, cross nested, or mixed structures.

Joint Location and Cost Optimization MCP
In the context of the competitive maximum capture problem, a "newcomer" firm aims to locate new facilities in a competitive market where there are existing facilities from competitors. The firm's objective is to maximize the expected captured market share achieved by attracting customers to new facilities. To capture the customers' demand, we suppose that a customer selects a facility according to a RUM discrete choice model (ARUM or MRUM). In this context, the set of all locations and by I the set of all customer types. Depending on the application, I can be a set of customer types categorized by customers' characteristics (e.g, age or income), or can be a set of geographical zones where customers are located. Assume that there are q i customers for each type i ∈ I. Let V ij be the deterministic utility that customer i ∈ I assign to a facility at location j ∈ [m] when making choice decisions, and V i is a vector of size m with entries V ij , for all i ∈ I. Given any subset S ⊂ [m] of new facilities, under the additive MNL model, the choice probabilities of customer i ∈ I are given as where U c i represents the utility of the competitor. Without loss of generality, we can assume that U c i = 1 (Dam et al., 2021). When the facility planing and cost optimization problems are considered simultaneously, we write the utilities V ij as V ij = a ij x j +b ij , where a ij is a parameter representing the sensitivity of customer i w.r.t. the cost spent on facility j, x j is the cost to spend on facility j, and b ij is another factor that affect customer choice decisions, e.g., distance or parking availability. The parameters a ij play an important role in our model, in the sense if a customer i is located far away from location j, the investing cost of facility j would not make a significant impact on the choices of the customer, and on the other hand if location j is close to the location of customer i, then adding more budget to the facility setup would make a huge impact on the attractiveness of the facility. In fact, it is to be expected that larger x j (more cost to spend on facility j) will make the facility more attractive to customers, thus a ij should take positive values. The joint facility location and cost optimization problem can be formulated as where C is the maximum budget to spend on the new facilities, L x j and U x j are the lower and upper bounds for the cost on facility j ∈ [m]. It is required that j∈S L x j ≤ C for some S ∈ S to ensure feasibility. More general linear constraints on the costs x can be included, but we only consider a capacity constraint j∈S x j ≤ C and the bound constraints for the sake of simplicity.
It is then convenient to represent the set of locations S by binary variables and formulate the MCP under ARUM as a binary-continuous nonlinear program where M is the maximum number of facilities to be opened, constraints (4) is to ensure that if there is no facility at location j, the corresponding cost should be zero and (5) is to force the cost x j to be at least L x j if location j is selected (i.e., y j = 1).
If the choice model is a multiplicative MNL model, the choice probabilities become and the joint facility and cost optimization MCP can be formulated as max x,y If the costs x are fixed and only the facility location problem is considered, then (MCP-ARUM) and (MCP-MRUM) share the same structure, thus existing methods developed for the ARUMbased MCP problem (Benati and Hansen, 2002b, Haase and Müller, 2014, Mai and Lodi, 2020 can be applied to the MRUM-based problem. When the cost optimization is taken into consideration, the joint facility location and cost optimization problem under MRUM seems to have a simpler structure, as exponential functions are now replaced by linear ones. We discuss this in more detail in the next sections.
In this section we focus on the cost optimization problem, assuming that the location variables y are fixed. We show that the cost optimization problem under ARUM is generally non-concave and would have several locally optimal solutions, even when there is only one customer type, i.e., |I| = 1. In contrast, we show that the cost optimization problem under the MRUM is convex and can be solved to optimality by a nonlinear optimization solver. Furthermore, the cost optimization problem under MRUM can be formulated as a conic program, for which some exiting solvers such as CPLEX or GUROBI can handle.

Non-unimodality of the MCP under ARUM
We first consider the cost optimization problem under ARUM. The following remark states that As a result, the MCP under ARUM, even when we only seek optimal costs, is generally not tractable to handle.

Proposition 1 The objective function of the MCP under ARUM is not unimodal, even when
there is only one customer type, i.e., |I| = 1.
Proof. We validate the remark with a counterexample. Let us consider the following instance Here since we fix S, we remove the corresponding notation for notational simplicity. Clearly, the above objective function is an instance of the MCP under ARUM with 1 customer zone and 2 locations. The MCP can be written equivalently as and it is easy to see that there are to local optimal solutions at x 1 = 0 and x 1 = 1 and the objective function achieves its maximum value at x 1 = 0. We illustrate the two local optimums in Fig. 1 below. Thus, MCP has two local optimal solutions at x = (1, 0) and x = (0, 1).
In fact, when |I| = 1, we can write the objective value of the cost optimization problem under ARUM as where i is the unique customer type in I. The problem max x∈X j∈S e a ij x ij +b ij is a maximization problem with a convex objective function, thus several local optimums may exist. In

Cost Optimization MCP under MRUM
We consider the cost optimization problem under the MRUM framework, where the objective function can be written as It is known that a function of the form 1/(α α α T z) is convex in z Hansen, 2002a, Mai andLodi, 2020). As a result, f MRUM (y, x) is concave. We state this important result in Remark 1 below.
The concavity implies that the cost optimization problem under MRUM can be solved to optimality by a general nonlinear optimization algorithm, e.g., gradient ascent, trust region, or linear search (Nocedal and Wright, 2006).

Conic reformulation.
Conic optimization refers to optimization of a linear function over conic quadratic inequalities of the form ||Az−b|| ≤ cx+d, where ||·|| is the L2 norm. Solvers for such a conic quadratic optimization problem are now available in some commercial optimization tools such as CPLEX or GUROBI. We will make use of the fact that such a rotate cone/hyperbolic inequality of the form z 2 1 ≤ z 2 z 3 , for z 1 , z 2 , z 3 ≥ 0, can be formulated as a conic quadratic inequality ||(2z 1 , z 2 − z 3 )|| ≤ z 2 + z 3 .
In the following, we show that the cost optimization under MRUM can be formulated as a conic quadratic optimization problem. We first let We then can formulate the cost optimization problem under MRUM as max x i∈I Constraints (2)-(3)-(4)-(5), Constraints (6) are not rotated cones, but we can safely replace them by rotate cones θ i w i ≥ 1.
We state this result in the following proposition.
Proposition 2 (CP) can be formulated as the following conic quadratic optimization problem

Proof.
We observe that if we replace the equality constraints by inequalities θ i w i ≥ 1, then because θ i and w i are non-negative and the objective function involves terms q i θ i , the maximization problem always forces θ i to be as small as possible. Thus, at optimum, the inequality constraints θ i w i ≥ 1 are always active, i.e., θ i w i = 1. This leads to the desired result.
The conic program in (CP-CONIC) has m + 2|I| continuous variables while the original concave optimization problem max x {f MRUM (x)} has only m continuous variables. However, it is expected that solving the conic program using an advanced optimization tool such as CPLEX would be faster and more scalable than directly solving the problem by a convex optimization solver, due to some advanced linear and conic programming techniques implemented in CPLEX's conic solvers (Bonami and Tramontani, 2015).
The cost optimization MCP problem has the form of a some-of-ratio program. In its most general form, the problem can be written as max and α α α n , β β β n , n ∈ [N ], are vectors of the same size with x. Such a some-of-ratio problem is known to be highly non-convex and challenging to be solved globally (Schaible, 1995). In our context, the cost optimization problem can be solved by convex optimization because the objective function can be written as a sum of ratios of constant numerators.
It is also interesting to link the formulation in (CP-CONIC) to the context of price optimization under discrete choice models. Under the MRUM framework, if the choice model is the MNL, the objective function of the corresponding price optimization problem contains only one ratio, thus the problem can be conveniently converted to a linear program (Schaible, 1995). If the choice model is the mixed MNL, the problem will have the form of the general some-of-ratio program and would be highly non-convex and challenging to handle.

Joint Location and Cost Optimization under MRUM
In this section, we consider the joint facility location and cost optimization problem under MRUM. We will present our three approaches, two exact and one heuristic, to handle the problem, namely, an equivalent mixed-integer conic program, a multicut outer-approximation algorithm and a local search procedure.

CONIC Reformulation
We will also make use of the following rotated cone x 2 1 ≤ x 2 x 3 , with x 1 , x 2 , x 2 ≥ 0 to present conic quadratic inequality. To reformulate the nonlinear binary program (MCP-MRUM) as a CONIC program, we denote a ij y j x j and write (MCP-MRUM) as min x,y i∈I We now let z j = y j x j . Since this term involves a binary variable, the equality can be linearized using McCormick inequalities (McCormick, 1976) as Furthermore, since both θ i and w i are non-negative, similarly to Proposition 2, one can show that the equality θ i w i = 1 can be replaced by the inequality θ i w i ≥ 1, which is a rotated cone.
In summary, we can formulate (MCP-MRUM) as the following CONIC program min x,y i∈I The mixed-integer conic program in (FC-CONIC) has 2m + 2|I| continuous and m binary vari-

Multicut Outer-Approximation
We show that an outer-approximation algorithm can be used to solve the joint facility location and cost optimization problem. We also let z j = x j y j , j ∈ [m], and linearize these terms using McCormick inequalities (McCormick, 1976) to obtain the equivalent reformulation max x,y,z We can further see that the objective function of (MCP-MRUM-2) is concave in z, y. This remark is essential for the use of the outer-approximation method. We state it in the following remark.
Remark 2 (Concavity) Each component q i (1 + j∈[m] a ij z j + y j b ij ) of the objective function of (MCP-MRUM-2) is concave in y and z, ∀i ∈ I.
To apply the multicut outer-approximation scheme (Duran andGrossmann, 1986, Mai andLodi, 2020), we divide the set of customers I into L disjoint groups D 1 , . . . , D L such that l∈L D l = I.
We then write the objective function of (MCP-MRUM-2) as An multicut outer-approximation algorithm will build a piecewise linear function that outerapproximates each concave function φ l (y, z). Such a outer-approximation can be constructed by creating sub-gradient cuts of the form θ l ≤ ∇ y φ l (y, z)(z−z)+∇ z φ l (y, z)(y−y)+φ l (y, z), where (y, z) is the current solution candidate, and ∇ y φ l (y, z) and ∇ z φ l (y, z) are the gradients of φ l (·) w.r.t. y, z, respectively. The outer-approximation algorithm executes an iterative procedure where at each step it adds sub-gradient cuts to the following master problem max θ θ θ,x,y,z l∈ [L] θ l (sub-MOA) where the linear constraints in (7) are the sub-gradient cuts added to the master problem at each iteration. The algorithm will keep adding cuts and solving the master problem until its get a solution (x * , y * , z * , θ θ θ * ) such that l∈[L] θ * l ≤ l∈[L] φ l (y * , z * ) + τ , where τ > 0 is a stopping threshold. The concavity of φ l (y, z), ∀l ∈ [L] guarantees that the outer-approximation algorithm will eventually converge to an optimal solution (Bonami et al., 2011, Duran andGrossmann, 1986).

Local Search Heuristic
Previous works show that a local search procedure can achieve state-of-the-art performance for the facility location MCP under ARUM. Therefore, in this section, we explore a local search procedure to solve the joint facility and cost optimization problem under MRUM. First, let us define Φ(y) = max where X (y) is the feasible set of x conditional on y, i.e., }. According to Section 3, for a given y, the value of Φ(y) can be computed efficiently by solving a convex optimization problem, or an equivalent CONIC program. We now can perform a local search procedure on Φ(x). Prior works show that the objective function of the facility location MCP is monotonic, i.e., opening new facilities always increases the objective function. However, we show that it is not the case here in the context of the joint facility location and cost optimization problem.
Intuitively, when a new facility at location j is built and operated, it would require a minimum cost L x j > 0, which would reduce the investment/operational costs for other facilities. The objective function then would decrease if the new facility is much less attractive to the customer than the other ones. On the other hand, if the total budget C is sufficiently large, e.g., C ≥ j∈[m] U x j , then we can see that Φ(y) is monotonic increasing in y.
Proposition 4 tells us that we need to compute the Lagrange multipliers λ * , γ γ γ U * and γ γ γ L * to to compute the derivatives of Φ(y) w.r.t. y. This can be done by solving the Lagrange duality min λ,γ γ γ U ,γ γ γ L max x L(x, λ, γ γ γ U , γ γ γ L |y), which would be expensive. Alternatively, we can directly solve the convex problem max x∈X (y) f MRUM (y, x) by an existing optimization solver and infer the Lagrange multipliers from the optimal solution obtained. That is, let x * be the unique optimal solution to max x∈X (y) f MRUM (y, x). From (12) we have To infer λ * , γ γ γ U * and γ γ γ L * , we consider the following cases: • If j∈[m] x * j < C, then from (13) we see that λ * = 0. Then using the complementary slackness conditions in (14)-(15) we can infer the values of γ U * j and γ L * j as follows. For each x * j such that y j > 0 we have and for any j ∈ [m] we have . This means that C can be written as a sum of some lower bounds L x j and some upper bounds U x j . In this situation, the Lagrange multipliers cannot be uniquely identified using the KKT conditions. We can simply add some small amount to C such that it no-longer can be written as a sum of some upper and lower bounds L x j , U x j . This allows us to switch the situation to the two above cases, for which the Lagrange multipliers can be well identified. Note that, by adding a small amount to C, we slightly modify the objective function Φ(y), but we expect that if the amount added to C is relatively small, we still can obtain a good approximation of the gradients of Φ(y).
The local search algorithm consists of three steps. In the first step, we start with an empty solution and keep adding locations to the current solution, taking locations that increase the objective function Φ(y) the most. The first step stops when the solution candidate reaches the capacity M or it cannot find a better solution. The second step is a gradient-based local search.
The gradient information given in Proposition 4 is made use to approximate the nonlinear objective function f MRUM and find the next solution candidates. The last step is a simple exchanging procedure trying to swap a location in the current choice set with some other locations outside the current choice set of locations to improve the solution found after the second step. We refer the reader to Dam et al. (2021) for more details.
The above local search procedure runs fast and returns good solutions for previous competitive facility location problems (Dam et al., 2021, Thuy Ta et al., 2021, but it would be not the case in the context of the joint problem because each iteration of the local search requires to compute several values of Φ(y), thus requires to solve several cost optimization problems. In other words, the local search algorithm developed for the joint location and cost optimization under MRUM would be expensive and not as competitive as the other exact methods discussed above (i.e., the CONIC reformulation and the outer-approximation algorithm). We will show this clearly in the experimental section below.

Numerical Experiments
In this section, we provide experimental results for the two problems we study, i.e. the cost optimization MCP and the joint location and cost optimization MCP problems under MRUM.
We first present our experimental settings and then provide our comparison results.

Experimental Settings
We randomly generated a dataset for each problem to evaluate the performance of the algorithms proposed. The dataset for the cost optimization problem has totally 240 instances, in which we generate 24 instances for each pair (|I|, m) in the set {(100, 100), (100, 1000), (100, 3000), (200,2000), (400, 1000), (800, 400), (800, 800), (1000, 1000), (2000,2000), (5000, 1000) }, and the dataset for the joint location and cost optimization problem has 216 instances of the same values of (|I|, m) as in the cost optimization problem, but excludes the pair (2000,2000) since instances of this size become too expensive to be solved by any approaches within the time budget.
We set the maximum budget to spend on the new facilities as C ∈ {0.2m, 0.5m, 0.7m} and the maximum number of facilities that can be opened as M ∈ {0.2m, 0.5m, 0.7m}, recalling that m is the total number of possible locations. As describe above, given i ∈ I and j ∈ [m], the parameter a ij represents the sensitivity of customer i w.r.t the cost spent on facility j, and the parameter b ij represents other factors that affect customers' choice decisions. Both a ij and b ij parameters are generated randomly and uniformly from {[0.5, 1.5] and [1, 10]}, respectively.
The parameter q i representing demand of customer i is also generated randomly and uniformly from two intervals [1, 10] and [90,100]. The two parameters L x j and U x j , ∀j ∈ [m], (i.e., the lower and upper bounds for the cost to spend on facility j ∈ [m]) are also generated uniformly from two closed intervals satisfying that j∈[m] L x j ≤ C for some sets of j ∈ [m]. We note that the dataset for the cost optimization MCP problem needs to satisfy j∈[m] L x j ≤ C to ensure that the problem always has a feasible solution.
The experiments are conducted on a PC with processors AMD Ryzen 3-3100 CPU @ 3.60 GHz, RAM of 16 gigabytes, and operating system Window 10. We use MATLAB 2020 to implement and run the convex optimization algorithms for the cost optimization problem. We use C++ and link to IBM ILOG-CPLEX 12.10 (under default settings) to solve CONIC programs and the master problem of the multicut outer-approximation algorithm. The CPU time limit for each instance is 600 seconds, i.e., we stop the algorithms if they exceed the time budget and report the best solutions found.

Cost Optimization MCP
In this section, we provide comparison results for the cost optimization MCP. We solve the instances generated above by the two approaches discussed in Section 3, i.e., using a general convex optimization solver (i.e., fmincon of MATLAB), and solving the equivalent CONIC program by CPLEX. We denote the two approaches as CONIC and CONVEX. Table 1 below reports the numbers of instances solved with the best objectives and the average CPU times.
Each row of this table reports averages over 8 instances grouped by(|I|, m), and C. We highlight in bold the largest numbers of instances solved with best objective values, noting that both approaches within the time budget, we know that the instance is solved to optimality.  the CONIC approach is about 5 to 30 times faster than the CONVEX. More specifically, for instances of (|I|, m) = (100, 1000), the average CPU times required by CONVEX are about 15 times larger than those required by the CONIC. CONIC is even about 30 times faster than CONVEX for instances of m = 3000. In addition, we can see that an increase in the number of zones |I| or the number of locations m produces remarkable changes in performance for both CONIC and CONVEX, while a change in C has almost no effect.

Joint Location and Cost Optimization MCP
In this section, we report numerical results for the joint location and cost optimization problem.
We perform a comparison between three approaches proposed above, namely, the CONIC reformulation solved by the CPLEX's conic solver (Bonami and Tramontani, 2015), the multicut outer-approximation algorithm (denoted as MOA), and the local search heuristic (denoted as LS). We note that one of the most important parameters affecting the performance of the MOA algorithm is the number of groups T (i.e, the number of cuts added to the master problem at each iteration). Therefore, we test our MOA algorithm with T ∈ {1, 5, 20}. A more detailed analysis on the performance of MOA when T varies will be provided later. For the LS approach, the computation of each Φ(y) requires to solve a cost optimization problem over x. To this end, we use the CONIC approach (i.e. the better one among the two methods proposed to solve the cost optimization problem -see Section 5.2 for instance).
We first report the comparison results for our small and medium instances in Table 2, where each row of the table reports the averages for 8 instances grouped by |I|, m, C, and M . There are 45 groups of instances in total. Here, we know that the CONIC and MOA are global approaches, thus if they stop before exceeding the time budget (600 seconds), then we report that the corresponding instances are solved to optimality. In contrast, since LS is heuristic, we do not include this approach in the "solved to optimality" columns. We also take the best solutions found by the three approaches (CONIC, MOA, and LS) and report the numbers of instances solved with the best objectives. We also indicate the largest numbers of instances solved to optimality and the largest numbers of instances solved with the best objective values in bold. Table 2 shows that the MOA algorithms seem to achieve the best performance for all the instances considered in terms of the number of instances solved to optimality; they provide optimal solutions for all the instances of each group, while the CONIC approach only gives the optimal solutions for 22/45 groups of instances. We also observe that the CONIC approach is less efficient in cases where M = m/5. In particular, for larger problem instances (e.g.,  We now turn our attention to the average CPU times. In Table 2 we indicate in bold the smallest average CPU times. We first remark that LS has the worst performance as it always requires more than 600 seconds to solve 43/45 groups of instances. This is contrary to what has been observed for other MCP facility location problems (Dam et al., 2021) but is to be expected, as we discuss earlier, each step of the LS requires to solve numerous cost optimization problems, thus is much more expensive than when only the selection of locations is considered. Moreover, we also observe that the MOA algorithms outperform the other approaches (CONIC and LS) in terms of average CPU time for instances of (|I|, m) ∈ {(100,100), (800,400), (800,800),(400,1000)} and they are just slightly slower than CONIC for 6 instances of (|I|, m) = (100, 1000). If we count the numbers of groups for which each approach requires the shortest average CPU times (number of values in bold on each column), we can see that M1 (i.e. single-cut outer-approximation) performs the best with 32/45 times dominating the other approaches, followed by M2 (with 9/45 times) and M20 (8/45 times). In particular, the CONIC only performs the best for only 1/45 group of instances and LS exceeds the time budget for most the cases and is always the slowest approach.
In Table 3 we report the comparison results for large-size instances. Each row of the    Table 3: Comparison results for the joint location and cost optimization problem, for large-size instances grouped by (m, |I|, C, M ) (8 instances per row); CN stands for the CONIC approach and M1, M5, M20 stand for the MOA algorithm with T = 1, 5, 20, respectively.
In terms of average CPU time, we first note that LS remains to be the worst since it exceeds the time budget of 600 seconds for all the instances. In fact, for medium-size and large-size instances, due to the expensiveness of the computation of Φ(y), the LS algorithm could not complete the first step (i.e., adding locations to an empty set) within the time budget. Moreover, if we look at the groups of instances that all the four approaches (CONIC, M1, M5 and M0) provide optimal solutions for all 8/8 instances, the average CPU times required by CONIC are higher than those required by M1 and M5, but lower than the average CPU times of M20. We also observe that CONIC performs well for instances of |I| ≤ 200, m ≥ 1000 and M = 0.7m. For these instances, CONIC is even better than M5. In summary, MOA with T = 1 requires the shortest CPU times in most groups of instances (20/36). It is better than the MOA algorithm with T ∈ {5, 20} (the numbers of such groups for M5 and M20 are 12 and 9, respectively), although the gaps are not as large as in the small-size and medium-size instances. The CONIC and LS approaches always require higher average CPU times for all the groups of instances, as compared to the  Figure 3 shows that the MOA algorithms with small T (i.e, T = 1 or T = 5) seem to achieve good performance for M ∈ {0.5m, 0.7m}. However, the algorithm becomes slower for instances of M = 0.2m. Such instances seem to be better solved by MOA with T from 10 to 25. We also observe that, when T becomes too large (e.g. T ≥ 50), the MOA algorithm becomes slow and often encounters out-of-memory issues. This is to be expected as if T is large, the master problem grows quickly in size, and will become much more expensive to solve. All these are consistent with observations in (Mai and Lodi, 2020). It is interesting to note that the MOA algorithm with T = 25 seems to performs the best in terms of CPU time, but the results in Table 2 and Table 3 show that the MOA with T = 1 seems to be more robust, in the sense that it gives the highest number of instances solved to optimality.
This can be explained by the fact that MOA with a high value of T would better explore the structure of the problem and require less iterations to converge. On the contrary, MOA with T = 1 will require more iterations, but the cost to perform one iteration will be cheaper. Thus, the MOA with high T would finish small-or medium-size instances faster, but for large-size instances, the master problem is getting expensive quickly and the MOA would not be able to terminate the instances within the time budget.
In summary, for the cost optimization problem, we observe that our proposed methods (CONIC and CONVEX) are able to solve large-scale instances to optimality in fairly short CPU times, and the CONIC approach performs better than CONVEX. For the joint location and cost optimization problem, the MOA with T = 1 performs the best in terms of number of instances solved to optimality. In particular, the MOA algorithms can efficiently handle instances of thousands of locations and customer zones. The LS approach, even-though performs well in prior MCP work, performs the worst.

Conclusion
In this paper, we studied a joint facility location and cost optimization problem under RUM models. We examined the two popular RUM frameworks in the discrete choice literature, namely the ARUM and MRUM. We showed that, while the cost optimization under ARUM is highly non-convex and would be challenging to handle, the cost optimization problem under MRUM seems more appealing to deal with, as it can be efficiently and exactly solved by a convex optimization or conic programming solver. We further dealt with the joint location and cost optimization problem under MRUM by proposing two exact methods based on a conic reformulation and the multicut outer-approximation scheme, and a local search heuristic. We provided experiments based on generated instances of various sizes, which show the efficiency and scalability of our approaches, in particular the CONIC approach for the cost optimization problem and the MOA algorithms for the joint problem.
Our paper clearly shows several advantages of the MRUM framework in facility location, which would suggest promising directions for future work, for instance, exploring the use of the MRUM framework in other choice-based decision-making problems such as joint assortment and price optimization (Wang, 2012) or security game problems (Yang et al., 2012).