Extracted main text — title through conclusion, appendix excluded. This is what our citation measures are computed over, published so the extraction can be checked by eye.
87,091 characters · 18 sections · 67 citation commands
Joint Location and Cost Planning in Maximum Capture Facility Location under Random Utilities
\newcolumntype{C}{>{\arraybackslash}p{4em}}
\affil[1]{\it ORLab, Department of Computer Science, Phenikaa University} \affil[2]{\it School of Computing and Information Systems, Singapore Management University}
{\bf Keywords:} Competitive facility location, maximum capture, joint location and cost optimization, multiplicative random utility maximization, convex optimization, conic programming, outer-approximation, local search heuristic
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 modeled and predicted by a random utility maximization (RUM) model BenaHans02,Ljubic2018outer,mai2020multicut,Dam2021submodularity. 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 or infrastructure of the facilities, or transportation costs. The use of the RUM framework in the context is well supported by the popularity and advantages of RUM models in modeling and predicting people's choice behavior BenALerm85. 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 aboolian2007competitive,ciari2014modeling. 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, jorge2013carsharing,ciari2014modeling show that customer demand is mainly affected by the distance to the car-rental stations and the service availability at these stations, and shaheen1998carsharing 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 facility and cost optimization problem, the objective is to maximize an expected captured customer demand by making decisions on choosing locations to open new facilities and distributing the available budget to the new facilities. Since the objective is to maximize a captured demand function, such a problem is also referred to as the maximum capture problem (MCP). 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 spending a higher budget on 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 discrete choice model.
Contributions: We consider both the additive RUM (ARUM) McFa78 and multiplicative RUM (MRUM) FosgBier09 frameworks, where the former assumes that a random utility is a sum of a deterministic and a random error term and 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 (and other choice-based decision-making problems), we are the first to consider the latter in the context. We first provide a numerical study on the relation between the ARUM and MRUM frameworks in the context of the MCP. More precisely, we experimentally show that the choice probability functions and the MCP objective functions under the ARUM and MRUM can be well approximated by each other, supporting the use of the MRUM framework even when ARUM is the “ground-truth” one.
We further 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. In addition, we show that the cost optimization problem under MRUM can be reformulated as a conic quadratic program, which can be efficiently handled by an off-the-shelff solver (e.g. CPLEX or GUROBI). These findings indicate the fact that the MRUM framework would bring great advantages in 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 an off-the shelf solver such as CPLEX or GUROBI bonami2015recent. Second, we show that the joint problem can be also handled exactly by a multicut outer-approximation algorithm Bonami2011_BB_MIP,hijazi2014outer,mai2020multicut. 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 Dam2021submodularity, we develop such a local search procedure to solve our joint problem. We summarize our findings and solution methods in Table (ref) below.
We provide numerical experiments based on synthetic instances of various sizes to validate the performances of our approaches, for both the cost optimization and the joint location and cost optimization problems 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.
In this paper, we focus on multinomial logit (MNL) based models, i.e., the random terms are independent and identically distributed (i.i.d.) Trai03. 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 cross-nested logit models McFaTrai00,Trai03, but the MCP under such models are generally intractable to solve mai2020multicut,Dam2021submodularity and we keep them for future work.
Literature review: Our work contributes to the line of research on the maximum capture facility location problem under random utility maximization discrete choice models. In this context, BenaHans02 seems to be the first to formulate the 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 FLO_Zhang2012impact and FLO_Hasse2009MIP. FLO_Haase2014comparison provide a comparison of existing MILP reformulation models and conclude that the MILP model from FLO_Hasse2009MIP gives the best performance. FLO_Freire2016branch strengthen the MILP reformulation of FLO_Hasse2009MIP using a branch-and-bound algorithm with some tight inequalities. Lin2021branch,Lin2021generalized further improve the MILP approach using Benders decomposition. Ljubic2018outer propose a branch-and-cut method combining outer-approximation and submodular cuts, and mai2020multicut propose a multicut outer-approximation algorithm to efficiently solve large-scale instances. Recently, Dam2021submodularity 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 under RUM only focus on the selection of locations, yielding optimization problems that only involve binary variables. In contrast, our joint location and cost optimization problem involves both binary and continuous variables, thus existing exact combinatorial optimization algorithms do not directly apply.
It is worth mentioning that there have been papers proposing to use simulation to approximate the choice model, yielding mixed-integer linear programs (MILP) for the approximated choice-based optimization problems paneque2021integrating,lamontagne2022optimising. This approach is general as any RUM based choice model can be approximated by simulation, but is limited in the sense that a large number of samples would be required to deliver a good approximation of the choice model and the size of the MILP grows quickly as the number of samples increases. In contrast, our approach is exact and the sizes of our MILP and conic reformulations are remarkably smaller as they are only proportional to the number of locations. Our work also belongs to the broad literature of facility location Laporte2015introduction, noting that decisions on both locations and costs have been widely considered in the broad context aboolian2007competitive,berman2009modeling.
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 McFa78,McFa81,Trai03. The MRUM framework appears in the literature since the 2000s and seems to be less popular. MRUM_brilon2002multiplicative seem to be the first to mention the multiplicative structure and since then this framework has been studied and applied by various researchers FosgBier09, MRUM_hess2018revisiting,MRUM_borjesson2012valuations,MRUM_borjesson2014experiences,MRUM_de2014new,MRUM_fosgerau2006investigating. 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 McFaTrai00) FosgBier09. As far as we know, in the context of the choice-based facility location and other choice-based decision-making problems such as assortment and price optimization Talluri2004revenue,rusmevichientong2010dynamic,rusmevichientong2014assortment, our work is the first time the MRUM framework is explored.
Since we study a joint location and cost optimization problem, our work closely relates to joint assortment and pricing optimization problems wang2012capacitated,chen2020capacitated,miao2021dynamic, 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 McFaTrai00, for which li2019product 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 optima. 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 (ref) presents the problem formulations where we introduce the formulations of the joint location and cost optimization problems under both ARUM and MRUM frameworks. Section (ref) analyse the relation between the ARUM and MRUM frameworks in the context of the MCP. Section (ref) presents our solution methods to solve the cost optimization and joint location and cost optimization problems under MRUM. Section (ref) shows our numerical evaluations, and Section (ref) concludes.
Notation: Boldface characters represent matrices (or vectors), and $a_i$ denotes the $i$-th element of vector $\textbf{a}$. We use $[m]$, for any $m\in \mathbb{N}$, to denote the set $\{1,\ldots,m\}$.
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.
The discrete choice framework Trai03 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 $\epsilon_{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} = \pmb{\beta}^{{\mbox{\tiny T}}} \textbf{a}_{ni}$, where $\pmb{\beta}$ is a vector of parameters that can be estimated using historical observations and $\textbf{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\in S_n$ can be computed as $P(U_{ni}\geq U_{nj},\;\forall j\in S_n)$, i.e., the individual chooses an item of the highest utility.
Under the additive RUM (ARUM) framework McFa78,Trai03, the deterministic parts and random terms have an additive form, $U_{in} = V_{ ni}+\epsilon_{ni}$. Under the popular multinomial logit (MNL) model where $\epsilon_{ni}$ are i.i.d and follow the standard Gumbel distribution, the choice probabilities have the following form \[ P(i|S_n) = \frac{e^{V_{ni}}}{\sum_{j\in S_n} e^{V_{nj}}},\;\forall i\in S_n. \] The MNL is widely used in both demand modeling and decision-making Trai03,Talluri2004revenue due to its simple structure. The model however retains the independence from irrelevant alternatives (IIA) property which may be not holds in many situations. Efforts have been made to overcome this shortcoming, resulting in several discrete choice models, i.e., the nested logit BenA73, cross nested logit VovsBekh98, network multivariate extreme value (MEV) DalyBier06, or mixed logit McFa81 models.
The multiplicative RUM framework MRUM_brilon2002multiplicative,FosgBier09,MRUM_borjesson2012valuations replaces the additive assumption in the ARUM framework by its multiplicative couter part, i.e., $U_{ni} = V_{ni}\epsilon_{ni}$, where $V_{ni}$ and the random terms $\epsilon_{ni}$ are additionally assumed to be positive to make $\ln V_{ni}$ and $\ln\epsilon_{ni}$ valid to derive the choice probabilities. The choice probability that individual $n$ selects item $i$ becomes $P(V_{ni}\epsilon_{ni}\geq V_{nj}\epsilon_{nj}\;\forall j\in S_n)$. Since the logarithm is a strictly increasing function, the choice probabilities can be further written as \[ P(V_{ni}\epsilon_{ni}\geq V_{nj}\epsilon_{nj}\;\forall j\in S_n) = P( \ln V_{ni} +\ln \epsilon_{ni} \geq \ln V_{nj} +\ln \epsilon_{nj},\;\forall j\in S_n). \] We then can impose some similar assumptions on the random terms $\ln\epsilon_{nj}$, as in the ARUM framework, to get closed form choice probabilities. For instance, if $\ln \epsilon_{ni}$ are i.i.d and follow the standard Gumbel distribution, the choice probabilities become \[ P(i|S_n) = \frac{e^{\ln V_{ni}}}{\sum_{j\in S_n}e^{\ln V_{nj}}} = \frac{V_{ni}}{\sum_{j \in S_n} V_{nj}}. \] Here, we note that it is only necessary to assume that the signs of $V_{ni}$ are the same over $i\in S_n$. In the case that $V_{ni}$ are negative, we can write the choice probabilities as $P((-V_{ni})(-\epsilon_{ni})\geq (-V_{nj})(-\epsilon_{nj}),\;\forall j\in S_n) = P(\ln (-V_{ni}) +\ln(-\epsilon_{ni})\geq \ln(-V_{nj}) + \ln(-\epsilon_{nj}),\;\forall j\in S_n)$, with the assumption that $-\epsilon_{ni}$ are positive. One then can assume that $\ln(-\epsilon_{ni})$ are i.i.d Gumbel distributed to obtained a MNL-based model $P(i|S_n) = (-V_{ni})/\left(\sum_{j\in S_n}(-V_{nj})\right)$. Similarly to the ARUM framework, other assumptions can be made for the random terms ($\ln \epsilon_{ni}$ or $\ln (-\epsilon_{ni})$) to obtain models with nested, cross nested, or mixed structures.
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, each customer $n$ associates each new facility $i$ with a random utility $U_{ni}$ and choices are made by maximizing his/her utilities. The firm's decisions are a set of locations to setup new facilities and costs to spend on new facilities. In the following, we describe in detail our problem formulations under both ARUM and MRUM MNL-based models.
Assume that there are $m$ possible locations to locate new facilities. Let us denote by ${\mathcal{V}}= [m]$ the set of all possible locations and by $I$ the set of all customer zones. 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_n$ customers for each zone $n \in I$. Let $V_{ni}$ be the deterministic utility that customer zone $n\in I$ assign to a facility at location $i\in [m]$ when making choice decisions, and $\textbf{V}^n$ is a vector of size $m$ with entries $V_{ni}$, for all $n\in I$. Given any subset $S$ of possible locations i.e. $S\subset [m]$ under the additive MNL model, the choice probabilities of customer zone $n\in I$ are given as \[ P^{\textsc{ARUM}}(i|S,\textbf{V}^n) = \frac{e^{V_{ni}}}{U^c_n+ \sum_{i'\in S} e^{V_{ni'}}}, \] where $U^c_n$ represents the customer zone n’s utility of choosing a competitor’s facility. When the facility planing and cost optimization problems are considered simultaneously, we write the utilities $V_{ni}$ as $V_{ni} = a_{ni} x_i + b_{ni}$, where $a_{ni}$ is a parameter representing the sensitivity of customer zone $n$ w.r.t. the cost spent on facility $i$, $x_i$ is the cost to spend on facility $i$, and $b_{ni}$ is another factor that affects customer choice decisions, e.g., distance or parking availability. The parameters $a_{ni}$ play an important role in our model, in the sense if a customer zone $n$ is located far away from location $i$, the investing cost of facility $i$ would not make a significant impact on the choices of the customers of this zone, and on the other hand if location $i$ is close to the location of customer zone $n$, 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_i$ (more cost to spend on facility $i$) will make the facility more attractive to customers, thus $a_{ni}$ 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_i$ and $U_i$ are the lower and upper bounds for the cost on facility $i\in [m]$, ${\mathcal{S}}$ is the set of all subsets of [m]. It is required that $\sum_{i\in S}L_i \leq C$ for some $S\in{\mathcal{S}}$ to ensure feasibility. More general linear constraints on the costs $\textbf{x}$ can be included, but we only consider a budget constraint $\sum_{i\in S}x_i\leq C$ and the bound constraints for the sake of simplicity. We can represent set $S$ by binary variables vector with $y_i= 1$ if set S consists of location $i$ and $y_i = 0$ otherwise. Then, we formulate the MCP under ARUM as a binary-continuous nonlinear program
where $K$ is the maximum number of facilities to be opened, constraints (ref) is to ensure that if there is no facility at location $i$, the corresponding cost should be zero and (ref) is to force the cost $x_i$ to be at least $L_i$ if location $i$ is selected (i.e., $y_i = 1$).
If the choice model is a multiplicative MNL model, the choice probabilities become \[ P^{\textsc{MRUM}}(i|S,\textbf{V}^n) = \frac{{V_{ni}}}{1 + \sum_{i'\in S} {V_{ni'}}} = \frac{{a_{ni}x_i+b_{ni}}}{U^c_n + \sum_{i'\in S} {a_{ni'}x_{i'}+b_{ni'}}}, \] and the joint facility and cost optimization MCP can be formulated as
If the costs $\textbf{x}$ are fixed and only the facility location problem is considered, then (ref) and (ref) share the same structure, thus existing methods developed for the ARUM-based MCP problem FLO_Benati2002maximum,FLO_Haase2014comparison,mai2020multicut 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.
We numerically analyse the relation between the ARUM and MRUM frameworks in the context of the MCP. We employ MNL-based models (i.e., the random terms are i.i.d extreme value Type I) for our analyses, setting our focus on the impact of the structures of the deterministic terms under the MRUM and ARUM on the choice probabilities and on the objective function of the MCP. Since the ARUM framework is well understood and widely studied, we aim to explore the question of whether the MRUM models and the MCP under MRUM are able to well approximate their counterparts under the ARUM.
We first note that the choice probability of an alternative $j$ under ARUM is of the form $(\exp(a_jx_j+b_i))/(\exp(a_jx_j+b_j) + c)$, where $a_j,b_j$ are some choice parameters, $x_j$ is the investment cost of $j$, and $c$ represents the utilities of the other alternatives. On the other hand, under MRUM, the choice probability of an alternative $j$ under ARUM is of the form $((a'_jx_j+b'_i))/((a'_jx_j+b'_j) + c')$, where $a'_j,b'_j$ are choice parameters and $c'$ is the sum of the utilities of the other alternatives. We first explore the shapes of the choice probabilities, under the ARUM and MRUM, as functions of the cost. To this end, we select some sets of parameters $(a_j,b_j,c,a'_j,b'_j,c')$ and vary the cost $x_j$. The choice probabilities under the ARUM and MRUM are plotted in Figure (ref). It can be seen that the choice probability function under MRUM has a concave shape, while it is not the case under the ARUM. This can be validated by seeing that function $((a'_jx_j+b'_i))/((a'_jx_j+b'_j) + c')$ is concave in $x_j$. Moreover, under MRUM, the choice probability seems to increase faster when $x_j$ is small, but slower when $x_j$ becomes large, as compared to the choice probability function under ARUM.
In the second experiment, we aim to explore whether the MRUM can well approximate the choice probabilities given by the ARUM, and vice versa. To this end, we choose a ARUM model with choice probabilities of the form $(\exp(a_jx_j+b_i))/(\exp(a_jx_j+b_j) + c)$. We then vary $x_j$ to get pairs of costs and choice probabilities $\{(x_j^1,p_j^1), (x_j^2,p_j^2)\ldots\}$. Next, we fit these data points with a MRUM choice probability function of the form $((a'_jx_j+b'_i))/((a'_jx_j+b'_j) + c')$, using Least-Squares regression. We do the same to fit an ARUM choice probability function with data points generated by a MRUM model. In the left figure of Figure (ref) we generate data points using function $(\exp(0.1x_j-0.3))/(\exp(0.1x_j-0.3)+5)$ and get $((0.14x_j+0.82))/((0.14x_j+0.82) +6.02)$ after fitting, with a Root Mean Square Error (RMSE) of 0.0049 (about 2%). On the right hand side of Figure (ref) we generate the data points using $((x_j+3))/(((x_j+3))+30)$ and get $(\exp(0.14x_j+0.1))/(\exp(0.14x_j+0.1) +8.67)$ after fitting, yielding a RMSE of 0.0092 (about 4%). In general, our experiment shows that, even-though the choice probability functions under ARUM and MRUM have different shapes, they can well approximate each other.
We extend the second experiment to a three-dimensional (3D) space to see how the MCP objective functions can approximate each other in higher dimensions. To this end, we select MCP objective functions depending on two cost variable $x_i,x_j$ to generate data points. We plot the data points (blue dots) and the fitted functions (surfaces) in Figure (ref), where the left hand side figure show data points from the function $(\exp(0.1x_i-0.3)+(0.2x_j-0.3))/(\exp(0.1x_i-0.3)+(0.2x_j-0.3)+5)$ and a surface of the fitted function $((0.15x_i-0.24)+(0.25x_j-0.24))/((0.15x_i-0.24)+(0.25x_j-0.24)+6.25)$, with a RMSE of 0.0044. On the right hand side of Figure (ref) we plot data points from the function $((x_i+3)+(2x_j+1))/(((x_i+3)+(2x_j+1))+30)$ and a surface of the function $(\exp(0.16x_i-0.36)+\exp(0.13x_j+0.71))/(\exp(0.16x_i-0.36)+\exp(0.13x_j+0.71)+8.8)$, with a RMSE of 0.0054, which is just about 1% of the average of the MCP objective values. In general, the experiment shows that the MCP objective functions under the ARUM and MRUM can well approximate each other in a 3D space.
In the fourth experiment, we further explore whether the MRUM framework can approximate the ARUM in the context of the MCP. We randomly create a “ground-truth” ARUM model and use it to generate 1000 choice observations. We then specify a MRUM model of the same utility specification and estimate it's parameters using the generated choice observations by maximum likelihood estimation. To compare the ARUM model and the estimated MRUM one, we randomly and uniformly generate 1000 samples of the cost vector $\textbf{x}$ and compute the percentage gaps between the MCP objective functions under the two choice models. We vary the number of alternatives from 20 to 200 and plot the means (solid curve) and standard errors (shaded area) of the percentage gaps in Figure (ref). It can be seen that the percentage gap, on average, is only 4% when $m=20$ and just about $1\%$ for the other cases, showing that even when the “ground-truth” choice model is an ARUM, one still can well approximate it with small gaps by a MRUM model, noting that the MCP under MRUM is more tractable to solve (see Table (ref) above).
In this section, we develop solution methods to solve the joint location and cost MCP. As will be shown later, the MCP under ARUM is highly non-convex and intractable to handle, we will set our focus on the MCP under MRUM.
We first consider the cost optimization problem, assuming that the location variables $\textbf{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 zone, 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 off-the-shelf solvers such as CPLEX or GUROBI can efficiently handle.
We first consider the cost optimization problem under ARUM. The following remark states that $f^{\textsc{ARUM}}(\textbf{y},\textbf{x})$ is not unimodal in $\textbf{x}$. As a result, the MCP under ARUM, even when we only seek optimal costs, is generally not tractable to handle.
\proof We validate the remark with an example. Let us consider the following instance of $|I|=1$, \[ f^{\textsc{ARUM}}(\textbf{x}) = \frac{e^{x_1} + 1.2e^{x_2}}{1+ e^{x_1} + 1.2e^{x_2}} \] and a feasible set ${\mathcal{X}}$ defined as ${\mathcal{X}} = \{\textbf{x} \in [0,1]^2|\; x_1+x_2\leq 1\}$. 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 $$\max_{x_1 \in [0,1]} \left\{e^{x_1}+ 1.2e^{1- x_1}\right\}, $$ and it is easy to see that there are two 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. (ref) below. Thus, MCP has two local optimal solutions at $\textbf{x} = (1,0)$ and $\textbf{x} = (0,1)$.
\endproof
In fact, when $|I|=1$, we can write the objective value of the cost optimization problem under ARUM as \[ \max_{\textbf{x} \in {\mathcal{X}}}\{f^{\textsc{ARUM}}(\textbf{x})\} = q_n - \frac{1}{1+ \max_{\textbf{x}\in {\mathcal{X}}}\left\{ \sum_{i\in S} e^{a_{ni}x_{i}+b_{ni}} \right\}} \] where $n$ is the unique customer zone in $I$. The problem $ \max_{\textbf{x}\in {\mathcal{X}}}\left\{ \sum_{i\in S} e^{a_{ni}x_{i}+b_{ni}} \right\}$ is a maximization problem with a convex objective function, thus several local optimums may exist. In general, the non-unimodality of the cost optimization problem under MRUM implies that a nonlinear optimization algorithm would end up with a sub-optimal solution.
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/(\pmb{\alpha}^{\mbox{\tiny T}} \textbf{z})$ is convex in $\textbf{z}$ BenaHans02,mai2020multicut. As a result, $f^{\textsc{MRUM}}(\textbf{y}, \textbf{x})$ is concave. We state this important result in Remark (ref) 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 NoceWrig06.
{Conic reformulation}. Conic optimization refers to optimization of a linear function over conic quadratic inequalities of the form $||\textbf{A}\textbf{z} -\textbf{b}|| \leq \textbf{c} \textbf{x} + \textbf{d}$, where $||\cdot||$ is the L2 norm, and $\textbf{A}, \textbf{b},\textbf{c},\textbf{d}$ are matrices/vectors of appropriate sizes. 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 rotated second-order cone/hyperbolic inequality of the form $z_1^2\leq z_2z_3$, for $z_1,z_2,z_3\geq 0$, can be formulated as a conic quadratic inequality $||(2z_1,z_2-z_3)||\leq 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
Constraints (ref) are not rotated second-order cones, but we can safely replace them by rotated second-order cones $\theta_n w_n \geq 1$. We state this result in the following proposition.
\proof We observe that if we replace the equality constraints by inequalities $\theta_nw_n\geq 1$, then because $\theta_n$ and $w_n$ are non-negative and the objective function involves terms $q_n\theta_n$, the maximization problem always forces $\theta_n$ to be as small as possible. Thus, at optimum, the inequality constraints $\theta_nw_n\geq 1$ are always active, i.e., $\theta_nw_n= 1$. This leads to the desired result. \endproof
The conic program in (ref) has $m+2|I|$ continuous variables while the original concave optimization problem $\max_{\textbf{x}} \{ f^{\textsc{MRUM}}(\textbf{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 bonami2015recent.
The cost optimization MCP problem has the form of a sum-of-ratio program. In its most general form, the problem can be written as $\max_{\textbf{x}}\{\sum_{k\in [N]} ({(\pmb{\alpha}^k)^{\mbox{\tiny T}} \textbf{x}})/((\pmb{\beta}^k)^{\mbox{\tiny T}} \textbf{x}) \}$, where $N\in \mathbb{N}_+$, and $\pmb{\alpha}^k, \pmb{\beta}^k$, $k\in [N]$, are vectors of the same size with $\textbf{x}$. Such a sum-of-ratio problem is known to be highly non-convex and challenging to be solved globally schaible1995fractional. 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 (ref) 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 schaible1995fractional. If the choice model is the mixed MNL, the problem will have the form of the general sum-of-ratio program and would be highly non-convex and challenging to handle.
We consider the joint facility location and cost optimization problem under MRUM. We will present our three approaches, two exact and one heuristic methods, to handle the problem, namely, an equivalent mixed-integer conic program, a multicut outer-approximation algorithm and a local search procedure.
We will also make use of the following rotated second-order cone $x_1^2 \leq x_2x_3$, with $x_1,x_2,x_2 \geq 0$ to present conic quadratic inequality. To reformulate the nonlinear binary program (ref) as a CONIC program, we denote
and write (ref) as
We now let $z_{i} = y_i x_i \; \forall i \in [m]$. Since this term involves a binary variable, the equality can be linearized using McCormick inequalities mccormick1976computability as
Furthermore, since both $\theta_n$ and $w_n$ are non-negative, similarly to Proposition (ref), one can show that the equality $\theta_nw_n=1$ can be replaced by the inequality $\theta_nw_n\geq 1$, which is a rotated second-order cone. In summary, we can formulate (ref) as the following CONIC program
The mixed-integer conic program in (ref) has $2m+2|I|$ continuous and $m$ binary variables, and has $6m + 2|I| +2$ constraints, as compared to $m$ continuous and $m$ binary variables and 2 constraints of the original joint problem (ref).
We show that an outer-approximation algorithm can be used to solve the joint facility location and cost optimization problem. We also let $z_{i} = y_i x_i, i \in [m]$, and linearize these terms using McCormick inequalities mccormick1976computability to obtain the equivalent reformulation
We can further see that the objective function of (ref) is concave in ${\textbf{z},\textbf{y}}$. This remark is essential for the use of the outer-approximation method. We state it in the following remark.
To apply the multicut outer-approximation scheme OA_Duran1986outer,mai2020multicut, we divide the set of customer zones $I$ into ${\mathcal{L}}$ disjoint groups ${\mathcal{D}}_1,\ldots,{\mathcal{D}}_{{\mathcal{L}}}$ such that $\bigcup_{l\in {\mathcal{L}}}{\mathcal{D}}_l = I$. We then write the objective function of (ref) as \[ f(\textbf{x},\textbf{y},\textbf{z}) = \sum_{l\in[{\mathcal{L}}]} \phi_l(\textbf{y}, \textbf{z}) \] where \[ \phi_l(\textbf{y}, \textbf{z}) = \sum_{n\in {\mathcal{D}}_l}\left(q_n - \frac{{q_n U^c_n }}{U^c_n+ \sum_{i\in [m]} {a_{ni}z_i + y_ib_{ni}}}\right) \] A multicut outer-approximation algorithm will build a piecewise linear function that outer-approximates each concave function $\phi_l(\textbf{y},\textbf{z})$. Such a outer-approximation can be constructed by creating sub-gradient cuts of the form $\theta_l \leq \nabla_{\textbf{y}} \phi_l(\textbf{y},\textbf{z}) (\textbf{z}- \overline{\textbf{z}}) + \nabla_{\textbf{z}} \phi_l(\textbf{y},\textbf{z}) (\textbf{y}- \overline{\textbf{y}}) +\phi_l(\overline{\textbf{y}}, \overline{\textbf{z}})$, where $(\overline{\textbf{y}},\overline{\textbf{z}})$ is the current solution candidate, and $\nabla_{\textbf{y}} \phi_l(\textbf{y},\textbf{z})$ and $\nabla_{\textbf{z}} \phi_l(\textbf{y},\textbf{z})$ are the gradients of $\phi_l(\cdot)$ w.r.t. $\textbf{y}$, $\textbf{z}$, respectively. The outer-approximation algorithm executes an iterative procedure where at each step it adds sub-gradient cuts to the following master problem
where $(\overline{\textbf{z}}^t,\overline{\textbf{y}}^t)$ are the solution candidates found at the $t$-th iteration of the outer-approximation algorithm and the linear constraints in (ref) are the sub-gradient cuts added to the master problem over iterations $t=1,2,\ldots$. The algorithm keeps adding cuts and solving the master problem until its get a solution $(\textbf{x}^*,\textbf{y}^*,\textbf{z}^*,\pmb{\theta}^*)$ such that $\sum_{l\in [{\mathcal{L}}]}\theta^*_l\leq \sum_{l\in [{\mathcal{L}}]} \phi_l(\textbf{y}^*,\textbf{z}^*)+\tau$, where $\tau>0$ is a stopping threshold. The concavity of $\phi_l(\textbf{y},\textbf{z})$, $\forall l\in[{\mathcal{L}}]$ guarantees that the outer-approximation algorithm will eventually converge to an optimal solution OA_Duran1986outer,Bonami2011_BB_MIP. Here, we note that since the objective function is concave, one possible alternative is the outer-approximation-based Branch-and-Cut (B&C) method Ljubic2018outer,Lin2021branch,Lin2021generalized. We however stick to the multicut outer-approximation approach as it generally outperforms the B&C one mai2020multicut
Dam2021submodularity 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
where ${\mathcal{X}}(\textbf{y})$ is the feasible set of $\textbf{x}$ conditional on $\textbf{y}$, i.e., ${\mathcal{X}}(\textbf{y}) = \{\textbf{x}\in \mathbb{R}^{m}_+|\; \sum_{i\in [m]} x_i\leq C,\; x_i\leq y_iU_i,\; x_i\geq y_i L_i,\;\forall i\in [m] \}$. According to Section (ref), for a given $\textbf{y}$, the value of $\Phi(\textbf{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 $\Phi(\textbf{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.
\proof We provide a counter example to prove the claim. Let us consider a simple example with $I = \{1\}$ (there is only one customer zone), $m=2$, $q_n=1$ for all $n\in I$, $b_{11} = b_{12} = 0$, $a_{11} = 5$, $a_{12}=1$, $U_1 = U_2=3$, $L_1 = L_2=3$, $C = 4$. Let $\textbf{y}^1 = (1,0)$ and $\textbf{y}^2 = (1,1)$. We see that
Thus, $\Phi(\textbf{y}^1) > \Phi(\textbf{y}^2)$, implying that $\Phi(\textbf{y})$ is not monotonic increasing in $\textbf{y}$, as desired. \endproof
Intuitively, when a new facility at location $i$ is built and operated, it would require a minimum cost $L_i>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\geq \sum_{i\in[m]} U_i$, then we can see that $\Phi(\textbf{y})$ is monotonic increasing in $\textbf{y}$.
Proposition (ref) implies that an optimal solution to (ref) would not necessarily reach the maximum capacity $K$. Moreover, in prior MCP work, Dam2021submodularity show that a simple greedy local search based on adding locations to an empty set of locations can guarantee $(1-1/e)$ approximation solutions. This would be not the case for (ref) due to the non-monotonicity Nemhauser1978analysis.
Dam2021submodularity propose a three-step local search procedure that performs very well for the ARUM-based facility location MCP. The second step of this algorithm requires gradient information to direct the local search. To adapt this in the context of the joint facility location and cost optimization problem, we need to compute the gradients of $\Phi(\textbf{y})$ w.r.t. any $\textbf{y}$. To this end, let us consider a Lagrange dual of the maximization problem in (ref).
For a given $\textbf{y}\in{\mathcal{Y}}$ with ${\mathcal{Y}}$ is the feasible set of $\textbf{y}$, i.e., ${\mathcal{Y}} = \{ \textbf{y} \in \{ 0,1 \}^m|\sum_{i \in [m]} y_i \leq K \}$, let $\textbf{x}^*(\textbf{y}), \lambda^*(\textbf{y}), \gamma^{U*}_i(\textbf{y})$ and $\gamma^{L*}_i(\textbf{y})$, $\forall i\in [m]$ be the saddle point of $L(\textbf{x},\lambda,\pmb{\gamma}^U,\pmb{\gamma}^L |\textbf{y})$. The following proposition gives a formula for the first-order derivatives of $\Phi(\textbf{y})$ w.r.t. $\textbf{y}$.
Proposition (ref) tells us that we need to compute the Lagrange multipliers $\lambda^*, \pmb{\gamma}^{U*}$ and $\pmb{\gamma}^{L*}$ to compute the derivatives of $\Phi(\textbf{y})$ w.r.t. $\textbf{y}$. This can be done by solving the Lagrange duality $\min_{\lambda,\pmb{\gamma}^{U},\pmb{\gamma}^{L}} \max_{\textbf{x}} L(\textbf{x},\lambda,\pmb{\gamma}^U,\pmb{\gamma}^L |\textbf{y})$, which would be expensive. Alternatively, we can directly solve the convex problem $\max_{\textbf{x}\in {\mathcal{X}}(\textbf{y})} f^{\textsc{MRUM}}(\textbf{y},\textbf{x})$ by an existing optimization solver and infer the Lagrange multipliers from the optimal solution obtained. That is, let $\textbf{x}^*$ be the unique optimal solution to $\max_{\textbf{x}\in {\mathcal{X}}(\textbf{y})} f^{\textsc{MRUM}}(\textbf{y},\textbf{x})$. From (ref) we have \[ \frac{\partial f^{\textsc{MRUM}}(\textbf{y},\textbf{x}^*)}{\partial x_i} -\lambda^* - \gamma^{U*}_i + \gamma^{L*}_i = 0,\;\forall i\in[m]. \] To infer $\lambda^*,\pmb{\gamma}^{U*}$ and $\pmb{\gamma}^{L*}$, we consider the following cases:
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 $\Phi(\textbf{y})$ the most. The first step stops when the solution candidate reaches the capacity $K$ or it cannot find a better solution. The second step is a gradient-based local search. The gradient information given in Proposition (ref) is made use to approximate the nonlinear objective function $f^{\textsc{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 Dam2021submodularity for more details.
The above local search procedure runs fast and returns good solutions for previous competitive facility location problems Dam2021submodularity,thuy2021robust, 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 $\Phi(\textbf{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.
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.
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 \in \{0.2m, 0.5m, 0.7m\}$ and the maximum number of facilities that can be opened as $M \in \{ 0.2m, 0.5m, 0.7m \}$, recalling that $m$ is the total number of possible locations. As describe above, given $n\in I$ and $i\in [m]$, the parameter $a_{ni}$ represents the sensitivity of customer zone $n$ w.r.t the cost spent on facility $i$, and the parameter $b_{ni}$ represents other factors that affect customers' choice decisions, e.g. distances to the locations. We randomly and uniformly generate $a_{ni}$ from [0.5,1.5]. For $b_{ni}$, we also randomly generate values from [1,10]. The parameter $q_n$ representing the number of customers in customer zone $n$ is also generated randomly and uniformly from two intervals $[1,10]$ and $[90,100]$. The two parameters $L_i$ and $U_i$, $\forall i\in [m]$, (i.e., the lower and upper bounds for the cost to spend on facility $i\in [m]$) are also generated uniformly from two closed intervals satisfying that $\sum_{i\in[m]}L_i \leq C$ for some sets of $i\in[m]$. We note that the dataset for the cost optimization MCP problem needs to satisfy $\sum_{i\in[m]}L_i \leq 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.
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 (ref), i.e., using a general convex optimization solver, and solving the equivalent CONIC program by CPLEX. We denote the two approaches as CONIC and CONVEX (i.e., solving the convex optimization problem by fmincon). Table (ref) 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 CONIC and CONVEX are exact methods, thus if an instance is completed by any of the two approaches within the time budget, we know that the instance is solved to optimality.
Table (ref) shows that the CONIC approach outperforms the general convex solver in terms of both number of instances with the best objective values and average CPU time. The CONIC approach gives the best objective values for all the instances in all the 30 groups of instances while the CONVEX just gives the largest numbers of best objective values in 24/30 groups of instances. On the other hand, the average CPU times required by CONIC are significantly less than the time taken by CONVEX. {For some medium and large instances (i.e., when $m>400$), 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.
We now report numerical results for the joint location and cost optimization problem. We perform a comparison between the three approaches proposed above, namely, the CONIC reformulation solved by the CPLEX's conic solver bonami2015recent, 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 \in \{ 1, 5\}$. A more detailed analysis on the performance of MOA when $T$ varies will be provided later. For the LS approach, the computation of each $\Phi(\textbf{y})$ requires to solve a cost optimization problem over $\textbf{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 (ref) for instance).
We first report the comparison results for our small-sized and medium-sized instances in Table (ref), where each row of the table reports the averages for 8 instances grouped by $|I|,m, C,$ and $K$. More results with large-sized instances can be found in the appendix. 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 (ref) 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 $K = m/5$. {In particular, for larger problem instances (e.g., $|I| = 800$), on average, the CONIC approach only solves less than 3/8 instances to optimality within 600 seconds.} In overall, the CONIC approach can only solve about 79.6% instances to optimality while the MOA algorithms give optimal solutions for 100% instances. However, when comparing the number of instances with the best objective values, we observe that, on average, both CONIC and MOA are able to return the best values for all the instances. This is because CONIC exceeds the time budget and cannot confirm that the solutions found are optimal. The LS algorithm is much worse, as compared to the other exact approaches, as it only gives the best solutions to only 5.6% of the instances.
We now turn our attention to the average CPU times. In Table (ref) 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 Dam2021submodularity 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) \in$ \{(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 35/45 times dominating the other approaches, followed M5 (13/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.
Since MOA algorithms perform the best for the joint location and cost optimization instances, and their performance would depend on the number of cuts added to the master problem at each iteration (i.e., $T$), we provide additional results to analyse how $T$ affects the running time of the MOA. To this end, we let $T$ vary in $ \{1,5,10,20, 25,50\}$ and plot the corresponding average running times in Figure (ref) for four groups of instance of sizes $(|I|,m) \in$ \{(100,100), (800,400), (800,800), (1000,1000)\}, where each line represents the average CPU time of 432 instances of the same $(|I|,m)$. We also plot in Figure (ref) the average CPU times for each group $(|I|,m)$ with different values of $K$, i.e., $K \in \{0.2m, 0.5m,0.7m\}$. Each line on each sub-figure corresponds to 144 instances. We see from the Figure (ref) that the MOA algorithm with $T=25$ seems to have the lowest average running times. Moreover, Figure (ref) shows that the MOA algorithms with small $T$ (i.e, $T=1$ or $T = 5$) seem to achieve good performance for $K \in \{ 0.5m,0.7m\}$. However, the algorithm becomes slower for instances of $K=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\ge 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 mai2020multicut. 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 (ref) 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 results are reported in the appendix), 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.
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 the two frameworks can well approximate each other on the context of MCP cost optimization. In the optimization perspective, 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 is 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 wang2012capacitated or security game problems yang2012computing.