text:
\section{Introduction  and Preliminaries}
We study the following non-convex optimization problem with binary and continuous variables
\begin{equation}
\label{prob:SoR-original}\tag{\sf SoR}
     \max_{\textbf{y}\in {\mathcal{Y}},\textbf{x}\in {\mathcal{X}} }\left\{f(\textbf{y},\textbf{x}) = \sum_{t\in [T]}  \frac{a_t + \sum_{i\in [m]} y_i g^t_i(x_i) }{b_t + \sum_{i\in [m]} y_i h^t_i(x_i)}\Big|~~  \textbf{A} \textbf{x} +\textbf{B}\textbf{y} \leq \textbf{D}\right\}
\end{equation}
where $\textbf{y}$ are binary and $\textbf{x}$ are continuous variables, ${\mathcal{Y}} \subset \{0,1\}^m$  is the feasible set of $\textbf{y}$ and ${\mathcal{X}} \subset \bigotimes_{i\in [m]} [l_i,u_i]$ is the feasible set of $\textbf{x}$, $g^t_i(x),h^t_i(x)$ are univariate functions, i.e., $g^t_i(x),h^t_i(x) : \mathbb{R}\rightarrow \mathbb{R}$, $\forall t\in [T],i\in [m]$, noting that  $g^t_i(x),h^t_i(x)$, $t\in [T], i\in [m]$, are univariate functions and are not necessarily  convex (or concave), and $\textbf{A} \textbf{x} +\textbf{B}\textbf{y} \leq \textbf{D}$ are some linear constraints  on $\textbf{x},\textbf{y}$. Such a sum-of-ratios problem arises from the use of discrete choice models \citep{McFa81,Trai03} to predict customer/adversary's behavior in decision-making and is known to be highly non-convex and challenging to solve, even when the binary variables $\textbf{y}$ are fixed \citep{li2019product,duong2022joint}.  As far as we know, this is a first attempt to solve the aforementioned non-convex problems to near global optimality. The problem formulation above has several applications in revenue  management, facility location and security games, as described below.

\noindent \textbf{Product assortment and pricing optimization.} This problem refers to the problem of selecting a set of products and  making pricing decisions  to maximize an expected revenue, assuming that customers make  choice decisions according to a discrete choice model. Product assortment and pricing has been one of the most essential problems in revenue management and has received remarkable attention over the recent decades \citep{talluri2004revenue,vulcano2010om,rusmevichientong2014assortment,wang2018impact}.
The joint assortment and price optimization problem under a (general) mixed-logit model (i.e., one of the most popular and general choice models in the literature) can be formulated in the form of \eqref{prob:SoR-original}. When the variables $\textbf{x}$ are fixed  and the objective function contains  only one ratio, the optimization problem can be solved in polynomial time under some simple settings, e.g. the problem is unconstrained or with a cardinality constraint \citep{rusmevichientong2010dynamic,talluri2004revenue}.
When the objective function is a sum of ratios and the variable $\textbf{x}$ are fixed, the problem is generally NP-Complete even when there are only two fractions \citep{rusmevichientong2014assortment}. Approximate solutions, mixed-integer linear programming (MILP) and mixed-integer second order cone programming (MISOCP) reformulations have been developed for this setting \citep{bront2009column,mendez2014branch,sen2018conic}. When only the pricing is considered (i.e., the variables $\textbf{y}$ are fixed)  and the objective function contains multiple ratios, the problem is highly non-convex and may have several local optima, with respect to both the prices and market shares \citep{li2019product}. Joint assortment and price optimization has been also studied in the literature \citep{wang2012capacitated}, but just under some simple settings (e.g., unconstrained on the prices and a cardinality constraint on the assortment, and the objective functions involves only one ratio). In general, as far as we know, in the context of assortment and price optimization, there is no global solution method to handle the joint problem with multiple ratios and general constraints. Our work is the first attempt to fill this literature gap.

\noindent \textbf{Competitive facility location and cost planning}. The formulation \eqref{prob:SoR-original} can be found along an active line of research on competitive maximum covering (or maximum capture) facility location problem with customers' random utilities \citep{benati2002maximum,FLO_Hasse2009MIP,mai2020multicut,lin2021branch,dam2022submodularity}. The problem refer to maximizing an expected customer demand, in a competitive market,  by locating new facilities and making decisions of the budget to spend on each opening facility,  assuming that customers make choice decisions according to a discrete choice model. When the costs are fixed, which is the focus of most of the works in the relevant literature,  researchers have shown that the facility location problem can be formulated as a MILP \citep{benati2002maximum,freire2016branch, haase2014comparison}, or can be solved efficiently by outer-approximation algorithms \citep{mai2020multicut,Ljubic2018outer}. When the cost  optimization is considered, the problem becomes highly non-convex and may have several local optima \citep{duong2022joint}. As far as we know, \cite{duong2022joint} is the only work to consider both facility location and cost optimization. In this work, the authors state that the use of the standard mixed-logit model leads to a very intractable optimization problem to be handled exactly, and they instead propose to use a less-popular discrete choice framework. So, the joint location and cost optimization  under the standard logit and mixed-logit model is still an open problem in the respective literature and we deal with it in this work.

\noindent \textbf{Stackelberg game under quantal response adversary.}
Stackelberg sercurity games (SSG) \citep{tambe2011security} are a prominent class of security models that have been widely studied in the  Artificial Intelligent and Operations Research community.
Such model have many real world applications, for example,  airport sercurity \citep{pita2008armor}, wide-life protection \citep{fang2017paws}, and coast guard \citep{an2012protect}. In a SSG model, the objective is to allocate some security resources to some defending targets, aiming at maximizing an expected defending utility function.
Quantal response  (or multinomial logit) model has  been popularly used to predict adversary's behavior \citep{yang2011improving,yang2012computing}.
Solution methods developed for SSG problems under quantal response include convex optimization or piece-wise linear approximation \citep{yang2012computing}.
To the best of our knowledge, existing works only focus on single-ratio objective functions and continuous decision variables, offering room for  exploring and  improvement, e.g., using mixed-logit models to predict  adversary's behavior, or include binary decisions for the selection of facilities to operate.  Our work provides a global and general solution method to deal with such general settings.

\noindent \textbf{Our contributions. } We make the following contributions:
\begin{itemize}
    \item[(i)] Being the first to consider the non-convex problem in \eqref{prob:SoR-original}, we develop a discretization mechanism to approximate the nonlinear  numerators and denominators of the objective functions by linear functions. We further show that the approximate problem can be reformulated  as a MILP. Moreover, we show that, under some mild conditions that hold in the aforementioned applications, the approximate problem can be reformulated as mixed-integer second-order cone program (MISOCP). The MILP or MISOCP programs then can be handled conveniently by commercial software (e.g.,  CPLEX or GUROBI).

    \item[(ii)] Noting that a solution to the approximated problem might not be feasible to the original problem, we establish (mild) conditions under which solutions to the approximate problem will converge to ``true'' optimal solutions as the number of discretization points increases. We also establish bounds of ${\mathcal{O}}(1/K)$ for the approximation errors yielded by the approximate solutions, where $K$ is the number of discretization points. We also provide estimates for $K$ to guarantee a desired approximation bound.  Note that most of previous works rely on the assumption that the costumers' or adversaries' utility functions have  linear structures  (e.g., linear in the prices, costs or sercurity resources), our approach can handle any non-linear structures (e.g., the utility function is modelled by a deep neural network) while securing the same performance guarantees.

    \item[(iii)] We finally conduct numerical experiments based on instances of various sizes  showing the efficiency of our discretization approach and the MILP and MISOCP reformulations in offering near optimal solutions to the non-convex problem.
\end{itemize}
In short, we develop a solution method that uses commercial software to  provide near optimal solutions to the class on non-convex problems in \eqref{prob:SoR-original}. The advantage of this approach is clear; commercial software
allows the inclusion of complex business constraints without the need for redesigning algorithms, and
is continually improved with new  optimization methods and advanced hardware. We seem to be the first to provide global methods for several important constrained problems in product assortment and pricing, facility location and sercurity games.

\noindent\textbf{Paper Outline.}
Section \ref{sec:discr-approach} presents our discretization approach and the MILP and MISOCP reformulations. Section \ref{sec:performance-bounds} provides performance guarantees for our approximation approach. Section \ref{sec:experiments} presents numerical experiments and finally, Section \ref{sec:concl} concludes. All the proofs are in the appendix.

\section{Towards a Globally Optimal Solution: a Discretization Approach}\label{sec:discr-approach}

In this section we present our discretization approach to approximate the non-convex problem \eqref{prob:SoR-original} via MILP and MISOCP programs. To begin, let us introduce the following mild assumptions which generally holds in all the aforementioned applications.
\begin{assumption}[\textbf{A1}]\label{assm:as1}
The following assumptions hold:
\begin{itemize}
    \item [(i)] $b_t + \sum_{i\in [m]} y_i h^t_i(x_i)>0$ for all $\textbf{y}\in {\mathcal{Y}}$, $\textbf{x}\in {\mathcal{X}}$

    \item [(ii)] $h^t_i(x_i)$  and $g^t_i(x_i)$ are Lipschitz continuous, i.e., there exist  $L^{gt}_i, L^{ht}_i>0$ such that
    \begin{align}
        |h^t_i(x_1) - h^t_i(x_2)| \leq L^{ht}_i |x_1-x_2|,&\;\forall x_1,x_2 \in [l_i,u_i] \nonumber \\
        |g^t_i(x_1) - g^t_i(x_2)| \leq L^{gt}_i |x_1-x_2|,&\;\forall x_1,x_2 \in [l_i,u_i] \nonumber
    \end{align}
\end{itemize}
\end{assumption}

\subsection{Discretizing Univariate Functions}
We first introduce an approach to approximate an univariate function by a linear function of binary variables. Let $g(x):\mathbb{R}\rightarrow \mathbb{R}$ be an univariate function. Assuming that $g(x)$ is  Lipschitz continuous in $[l,u]$ with Lipschitz constant $L>0$, i.e., $|g(x_1)-g(x_2)|\leq L|x_1-x_2|$ for all $x_1,x_2 \in [l,u]$. For any $K\in \mathbb{N}$, we  discretize the interval $[l,u]$ into $K$ equal intervals of length $\Delta = (u-l)/K$ and approximate $x$ as \[x \approx \widehat{x} =  l+ \Delta\floor{(x-l)/\Delta}.\]
To use this to approximate the original problem as a mixed-integer nonlinear program, we introduce  binary variables $z_k\in \{0,1\}$, $k\in [K]$ and approximate $x$ as
\[
x \approx \widehat{x} =  l+ \Delta\sum_{k\in [K]}z_k
\]
where $z_k\geq z_{k+1}$ and for $k^* = \floor{(x-l)/\Delta}$ we have $z_{k^*} = 1$ and $z_{k^*+1} = 0$.
We then can approximate $g(x)$ by the following  discrete linear function.
\begin{align}
   g(x) \approx g(\widehat{x}) =  g(l) + \Delta\sum_{k\in [K]} \gamma^{g}_{k}{z_{k}},
\end{align}
where $\gamma^{g}_{k}$ is the slope of function $g(x)$ in the interval $[l+ (k-1)\Delta; l+ k\Delta]$, i.e.,
\[
\gamma^{g}_{k} = \frac{1}{\Delta}(g(l+ k\Delta) - g(l+ \Delta(k-1))), \;\forall k\in [k].
\]
From  the Lipschitzness of $g(x)$, we have the following bound for the gap between $g(x)$ and $g(\widehat{x})$. We will use this for establishing performance guarantees for the approximate problem.
\begin{lemma}
For any $x\in [l,u]$ and $\widehat{x}$ from the discretization mechanism above, we have
$$|g(x) - g(\widehat{x})| \leq L\Delta$$
\end{lemma}
Thus, it can be seen that $\widehat{x}$ and $g(\widehat{x})$ will approach $x$ and $g(x)$ linearly as $K$ increases.

\subsection{Discretizing  the Sum-of-ratios Problem}
We now show how to use the discretization technique above to approximate the binary-continuous sum-of-ratios program  in \eqref{prob:SoR-original}. For ease of notation, let us first denote $\Delta_i = {(u_i-l_i)/}{K}$.
Given any $\textbf{x}\in {\mathcal{X}}$, we approximate $x_i$, $i\in[m]$, by $l+ \Delta_i\floor{K(x_i-l)/(u_i-l_i)}$ and approximate the functions $g^t_i(x_i)$ and $h^t_i(x_i)$  by binary variables $z_{ik}\in \{0,1 \}$, $\forall i\in [m], k\in [K]$ as
\begin{align}
    g^{t}_i(x_i) \approx   \widehat{g}^{t}_i(x_i)  = g^{t}_j(l_i) + \Delta_i\sum_{k\in [K]}  \gamma^{gt}_{jk}{z_{jk}} \nonumber\\
        h^{t}_i(x_i) \approx \widehat{h}^{t}_i(x_i)  = h^{t}_i(l_i) + \Delta_i\sum_{k\in [K]}  \gamma^{ht}_{ik}{z_{ik}} \nonumber
\end{align}
where $\gamma^{gt}_{jk}$ and $\gamma^{ht}_{jk}$ are the slopes of $g^t(x_i)$ and $h^t(x_i)$ in $[l_i+ (k-1)\Delta_i;l_i+k\Delta_i]$, $\forall k\in[K]$, i.e.,
\begin{align}
    \gamma^{gt}_{ik} = \frac{1}{\Delta_i}\left(g^{t}_i(l_i+k\Delta_i) -g^{t}_i(l_i+(k-1)\Delta_i) \right),\; \forall k\in [K] \nonumber \\
    \gamma^{ht}_{ik} =\frac{1}{\Delta_i}\left(h^{t}_i(l_i+k\Delta_i) -h^{t}_i(l_i+(k-1)\Delta_i) \right),\; \forall k\in [K]  \nonumber
\end{align}
We now approximate \eqref{prob:SoR-original} by the following mixed-integer nonlinear program
\begin{align}
     \max_{\textbf{x},\textbf{y},\textbf{z} } &\quad \widehat{f}(\textbf{y},\textbf{x}, \textbf{z}) = \sum_{t\in [T]}\frac{a_t+ \sum_{i\in [m]}y_i g^t_i(l_i) +  \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} \gamma^{gt}_{ik} y_iz_{ik} }{ b_t+ \sum_{i\in [m]}y_i h^t_i(l_i) +  \sum_{i\in [m]}{\Delta_i}\sum_{k\in [K]} \gamma^{ht}_{ik} y_iz_{ik} } \label{prob:Approx}  \tag{\sf Approx}    \\
    \mbox{subject to} &\quad  z_{ik}\geq z_{i,k+1},\;\forall k\in [K-1], i\in [m] \nonumber \\
&\quad  {x}_i = l_i+\Delta_i \sum_{k\in [K]} z_{ik},\;\forall i\in [m]    \nonumber \\
&\quad  \textbf{A}{\textbf{x}} +\textbf{B} \textbf{y} \leq \textbf{D}    \nonumber \\
     &\quad \textbf{x}\in {\mathcal{X}},\;\textbf{z} \in \{0,1\}^{m\times K},\; \textbf{y}\in {\mathcal{Y}}.   \nonumber
\end{align}
The objective function of \eqref{prob:Approx-1} involves bi-linear terms $y_iz_{ik}$ which can be linearized by  introducing some additional binary variables $s_{ik} = y_iz_{ik}$  and linear constraints $s_{ik}\leq z_{ik},\; s_{ik}\leq y_{i},\; s_{ik}\geq z_{ik}+y_i-1,\;\forall i\in [m], k\in [K]$. As a result,
\eqref{prob:Approx-1} is equivalent to the following mixed-integer nonlinear program.
\begin{align}
     \max_{\textbf{z},\textbf{s},\textbf{y} } &\quad  \sum_{t\in [T]}\frac{a_t+ \sum_{i\in [m]}y_i g^t_i(l_i) + \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} \gamma^{gt}_{ik} s_{ik} }{ b_t+ \sum_{i\in [m]}y_i h^t_i(l_i) + \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} \gamma^{ht}_{ik} s_{ik} } \label{prob:Approx-1}  \tag{\sf Approx-1}    \\
    \mbox{subject to} &\quad  z_k\geq z_{k+1},\;\forall k\in [K-1] \nonumber \\
    &\quad  s_{ik}\leq z_{ik},\; s_{ik}\leq y_{i},\; s_{ik}\geq z_{ik}+y_i-1,\;\forall i\in [m], k\in [K] \label{ctr:1} \\
&\quad  {x}_i = l_i+\Delta_i \sum_{k\in [K]} z_{ik},\;\forall i\in [m]    \nonumber \\
&\quad  \textbf{A}{\textbf{x}} +\textbf{B} \textbf{y} \leq \textbf{D}    \nonumber \\
     &\quad \textbf{z},\textbf{s} \in \{0,1\}^{m\times K},\; \textbf{x}\in {\mathcal{X}},~\textbf{y}\in {\mathcal{Y}}.   \nonumber
\end{align}
 In the Proposition \ref{prop:approx-simplified} below, we show that under a condition that often holds in the applications mentioned above, the bi-linear terms $y_iz_{ik}$ in \eqref{prob:Approx} can be simplified without introducing new binary variables.  To facilitate this point, we first let ${\mathcal{S}}$  be the feasible set of the original problem \eqref{prob:SoR-original} i.e., $
{\mathcal{S}} = \{(\textbf{y},\textbf{x})|\; (\textbf{y},\textbf{x}) \in {\mathcal{Y}}\times {\mathcal{X}};\; \textbf{A}\textbf{x}+\textbf{B}\textbf{y}\leq D \}$,
and ${\mathcal{S}}(\textbf{y})$  be the feasible set of the original problem \eqref{prob:SoR-original} with fixed $\textbf{y}\in {\mathcal{Y}}$, i.e., ${\mathcal{S}}(\textbf{y}) = \{\textbf{x}|\; \textbf{x} \in  {\mathcal{X}};\; \textbf{A}\textbf{x}+\textbf{B}\textbf{y}\leq D \}$. We first introduce the following assumption that is needed for the result.
\begin{assumption}[A2]\label{assum:a2}

For any $(\textbf{x},\textbf{y})\in {\mathcal{S}}$ we have $(\textbf{x}',\textbf{y})\in {\mathcal{S}}$ for all $(\textbf{x}',\textbf{y})\in {\mathcal{X}}\times {\mathcal{Y}}$ and $\textbf{x}'\leq \textbf{x}$.
\end{assumption}
The above assumption is not restrictive in  our applications of interests. For example, in the context of joint assortment and price optimization, one may only require that the prices can vary between some lower and upper bounds, or a weighted sum (with non-negative weight parameters) of the prices is less than  a threshold. In the context of facility location and SSG, one may impose an upper bound for the total cost/security resources,  i.e., $\sum_{i\in [m]} x_i \leq C$. With such typical constraints, Assumption (\textbf{A1}) indeed holds.

Under Assumption (\textbf{A1}), we show in Proposition \ref{prop:approx-simplified} that \eqref{prob:Approx} can be simplified by replacing $y_iz_{ik}$ with only $z_{ik}$, and adding  constraints  $y_i\geq  z_{i1}$, which implies that if  $y_i = 0$ then $z_{ik} = 0$ for all $i\in [m], k\in [K]$.
\begin{proposition}\label{prop:approx-simplified}
Suppose (\textbf{A1}) and (\textbf{A2}) hold, we have that \eqref{prob:Approx} is equivalent to the following integer program.
\begin{align}
     \max_{\textbf{z},\textbf{x},\textbf{y} } &\quad \widetilde{f}(\textbf{y},\textbf{x},  \textbf{z}) = \sum_{t\in [T]}\frac{a_t+ \sum_{i\in [m]}y_i g^t_i(l_i) + \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} \gamma^{gt}_{ik} z_{ik} }{ b_t+ \sum_{i\in [m]}y_i h^t_i(l_i) + \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} \gamma^{ht}_{ik} z_{ik} } \label{prob:Approx-2}  \tag{\sf Approx-2}    \\
    \mbox{subject to} &\quad  z_{ik}\geq z_{i,k+1},\;\forall k\in [K-1] \nonumber \\
    &\quad  y_i\geq z_{i1},\;\forall i\in [m]\label{ctr:2} \\
&\quad  {x}_i = l_i+\Delta_i \sum_{k\in [K]} z_{ik},\;\forall i\in [m]    \nonumber \\
&\quad  \textbf{A} {\textbf{x}} +\textbf{B} \textbf{y} \leq \textbf{D}    \nonumber \\
     &\quad \textbf{z} \in \{0,1\}^{m\times K},\; \textbf{y}\in {\mathcal{Y}}, \textbf{x} \in {\mathcal{X}}.   \nonumber
\end{align}
\end{proposition}

In the following we further characterize  the approximate problem. To this end, let (\textbf{$P^K$}) be the approximate problem with $K$ discrete points on each coordinate $x_i$, and let $(\textbf{y}^K,\textbf{x}^K)$ be an optimal solution to (\textbf{$P^K$}).
\begin{proposition}[Characterizing the approximate problem]\label{prop:Characterizing}
We have the following properties
\begin{itemize}
    \item[(i)] (\textbf{$P^K$}) may not have feasible solutions for some $K$, even-when the original problem always has a feasible solution.
    \item[(ii)] Assume that (\textbf{$P^K$}) always has solutions for any $K$, we have
    \[
        f(\textbf{y}^K,\textbf{x}^K) \leq f(\textbf{y}^{Kh},\textbf{x}^{Kh})
    \]
    for any $h\in \mathbb{N}, h\geq 1$. This implies that using a multiple of $K$ always yields better solutions.
    \item[(iii)] If (\textbf{A2}) holds, then (\textbf{$P^K$}) always has a feasible solution for any $K$ and $\lim_{K\rightarrow \infty }f(\textbf{y}^K,\textbf{x}^K) \rightarrow f^*$, when $f^*$ is the optimal value of the original problem.
    \item[(iv)] ${\mathcal{S}}(\textbf{y})$ satisfies the Slater's conditions for any $\textbf{y}\in {\mathcal{Y}}$, there is $K_0\in \mathbb{N}$ such that  (\textbf{$P^K$}) always has a solution for any $K\geq K_0$, and $$\lim_{K\rightarrow \infty }f(\textbf{y}^K,\textbf{x}^K) \rightarrow f^*.$
\end{itemize}
\end{proposition}

\subsection{MILP Reformulation}
We present a MILP reformulation for the approximation problem \eqref{prob:Approx}. We will focus on \eqref{prob:Approx-2}, noting that \eqref{prob:Approx-1} can be done in a similar way. First, let
\begin{align}
    w_t = \frac{1}{b_t+ \sum_{i\in [m]}y_i h^t_i(l_i) + \sum_{i\in [m]}{\Delta_i}\sum_{k\in [K]} \gamma^{ht}_{ik} z_{ik}}\nonumber
\end{align}
we can write \eqref{prob:Approx-2} as
\begin{align}
     \max_{\textbf{z},\textbf{w},{\textbf{x}},\textbf{y}} \quad & \sum_{t\in [T]} a_t w_t + \sum_{i\in [m]}y_iw_t g^t_i(l_i) + \sum_{i\in [m]}{\Delta_i}\sum_{k\in [K]} \gamma^{gt}_{ik} w_t z_{ik} \nonumber\\
    \mbox{subject to} \quad&
    b_tw_t+ \sum_{i\in [m]}y_iw_t h^t_i(l_i) +  \sum_{i\in [m]}{\Delta_i}\sum_{k\in [K]} \gamma^{ht}_{ik} w_t z_{ik}  = 1\nonumber\\
   &  z_{ik}\geq z_{i,k+1},\;\forall i\in [m], k\in [K-1] \nonumber \\
    &  y_i\geq z_{i1},\;\forall i\in [m]\nonumber \\
&  {x}_i = l_i+\Delta_i \sum_{k\in [K]} z_{ik},\;\forall i\in [m]    \nonumber \\
&  \textbf{A}{\textbf{x}} +\textbf{B} \textbf{y} \leq \textbf{D}    \nonumber \\
     & \textbf{z} \in \{0,1\}^{m\times K},\; \textbf{y}\in {\mathcal{Y}},\textbf{w} \in \mathbb{R}^T,{\textbf{x}}\in {\mathcal{X}}.   \nonumber
\end{align}
The above formulation involves some bi-linear terms: $w_tz_{ik}$  and $w_ty_i$, $\forall t\in [T], i\in [m], k\in [K]$,  that can be linearized using the Big-M technique or McCormick inequalities \citep{mccormick1976computability}. We will employ the McCormick inequalities since they give tighter constraints for the relaxation.  To this end, let $U^w_t$ and  $L^w_t$ are an upper bound and lower bound of $w_t$.
By introducing new variables  $u_{tik}$ and $v_{ti}$ to represent $w_tz_{ik}$ and $w_ty_i$, we  can linearize the bi-linear terms as
\begin{align}
    &u_{tik} \leq U^w_t z_{ik};\;u_{tik} \geq L^w_t z_{ik} \label{ct:MC-1} \\
    &u_{tik} \leq w_t - L^w_t (1-z_{ik});\;u_{tik} \geq w_t - U^w_t (1-z_{ik})\label{ct:MC-2}\\
    &v_{ti} \leq U^w_t y_{i};\;u_{tik} \geq L^w_t y_{i} \label{ct:MC-3} \\
    &v_{ti} \leq w_t - L^w_t (1-y_{i});\;v_{ti} \geq w_t - U^w_t (1-y_{i})\label{ct:MC-4}
\end{align}
We then can reformulate \eqref{prob:Approx-2} as  the following MILP:
\begin{align}
     \max_{\textbf{x},\textbf{y},\textbf{z},\textbf{w},\textbf{u},\textbf{v}} \quad & \sum_{t\in [T]} a_t w_t + \sum_{i\in [m]}v_{ti} g^t_i(l_i) + \sum_{i\in [m]}{\Delta_i}\sum_{k\in [K]} \gamma^{gt}_{ik} u_{tik} \nonumber\\
    \mbox{subject to} \quad&
    b_tw_t+ \sum_{i\in [m]}v_{ti} h^t_i(l_i) + \sum_{i\in [m]}{\Delta_i}\sum_{k\in [K]} \gamma^{ht}_{ik} u_{tik}  = 1\nonumber\\
   &  z_{ik}\geq z_{i,k+1},\;\forall i\in [m], k\in [K-1] \nonumber \\
    &  y_i\geq z_{i1},\;\forall i\in [m]\label{ctr:2} \\
&  {x}_i = l_i+\Delta_i \sum_{k\in [K]} z_{ik},\;\forall i\in [m]    \nonumber \\
&  \textbf{A} {\textbf{x}} +\textbf{B} \textbf{y} \leq \textbf{D}    \nonumber \\
 &\text{Constraints \eqref{ct:MC-1}-\eqref{ct:MC-2}-\eqref{ct:MC-3}-\eqref{ct:MC-4}}\nonumber \\
     & \textbf{z} \in \{0,1\}^{m\times K},\; \textbf{y}\in {\mathcal{Y}},\textbf{w} \in \mathbb{R}^T,{\textbf{x}}\in {\mathcal{X}}, \textbf{u} \in \mathbb{R}^{T\times m\times K}, \textbf{v}\in \mathbb{R}^{t\times m}.   \nonumber
\end{align}

\subsection{MISOCP Reformulation}
We reformulate \eqref{prob:Approx-2} as MISOCP programs, which would give tighter relaxations, as compared the
MILP developed above. The idea is to introduce additional variables and  make use of conic quadratic inequalities of the form $x_1^2\leq x_2x_3$ with $x_1,x_2,x_3 \geq 0$.
We need additional assumptions which hold in the context of the maximum covering facility location problem.
\begin{proposition}\label{prop:misocp-1}
If $h^t_i(l_i) >0$  and $h^t_i(x_i)$ are monotonic increasing for $x_i\in [l_i,u_i]$, for all $t\in [T]$ and $i\in [m]$, then \eqref{prob:Approx-2} can be reformulated as the following MISOCP
\begin{align}
  \min_{\textbf{y},\textbf{x},\textbf{z},{\pmb{\theta}},\textbf{w}, \textbf{v},\textbf{u}}\quad& \left\{\sum_{t\in [T]}w_t(\lambda_tb_t - a_t) + \sum_{i\in [m]}v_{ti} (\lambda_th^t_i(l_i)- g^t_i(l_i)) + \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} (\lambda_t\gamma^{ht}_{ik}- \gamma^{gt}_{ik}) u_{tik} - \sum_{t\in [T]}\lambda_t \right\}\label{conic-1}\tag{\sf MISOCP-1} \\
  \text{such that}\quad &  \theta_t =   b_t+ \sum_{i\in [m]}y_i h^t_i(l_i) + \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} \gamma^{ht}_{ik} z_{ik},\;\forall t\in [T] \nonumber \\
  &w_t\theta_t \geq  1;\;\forall t\in [T] \nonumber \\
  &v_{ti}\theta_t \geq  y^2_i \;\forall t\in [T], i\in [m] \nonumber\\
  &u_{tik}\theta_t \geq  z^2_{ik} \;\forall t\in [T], i\in [m], k\in [K] \nonumber\\
  &  z_{ik}\geq z_{i,k+1},\;\forall i\in [m], k\in [K-1] \nonumber \\
    &  y_i\geq z_{i1},\;\forall i\in [m]\nonumber \\
&  {x}_i = l_i+\Delta_i \sum_{k\in [K]} z_{ik},\;\forall i\in [m]    \nonumber \\
&  \textbf{A}{\textbf{x}} +\textbf{B} \textbf{y} \leq \textbf{D}    \nonumber \\
     &  \textbf{z} \in \{0,1\}^{m\times K},\; \textbf{y}\in {\mathcal{Y}},\textbf{w},{\pmb{\theta}} \in \mathbb{R}^T,{\textbf{x}}\in {\mathcal{X}}, \textbf{u} \in \mathbb{R}^{T\times m\times K}, \textbf{v}\in \mathbb{R}^{t\times m}     \nonumber
\end{align}
where $\lambda_t>0$, $\forall t\in [T]$, such that
\[
\lambda_t >\max\left\{\max_{i\in [m]}\left\{\frac{g^t_i(l_i)}{h^t_i(l_i)}\right\};\max_{\textbf{x}, \textbf{y}} \left\{\frac{a_t + \sum_{i\in [m]} y_i g^t_i(x_i) }{b_t + \sum_{i\in [m]} y_i h^t_i(x_i)}\right\};\max_{t,i,k} \left\{\frac{\gamma^{gt}_{ik}}{\gamma^{ht}_{ik}}\right\}\right\}.
\]
\end{proposition}

If $h^t_i(x_i)$ is not monotonic increasing  as in the case of the joint assortment and price optimization problem, some bi-linear terms cannot be converted into rotated cones, thus we need to make use of McCormick inequalities to linearize them. We state this result the proposition below.

\begin{proposition}\label{prop:conic-2}
If $h^t_i(l_i) >0$ for all $t\in [T]$ and $i\in [m]$, then \eqref{prob:Approx-2} can be reformulated as the following MISOCP
\begin{align}
  \min_{\textbf{y},\textbf{x},\textbf{z},{\pmb{\theta}},\textbf{w}, \textbf{v},\textbf{u}}\quad& \left\{\sum_{t\in [T]}w_t(\lambda_tb_t - a_t) + \sum_{i\in [m]}v_{ti} (\lambda_th^t_i(l_i)- g^t_i(l_i)) + \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} (\lambda_t\gamma^{ht}_{ik}- \gamma^{gt}_{ik}) u_{tik} - \sum_{t\in [T]}\lambda_t \right\}\label{conic-2}\tag{\sf MISOCP-2} \\
  \text{such that}\quad &  \theta_t =   b_t+ \sum_{i\in [m]}y_i h^t_i(l_i) + \sum_{i\in [m]}\Delta_i\sum_{k\in [K]} \gamma^{ht}_{ik} z_{ik},\;\forall t\in [T] \nonumber \\
  &w_t\theta_t \geq  1;\;\forall t\in [T] \nonumber \\
  &v_{ti}\theta_t \geq  y^2_i \;\forall t\in [T], i\in [m] \nonumber\\
 &u_{tik} \leq U^w_t z_{ik};\;u_{tik} \geq L^w_t z_{ik} \nonumber \\
    &u_{tik} \leq w_t - L^w_t (1-z_{ik});\;u_{tik} \geq w_t - U^w_t (1-z_{ik})\nonumber \\
  &  z_{ik}\geq z_{i,k+1},\;\forall i\in [m], k\in [K-1] \nonumber \\
    &  y_i\geq z_{i1},\;\forall i\in [m]\nonumber \\
&  {x}_i = l_i+\Delta_i \sum_{k\in [K]} z_{ik},\;\forall i\in [m]    \nonumber \\
&  \textbf{A}{\textbf{x}} +\textbf{B} \textbf{y} \leq \textbf{D}    \nonumber \\
     &  \textbf{z} \in \{0,1\}^{m\times K},\; \textbf{y}\in {\mathcal{Y}},\textbf{w},{\pmb{\theta}} \in \mathbb{R}^T,{\textbf{x}}\in {\mathcal{X}}, \textbf{u} \in \mathbb{R}^{T\times m\times K}, \textbf{v}\in \mathbb{R}^{t\times m}     \nonumber
\end{align}
where $\lambda_t>0$, $\forall t\in [T]$, such that
\[
\lambda_t >\max\left\{\max_{i\in [m]}\left\{\frac{g^t_i(l_i)}{h^t_i(l_i)}\right\};\max_{\textbf{x}, \textbf{y}} \left\{\frac{a_t + \sum_{i\in [m]} y_i g^t_i(x_i) }{b_t + \sum_{i\in [m]} y_i h^t_i(x_i)}\right\}\right\}
\]
\end{proposition}

\section{Performance Guarantees}
\label{sec:performance-bounds}
In this section, we study performance guarantees for  our discretization approach. In Section \ref{sec:perfomance-1} we establish conditions and   guarantees for the convergence of the  approximate problem \eqref{prob:Approx}  to the original problem \eqref{prob:SoR-original} as the number of discretization points $K$ increases. We then extend the results for a general stochastic sum-of-ratios program arising from the use of the mixed-logit discrete choice model \cite{McFa81} with  continuous-distributed random parameters, for which one need to approximate the expectation by sample  average approximation before the discretization techniques can be used.

\subsection{Main Results} \label{sec:perfomance-1}
In this section we establish a bound for the approximation errors of the solutions returned by \eqref{prob:Approx}. For ease of notation, given any $\textbf{x}\in {\mathcal{X}}$, let ${\pmb{\delta}}^K(\textbf{x})$ be a vector of size $m$ with elements
\[
\delta^K(\textbf{x})_i = l_i+ \Delta_i\floor{(x_i-l_i)\Delta_i},~ \forall i\in [m].
\]
Let us also define $\underline{H}^t = \min_{(\textbf{y},\textbf{x}) \in {\mathcal{S}}} \{b_t + \sum_{i\in [m]} y_i h^t_i(x_i)\}$ and $\overline{F}^t  =\max_{(\textbf{y},\textbf{x}) \in {\mathcal{S}}} |(a_t + \sum_{i\in [m]} y_i g^t_i(x_i))/(b_t + \sum_{i\in [m]} y_i h^t_i(x_i))|$. Let us also denote  $(\textbf{x}^*,\textbf{y}^*)$ as an optimal solution to the original problem \eqref{prob:SoR-original} and $(\widetilde{\textbf{x}},\widetilde{\textbf{y}})$ as an  optimal solution to the approximate problem \eqref{prob:Approx}.
We start with the following lemma.
\begin{lemma}
\label{lm:lm2}
For any  $\textbf{y}\in {\mathcal{Y}}$ and $\textbf{x},\textbf{x}' \in {\mathcal{X}}$ and $\epsilon >0$ such that $||\textbf{x}-\textbf{x}'||_\infty \leq \epsilon$, we have
\[
\left| f(\textbf{y}, \textbf{x}) - f(\textbf{y},\textbf{x}')\right| \leq \epsilon C,
\]
where $C = \sum_{t\in [T]} \left(\frac{\sum_{i}L^{gt}_i}{\underline{H}^t} + \frac{\overline{F}^t \sum_{i\in[m]}L^{ht}_i}{\underline{H}^t}
         \right)$.
\end{lemma}

We then have the following corollary which is a direct result of Lemma \ref{lm:lm2} and the fact that $||\textbf{x}-{\pmb{\delta}}(\textbf{x})||_\infty \leq \max_{i\in [m]}\{{(u_i-l_i)/}{K}\}$.
\begin{corollary}\label{coro:coro1}
 For any $(\textbf{y},\textbf{x})\in {\mathcal{S}}$ we have
 \[
 |f(\textbf{y},\textbf{x}) - f(\textbf{y},{\pmb{\delta}}^K(\textbf{x}))| \leq \frac{C}{K}\max_{i\in [m]} \{u_i-l_i\}
 \]
\end{corollary}
Lemma \ref{lm:lm-simple-approx} below further simplifies \eqref{prob:Approx} by excluding variables $\textbf{z}$ and rewriting the objective function of \eqref{prob:Approx}  in the form  of the original objective function in \eqref{prob:SoR-original}. This will be useful for the proof of Theorem \ref{th:th1} below.

\begin{lemma}\label{lm:lm-simple-approx}
The approximate problem \eqref{prob:Approx} is equivalent to
\begin{align}
     \max_{\textbf{x},\textbf{y} } &\quad {f}(\textbf{y}, \textbf{x})  \label{prob:SoR-apprx-P1}  \tag{\sf P1}    \\
    \mbox{subject to} &\quad    \textbf{A}{\textbf{x}} +\textbf{B} \textbf{y} \leq \textbf{D}    \nonumber \\
    &\quad  x_i \in \left\{l_i+ \Delta_i k;\; k = 0,1,2,\ldots,K \right\},\;\forall i\in [m] \nonumber \\
     &\quad  \textbf{x}\in {\mathcal{X}}, \textbf{y}\in {\mathcal{Y}}.   \nonumber
\end{align}
\end{lemma}
\begin{proof}
It can be seen that if $(\textbf{y},\textbf{x})$ is feasible to \eqref{prob:SoR-apprx-P1}, then we have $k_i \in \{0,1,\ldots,K\}$ such that  $x_i = l_i+ \Delta_i k_i$. By selecting $\textbf{z}\in \{0,1\}^{m\times K}$  such that $z_{ik} = 1$ if $k\leq k_i$ and  $z_{ik} = 0$ if $k> k_i$, we can see that $(\textbf{y},\textbf{x}, \textbf{z})$ is feasible to \eqref{prob:Approx}. On the other hand,
if $(\textbf{y},\textbf{x}, \textbf{z})$ is feasible  to \eqref{prob:Approx}, then $x_i \in \left\{l_i+ \Delta_i k;\; k = 0,1,2,\ldots,K \right\}$. Putting all together, we have the equivalence.
\hspace*{0pt}\hfill \rule{0.5em}{0.5em}
\end{proof}
Intuitively, \eqref{prob:Approx} is a restricted version of the original problem where we require that $\textbf{x}$ is exactly one of the discrete points of the grid.
Now we state our first result. To facilitate our exposition, let $(\textbf{x}^*,\textbf{y}^*)$ be an optimal solution to the original problem \eqref{prob:SoR-original} and $(\widetilde{\textbf{x}},\widetilde{\textbf{y}})$ be optimal to the approximate problem \eqref{prob:SoR-apprx-P1}.

The following theorem establishes a bound for an approximate solution under Assumption (\textbf{A1}) and (\textbf{A2}).
\begin{theorem}\label{th:th1}
Suppose that (\textbf{A1}) and (\textbf{A2}) hold, then
\[
  \left|f(\textbf{y}^*,\textbf{x}^*) - f(\widetilde{\textbf{y}},\widetilde{\textbf{x}})\right| \leq  \sum_{t\in [T]} \left(\frac{\sum_{i}L^{gt}_i}{\underline{H}^t} + \frac{\overline{F}^t \sum_{i\in[m]}L^{ht}_i}{\underline{H}^t}
         \right)\frac{\max_{i\in [m]}\{u_i-l_i\}}{K}.
\]
\end{theorem}

From Proposition \ref{prop:Characterizing} we see that when $K$ increases, the feasible set of the approximate problem \eqref{prob:Approx} will approach  the feasible set of the original one \eqref{prob:SoR-original}. However, in a general setting, \eqref{prob:Approx} would have no feasible solution for any $K\in \mathbb{N}$. For  example, if the constraints $\textbf{A}\textbf{x}+\textbf{B}\textbf{y} \leq \textbf{D}$ forces  $(x_i-l_i)/(u_i-l_i)$  to be equal to an \textit{irrational number} for some $i\in [m]$, then  there are no integer numbers $K,k$ such that $0\leq k\leq K$ and $x_i = l_i+ (u_i-l_i)k/K$, i.e., \eqref{prob:Approx} has no feasible solution. We therefore relax the assumption in Theorem \ref{th:th1} by only requiring ${\mathcal{S}}$ to satisfy the \textit{Slater's condition} (i.e., ${\mathcal{S}}$ contains an interior point) for any fixed $y\in {\mathcal{Y}}$.
\begin{assumption}[A3]
For any $\textbf{y}\in {\mathcal{Y}}$, ${\mathcal{S}}(\textbf{y})$ satisfies the Slater's condition, i.e., it contains an interior point.
\end{assumption}
The following theorem shows another approximation bound when Assumption (\textbf{A3}) holds. Since  (\textbf{A3}) is less restrictive than (\textbf{A2}), this result is more general than Theorem \ref{th:th1}. The bound however involves the minimum size of balls that are contained in ${\mathcal{S}}(\textbf{y})$ for any $\textbf{y}$.
\begin{theorem}\label{th:th2}
Suppose (\textbf{A1}) and (\textbf{A3}) hold, then given any $\epsilon>0$, there exists a constant $K_0\in\mathbb{N}$ such that for all $K\geq K_0$ we have
\[
 \left|f(\textbf{x}^*,\textbf{y}^*) - f(\widetilde{\textbf{x}},\widetilde{\textbf{y}})\right| \leq \epsilon C,
\]
where $C = \sum_{t\in [T]} \left(\frac{\sum_{i}L^{gt}_i}{\underline{H}^t} + \frac{\overline{F}^t \sum_{i\in[m]}L^{ht}_i}{\underline{H}^t}
         \right)$.
\end{theorem}

From Theorem \ref{th:th2}  and its proof, we can get more insights about how to select $K_0$ and how the gap $|f(\textbf{y}^*,\textbf{x}^*)-f(\textbf{y}^K,\textbf{x}^K)|$ converges as $K$ increases. We present these results in the following propositions.
\begin{proposition}
\label{prop:bound-1}Suppose (\textbf{A1}) and (\textbf{A3}) hold and assume that there exists $\alpha>0$ such that for any $\textbf{y}\in {\mathcal{Y}}$, ${\mathcal{S}}(\textbf{y})$ contains an interior point $\textbf{x}^0$ such that the ball $\{\textbf{x}\big|\; ||\textbf{x}-\textbf{x}^0||_\infty \leq \alpha\}$ is contained in ${\mathcal{S}}(\textbf{y})$, then  given any $\epsilon>0$, we have
$ \left|f(\textbf{x}^*,\textbf{y}^*) - f(\widetilde{\textbf{x}},\widetilde{\textbf{y}})\right| \leq \epsilon C$ for any
\[
K\geq \max_{i\in[m]} \left\{ \frac{(u_i-l_i)(\alpha+u_i-l_i)}{\alpha\epsilon}\right\}.
\]
\end{proposition}

The following corollary gives a different view on how the gap converges when $K$ grows.
\begin{proposition}
\label{prop:bound-2} Under  (\textbf{A1}) and (\textbf{A3}), assume that there exists $\alpha>0$ such that for any $\textbf{y}\in {\mathcal{Y}}$, ${\mathcal{S}}(\textbf{y})$ contains an interior point $\textbf{x}^0$ such that $\{\textbf{x}\big|\; ||\textbf{x}-\textbf{x}^0||_\infty \leq \alpha\} \subset {\mathcal{S}}(\textbf{y})$, then  for any $K\geq \max_{i\in [m]} \{(u_i-l_i)/\alpha\}$ we have
\[
\left|f(\textbf{x}^*,\textbf{y}^*) - f(\widetilde{\textbf{x}},\widetilde{\textbf{y}})\right| \leq \frac{C}{\alpha K}\max_{i\in [m]}\left\{ (u_i-l_i)(\alpha+u_i-l_i)\right\}.
\]
\end{proposition}

\subsection{Sampling and Discretization}
\label{sec:performance-stoch}
We have so far consider sum-of-ratios programs which arises from using the mixed-logit model with random choice parameters supported by a finite set of parameters. In a more general setting, the choice parameters can follow a continuous distribution \citep{McFa81}, for which the objective function would involve an expectation over an infinite set of  random parameters. To handle this, one can approximate the expectation by SSA and then use the discretization techniques developed above. In the following we  establish approximation bounds for such a 2-level approximation approach. We first consider  a stochastic sum-of-ratios optimization problem of the following form.
\begin{align}
     \max_{\textbf{y},\textbf{x}} \quad &  {\mathcal{F}}(\textbf{y},\textbf{x}) = \mathbb{E}_{{\pmb{\xi}}} \left[\frac{a({\pmb{\xi}}) +\sum_{i\in [m]}y_i g_i(x_i,{\pmb{\xi}}) }{b({\pmb{\xi}}) +\sum_{i\in [m]}y_i h_i(x_i,{\pmb{\xi}})}\right] \label{prob:SSoR}\tag{\sf Stoc-SoR} \\
    \mbox{subject to} \quad& \textbf{A}\textbf{x}+\textbf{B}\textbf{y}\leq \textbf{D} \nonumber\\
     & \textbf{y}\in{\mathcal{Y}},\; \textbf{x}\in{\mathcal{X}}\nonumber
\end{align}
Let us define an SAA version of  \eqref{prob:SSoR}, obtained by taking $T$ sample of ${\pmb{\xi}}$.
\begin{align}
     \max_{\textbf{y},\textbf{x}} \quad &  \widehat{{\mathcal{F}}}^T (\textbf{y},\textbf{x}) = \sum_{t\in [T]}\frac{a({\pmb{\xi}}^t) +\sum_{i\in [m]}y_i g_i(x_i,{\pmb{\xi}}^t) }{b({\pmb{\xi}}^t) +\sum_{i\in [m]}y_i h_i(x_i,{\pmb{\xi}}^t)} \label{prob:SAA-SoR}\tag{\sf SAA-SoR} \\
    \mbox{subject to} \quad& \textbf{A}\textbf{x}+\textbf{B}\textbf{y}\leq \textbf{D} \nonumber\\
     & \textbf{y}\in{\mathcal{Y}},\; \textbf{x}\in{\mathcal{X}}\nonumber
\end{align}
where $\{{\pmb{\xi}}^1,\ldots,{\pmb{\xi}}^T\}$ are $T$ i.i.d. samples of ${\pmb{\xi}}$. \eqref{prob:SAA-SoR} is of  the same structure with the  sum-of-ratios problem considered in \eqref{prob:SoR-original}. Let $(\textbf{y}^*,\textbf{x}^*)$, $(\widehat{\textbf{y}},\widehat{\textbf{x}})$ and $(\widehat{\textbf{y}}^K,\widehat{\textbf{x}}^K)$ be optimal solution to the stochastic problem \eqref{prob:SSoR}, its SAA version \eqref{prob:SAA-SoR} and the discretization version of \eqref{prob:SAA-SoR}, respectively. We aim to  establish a bound for $|{\mathcal{F}}(\textbf{y}^*,\textbf{x}^*)-{\mathcal{F}}(\widehat{\textbf{y}}^K,\widehat{\textbf{x}}^K)|$ which reflects  the performance of a solution given by our SAA and discretization approach.
Before presenting the main result, we need assumptions that are similar to those used in the sum-of-ratios case.
\begin{assumption}[A4]
The following holds almost surely
\begin{itemize}
    \item The ratio $\frac{a({\pmb{\xi}}) +\sum_{i\in [m]}y_i g_i(x_i,{\pmb{\xi}}) }{b({\pmb{\xi}}) +\sum_{i\in [m]}y_i h_i(x_i,{\pmb{\xi}})}$ is lower and upper bounded
    \item $b({\pmb{\xi}}) +\sum_{i\in [m]}y_i h_i(x_i,{\pmb{\xi}}) >0$

\item $h_i(x_i,{\pmb{\xi}})$  and $g_i(x_i, {\pmb{\xi}})$ are Lipschitz continuous, i.e., there exist  $L^{g}_i, L^{h}_i>0$ such that
    \begin{align}
        |h_i(x_1,{\pmb{\xi}}) - h_i(x_2,{\pmb{\xi}})| \leq L^{h}_i |x_1-x_2|,&\;\forall x_1,x_2 \in [l_i,u_i] \nonumber \\
        |g_i(x_1,{\pmb{\xi}}) - g_i(x_2,{\pmb{\xi}})| \leq L^{g}_i |x_1-x_2|,&\;\forall x_1,x_2 \in [l_i,u_i] \nonumber
    \end{align}
\end{itemize}
\end{assumption}
Under (\textbf{A4}), let assume that there are two constants $\underline{F}$ and $\overline{F}$ such that, with probability one,
\[
\underline{F} \leq \frac{a({\pmb{\xi}}) +\sum_{i\in [m]}y_i g_i(x_i,{\pmb{\xi}}) }{b({\pmb{\xi}}) +\sum_{i\in [m]}y_i h_i(x_i,{\pmb{\xi}})} \leq \overline{F}.
\]
Let $\underline{H}$ be a constant such that, with probability one,  $\underline{H} \leq b({\pmb{\xi}}) + \sum_{i\in [m]} y_i h_i(x_i,{\pmb{\xi}})$ for all $(\textbf{y},\textbf{x}\in {\mathcal{S}})$,
and $C^* = \left(\frac{\sum_{i\in [m]} L^g_i}{\underline{H}} + \frac{\overline{F}\sum_{i\in [m] }L^h_i}{\underline{H}}\right)$.
We also let $\Psi = \overline{F} - \underline{F}$ for notation brevity.
We state our main results in Theorem \ref{th:th3} below.
\begin{theorem}
\label{th:th3}
Given any $\epsilon>0$, suppose (\textbf{A3}) and (\textbf{A4}) hold,  the inequality $|{\mathcal{F}}(\textbf{y}^*,\textbf{x}^*) - {\mathcal{F}}(\widehat{\textbf{y}}^K,\widehat{\textbf{x}}^K)| \leq \epsilon$ holds with a probability at least  $1 - 6\exp\left(\frac{-2T\epsilon^2}{25\Psi}\right)$
if we choose $K$ such that
\[
K \geq \frac{5TC^*}{\alpha \epsilon}\max_{i\in[m]} \left\{ {(u_i-l_i)(\alpha+u_i-l_i)}\right\}.
\]
Moreover, if (\textbf{A2}) and (\textbf{A4}) hold, then $\mathbb{P}[|{\mathcal{F}}(\textbf{y}^*,\textbf{x}^*) - {\mathcal{F}}(\widehat{\textbf{y}}^K,\widehat{\textbf{x}}^K)| \leq \epsilon] \geq 1 - 6\exp\left(\frac{-2T\epsilon^2}{25\Psi}\right)$  if we choose
\[
K\geq \frac{5TC^*}{\epsilon} \max_{i\in [m]} (u_i-l_i).
\]
\end{theorem}
The above theorem provides a relation between the number of samples $T$ of the SSA and the number of discretization points $K$. It generally implies that, to have a high probability of getting near-optimal solutions, one would need to select a sufficiently large $T$, and $K = {\mathcal{O}}(T)$. Moreover, if (\textbf{A3})  holds (i.e., the feasible set satisfies the Slater's conditions), the selection
 of $K$ should depend on the minimum size of  balls that are interior to the feasible set of \eqref{prob:SoR-original}. In the following corollary, we further elaborate this point by establishing some estimates for $T$ and $K$ that secures a high probability of getting good solutions. The estimates are direct  results from the proof of Theorem \ref{th:th2}.
\begin{corollary}
 For any $\gamma \in (0,1)$ and $\epsilon>0$, we have $\mathbb{P}[|{{\mathcal{F}}}({\textbf{y}^*},{\textbf{x}^*}) - {{\mathcal{F}}}(\widehat{\textbf{y}}^K,\widehat{\textbf{x}}^K)| \leq \epsilon] \geq 1-\gamma$  if  one of the following conditions satisfies
 \begin{itemize}
 \item[(i)] (\textbf{A2}) and (\textbf{A4}) hold and
  \[
 T\geq \frac{25 \Psi\ln(6/\gamma)}{2\epsilon^2};\; K\geq  \frac{5TC^*}{ \epsilon}\max_{i\in[m]} \left\{ {(u_i-l_i)}\right\},
 \]
     \item[(ii)] (\textbf{A3}) and (\textbf{A4}) hold and
    \[
     T\geq \frac{25 \Psi\ln(6/\gamma)}{2\epsilon^2};\; K\geq  \frac{5TC^* }{\alpha \epsilon}\max_{i\in[m]} \left\{ {(u_i-l_i)(\alpha+u_i-l_i)}\right\}
 \]
 \end{itemize}
\end{corollary}

\section{Applications}\label{sec:app}
We briefly  discuss the applications of our discretization approach to two prominent classes of  decision-making problems, i.e., assortment and price optimization,  and maximum covering facility location. The SSG formulation is similar to that of the assortment and price optimization and we refer the reader to  \citep{yang2012computing,fang2017paws} for more details.
\subsection{Joint Assortment  and Price Optimization}
Let $[m]$ be the set of products. There is a non-purchase item indexed by $0$. Let $x_i$ be the price of product $i\in [m]$. For each customer segment $t\in [T]$, each product is associated with an utility $v_{ti} = x_i\eta_{ti} +\kappa_{ti}$, where $\eta_{ti}$ is a price sensitivity parameter of product $i$, which should take a negative value, and  $\kappa_{ti}$ are other parameters that affect the choices (e.g., values that capture other product features). The purchasing probability of a product $i$ can be computed as
\[
P\left(i\Big|~[m]\cup\{0\}\right) =
\sum_{t\in [T]}\frac{\exp(x_i\eta_{ti}+\kappa_{ti})}{1+\sum_{i\in [m]} \exp(x_i\eta_{ti}+\kappa_{ti})},
\]
where the value $1$ in the denominator refers to the utility of the non-purchase option.
The joint assortment and price optimization problem under the mixed logit model  has the following form
\begin{equation}\label{prob:asso-prive}\tag{\sf Assort-Price}
     \max_{\textbf{y}\in {\mathcal{Y}},\textbf{x}\in {\mathcal{X}} }\left\{f(\textbf{y},\textbf{x}) = \sum_{t\in [T]}  \frac{ \sum_{i\in [m]} y_i x_i \exp\big(x_i \eta_{ti} + \kappa_{ti}\big) }{1 + \sum_{i\in [m]} y_i \exp\big(x_i \eta_{ti} + \kappa_{ti}\big)}\right\}
\end{equation}
where the objective $f(\textbf{y},\textbf{x})$ is an expected revenue,  $y_i, x_i$ are assortment and price decisions, respectively. To apply the approximation methods above, we can simply let $g^t_i(x_i) = x_i\exp\big(x_i \eta_{ti} + \kappa_{ti}\big)$ and $h^t_i(x_i) = \exp\big(x_i \eta_{ti} + \kappa_{ti}\big)$, noting that the assumptions in Proposition \ref{prop:conic-2} holds as  $h^t_i(x_i)$ is monotonic decreasing, thus \eqref{conic-2} can be used. Some relevant constraints would be $\sum_{i\in [m]}y_i\leq M$ (i.e., a {cardinality } constraint on the number of products offered), lower and upper bounds $(l_i,u_i)$ for the prices. In some contexts one may require that a total price of a \textit{product bundle}  to be less than an upper bound, i.e., $\sum_{i\in S} y_i x_i \leq W$ for some $S\subset [m]$. With these constraints, we can see that Assumption (\textbf{A2}) satisfies, thus the simplified version in \eqref{prob:Approx-1} can be used. Note that such a constraint $\sum_{i\in S} y_i x_i \leq W$ can be easily linearized using McCormick inequalities \citep{mccormick1976computability}.

\subsection{Maximum Covering Facility Location }
We reuse the same notations as in the previous section to reduce notational burden, noting that notations in this section would have different interpretations. Now, let $[m]$ be the set of available locations to setup new facility. For each costumer segment $t\in [T]$, let $v_{tj} = x_i\eta_{ti} -\kappa_{ti}$ be the corresponding utility function of location $i\in [m]$, where $x_i$ is the cost to spend on location $i$, $\eta_{ti}$ is a cost sensitivity parameter that reflects the impact of the cost $x_i$ on the choice probabilities, and $\kappa_{ti}$ are other parameters that affect the choices. We should have $\eta_{ti}>0$.
The probability that a facility located at location $i$ will be chosen, under the mixed-logit model, is given as
\[
P\left(i\Big|~[m]\cup\{0\}\right) =
\sum_{t\in [T]}\frac{\exp(x_i\eta_{ti}+\kappa_{ti})}{U_C+\sum_{i\in [m]} \exp(x_i\eta_{ti}+\kappa_{ti})},
\]
where $U_C$ captures the utilities of the competitor. The objective now is to maximize an expected covering function, i.e., expected  captured demand. We can write the problem as
\begin{equation}\label{prob:maxcap}\tag{\sf Max-Cov}
     \max_{\textbf{y}\in {\mathcal{Y}},\textbf{x}\in {\mathcal{X}} }\left\{f(\textbf{y},\textbf{x}) = \sum_{t\in [T]}  \frac{q_t \sum_{i\in [m]} y_i \exp\big(x_i \eta_{ti} + \kappa_{ti}\big) }{U_C + \sum_{i\in [m]} y_i \exp\big(x_i \eta_{ti} + \kappa_{ti}\big)}\right\}
\end{equation}
where $q_t$ is the weight of customer $t$, e.g., the proportion  of customers in segment $t$. The maximum covering problem \eqref{prob:maxcap} differs  from \eqref{prob:asso-prive} as the objective function of \eqref{prob:maxcap} is concave in $\textbf{x}, \textbf{y}$ and can  be simplified into a sum of ratios in which the variables $\textbf{y},\textbf{x}$ only appear in the denominators: \[
f(\textbf{y},\textbf{x}) = \sum_{t\in[T]}q_t -  \sum_{t\in [T]}  \frac{U_C}{U_C + \sum_{i\in [m]} y_i \exp\big(x_i \eta_{ti} + \kappa_{ti}\big)}.
\]
As a result, to apply the approximation methods above, we can let $g_i^t(x_i) = 0$, $a_t=U^t_C$, $b_1 = U^t_C$ and $h^t_i(x_i) = \exp(x_i\eta_{ti}+\kappa_{ti})$.
Since $\eta_{ti}>0$, $h^t_i(x_i)$ is monotonic increasing in $x_i$, thus
the MISOCP reformulation in Proposition \ref{prop:misocp-1} can be used. Moreover, due to the concavity, the approximated problem can also be solved by a multi-cut outer-approximation algorithm \citep{mai2020multicut}, besides using an off-the-shelf solver (e.g.,  CPLEX) to solve  the MILP and MISOCP reformulations in Section \ref{sec:discr-approach}.

\section{Numerical Experiments}
\label{sec:experiments}
\subsection{Experimental settings} 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. The code is in C++
and links to IBM ILOG-CPLEX 12.10 (under default settings) to solve the  MILP and MISOCP programs. We set  the CPU time limit for
each instance as 3600 seconds, i.e., we stop the algorithms/solver if they exceed the time budget and report the best solutions found. We provide numerical experiments based on two applications: assortment and price optimization (A\&P), and maximum covering facility location (MaxCov). The SSG problem shares the same structure with (A\&P) thus we do not consider it here.

\subsection{{Solution quality as a function of $K$.}}
In this first experiment we study the performance  of our discretization approach as a function of $K$, aiming to explore  how we should select $K$ to practically achieve desirable solutions. Note that the sizes of the MILP and MISOCP reformulations  are proportional to $K$, so it is important  to have a  good selection for $K$ to balance the trade-off between computational cost  and  solution quality. To assess the solution quality with different values of $K$, we randomly  generate A\&P instances of $T=5$, $m=10$, $C\in [4,6]$ and $M\in [3,5]$. For  each instance,
we vary $K$ from 1  to 50  and solve the approximate problem to get  solutions $(\textbf{y}^K,\textbf{x}^K)$. We then compute the percentage gaps between $f(\textbf{y}^K,\textbf{x}^K)$  and $f(\textbf{y}^{K_0},\textbf{x}^{K_0})$, where $K_0$ is chosen to be sufficiently large to ensure that  $f(\textbf{y}^{K_0},\textbf{x}^{K_0})$ is almost  equal to the optimal value. Here, we choose $K_0=100$, noting that the values of $f(\textbf{y}^{K},\textbf{x}^{K})$ remain almost  the same for  any $K>K_0$. In Figure \ref{fig:gaps} we plot the  means and standards errors of the percentage gaps (\%) over 10 random instances, where the solid curve shows  the means, and the shaded area represents the standard errors. We can see that the percentage gaps become about less than 0.4\% with $K=10$, and are just below 0.03\% with $K=25$. This indicates that $K=25$ would be sufficient to achieve very good approximations. According to this experiment, we will use $K=25$ for the next experiments.

\begin{figure}[htb]
    \centering
    \includegraphics[width=0.7\textwidth]{gaps.pdf}
    \caption{Performance as $K$ increases.}
    \label{fig:gaps}
\end{figure}

\subsection{Comparison results}
We make comparisons with the following baseline method. First, noting that when $\textbf{x}$ are fixed, one can solve \eqref{prob:SoR-original} exactly by reformulating the problem as a MILP and solving it by CPLEX \citep{bront2009column,benati2002maximum},
we develop a simple method (called as \textit{3-Steps}) working as follows. We first fix $\textbf{y}$ and solve \eqref{prob:SoR-original} by a gradient-based method \citep{NoceWrig06} on $\textbf{x}$. We then fixed $\textbf{x}$ and solve the problem through the MILP reformulation. The last step is to correct $\textbf{x}$ by fixing $\textbf{y}$ obtained from second step and improving $\textbf{x}$ by a gradient-based method.

Table \ref{table1} reports  comparison results for A\&P instances. For each group of $(|I|,m,C,M)$, we randomly generate 3 instances and report the numbers of instances that are solved to optimality and solved with the best returned objective values. It is clear that the baseline \textit{3-Steps} is outperformed by our approaches in terms of solution quality, and the MILP seems better than MISOCP in returning good solutions. MILP is also slightly faster than MISOCP.
\begin{table}[htb]
\centering
\caption{Comparison results for A\&P instances; instances grouped by $(|I|,m,C,M)$ (3 instances per row); ``-'' indicates that the algorithm/solver exceeds the time budget.}
\label{table1}
\resizebox{\linewidth}{!}{%
\begin{tabular}{llll|ll|lll|lll|ll}
\multirow{2}{*}{$|I|$} & \multirow{2}{*}{$m$} & \multirow{2}{*}{$C$} & \multirow{2}{*}{$M$} & \multicolumn{2}{c|}{\begin{tabular}[c]{@{}c@{}}\# Instances solved\\to optimality\end{tabular}} & \multicolumn{3}{c|}{\begin{tabular}[c]{@{}c@{}}\# Instances with\\best objectives\end{tabular}} & \multicolumn{3}{c|}{\begin{tabular}[c]{@{}c@{}}Average\\CPU time (s)\end{tabular}} & \multicolumn{2}{c}{\begin{tabular}[c]{@{}c@{}}Average\\gap (\%)\end{tabular}} \\
\cline{5-14}
 &  &  &  & MILP & MISOCP & 3-Steps & MILP & MISOCP & Ben & MILP & MISOCP & MILP & MISOCP \\
\hline
5 & 10 & 4 & 5 & \textbf{3} & \textbf{3} & 0 & \textbf{3} & \textbf{3} & \textbf{3.2} & 7.6 & 54.4 & \textbf{0.0} & \textbf{0.0} \\
\hline
5 & 10 & 4 & 3 & \textbf{3} & \textbf{3} & 2 & \textbf{3} & \textbf{3} & 152.4 & \textbf{1.9} & 7.8 & \textbf{0.0} & \textbf{0.0} \\
\hline
5 & 10 & 6 & 5 & \textbf{3} & \textbf{3} & 0 & \textbf{3} & \textbf{3} & 53.0 & \textbf{4.3} & 57.6 & \textbf{0.0} & \textbf{0.0} \\
\hline
5 & 10 & 6 & 3 & \textbf{3} & \textbf{3} & 1 & \textbf{3} & \textbf{3} & 102.3 & \textbf{1.2} & 6.9 & \textbf{0.0} & \textbf{0.0} \\
\hline
5 & 20 & 8 & 10 & \textbf{0} & \textbf{0} & 0 & \textbf{3} & 0 & \textbf{30.5} & - & - & \textbf{7.2} & 37.3 \\
\hline
5 & 20 & 8 & 6 & \textbf{2} & 0 & 0 & \textbf{3} & \textbf{3} & \textbf{18.4} & 1762.2 & - & \textbf{0.1} & 0.9 \\
\hline
5 & 20 & 12 & 10 & \textbf{0} & \textbf{0} & 0 & \textbf{3} & 0 & \textbf{18.7} & - & - & \textbf{5.0} & 32.6 \\
\hline
5 & 20 & 12 & 6 & \textbf{3} & 1 & 0 & \textbf{3} & \textbf{3} & \textbf{16.0} & 331.7 & 3063.7 & \textbf{0.0} & 0.3 \\
\hline \hline
\multicolumn{4}{l|}{Average} & 2.1 & 1.6 & 0.4 & 3 & 2.3 &  &  &  & 1.5 & 8.9 \\
\end{tabular}
}
\end{table}

In the next experiment, we fix $\textbf{y}$ and conduct numerical comparisons for  price optimization instances. Under this setting, the \textit{3-Steps}
becomes a single step of using a gradient-based method to optimize $\textbf{x}$, noting that the problem itself is highly non-convex and one cannot get any guarantees with a gradient-based method. Table \ref{table2} reports the comparison results, which generally show that all the approaches are able  to return best objective values. The  \textit{3-Steps} now performs well and, as expected, faster than the other methods. MILP can confirm 6 instances to be solved to optimality while MISOCP cannot do so for any instances within the time limit. In general, we also see that MILP is better than MISOCP.

\begin{table}[htb]
\centering
\caption{Comparison results for the price optimization problem; instances are grouped by $(|I|,m,C)$ (3 instances per row); ``-'' indicates that the algorithm/solver exceeds the time budget}
\label{table2}
\resizebox{\linewidth}{!}{%
\begin{tabular}{lll|ll|lll|lll|ll}
\multirow{2}{*}{$|I|$} & \multirow{2}{*}{$m$} & \multirow{2}{*}{$C$} & \multicolumn{2}{c|}{\begin{tabular}[c]{@{}c@{}}\# Instances solved\\to optimality\end{tabular}} & \multicolumn{3}{c|}{\begin{tabular}[c]{@{}c@{}}\# Instances with\\best objectives\end{tabular}} & \multicolumn{3}{c|}{Average CPU time (s)} & \multicolumn{2}{c}{Average gap (\%)} \\
\cline{4-13}
 &  &  & MILP & MISOCP & 3-Steps & MILP & MISOCP & Ben & MILP & MISOCP & MILP & MISOCP \\
\hline
5 & 10 & 4 & \textbf{3} & 0 & \textbf{3} & \textbf{3} & \textbf{3} & \textbf{2.5} & 61.0 & - & \textbf{0.0} & 1.5 \\
\hline
5 & 10 & 6 & \textbf{3} & 0 & \textbf{3} & \textbf{3} & \textbf{3} & \textbf{2.2} & 70.4 & - & \textbf{0.0} & 1.4 \\
\hline
5 & 20 & 8 & \textbf{0} & \textbf{0} & \textbf{3} & \textbf{3} & \textbf{3} & \textbf{19.3} & - & - & \textbf{0.7} & 3.4 \\
\hline
5 & 20 & 12 & \textbf{0} & \textbf{0} & \textbf{3} & \textbf{3} & \textbf{3} & \textbf{19} & - & - & \textbf{0.7} & 4.8 \\
\hline \hline
\multicolumn{3}{l|}{Average} & 1.5 & 0 & 3 & 3 & 3 & 10.8 & 1832.9 & - & 0.4 & 2.8
\end{tabular}
}
\end{table}

 We now move to the MaxCov problem. As stated earlier, apart from the MILP and MISOCP reformulations, the problem can also be solved by an outer-approximation algorithm (denoted as OA). We therefore conduct numerical comparisons  of the four approaches: OA, MILP, MISOCP and 3-Steps.  The results are reported in Table \ref{table3}. It  is not surprising to see that 3-Steps is outperformed by the other methods, in terms of solution quality. Interestingly, MISOCP clearly outperforms MILP in terms of both solution quality and computing time --- MISOCP is able to return best objective values for all the instances and the average running time is just about 5.4 seconds, while MILP cannot return the best objectives for several large-sized instances and always exceeds the time budget of 3600 seconds. This would be due to the concavity of the objective function and the fact that the function $h^t_i(x_i)$ is monotonic increasing and the MISOCP reformulation \eqref{conic-1} can be used, instead of \eqref{conic-2}. It can be seen that  \eqref{conic-1} has no McCormick inequalities, thus yields tighter relaxations than \eqref{conic-2}.
 The OA, by leveraging the concavity of the objective function, performs the best in terms of both solution quality and running time.

\begin{table}[htb]\footnotesize
\centering
\caption{Comparison results for MaxCov instances; instances  are grouped by $(|I|,m,C,M)$ (3 instances per row); MIS stands for MISOCP to reduce the table size.}
\label{table3}
\resizebox{\linewidth}{!}{%
\begin{tabular}{llll|lll|llll|llll|ll}
\multirow{2}{*}{$|I|$} & \multirow{2}{*}{$m$} & \multirow{2}{*}{$C$} & \multirow{2}{*}{$M$} & \multicolumn{3}{c|}{\begin{tabular}[c]{@{}c@{}}\# Instances solved\\to optimality\end{tabular}} & \multicolumn{4}{c|}{\begin{tabular}[c]{@{}c@{}}\# Instances with\\best objectives\end{tabular}} & \multicolumn{4}{c|}{\begin{tabular}[c]{@{}c@{}}Average\\CPU time (s)\end{tabular}} & \multicolumn{2}{c}{\begin{tabular}[c]{@{}c@{}}Average\\gap (\%)\end{tabular}} \\
\cline{5-17}
 &  &  &  & MILP & MIS & OA & 3-Steps & MILP & MIS & OA & 3-Steps & MILP & MIS & OA & MILP & MIS\\
\hline
5 & 50 & 20 & 16 & 0 & \textbf{3} & \textbf{\textbf{3}} & 1 & \textbf{\textbf{3}} & \textbf{3} & \textbf{3} & 434.8 & - & \textbf{0.5} & \textbf{0.5} & 6.5 & \textbf{0.0} \\
\hline
5 & 50 & 20 & 25 & 0 & \textbf{3} & \textbf{\textbf{3}} & 2 & \textbf{\textbf{3}} & \textbf{3} & \textbf{3} & 352.5 & - & \textbf{0.4} & \textbf{0.4} & 5.5 & \textbf{0.0} \\
\hline
5 & 50 & 30 & 16 & 0 & \textbf{3} & \textbf{\textbf{3}} & 0 & \textbf{\textbf{3}} & \textbf{3} & \textbf{3} & 364.2 & - & 2.1 & \textbf{1.2} & 3.5 & \textbf{0.0} \\
\hline
5 & 50 & 30 & 25 & 0 & \textbf{3} & \textbf{\textbf{3}} & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & \textbf{3} & 409.8 & - & 2.1 & \textbf{1.0} & 2.8 & \textbf{0.0} \\
\hline
5 & 100 & 40 & 33 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & \textbf{\textbf{3}} & \textbf{3} & \textbf{\textbf{3}} & 477.5 & - & 2.2 & \textbf{1.3} & 13.9 & \textbf{\textbf{0.0}} \\
\hline
5 & 100 & 40 & 50 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & \textbf{\textbf{3}} & \textbf{3} & \textbf{\textbf{3}} & 523.6 & - & 1.7 & \textbf{1.2} & 11.6 & \textbf{\textbf{0.0}} \\
\hline
5 & 100 & 60 & 33 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & \textbf{\textbf{3}} & \textbf{3} & \textbf{3} & 469.6 & - & 2.7 & \textbf{1.8} & 8.5 & \textbf{\textbf{0.0}} \\
\hline
5 & 100 & 60 & 50 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 545.3 & - & 2.7 & \textbf{1.7} & 8.3 & \textbf{\textbf{0.0}} \\
\hline
10 & 50 & 20 & 16 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 453.8 & - & 1.4 & \textbf{0.1} & 15.6 & \textbf{\textbf{0.0}} \\
\hline
10 & 50 & 20 & 25 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 460.0 & - & 1.2 & \textbf{0.1} & 12.4 & \textbf{\textbf{0.0}} \\
\hline
10 & 50 & 30 & 16 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & 2 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 453.7 & - & 3.5 & \textbf{0.1} & 20.2 & \textbf{\textbf{0.0}} \\
\hline
10 & 50 & 30 & 25 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 1 & 2 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 461.8 & - & 2.9 & \textbf{0.1} & 14.4 & \textbf{\textbf{0.0}} \\
\hline
100 & 50 & 20 & 16 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 455.7 & - & 10.6 & \textbf{3.1} & - & \textbf{\textbf{0.0}} \\
\hline
100 & 50 & 20 & 25 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 471.8 & - & 9.7 & \textbf{3.1} & - & \textbf{\textbf{0.0}} \\
\hline
100 & 50 & 30 & 16 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 455.4 & - & 19.0 & \textbf{3.3} & - & \textbf{\textbf{0.0}} \\
\hline
100 & 50 & 30 & 25 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & 0 & \textbf{3} & \textbf{\textbf{3}} & 454.0 & - & 18.6 & \textbf{3.2} & - & \textbf{\textbf{0.0}} \\
\hline
100 & 100 & 40 & 33 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 496.4 & - & \textbf{8.3} & 8.5 & - & \textbf{\textbf{0.0}} \\
\hline
100 & 100 & 40 & 50 & 0 & \textbf{\textbf{3}} & \textbf{\textbf{3}} & 0 & 0 & \textbf{3} & \textbf{\textbf{3}} & 595.2 & - & \textbf{8.3} & \textbf{8.3} & - & \textbf{\textbf{0.0}} \\
\hline\hline
\multicolumn{4}{l|}{Average} & 0 & 3 & 3 & 0.2 & 1.9 & 3.0 & 3.0 & 463.1 & - & 5.4 & 2.2 & 1.5 & \textbf{\textbf{0.0}}
\end{tabular}
}
\end{table}

In summary, our experiments based on A\&P and MaxCov instances clearly shows that our approaches outperform the baseline 3-Steps. For A\&P instances, MILP seems to be better than MISOCP, but the opposite has been observed for MaxCov instances. Moreover, OA seems to work very well for the MaxCov instances as it clearly outperforms other methods.
\section{Conclusion}
\label{sec:concl}
We studied a class of non-convex binary-continuous sun-of-ratios programs that can be used for decision-making in prominent application domains such as  assortment and price optimization, maximum covering facility location or sercurity games. We developed a discretization technique that allows us to linearize the nonlinear numerators and denominators of the objective function, which further opens up the possibility of reformulating the nonlinear problem as MILP or MISOCP. We then established (mild) conditions under which solutions  to the approximate problem converge to the true ones as the number of discretization points $K$ increases, and provided estimates for $K$ to guarantee near-optimality. Numerical experiments based on assortment and price optimization and maximum covering instances show the efficiency of our approximation and convexification approaches. Future directions would be to develop ways  to improve the MILP and MISOCP reformulations with valid inequalities  and cuts, or to explore other classes of problems, e.g.,  those resulting from the use of other discrete choice models such as the nested or cross-nested logit \citep{Trai03}.

\bibliographystyle{plainnat}

redpajama_set_name: RedPajamaArXiv


The Natoma Company manages approximately 2,600 units of individually owned investment properties, as well as syndicated properties. Currently, The Natoma Company manages apartment communities in the greater Sacramento area and surrounding foothills. The Natoma Company has established a sound reputation for exceptional service in the rental market, increasing property values, renting up of new projects, control of expenses, and rehabilitating existing properties. The Natoma Company was recently rated in the top 10 property management firms by the Sacramento Business Journal.
The company has managed all types of properties and has extensive experience with receiverships and REO's. By utilizing flexibility and by customizing our services, we are able to fully meet the individual needs of our clients.
Currently, The Natoma Company has three full-time property managers on staff. While each property is assigned a specific property manager, The Natoma Company utilizes an overall team management approach in order to take advantage of each property manager's area of expertise. Their individual areas of strength include the fields of marketing, budget preparation, and risk management. Regularly scheduled meetings are conducted with on-site personnel on these and other topics. The property managers are backed by an experienced support team, which includes top-level property management assistants, administrative support, and a fully staffed accounting department.
I pledge myself to seek and maintain an equitable, honorable, and cooperative association with fellow Members of the Institute and with all others who may become a part of business and professional life. I recognize and support the need to preserve and encourage fair and equitable practices and competition among all who are engaged in the profession of real estate management.
I pledge myself to place honesty, integrity, and industriousness above all else and to pursue my gainful efforts with diligent study and ongoing education so that my services shall be benficial to the general public and my obligations to my clients shall always be maintained at the highest possible level.
The Natoma Company is determined to be a good neighbor at every property we represent. It's all part of our strategy to make the world a better place on the corporate, community and personal level.
Every member of our team emphasizes green practices at each of our communities, helping property owners and residents alike to maximize an environmentally-friendly lifestyle.
We offer green assessments for any property owner interested in lowering their community's carbon footprint.
We install energy efficient appliances and low-flush toilets upon replacement.
We maximize water conservation methods throughout every building we manage through smart controllers, drip systems, and bubbler heads in landscape irrigation systems.
Working hand-in-hand with area agencies, The Natoma Company has initiated a conservation and prevention program to help our communities benefit from the financial incentive programs being offered by water, power and rubbish removal authorities.
Residents are regularly educated in ways to "green" their apartments and practice low-impact living in an effort to minimize their own carbon footprint.


* Same day appointments are also available throughout the day.
Weekend hours are available for routine and same day walk-in visits.
A provider is on call after business hours for medical emergencies.
Calls for appointments, billing, refills, return calls, and non-urgent matters, should be made during regular business hours.
Please call the main number and follow the instructions to leave a voicemail for the on-call provider.


text:
"The White Storm 2" is NYAFF's closing film
Writer: Heidi Hsia
Andy Lau and Louis Koo star in "The White Storm 2: Drug Lords".
8 Jul – It was reported that Hong Kong's "The White Storm 2: Drug Lords" has been selected as the closing film at this year's New York Asian Film Festival (NYAFF).
As reported on Singtao, the film's producer and lead actor Andy Lau recently expressed his elation over the news, saying that they will continue to work hard.
Meanwhile, co-star Louis Koo expressed, "It's such good news to come on the day of the film's release. I hope that the audiences around the world would love the movie."
Karena Lam also couldn't help but feel happy upon hearing the news, and congratulated director Herman Yau and producer Andy Lau for the job well done.
The upcoming film will be screened this 14 July at the SVA Theatre in New York, at the 18th New York Asian Film Festival which has been running since 28 June.
Cinema Online, 08 July 2019
The White Storm 2: Drug Lords (Mandarin) (11 Jul 2019)
The White Storm (Mandarin) (05 Dec 2013)
Andy Lau and Louis Koo team up for "White Storm 2" theme song
The two Hong Kong stars recorded "Brothers Don't Suspect", penned by Andy himself
Movies Not to Miss: July 2019
"Spider-Man: Far From Home", "The Lion King", "Ma" and the movies you shouldn't miss this July!
Top 10 Andy Lau action movies
We countdown Andy's top 10 films in conjunction with "Shock Wave"!
Louis Koo stars in fantasy wuxia film, "Kung Fu Monster"
The actor's upcoming movie is a creature feature meets martial arts action piece
Movies Not to Miss: May 2018
"Deadpool 2", "Solo: A Star Wars Story", "Isle of Dogs" and the movies you shouldn't miss this May!
Celebrities express support for Andy Lau
Joey Yung, Shu Qi, Cheryl Yang assure the actor-singer that everybody understands
Andy Lau, Takeshi Kaneshiro join AMPAS
They were among the many Asian stars who were invited to join the Academy of Motion Picture Arts and Sciences
Louis Koo recalls "Line Walker" filming in dangerous Brazil
Also of hearing gun shots and working with Charmaine Sheh again.
Andy Lau thinks being director is hard work
Instead of trying his hands on directing, the actor prefers being a producer

redpajama_set_name: RedPajamaCommonCrawl


text:
Blackmore Vale::
West Stour
Postcode for SatNav SP8 5RL
The little church has its origins in the 13c, and for more than 600 years, has been the responsibility of the Rector of Gillingham. However in 1840, like so many others in the county, the whole structure, including the tower, was rebuilt. Some elements were salvaged, which included an 18c window in the east wall and in the chancel two widely-splayed lancets in the north wall and another one-light 13c window with a 16c trefoil head, plus another 14c window.
There is a gallery, limited to 40 persons, across the west end of the nave. The pulpit and communion table are both 17c and there is a piscina. The font is 13c. The pine pews together with new floor tiles were installed in 1912.
Outside, the entrance gate was improved with brick pillars and an ornamental arch to commemorate the coronation of King Edward VII (1901). The exceptionally long handrail was installed in 1986 as a memorial.
The Trust gratefully acknowledges drone image by Richard Noble and text input from Robin Adeney ©