Tractable Profit Maximization over Multiple Attributes under Discrete Choice Models

abstractA fundamental problem in revenue management is to optimally choose the attributes of products, such that the total profit or revenue or market share is maximized. Usually, these attributes can affect both a product's market share (probability to be chosen) and its profit margin. For example, if a smart phone has a better battery, then it is more costly to be produced, but is more likely to be purchased by a customer. The decision maker then needs to choose an optimal vector of attributes for each product that balances this trade-off. In spite of the importance of such problems, there is not yet a method to solve it efficiently in general. Past literature in revenue management and discrete choice models focus on pricing problems, where price is the only attribute to be chosen for each product. Existing approaches to solve pricing problems tractably cannot be generalized to the optimization problem with multiple product attributes as decision variables. On the other hand, papers studying product line design with multiple attributes all result in intractable optimization problems. Then we found a way to reformulate the static multi-attribute optimization problem, as well as the multi-stage fluid optimization problem with both resource constraints and upper and lower bounds of attributes, as a tractable convex conic optimization problem. Our result applies to optimization problems under the multinomial logit (MNL) model, the Markov chain (MC) choice model, and with certain conditions, the nested logit (NL) model.

itemize• A ride-sharing service operator wants customers to walk to a pick-up location and to wait for some time before being picked up. With more waiting time and walking distance, the operator can make better matchings, and reduce the operational cost. However, customers are less likely to accept rides if waiting times and walking distances are long. • A health insurance company needs to design both the price and the coverage of a plan. A insurance plan that covers more health care providers is more attractive to customers, but is also more costly to the company. • An airline company sets (1) price, (2) cancelation fee, (3) baggage allowance, and (4) frequent flyer credits for each type of airline ticket (fare class). Lower fees and better services can attract more customers, but reduce the profit margin. • A hotel decides (1) price, (2) cancellation policy, (2) earliest check-in time, and (4) latest check-out time for its rooms. Stricter cancelation policy and check-in / check-out time hurt customer satisfaction (and thus total sales), but also reduce the operational cost. • An e-commerce platform chooses a combination of (1) price, (2) delivery time, and (3) return policy for each product. By offering better delivery time and return policy, the platform is able to charge a higher price without losing sales.

enumerate• Usually discrete choice models and profit margin models are calibrated with a limited range of attribute value data, and it would be unwise to allow selection of attribute values much outside this range. • As explained in Remark (ref) below, if multiple attributes are unbounded, then one attribute can be traded off for another attribute to obtain unbounded profit.

remarkBounds on attribute values are important when multiple attributes are chosen for a product. Suppose that $\phi_{k} > \phi_{k'}$ and that $k, k' \in \mathcal{K}_{j}$ for some $j \in \mathcal{J}$. If attribute $k$ is not bounded above and attribute $k'$ is not bounded below, then $x_{jk}$ can be increased and $x_{jk'}$ can be decreased by the same amount, while keeping all other attribute values constant. Thereby all demands remain constant, while the profit contribution of product $j$ grows without bound. In an application, it makes sense that attributes can be traded off to some extent, but arbitrarily large or small attribute values are not sensible.

lemma(ref) has an optimal solution if and only if for each $j \in \mathcal{J}$, and for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it holds that $\phi_{k_{1}} \le \phi_{k_{2}}$; otherwise, (ref) is unbounded.

lemmaEvery optimal solution for (ref) is also optimal for (ref).

theorem(ref) has an optimal solution if and only if for each $j \in \mathcal{J}$, and for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it holds that $\phi_{k_{1}} \le \phi_{k_{2}}$, in which case an optimal solution can be found by solving the convex conic program (ref). Otherwise, (ref) is unbounded.

lemmaIf (ref) is feasible, then (ref) has an optimal solution if and only if for each $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} \le \phi_{k_{2},t}$.

lemmaSuppose that (ref) has a feasible solution $(d', d_{0}', u')$ with $d' > 0$. Then, any optimal solution $(d^*, d_{0}^*, u^*)$ for (ref) satisfies $d^* > 0$, $d_{0}^* > 0$.

theorem(ref) can be solved by solving (ref) and taking into account the following possibilities: \begin{enumerate} • If (ref) is infeasible, then (ref) is infeasible. • If (ref) is feasible, then the following possibilities hold: \begin{enumerate} • If (ref) is unbounded (which happens if and only if for some $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} > \phi_{k_{2},t}$), then the following possibilities hold: \begin{enumerate} • If (ref) does not have a feasible solution $(d', d_{0}', u')$ with $d' > 0$, then (ref) is infeasible. • If (ref) has a feasible solution $(d', d_{0}', u')$ with $d' > 0$, then (ref) is unbounded. \end{enumerate} • If (ref) has an optimal solution $(d^*, d_{0}^*, u^*)$ (which happens if and only if for each $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} \le \phi_{k_{2},t}$), then the following possibilities hold: \begin{enumerate} • If $d^* > 0$, then $(d^*, x^*)$ with $x^*$ given by $x_{jkt}^* = u_{jkt}^* / d_{jt}^*$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$, is an optimal solution for (ref). • If $d_{jt}^* = 0$ for some $j \in \mathcal{J}$ and $t \in \{0,1,\ldots,T\}$, then (ref) is infeasible. \end{enumerate} \end{enumerate} \end{enumerate}

enumerate• $\theta_{t} \geq 0$ and $\sum_{j \in \mathcal{J}} \theta_{jt} > 0$ (otherwise the problem is trivial); • $\rho_{t} \geq 0$ and $I - \rho_{t}$ is nonsingular ($I$ is an identity matrix with proper dimensionality); • $\check{Q}_{jt}(y_{t}) \in [0,1]$ for all feasible $y_{t}$.

remarkdong2019pricing provided the following interpretation to the MC model: Each arriving customer first visits product $j$ with probability $\theta_{jt}$. A customer visiting product $j$ purchases the product with probability $\check{Q}_{jt}(y_{t})$, or transition from the product with probability $1 - \check{Q}_{jt}(y_{t})$. When a customer choose to transition from product $j$, she either transition to another product $i$ with probability $\rho_{jit}$, or transition to the no purchase option (and leaves the system) with probability $1 - \sum_{i \in \mathcal{J}} \rho_{jit}$. In this way, each arriving customer transitions between different products until purchasing one of the products, or deciding to leave without making a purchase. Thus, $\check{V}_{jt}(y)$ gives the expected number of times that a customer visits product $j$. However, as dong2019pricing stated, we should not view the MC model as a faithful model of the mental thought process of the customers when they purchase a product. The value of the MC model comes from the facts that (1) this model is compatible with the random utility maximization principle (see Theorem 1 in dong2019pricing), (2) its parameter values can be set so that the purchase probabilities under it become identical to the generalized attraction model, which subsumes the MNL model (see Lemma 2 in dong2019pricing), and (3) it yields tractable optimization problems (see blanchet2016markov, feldman2017revenue and dong2019pricing).

remarkdong2019pricing showed that parameter values of the MC model can be set so that the purchase probabilities under it become identical to the MNL model. The result is established assuming that price attribute is lower bounded for all products. We can extend this result to the case with multiple attributes, assuming that all attributes are lower bounded. See Section (ref).

subequations\begin{align} \max_{v, \, d, \, u} \quad & \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} u_{jkt} - \psi_{jt} d_{jt}\right) \tag{$\mathsf{FP_2^{MC}}$} \\ s.t. \quad & v_{jt} \ \ = \ \ \theta_{jt} + \sum_{i \in \mathcal{J}} \rho_{ij} (v_{it} - d_{it}) & \forall \ j \in \mathcal{J}, \ t = 0,1,\ldots,T \\ & \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} a_{rj} d_{jt} \ \ \le \ \ b_{r} & \forall \ r \in \mathcal{R} \\ & \left(v_{jt}, d_{jt}, \sum_{k \in \mathcal{K}_{jt}} u_{jkt}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ j \in \mathcal{J}, \ t = 0,1,\ldots,T \\ & \left(d_{jt}, v_{jt}, - \sum_{k \in \mathcal{K}_{jt}} \overline{x}_{jkt} v_{jt}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ j \in \overline{\mathcal{J}}_{t}, \ t = 0,1,\ldots,T \\ & u_{jkt} \ \ \geq \ \ x_{jkt} d_{jt} & \forall \ j \in \mathcal{J}, \ k \in \mathcal{K}_{jt}, \ t = 0,1,\ldots,T \\ & u_{jkt} \ \ \leq \ \ \overline{x}_{jkt} d_{jt} & \forall \ j \in \mathcal{J}, \ k \in \overline{\mathcal{K}}_{jt}, \ t = 0,1,\ldots,T \end{align}

theorem(ref) can be solved by solving (ref) and taking into account the following: \begin{enumerate} • If (ref) is infeasible, then (ref) is infeasible. • If (ref) is feasible, then: \begin{enumerate} • (ref) is bounded, and has an optimal solution. • (ref) is bounded, and has an optimal solution. • Let $(v^*, d^*, u^*)$ be an optimal solution of (ref). Let $x_{jkt}^* = u_{jkt}^* / d_{jt}^*$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$ such that $d_{jt}^* > 0$, and let $x_{jkt}^* = \underline{x}_{jkt}^*$ otherwise. Then $(v^*, d^*, x^*)$ is an optimal solution of (ref). \end{enumerate} \end{enumerate}

remarkRecall that, with the three assumptions hold, any feasible $y$ corresponds to a unique solution of the system (ref). Thus, if there is no resource constraint in (ref), then it must be feasible (assuming that the upper and lower bounds of attributes are proper, such that a feasible $y$ exists). Therefore, while (ref) is a special case of (ref), the problem (ref) under the MC model is always feasible, and has an optimal solution.

displayquoteThe value of $\gamma_i$ must be within a particular range for the model to be consistent with utility-maximizing behavior. If $\gamma_i$ is between zero and one for all $i \in \mathcal{I}$, the model is consistent with utility maximization for all possible values of the explanatory variables. For $\gamma_i$ greater than one, the model is consistent with utility-maximizing behavior for some range of the explanatory variables but not for all values. kling1995empirical and herriges1996testing provide tests of consistency of nested logit with utility maximization when $\gamma_i > 1$; and train1987demand and lee1999calling provide examples of models for which $\gamma_i > 1$. A negative value of $\gamma_i$ is inconsistent with utility maximization and implies that improving the attributes of an alternative (such as lowering its price) can decrease the probability of the alternative being chosen. With positive $\gamma_i$, the nested logit approaches the “elimination by aspects” model of tversky1972elimination as $\gamma_i \to 0$.

theoremIf the following conditions hold: Condition (i): for any feasible solution $(d, p, p_{0}, v_{\leq}, u_{>})$ to (ref) at which \begin{align*} & \left(\frac{1}{\gamma_{it}} - 1\right) p_{it} \ln\left(\frac{p_{0t}}{p_{it}}\right) + \sum_{j \in \mathcal{J}_i} d_{jt} \ln\left(\frac{p_{0t}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{it}'} v_{ikt} & \forall \ i \in \mathcal{I}_{\leq}, \ t = 0,1,\ldots,T \end{align*} the system \begin{align*} & \left(\frac{1}{\gamma_{it}} - 1\right) d_{jt} \ln\left(\frac{p_{0t}}{p_{it}}\right) + d_{jt} \ln\left(\frac{p_{0t}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt} & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \mathcal{J}_{i}, \ t = 0,1,\ldots,T \\ & v_{ikt} \ \ = \ \ \sum_{j \in \mathcal{J}_{ikt}'} u_{jkt} & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \mathcal{K}_{it}', \ t = 0,1,\ldots,T \\ & u_{jkt} \ \ \geq \ \ x_{jkt} d_{jt} & \forall \ j \in \mathcal{J}_{\leq}, \ k \in \mathcal{K}_{jt}, \ t = 0,1,\ldots,T \nonumber \\ & u_{jkt} \ \ \leq \ \ \overline{x}_{jkt} d_{jt} & \forall \ j \in \mathcal{J}_{\leq}, \ k \in \overline{\mathcal{K}}_{jt}, \ t = 0,1,\ldots,T \nonumber \end{align*} has a solution $u_{\leq}$. Here $\mathcal{J}_{ikt}' := \{j \in \mathcal{J}_{i} \ : \ k \in \mathcal{K}_{jt} \}$. Condition (ii): $\overline{\mathcal{K}}_{jt} \subsetneq \mathcal{K}_{jt}$ for every $j \in \mathcal{J}_{>}$, i.e. $\sum_{k \in \mathcal{K}_{jt}} u_{jkt}$ is not upper bounded for any $j \in \mathcal{J}_{>}$. then (ref) can be solved by solving (ref) and taking into account the following possibilities: \begin{enumerate} • If (ref) is infeasible, then (ref) is infeasible. • If (ref) is feasible and unbounded, then (ref) is feasible and unbounded. • If (ref) is feasible and has an optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$, then $(d^*, p^*, x^*)$ with $x^*$ given by $x_{jkt}^* = u_{jkt}^* / d_{jt}^*$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$, is an optimal solution for (ref). (Here $u_{>}^*$ is part of the optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$ to (ref), while $u_{\leq}^*$ is obtained by solving the system in Condition (i), using $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$ as an input.) \end{enumerate}

remarkA simple sufficient condition for Condition (i) to hold in Theorem (ref), is that for any $i \in \mathcal{I}_{\leq}$, there is one unbounded attribute $k$ that is shared by all products in $\mathcal{J}_{i}$ (for example, the price attribute). That is, for any $i \in \mathcal{I}_{\leq}$, $j \in \mathcal{J}_{i}$ and $t = 0,1,\ldots,T$, we need $k \in \mathcal{K}_{jt}$ (which implies $\mathcal{J}_{i} = \mathcal{J}_{ikt}'$), $k \notin \overline{\mathcal{K}}_{jt}$, and $k \notin \underline{\mathcal{K}}_{jt}$. Then we can split all other attribute $k' \in \mathcal{J}_{i}$ for each $i \in \mathcal{I}_{\leq}$, $j \in \mathcal{J}_{i}$ and $t = 0,1,\ldots,T$, such that each of those attributes only apply to one product (i.e. $\mathcal{J}_{ik't}'$ are all singletons). Now, given any feasible solution $(d, p, p_{0}, v_{\leq}, u_{>})$ to (ref) at which \begin{align*} & \left(\frac{1}{\gamma_{it}} - 1\right) p_{it} \ln\left(\frac{p_{0t}}{p_{it}}\right) + \sum_{j \in \mathcal{J}_i} d_{jt} \ln\left(\frac{p_{0t}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{it}'} v_{ikt} & \forall \ i \in \mathcal{I}_{\leq}, \ t = 0,1,\ldots,T \end{align*} we can find a feasible solution to the system in Condition (i) as follow: Consider any $i \in \mathcal{I}_{\leq}$ and $j \in \mathcal{J}_{i}$. Let \begin{align*} & u_{jk't} \ \ = \ \ v_{ik't} & \forall \ t = 0,1,\ldots,T \end{align*} for any $k' \neq k$, and let \begin{align*} & u_{jkt} \ \ = \ \ \left(\frac{1}{\gamma_{it}} - 1\right) d_{jt} \ln\left(\frac{p_{0t}}{p_{it}}\right) + d_{jt} \ln\left(\frac{p_{0t}}{d_{jt}}\right) - \sum_{k' \in \mathcal{K}_{jt} \setminus \{k\}} u_{jk't} & \forall \ t = 0,1,\ldots,T \end{align*} Note that we automatically have \begin{align*} & v_{ikt} \ \ = \ \ \sum_{j \in \mathcal{J}_{i}} u_{jkt} & \forall \ t = 0,1,\ldots,T \end{align*} which implies that the $u_{\leq}$ constructed is a feasible solution to the system in Condition (i).

subequations\begin{align} \max_{\substack{d, \ p, \ p_{0}, \ v_{\leq}, \ u_{>} \\ e, \ f_{\leq}, \ g_{>}, \ r_{\leq}, \ s_{>}}} \quad & \sum_{t = 0}^{T} \lambda_{t} \sum_{i \in \mathcal{I}_{\leq}} \sum_{k \in \mathcal{K}_{it}'} \phi_{kt} v_{ikt} \nonumber \\ & + \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}_{>}} \sum_{k \in \mathcal{K}_{jt}} \phi_{kt} u_{jkt} \nonumber \\ & - \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \psi_{jt} d_{jt} \tag{$\mathsf{FP_3^{NL}}$} \\ & \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} a_{rj} d_{jt} \ \ \le \ \ b_{r} & \forall \ r \in \mathcal{R} \\ s.t. \quad & \left(\frac{1}{\gamma_{it}} - 1\right) r_{it} + \sum_{j \in \mathcal{J}_i} e_{jt} \ \ = \ \ \sum_{k \in \mathcal{K}_{it}'} v_{ikt} & \forall \ i \in \mathcal{I}_{\leq}, \ t = 0,1,\ldots,T \\ & \left(\frac{1}{\gamma_{it}} - 1\right) s_{it} + f_{jt} \ \ = \ \ - p_{0t} \sum_{k \in \mathcal{K}_{jt}} \overline{x}_{jkt}^{[i]} & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i}, \ t = 0,1,\ldots,T \\ & \left(1 - \frac{1}{\gamma_{it}}\right) g_{jt} + \left(\frac{1}{\gamma_{it}}\right) e_{jt} \ \ = \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt} & \forall \ i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i}, \ t = 0,1,\ldots,T \\ & \left(p_{0t}, d_{jt}, e_{jt}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}, \ j \in \mathcal{J}_{i}, \ t = 0,1,\ldots,T \\ & \left(d_{jt}, p_{0t}, f_{jt}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i}, \ t = 0,1,\ldots,T \\ & \left(p_{it}, d_{jt}, g_{jt}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i}, \ t = 0,1,\ldots,T \\ & \left(p_{it}, p_{0t}, s_{it}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}_{\leq}, \ t = 0,1,\ldots,T \\ & \left(p_{0t}, p_{it}, r_{it}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}_{\leq}, \ t = 0,1,\ldots,T \\ & p_{0t} + \sum_{i \in \mathcal{I}} p_{it} \ \ = \ \ 1 & \forall \ t = 0,1,\ldots,T \\ & p_{it} \ \ = \ \ \sum_{j \in \mathcal{J}_{i}} d_{jt} & \forall \ i \in \mathcal{I}, \ t = 0,1,\ldots,T \\ & v_{ikt} \ \ \geq \ \ \sum_{j \in \mathcal{J}_{i}} x_{jkt} d_{jt} & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \mathcal{K}_{it}', \ t = 0,1,\ldots,T \\ & v_{ikt} \ \ \leq \ \ \sum_{j \in \mathcal{J}_{i}} \overline{x}_{jkt} d_{jt} & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \overline{\mathcal{K}}_{it}', \ t = 0,1,\ldots,T \\ & u_{jkt} \ \ \geq \ \ x_{jkt} d_{jt} & \forall \ j \in \mathcal{J}_{>}, \ k \in \mathcal{K}_{jt}, \ t = 0,1,\ldots,T \\ & u_{jkt} \ \ \leq \ \ \overline{x}_{jkt} d_{jt} & \forall \ j \in \mathcal{J}_{>}, \ k \in \overline{\mathcal{K}}_{jt}, \ t = 0,1,\ldots,T \end{align}

theoremAssume that Condition (i) in Theorem (ref) holds. Then, (ref) can be solved by solving (ref) and taking into account the following: \begin{enumerate} • If (ref) is infeasible, then (ref) is infeasible. • If (ref) is feasible, then the following possibilities hold: \begin{enumerate} • If (ref) is unbounded (which happens if and only if for some $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} > \phi_{k_{2},t}$), then the following possibilities hold: \begin{enumerate} • If (ref) does not have a feasible solution $(d', p', p_{0}', v_{\leq}', u_{>}', e', f_{\leq}', g_{>}', r_{\leq}', s_{>}')$ with $d' > 0$, then (ref) is infeasible. • If (ref) has a feasible solution $(d', p', p_{0}', v_{\leq}', u_{>}', e', f_{\leq}', g_{>}', r_{\leq}', s_{>}')$ with $d' > 0$, then (ref) is unbounded. \end{enumerate} • If (ref) has an optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*, e^*, f_{\leq}^*, g_{>}^*, r_{\leq}^*, s_{>}^*)$ (which happens if and only if for each $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} \le \phi_{k_{2},t}$), then the following possibilities hold: \begin{enumerate} • If $d^* > 0$, then $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$ is an optimal solution for (ref). • If $d_{jt}^* = 0$ for some $j \in \mathcal{J}$ and $t \in \{0,1,\ldots,T\}$, then (ref) is infeasible. \end{enumerate} \end{enumerate} \end{enumerate}

exampleIn this example (ref) is infeasible, while (ref) has an optimal solution. Consider the following single-period instance of (ref) with two products indexed $\{1,2\}$. Each product $i$ has one attribute also indexed $i$. The time index is omitted. \begin{align} \max_{d, \, x} \quad & \big\{x_{1,1} d_{1} + x_{2,2} d_{2}\big\} \tag{$\mathsf{FP^{Example}_{1}}$} \\ s.t. \quad & d_{1} + d_{2} \ \ \leq \ \ \frac{1}{2} \nonumber \\ & d_{1} \ \ = \ \ \frac{\exp(- x_{1,1})}{1 + \exp(- x_{1,1}) + \exp(- x_{2,2})} \nonumber \\ & d_{2} \ \ = \ \ \frac{\exp(- x_{2,2})}{1 + \exp(- x_{1,1}) + \exp(- x_{2,2})} \nonumber \\ & x_{1,1} \ \ \leq \ \ 0 \nonumber \end{align} For any $x$ feasible for (ref), it holds that \begin{align*} d_{1} + d_{2} \ \ & = \ \ \frac{\exp(- x_{1,1}) + \exp(- x_{2,2})}{1 + \exp(- x_{1,1}) + \exp(- x_{2,2})} \\ & > \ \ \frac{\exp(- x_{1,1})}{1 + \exp(- x_{1,1})} \ \ \geq \ \ \frac{\exp(0)}{1 + \exp(0)} \ \ = \ \ \frac{1}{2} \end{align*} Thus, (ref) is infeasible. The corresponding instance of (ref) is \begin{align} \max_{d, \, d_{0}, \, u} \quad & \big\{u_{1,1} + u_{2,2}\big\} \tag{$\mathsf{FP^{Example}_{2}}$} \\ s.t. \quad & d_{1} + d_{2} \ \ \leq \ \ \frac{1}{2} \nonumber \\ & \left(d_{0}, d_{1}, u_{1,1}\right) \ \ \in \ \ \mathcal{K}_{\exp} \nonumber \\ & \left(d_{0}, d_{2}, u_{2,2}\right) \ \ \in \ \ \mathcal{K}_{\exp} \nonumber \\ & \left(d_{1}, d_{0}, 0\right) \ \ \in \ \ \mathcal{K}_{\exp} \nonumber \\ & d_{0} + d_{1} + d_{2} \ \ = \ \ 1 \nonumber \\ & u_{1,1} \ \ \leq \ \ 0 \nonumber \end{align} The only feasible solution of (ref) is $d_{0} = 1/2$, $d_{1} = 1/2$, $d_{2} = 0$, $u_{1,1} = 0$, $u_{2,2} = 0$. Thus, (ref) has an optimal solution.

exampleIn this example (ref) is infeasible, while (ref) is unbounded. Consider the following single-period instance of (ref) with two products indexed $\{1,2\}$. Product $1$ has one attribute indexed $1$, and product $2$ has two attributes indexed $1,2$. The time index is omitted. \begin{align} \max_{d, \, x} \quad & x_{1,1} d_{1} + \left(x_{2,1} + 2 x_{2,2}\right) d_{2} \tag{$\mathsf{FP^{Example}_{3}}$} \\ s.t. \quad & d_{1} + d_{2} \ \ \leq \ \ \frac{1}{2} \nonumber \\ & d_{1} \ \ = \ \ \frac{\exp(- x_{1,1})}{1 + \exp(- x_{1,1}) + \exp(- x_{2,1} - x_{2,2})} \nonumber \\ & d_{2} \ \ = \ \ \frac{\exp(- x_{2,1} - x_{2,2})}{1 + \exp(- x_{1,1}) + \exp(- x_{2,1} - x_{2,2})} \nonumber \\ & x_{1,1} \ \ \leq \ \ 0 \nonumber \end{align} For any $x$ feasible for (ref), it holds that \begin{align*} d_{1} + d_{2} \ \ & = \ \ \frac{\exp(- x_{1,1}) + \exp(- x_{2,1} - x_{2,2})}{1 + \exp(- x_{1,1}) + \exp(- x_{2,1} - x_{2,2})} \\ & > \ \ \frac{\exp(- x_{1,1})}{1 + \exp(- x_{1,1})} \ \ \geq \ \ \frac{\exp(0)}{1 + \exp(0)} \ \ = \ \ \frac{1}{2} \end{align*} Thus, (ref) is infeasible. The corresponding instance of (ref) is \begin{align} \max_{d, \, d_{0}, \, u} \quad & \big\{u_{1,1} + u_{2,1} + 2 u_{2,2}\big\} \tag{$\mathsf{FP^{Example}_{4}}$} \\ s.t. \quad & d_{1} + d_{2} \ \ \leq \ \ \frac{1}{2} \nonumber \\ & \left(d_{0}, d_{1}, u_{1,1}\right) \ \ \in \ \ \mathcal{K}_{\exp} \nonumber \\ & \left(d_{0}, d_{2}, u_{2,1} + u_{2,2}\right) \ \ \in \ \ \mathcal{K}_{\exp} \nonumber \\ & \left(d_{1}, d_{0}, 0\right) \ \ \in \ \ \mathcal{K}_{\exp} \nonumber \\ & d_{0} + d_{1} + d_{2} \ \ = \ \ 1 \nonumber \\ & u_{1,1} \ \ \leq \ \ 0 \nonumber \end{align} Consider the sequence of solutions $\{(d_{1}^{n}, \, d_{2}^{n}, \, d_{0}^{n}, \, u_{1,1}^{n}, \, u_{2,1}^{n}, \, u_{2,2}^{n}) = (1 / 2, 0, 1 / 2, 0, -n, n)\}_{n=1}^{\infty}$. The solutions are feasible for (ref) for all $n$, and the objective value of $(d_{1}^{n}, \, d_{2}^{n}, \, d_{0}^{n}, \, u_{1,1}^{n}, \, u_{2,1}^{n}, \, u_{2,2}^{n})$ is $n$. Thus, (ref) is unbounded.

appendix\section{Proofs} \subsection{Proof of Lemma (ref)} {\color{purple} \begin{manuallemma}{(ref)} (ref) has an optimal solution if and only if for each $j \in \mathcal{J}$, and for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it holds that $\phi_{k_{1}} \le \phi_{k_{2}}$; otherwise, (ref) is unbounded. \end{manuallemma} } \begin{proof} First, note that (ref) is feasible. For example, consider $(d^{0}, d^{0}_{0}, u^{0})$ given as follows: For all $j \in \mathcal{J}$ and $k \in \overline{\mathcal{K}}_{j}$, let $x^{0}_{jk} = \overline{x}_{jk}$. For all $j \in \mathcal{J}$ and $k \in \underline{\mathcal{K}}_{j} \setminus \overline{\mathcal{K}}_{j}$, let $x^{0}_{jk} = \underline{x}_{jk}$. For all $j \in \mathcal{J}$ and $k \in \mathcal{K}_{j} \setminus \left(\underline{\mathcal{K}}_{j} \cup \overline{\mathcal{K}}_{j}\right)$, let $x^{0}_{jk} = 0$. Next, let $d^{0}_{0}$ be given by (ref), let $d^{0}_{j}$ be given by (ref) for all $j \in \mathcal{J}$, and let $u^{0}_{jk} = d^{0}_{j} x^{0}_{jk}$ for all $j \in \mathcal{J}$ and $k \in \mathcal{K}_{j}$. Then $(d^{0}, d^{0}_{0}, u^{0})$ is feasible for (ref). Suppose that there is a $j \in \mathcal{J}$, a $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, and a $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, such that $\phi_{k_{1}} > \phi_{k_{2}}$. Then consider a sequence $\{(d^{n}, d^{n}_{0}, u^{n})\}_{n=0}^{\infty}$ of feasible solutions with $u^{n}_{jk_{1}} = u^{0}_{jk_{1}} + n$, $u^{n}_{jk_{2}} = u^{0}_{jk_{2}} - n$, $u^{n}_{jk} = u^{0}_{jk}$ for all $k \notin \{k_{1}, k_{2}\}$, $u^{n}_{j'k} = u^{0}_{j'k}$ for all $j' \neq j$ and $k \in \mathcal{K}_{j'}$, $d^{n}_{j'} = d^{0}_{j'}$ for all $j' \in \mathcal{J}$, and $d^{n}_{0} = d^{0}_{0}$. Then $(d^{n}, d^{n}_{0}, u^{n})$ is feasible for (ref) for all $n$, and the objective value of $(d^{n+1}, d^{n+1}_{0}, u^{n+1})$ exceeds the objective value of $(d^{n}, d^{n}_{0}, u^{n})$ by $\phi_{k_{1}} - \phi_{k_{2}}$ for all $n$, and thus the objective value of $(d^{n}, d^{n}_{0}, u^{n})$ increases without bound as $n \to \infty$. Next suppose that for each $j \in \mathcal{J}$, and for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it holds that $\phi_{k_{1}} \le \phi_{k_{2}}$. Let \begin{align*} \mathcal{K}_{\exp}^* \ \ & := \ \ closure\big\{(y_{1}, y_{2}, y_{3}) \; : \; y_{1} \ge -y_{3} \exp(y_{2}/y_{3} - 1), \; y_{1} > 0, \; y_{3} < 0\big\} \& = \ \ \big\{(y_{1}, y_{2}, y_{3}) \; : \; y_{1} \ge -y_{3} \exp(y_{2}/y_{3} - 1), \; y_{1} > 0, \; y_{3} < 0\big\} \cup \big\{(y_{1}, y_{2}, 0) \; : \; y_{1} \ge 0, \; y_{2} \ge 0\big\} \end{align*} denote the dual cone of $\mathcal{K}_{\exp}$. Let $\pi_{j} \in \mathcal{K}_{\exp}^*$ denote the dual variables corresponding to (ref), let $\varpi_{j} \in \mathcal{K}_{\exp}^*$ denote the dual variables corresponding to (ref), let $\underline{\nu}_{jk} \ge 0$ denote the dual variables corresponding to (ref), let $\overline{\nu}_{jk} \ge 0$ denote the dual variables corresponding to (ref), and let $\gamma$ denote the dual variable corresponding to (ref). Then the dual of (ref) is { \begin{subequations} \begin{align} \min_{\pi, \, \varpi, \, \nu, \, \overline{\nu}, \, \gamma} \quad & \gamma \tag{$\mathsf{SD^{MNL}_{5}}$} \\ s.t. \quad & \pi_{j3} \ \ = \ \ -\phi_{k} & \forall \ j \in \mathcal{J}, \ k \in \mathcal{K}_{j} \setminus \left(\mathcal{K}_{j} \cup \overline{\mathcal{K}}_{j}\right) \\ & \pi_{j3} + \nu_{jk} \ \ = \ \ -\phi_{k} & \forall \ j \in \mathcal{J}, \ k \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j} \\ & \pi_{j3} - \overline{\nu}_{jk} \ \ = \ \ -\phi_{k} & \forall \ j \in \mathcal{J}, \ k \in \overline{\mathcal{K}}_{j} \setminus \underline{\mathcal{K}}_{j} \\ & \pi_{j3} + \underline{\nu}_{jk} - \overline{\nu}_{jk} \ \ = \ \ -\phi_{k} & \forall \ j \in \mathcal{J}, \ k \in \underline{\mathcal{K}}_{j} \cap \overline{\mathcal{K}}_{j} \\ & \pi_{j2} + \varpi_{j1} - \sum_{k \in \underline{\mathcal{K}}_{j}} \underline{\nu}_{jk} \underline{x}_{jk} + \sum_{k \in \overline{\mathcal{K}}_{j}} \overline{\nu}_{jk} \overline{x}_{jk} - \gamma \ \ = \ \ \psi_{j} & \forall \ j \in \overline{\mathcal{J}} \\ & \pi_{j2} - \sum_{k \in \underline{\mathcal{K}}_{j}} \underline{\nu}_{jk} \underline{x}_{jk} + \sum_{k \in \overline{\mathcal{K}}_{j}} \overline{\nu}_{jk} \overline{x}_{jk} - \gamma \ \ = \ \ \psi_{j} & \forall \ j \in \mathcal{J} \setminus \overline{\mathcal{J}} \\ & \sum_{j \in \mathcal{J}} \pi_{j1} + \sum_{j \in \overline{\mathcal{J}}} \varpi_{j2} - \sum_{j \in \overline{\mathcal{J}}} \varpi_{j3} \sum_{k \in \mathcal{K}_{j}} \overline{x}_{jk} - \gamma \ \ = \ \ 0 \\ & \pi_{j} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ j \in \mathcal{J} \\ & \varpi_{j} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ j \in \overline{\mathcal{J}} \\ & \underline{\nu}_{jk} \ \ \ge \ \ 0 & \forall \ j \in \mathcal{J}, \ k \in \underline{\mathcal{K}}_{j} \\ & \overline{\nu}_{jk} \ \ \ge \ \ 0 & \forall \ j \in \mathcal{J}, \ k \in \overline{\mathcal{K}}_{j} \end{align} \end{subequations} } Next we show that there is a feasible solution $(\pi, \varpi, \underline{\nu}, \overline{\nu}, \gamma)$ of (ref) such that $\pi_{j} \in \mbox{int}\left(\mathcal{K}_{\exp}^*\right)$ for all $j \in \mathcal{J}$ and $\varpi_{j} \in \mbox{int}\left(\mathcal{K}_{\exp}^*\right)$ for all $j \in \overline{\mathcal{J}}$. Choose $\varpi_{j2} = 0$, $\varpi_{j3} = -1$, and $\varpi_{j1} = \exp(-1) + 1$ for all $j \in \overline{\mathcal{J}}$. Thus $\varpi_{j} \in \mbox{int}\left(\mathcal{K}_{\exp}^*\right)$ for all $j \in \overline{\mathcal{J}}$. For each $j \in \mathcal{J}$, choose $\pi_{j3}$, $\underline{\nu}_{jk}$ for all $k \in \underline{\mathcal{K}}_{j}$, and $\overline{\nu}_{jk}$ for all $k \in \overline{\mathcal{K}}_{j}$, by considering the following cases: \begin{enumerate} • If $\mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j} \neq \varnothing$, then choose $\pi_{j3} = - \min\left\{\phi_{k} \, : \, k \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}\right\}$. Since $\phi_{k} > 0$ for all $k$, it follows that $\pi_{j3} < 0$. Then, for each $k \in \mathcal{K}_{j}$, consider the following four cases. \begin{enumerate} • Suppose $k \in \mathcal{K}_{j} \setminus \left(\underline{\mathcal{K}}_{j} \cup \overline{\mathcal{K}}_{j}\right)$. Since $k \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it follows that $- \pi_{j3} \le \phi_{k}$. Since $k \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$ and $\phi_{k_{1}} \le \phi_{k_{2}}$ for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it follows that $\phi_{k} \le - \pi_{j3}$. Thus, $\phi_{k} = - \pi_{j3}$, and hence constraint (ref) is satisfied. • Suppose $k \in \underline{\mathcal{K}}_{j} \setminus \overline{\mathcal{K}}_{j}$. Then choose $\underline{\nu}_{jk} = - \pi_{j3} - \phi_{k}$. Hence constraint (ref) is satisfied. Since $k \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$ and $\phi_{k_{1}} \le \phi_{k_{2}}$ for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it follows that $\phi_{k} \le - \pi_{j3}$. Thus $\underline{\nu}_{jk} = - \pi_{j3} - \phi_{k} \ge 0$, and hence constraint (ref) is satisfied. • Suppose $k \in \overline{\mathcal{K}}_{j} \setminus \underline{\mathcal{K}}_{j}$. Then choose $\overline{\nu}_{jk} = \pi_{j3} + \phi_{k}$. Hence constraint (ref) is satisfied. Since $k \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it follows that $- \pi_{j3} \le \phi_{k}$. Thus $\overline{\nu}_{jk} = \pi_{j3} + \phi_{k} \ge 0$, and hence constraint (ref) is satisfied. • Suppose $k \in \underline{\mathcal{K}}_{j} \cap \overline{\mathcal{K}}_{j}$. Then choose $\underline{\nu}_{jk} = \max\left\{0, \, - \pi_{j3} - \phi_{k}\right\}$ and $\overline{\nu}_{jk} = \max\left\{0, \, \pi_{j3} + \phi_{k}\right\}$. Hence constraints (ref), (ref) and (ref) are satisfied. \end{enumerate} • If $\mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j} = \varnothing$ (that is, $\mathcal{K}_{j} = \underline{\mathcal{K}}_{j}$), then choose $\pi_{j3} = - \max\left\{\phi_{k} \, : \, k \in \mathcal{K}_{j}\right\}$. Since $\phi_{k} > 0$ for all $k$, it follows that $\pi_{j3} < 0$. Then, for each $k \in \mathcal{K}_{j}$, consider the following two cases (only these two cases are possible). \begin{enumerate} • Suppose $k \in \underline{\mathcal{K}}_{j} \setminus \overline{\mathcal{K}}_{j}$. Then choose $\underline{\nu}_{jk} = - \pi_{j3} - \phi_{k}$. Hence constraint (ref) is satisfied. Since $\phi_{k} \le - \pi_{j3}$, it follows that $\underline{\nu}_{jk} = - \pi_{j3} - \phi_{k} \ge 0$, and hence constraint (ref) is satisfied. • Suppose $k \in \underline{\mathcal{K}}_{j} \cap \overline{\mathcal{K}}_{j}$. Then choose $\underline{\nu}_{jk} = \max\left\{0, \, - \pi_{j3} - \phi_{k}\right\}$ and $\overline{\nu}_{jk} = \max\left\{0, \, \pi_{j3} + \phi_{k}\right\}$. Hence constraints (ref), (ref) and (ref) are satisfied. \end{enumerate} \end{enumerate} Thus $\pi_{j3}$, $\underline{\nu}_{jk}$, and $\overline{\nu}_{jk}$ have been chosen for all $j$ and $k$. Next we use (ref) and (ref) to express $\pi_{j2}$ as a function of $\gamma$ for each $j \in \mathcal{J}$. Then we choose $\pi_{j1}$ as a function of $\gamma$ such that $\pi_{j1} = - \pi_{j3} \exp(\pi_{j2} / \pi_{j3} - 1) + 1$. Then it will follow that $\pi_{j} \in \mbox{int}\left(\mathcal{K}_{\exp}^*\right)$ for all $j$. Finally we will show that there exists a $\gamma$ such that (ref) is satisfied, and thus all the constraints of (ref) will be satisfied. If $j \in \overline{\mathcal{J}}$, then let $e_{j} = - \varpi_{j1} + \sum_{k \in \underline{\mathcal{K}}_{j}} \underline{\nu}_{jk} \underline{x}_{jk} - \sum_{k \in \overline{\mathcal{K}}_{j}} \overline{\nu}_{jk} \overline{x}_{jk} + \psi_{j}$, and if $j \in \mathcal{J} \setminus \overline{\mathcal{J}}$, then let $e_{j} = \sum_{k \in \underline{\mathcal{K}}_{j}} \underline{\nu}_{jk} \underline{x}_{jk} - \sum_{k \in \overline{\mathcal{K}}_{j}} \overline{\nu}_{jk} \overline{x}_{jk} + \psi_{j}$. For all $j \in \mathcal{J}$, let $\pi_{j2} = \pi_{j2}(\gamma) = \gamma + e_{j}$, and let $\pi_{j1} = \pi_{j1}(\gamma) = - \pi_{j3} \exp\left(\pi_{j2}(\gamma) / \pi_{j3} - 1\right) + 1 = - \pi_{j3} \exp\left(\left[\gamma + e_{j}\right] / \pi_{j3} - 1\right) + 1$. It follows that for any $\gamma$, (ref) is satisfied for all $j \in \overline{\mathcal{J}}$ and (ref) is satisfied for all $j \in \mathcal{J} \setminus \overline{\mathcal{J}}$. It also follows that for any $\gamma$, $\pi_{j} \in \mbox{int}\left(\mathcal{K}_{\exp}^*\right)$ for all $j$. For constraint (ref) to be satisfied, $\gamma$ has to satisfy $\sum_{j \in \mathcal{J}} \pi_{j1}(\gamma) + \sum_{j \in \overline{\mathcal{J}}} \varpi_{j2} - \sum_{j \in \overline{\mathcal{J}}} \varpi_{j3} \sum_{k \in \mathcal{K}_{j}} \overline{x}_{jk} - \gamma = 0$, that is, \[ h(\gamma) \ \ := \ \ \sum_{j \in \mathcal{J}} \left\{- \pi_{j3} \exp\left(\frac{\gamma + e_{j}}{\pi_{j3}} - 1\right) + 1\right\} + \sum_{j \in \overline{\mathcal{J}}} \varpi_{j2} - \sum_{j \in \overline{\mathcal{J}}} \varpi_{j3} \sum_{k \in \mathcal{K}_{j}} \overline{x}_{jk} - \gamma \ \ = \ \ 0 \] Since $\pi_{j3} < 0$ for all $j$, it follows that $h$ is decreasing, $h(\gamma) \to \infty$ as $\gamma \to -\infty$, and $h(\gamma) \to -\infty$ as $\gamma \to \infty$. Thus it follows from the intermediate value theorem that there is a (unique) $\gamma^*$ such that $h(\gamma^*) = 0$, and hence $(\gamma^*, \, \pi_{j1}(\gamma^*), j \in \mathcal{J})$ satisfies (ref). The resulting solution $(\pi(\gamma^*), \varpi, \underline{\nu}, \overline{\nu}, \gamma^*)$ is feasible for (ref) and satisfies $\pi_{j}(\gamma^*) \in \mbox{int}\left(\mathcal{K}_{\exp}^*\right)$ for all $j \in \mathcal{J}$ and $\varpi_{j} \in \mbox{int}\left(\mathcal{K}_{\exp}^*\right)$ for all $j \in \overline{\mathcal{J}}$. Therefore it follows from the conic duality theorem (Theorem 1.4.2 in ben2001lectures) that (ref) has an optimal solution. \end{proof} \subsection{Proof of Lemma (ref)} {\color{purple} \begin{manuallemma}{(ref)} Every optimal solution for (ref) is also optimal for (ref). \end{manuallemma} } \begin{proof} Consider any $(d, d_{0}, u)$ feasible for (ref). Then $(d, d_{0}, u)$ is also feasible for (ref) and has the same objective value. Next, consider any $(d, d_{0}, u)$ feasible for (ref). Note that if $d > 0$ and $d_{0} > 0$, then $(d, d_{0}, u)$ is feasible for (ref) and has the same objective value. We show by contradiction that $d_{0} > 0$, and that $d_{j} > 0$ for any $j \in \overline{\mathcal{J}}$. Suppose that $d_{0} = 0$. Then it follows from constraint (ref) that $d_{j} = 0$ for all $j$, which would violate constraint (ref). Similarly, suppose that $d_{j} = 0$ for some $j \in \overline{\mathcal{J}}$, then it follows from constraint (ref) that $d_{0} = 0$, which as shown above cannot be feasible for (ref). However, $d_{j} = 0$ for $j \in \mathcal{J} \setminus \overline{\mathcal{J}}$ can be feasible for (ref). Next we show that if $(d^*, d_{0}^*, u^*)$ is an optimal solution for (ref), then it is also optimal for (ref). It remains to show that $d_{j}^* > 0$ for every $j \in \mathcal{J} \setminus \overline{\mathcal{J}}$. Suppose that $d_{i}^* = 0$ for some $i \in \mathcal{J} \setminus \overline{\mathcal{J}}$. Let $\underline{\mathcal{K}}_{i}^{+} := \{k \in \underline{\mathcal{K}}_{i} \, : \, \underline{x}_{ik} > 0\}$ and $\overline{\mathcal{K}}_{i}^{-} := \{k \in \overline{\mathcal{K}}_{i} \, : \, \overline{x}_{ik} < 0\}$. Consider any $\delta \in \big(0, \; \min\big\{1, \; \min\{u_{ik}^* / \underline{x}_{ik} \, : \, k \in \underline{\mathcal{K}}_{i}^{+}, u_{ik}^* > 0\}, \; \min\{u_{ik}^* / \overline{x}_{ik} \, : \, k \in \overline{\mathcal{K}}_{i}^{-}, u_{ik}^* < 0\}\big\}\big)$. Consider the solution $(d', d_{0}', u')$ for (ref) given by { \begin{align*} d'_{i} \ \ & = \ \ \delta \\ d_{0}' \ \ & = \ \ d_{0}^* \left(1 - \delta\right) \\ d'_{j} \ \ & = \ \ d_{j}^* \left(1 - \delta\right) \mbox{for all } j \in \mathcal{J} \setminus \{i\} \\ u'_{il} \ \ & = \ \ u_{il}^* \; - \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \underline{x}_{ik} \delta \; - \sum_{\left\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\right\}} \overline{x}_{ik} \delta \; - \; \delta \ln\left(\frac{\delta}{d_{0}^* \left(1 - \delta\right)}\right) \mbox{for some } l \in \mathcal{K}_{i} \setminus \overline{\mathcal{K}}_{i} \\ u'_{ik} \ \ & = \ \ u_{ik}^* + \underline{x}_{ik} \delta \ \ = \ \ \underline{x}_{ik} \delta \mbox{for all } k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0 \\ u'_{ik} \ \ & = \ \ u_{ik}^* + \overline{x}_{ik} \delta \ \ = \ \ \overline{x}_{ik} \delta \mbox{for all } k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0 \\ u'_{ik} \ \ & = \ \ u_{ik}^* \mbox{for all } k \in \mathcal{K}_{i} \setminus \big(\{l\} \cup \left\{k \in \underline{\mathcal{K}}_{i}^{+} \, : \, u_{ik}^* = 0\right\} \cup \big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}\big) \\ u'_{jk} \ \ & = \ \ u_{jk}^* \left(1 - \delta\right) \mbox{for all } j \in \mathcal{J} \setminus \{i\}, \ k \in \mathcal{K}_{j} \end{align*} } Note that, since $i \in \mathcal{J} \setminus \overline{\mathcal{J}}$, it holds that $\mathcal{K}_{i} \setminus \overline{\mathcal{K}}_{i} \neq \varnothing$, and thus an attribute $l \in \mathcal{K}_{i} \setminus \overline{\mathcal{K}}_{i}$ exists. Next we show that $(d', d_{0}', u')$ is feasible for (ref). \begin{itemize} • Note that for all $j \in \mathcal{J} \setminus \{i\}$, it holds that $d_{j}' / d_{0}' = d_{j}^* / d_{0}^*$, and thus $(d', d_{0}', u')$ satisfies (ref). • Next we show that $(d', d_{0}', u')$ satisfies (ref). \begin{itemize} • By (ref), $\sum_{k \in \mathcal{K}_{i}} u_{ik}^* \leq 0$, and thus \begin{align*} \sum_{k \in \mathcal{K}_{i}} u'_{ik} \ \ & = \ \ u_{il}^* \; - \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \underline{x}_{ik} \delta \; - \sum_{\left\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\right\}} \overline{x}_{ik} \delta \; - \; \delta \ln\left(\frac{\delta}{d_{0}^* \left(1 - \delta\right)}\right) \\ & \qquad + \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \big(u_{ik}^* + \underline{x}_{ik} \delta\big) \; + \sum_{\left\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\right\}} \big(u_{ik}^* + \overline{x}_{ik} \delta\big) \\ & \qquad + \sum_{k \in \mathcal{K}_{i} \setminus \big(\{l\} \cup \left\{k \in \underline{\mathcal{K}}_{i}^{+} \, : \, u_{ik}^* = 0\right\} \cup \big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}\big)} u_{ik}^* \\ & = \ \ \sum_{k \in \mathcal{K}_{i}} u_{ik}^* - \delta \ln\left(\frac{\delta}{d_{0}^* \left(1 - \delta\right)}\right) \ \ \le \ \ - d'_{i} \ln\left(\frac{d'_{i}}{d_{0}'}\right) \end{align*} and hence $(d', d_{0}', u')$ satisfies (ref) for $j = i$. • For $j \in \mathcal{J} \setminus \{i\}$, if $d_{j}^* > 0$ then it holds that \[ \sum_{k \in \mathcal{K}_{j}} u'_{jk} \ \ = \ \ \left(1 - \delta\right) \sum_{k \in \mathcal{K}_{j}} u_{jk}^* \ \ \le \ \ - \left(1 - \delta\right) d_{j}^* \ln\left(\frac{d_{j}^*}{d_{0}^*}\right) \ \ = \ \ - d'_{j} \ln\left(\frac{d'_{j}}{d_{0}'}\right) \] and if $d_{j}^* = 0$ then it holds that $d'_{j} = 0$ and \[ \sum_{k \in \mathcal{K}_{j}} u'_{jk} \ \ = \ \ \left(1 - \delta\right) \sum_{k \in \mathcal{K}_{j}} u_{jk}^* \ \ \le \ \ 0 \] and hence $(d', d_{0}', u')$ satisfies (ref) for all $j \in \mathcal{J}$. \end{itemize} • Next, we show that $(d', d_{0}', u')$ satisfies (ref). \begin{itemize} • Suppose that $l \in \underline{\mathcal{K}}_{i}$. Let $f(\delta) := - \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \underline{x}_{ik} \delta \, - \sum_{\left\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\right\}} \overline{x}_{ik} \delta \, - \, \delta \ln\left(\delta / \left[d_{0}^* \left(1 - \delta\right)\right]\right) - \underline{x}_{il} \delta$. Note that $f'(\delta) = - \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \underline{x}_{ik} \, - \sum_{\left\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\right\}} \overline{x}_{ik} \, - \, \ln\left(\delta / \left[d_{0}^* \left(1 - \delta\right)\right]\right) \, - \, 1 \, - \, \delta / \left(1 - \delta\right) - \underline{x}_{il} \to \infty$ as $\delta \downarrow 0$. Thus, $f'(s) > 0$ for all $s > 0$ sufficiently small, hence $\left[u'_{il} - \underline{x}_{il} d'_{i}\right] - \left[u_{il}^* - \underline{x}_{il} d_{i}^*\right] = \int_{0}^{\delta} f'(s) \mathop{}\!\mathrm{d} s > 0$, and therefore $u'_{il} - \underline{x}_{il} d'_{i} > u_{il}^* - \underline{x}_{il} d_{i}^* \ge 0$ for all $\delta > 0$ sufficiently small. • Consider any $k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\}$. If $u_{ik}^* = 0$, then $u'_{ik} = \underline{x}_{ik} \delta = \underline{x}_{ik} d'_{i}$. Otherwise, $u_{ik}^* > 0$, then $u'_{ik} = u_{ik}^* > \underline{x}_{ik} \delta = \underline{x}_{ik} d'_{i}$. • Consider any $k \in \underline{\mathcal{K}}_{i} \setminus \left(\underline{\mathcal{K}}_{i}^{+} \cup \{l\}\right)$. Then $u'_{ik} = u_{ik}^* \ge 0 \ge \underline{x}_{ik} \delta = \underline{x}_{ik} d'_{i}$. • Next, consider any $j \in \mathcal{J} \setminus \{i\}$ and any $k \in \underline{\mathcal{K}}_{j}$. Then $u'_{jk} = u_{jk}^* \left(1 - \delta\right) \ge \underline{x}_{jk} d_{j}^* \left(1 - \delta\right) = \underline{x}_{jk} d'_{j}$. Thus, $(d', d_{0}', u')$ satisfies (ref) for all $j \in \mathcal{J}$ and $k \in \underline{\mathcal{K}}_{j}$. \end{itemize} • Next, we show that $(d', d_{0}', u')$ satisfies (ref). \begin{itemize} • Consider any $k \in \overline{\mathcal{K}}_{i}^{-}$. If $u_{ik}^* = 0$, then $u'_{ik} = \overline{x}_{ik} \delta = \underline{x}_{ik} d'_{i}$. Otherwise, $u_{ik}^* < 0$, then $u'_{ik} = u_{ik}^* < \overline{x}_{ik} \delta = \overline{x}_{ik} d'_{i}$. • Consider any $k \in \overline{\mathcal{K}}_{i} \setminus \overline{\mathcal{K}}_{i}^{-}$. Then $u'_{ik} = u_{ik}^* \le 0 \le \overline{x}_{ik} \delta = \overline{x}_{ik} d'_{i}$. • Consider any $j \in \mathcal{J} \setminus \{i\}$ and any $k \in \overline{\mathcal{K}}_{j}$. Then $u'_{jk} = u_{jk}^* \left(1 - \delta\right) \le \overline{x}_{jk} d_{j}^* \left(1 - \delta\right) = \overline{x}_{jk} d'_{j}$. Thus, $(d', d_{0}', u')$ satisfies (ref) for all $j \in \mathcal{J}$ and $k \in \overline{\mathcal{K}}_{j}$. \end{itemize} • Since $d_{i}^* = 0$, it follows from (ref) that $d_{0}^* + \sum_{j \in \mathcal{J} \setminus \{i\}} d_{j}^* = 1$, and thus \[ d_{0}' + \sum_{j \in \mathcal{J}} d'_{j} \ \ = \ \ d_{0}^* \left(1 - \delta\right) + \delta + \sum_{j \in \mathcal{J} \setminus \{i\}} d_{j}^* \left(1 - \delta\right) \ \ = \ \ \left(d_{0}^* + \sum_{j \in \mathcal{J} \setminus \{i\}} d_{j}^*\right) \left(1 - \delta\right) + \delta \ \ = \ \ 1 - \delta + \delta \ \ = \ \ 1 \] Hence $(d', d_{0}', u')$ satisfies (ref), and therefore $(d', d_{0}', u')$ is feasible for (ref). \end{itemize} Next we show that the objective value of (ref) at $(d', d_{0}', u')$ is greater than the objective value at $(d^*, d_{0}^*, u^*)$. The change in objective value from $(d^*, d_{0}^*, u^*)$ to $(d', d_{0}', u')$ is \begin{align*} & \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{j}} \phi_{k} u'_{jk} - \psi_{j} d'_{j}\right) - \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{j}} \phi_{k} u_{jk}^* - \psi_{j} d_{j}^*\right) \\ = \ \ & \phi_{l} \left[u_{il}^* \; - \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \underline{x}_{ik} \delta \; - \sum_{\big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}} \overline{x}_{ik} \delta \; - \; \delta \ln\left(\frac{\delta}{d_{0}^* \left(1 - \delta\right)}\right)\right] \\ & + \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \phi_{k} \left[u_{ik}^* + \underline{x}_{ik} \delta\right] \; + \sum_{\big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}} \phi_{k} \left[u_{ik}^* + \overline{x}_{ik} \delta\right] \\ & + \sum_{k \in \mathcal{K}_{i} \setminus \big(\{l\} \cup \big\{k \in \underline{\mathcal{K}}_{i}^{+} \, : \, u_{ik}^* = 0\big\} \cup \big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}\big)} \phi_{k} u_{ik}^* \; - \; \psi_{i} \delta \\ & + \sum_{j \in \mathcal{J} \setminus \{i\}} \left(\sum_{k \in \mathcal{K}_{j}} \phi_{k} u_{jk}^* \left(1 - \delta\right) - \psi_{j} d_{j}^* \left(1 - \delta\right)\right) - \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{j}} \phi_{k} u_{jk}^* - \psi_{j} d_{j}^*\right) \\ = \ \ & \int_{0}^{\delta} g'(s) \mathop\!\mathrm{d} s \end{align*} where $g : (0,1) \mapsto \mathbb{R}$ is given by \begin{align*} g(s) \ \ := \ \ & \phi_{l} \left[u_{il}^* \; - \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \underline{x}_{ik} s \; - \sum_{\big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}} \overline{x}_{ik} s \; - \; s \ln\left(\frac{s}{d_{0}^* \left(1 - s\right)}\right)\right] \\ & + \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \phi_{k} \left[u_{ik}^* + \underline{x}_{ik} s\right] \; + \sum_{\big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}} \phi_{k} \left[u_{ik}^* + \overline{x}_{ik} s\right] \\ & + \sum_{k \in \mathcal{K}_{i} \setminus \big(\{l\} \cup \big\{k \in \underline{\mathcal{K}}_{i}^{+} \, : \, u_{ik}^* = 0\big\} \cup \big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}\big)} \phi_{k} u_{ik}^* \; - \; \psi_{i} s \\ & + \sum_{j \in \mathcal{J} \setminus \{i\}} \left(\sum_{k \in \mathcal{K}_{j}} \phi_{k} u_{jk}^* \left(1 - s\right) - \psi_{j} d_{j}^* \left(1 - s\right)\right) \end{align*} Note that { \begin{align*} g'(s) & \ \ = \ \ \phi_{l} \left[- \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \underline{x}_{ik} \; - \sum_{\big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}} \overline{x}_{ik} \; - \; \ln\left(\frac{s}{d_{0}^* \left(1 - s\right)}\right) \; - \; 1 \; - \; \frac{s}{1 - s}\right] \\ & + \sum_{\left\{k \in \underline{\mathcal{K}}_{i}^{+} \setminus \{l\} \, : \, u_{ik}^* = 0\right\}} \phi_{k} \underline{x}_{ik} \; + \sum_{\big\{k \in \overline{\mathcal{K}}_{i}^{-} \, : \, u_{ik}^* = 0\big\}} \phi_{k} \overline{x}_{ik} \; - \; \psi_{i} \; - \sum_{j \in \mathcal{J} \setminus \{i\}} \left(\sum_{k \in \mathcal{K}_{j}} \phi_{k} u_{jk}^* - \psi_{j} d_{j}^*\right) \ \ \to \ \ \infty \ \ \mbox{ as } \ \ s \downarrow 0 \end{align*} } Thus $g'(s) > 0$ for all $s > 0$ sufficiently small, and therefore for $\delta > 0$ sufficiently small the objective value of (ref) at $(d', d_{0}', u')$ is greater than the objective value at $(d^*, d_{0}^*, u^*)$. This contradiction establishes that $d_{j}^* > 0$ for all $j \in \mathcal{J} \setminus \overline{\mathcal{J}}$. In conclusion, it has been shown that $(d^*, d_{0}^*, u^*)$ is feasible for and therefore also optimal for (ref). \end{proof} \subsection{Proof of Lemma (ref)} {\color{purple} \begin{manuallemma}{(ref)} If (ref) is feasible, then (ref) has an optimal solution if and only if for each $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} \le \phi_{k_{2},t}$. \end{manuallemma} } \begin{proof} Suppose that there is a $j \in \mathcal{J}$, a $t \in \{0, 1, \ldots, T\}$, a $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and a $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, such that $\phi_{k_{1},t} > \phi_{k_{2},t}$. Consider any feasible solution $(d^{0}, d^{0}_{0}, u^{0})$ and a sequence $\{(d^{n}, d^{n}_{0}, u^{n})\}_{n=0}^{\infty}$ of feasible solutions with $u^{n}_{j,k_{1},t} = u^{0}_{j,k_{1},t} + n$, $u^{n}_{j,k_{2},t} = u^{0}_{j,k_{2},t} - n$, $u^{n}_{jkt} = u^{0}_{jkt}$ for all $k \notin \{k_{1}, k_{2}\}$, $u^{n}_{j'kt'} = u^{0}_{j'kt'}$ for all $j' \neq j$ or $t' \neq t$, and $k \in \mathcal{K}_{j't'}$, $d^{n}_{j't'} = d^{0}_{j't'}$ for all $j' \in \mathcal{J}$ and $t' \in \{0, 1, \ldots, T\}$, and $d^{n}_{0t'} = d^{0}_{0t'}$ for all $t' \in \{0, 1, \ldots, T\}$. Then $(d^{n}, d^{n}_{0}, u^{n})$ is feasible for (ref) for all $n$, and the objective value of $(d^{n+1}, d^{n+1}_{0}, u^{n+1})$ exceeds the objective value of $(d^{n}, d^{n}_{0}, u^{n})$ by $\phi_{k_{1},t} - \phi_{k_{2},t}$ for all $n$, and thus the objective value of $(d^{n}, d^{n}_{0}, u^{n})$ increases without bound as $n \to \infty$. Suppose that, for each $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, and $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} \le \phi_{k_{2},t}$. Let problem \textsf{$\mathsf{FP_3^{MNL}}$} be the same as problem (ref) with the resource constraint (ref) removed. Thus, \textsf{$\mathsf{FP_3^{MNL}}$} is a collection of separate problems, one problem for each $t \in \{0, 1, \ldots, T\}$, similar to (ref). By the proof of Lemma (ref), \textsf{$\mathsf{FP_3^{MNL}}$} is feasible, the dual of \textsf{$\mathsf{FP_3^{MNL}}$} is bounded, and has a feasible solution in the interior of the dual cones. Since (ref) is feasible, the dual of (ref) is bounded. Also, since (ref) is the same as \textsf{$\mathsf{FP_3^{MNL}}$} with additional linear inequality constraints, the dual of (ref) has additional signed variables beyond the dual of \textsf{$\mathsf{FP_3^{MNL}}$}. Then a feasible solution of the dual of \textsf{$\mathsf{FP_3^{MNL}}$} in the interior of the dual cones, combined with these additional signed variables set to $0$, gives a feasible solution of the dual of (ref) in the interior of the dual cones. Then it follows from the conic duality theorem (Theorem 1.4.2 in ben2001lectures) that (ref) has an optimal solution. \end{proof} \subsection{Proof of Lemma (ref)} {\color{purple} \begin{manuallemma}{(ref)} Suppose that (ref) has a feasible solution $(d', d_{0}', u')$ with $d' > 0$. Then, any optimal solution $(d^*, d_{0}^*, u^*)$ for (ref) satisfies $d^* > 0$, $d_{0}^* > 0$. \end{manuallemma} } \begin{proof} First, suppose that $d_{0t}^* = 0$ for some $t \in \{0, 1, \ldots, T\}$. Then it follows from (ref) that $d_{jt}^* = 0$ for all $j \in \mathcal{J}$, which violates (ref). Thus $d_{0t}^* > 0$ for all $t \in \{0, 1, \ldots, T\}$. Next, suppose that $d_{jt}^* = 0$ for some $t \in \{0, 1, \ldots, T\}$ and some $j \in \overline{\mathcal{J}}_{t}$. Then it follows from (ref) that $d_{0t}^* = 0$. It was shown above that $d_{0t}^* > 0$ for all $t \in \{0, 1, \ldots, T\}$, and thus $d_{jt}^* > 0$ for all $t \in \{0, 1, \ldots, T\}$ and $j \in \overline{\mathcal{J}}_{t}$. Next, suppose that $d_{is}^* = 0$ for some $s \in \{0, 1, \ldots, T\}$ and some $i \in \mathcal{J} \setminus \overline{\mathcal{J}}_{s}$. Note that it follows from $\phi_{ks} > 0$ for all $k \in \mathcal{K}_{is}$, $i \in \mathcal{J} \setminus \overline{\mathcal{J}}_{s}$, and (ref), that $\sum_{k \in \mathcal{K}_{is}} u_{iks}^* = 0$. Let $(d', d_{0}', u')$ be a feasible solution of (ref) with $d' > 0$. By the same argument used above, it holds that $d_{0}' > 0$. Consider any $\delta \in (0,1)$. Since the feasible set of (ref) is convex, it follows that $(1 - \delta) (d^*, d_{0}^*, u^*) + \delta (d', d_{0}', u')$ is feasible for (ref). Consider the feasible solution $(\hat{d}, \hat{d}_{0}, \hat{u})$ for (ref) constructed to be the same as $(1 - \delta) (d^*, d_{0}^*, u^*) + \delta (d', d_{0}', u')$, except for a single variable $u_{ils}$, as follows: Since $i \in \mathcal{J} \setminus \overline{\mathcal{J}}_{s}$, it holds that $\mathcal{K}_{is} \setminus \overline{\mathcal{K}}_{is} \neq \varnothing$. Choose any $l \in \mathcal{K}_{is} \setminus \overline{\mathcal{K}}_{is}$. Let $\hat{d}_{jt} = (1 - \delta) d_{jt}^* + \delta d_{jt}'$ for all $j \in \mathcal{J}$ and $t \in \{0,1,\ldots,T\}$, $\hat{d}_{0t} = (1 - \delta) d_{0t}^* + \delta d_{0t}' > 0$ for all $t \in \{0,1,\ldots,T\}$, and $\hat{u}_{jkt} = (1 - \delta) u_{jkt}^* + \delta u_{jkt}'$ for all $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$ such that $(j,k,t) \neq (i,l,s)$. Note that $\hat{d}_{is} = (1 - \delta) d_{is}^* + \delta d_{is}' = \delta d_{is}' > 0$. Finally, let \begin{align*} \hat{u}_{ils} \ \ = \ \ \hat{d}_{is} \ln\left(\frac{\hat{d}_{0s}}{\hat{d}_{is}}\right) - \sum_{k \in \mathcal{K}_{is} \setminus \{l\}} \hat{u}_{iks} \ \ = \ \ \delta d_{is}' \ln\left(\frac{(1 - \delta) d_{0s}^* + \delta d_{0s}'}{\delta d_{is}'}\right) - \sum_{k \in \mathcal{K}_{is} \setminus \{l\}} \big[(1 - \delta) u_{iks}^* + \delta u_{iks}'\big] \end{align*} Note that, by choice of $\hat{u}_{ils}$, (ref) is satisfied for $i \in \mathcal{J}$ and $s \in \{0, 1, \ldots, T\}$. If $l \in \underline{\mathcal{K}}_{is}$, then note that, since $(1 - \delta) (d^*, d_{0}^*, u^*) + \delta (d', d_{0}', u')$ is feasible for (ref), it follows from (ref) and (ref) that \begin{align*} \underline{x}_{ils} \hat{d}_{is} \ \ & = \ \ \underline{x}_{ils} \big[(1 - \delta) d_{is}^* + \delta d_{is}'\big] \ \ \le \ \ (1 - \delta) u_{ils}^* + \delta u_{ils}' \\ & \le \ \ \big[(1 - \delta) d_{is}^* + \delta d_{is}'\big] \ln\left(\frac{(1 - \delta) d_{0s}^* + \delta d_{0s}'}{(1 - \delta) d_{is}^* + \delta d_{is}'}\right) - \sum_{k \in \mathcal{K}_{is} \setminus \{l\}} \big[(1 - \delta) u_{iks}^* + \delta u_{iks}'\big] \\ & = \ \ \hat{d}_{is} \ln\left(\frac{\hat{d}_{0s}}{\hat{d}_{is}}\right) - \sum_{k \in \mathcal{K}_{is} \setminus \{l\}} \hat{u}_{iks} \ \ = \ \ \hat{u}_{ils} \end{align*} and thus $\hat{u}_{ils}$ satisfies (ref). In addition, since $l \in \mathcal{K}_{is} \setminus \overline{\mathcal{K}}_{is}$, the variable $u_{ils}$ is not upper bounded. Hence $(\hat{d}, \hat{d}_{0}, \hat{u})$ is feasible for (ref). The difference between the objective values of (ref) at $(\hat{d}, \hat{d}_{0}, \hat{u})$ and $(d^*, d_{0}^*, u^*)$ is \begin{align*} & \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} \hat{u}_{jkt} - \psi_{jt} \hat{d}_{jt}\right) - \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} u^*_{jkt} - \psi_{jt} d^*_{jt}\right) \\ & = \ \ \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} \big[(1 - \delta) u_{jkt}^* + \delta u_{jkt}'\big] - \psi_{jt} \big[(1 - \delta) d_{jt}^* + \delta d_{jt}'\big]\right) \\ & \qquad + \lambda_{s} \phi_{ls} \left\{\delta d_{is}' \ln\left(\frac{(1 - \delta) d_{0s}^* + \delta d_{0s}'}{\delta d_{is}'}\right) - \sum_{k \in \mathcal{K}_{is} \setminus \{l\}} \big[(1 - \delta) u_{iks}^* + \delta u_{iks}'\big] - \big[(1 - \delta) u_{ils}^* + \delta u_{ils}'\big]\right\} \\ & \qquad - \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} u^*_{jkt} - \psi_{jt} d^*_{jt}\right) \\ & = \ \ \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} u_{jkt}^* - \psi_{jt} d_{jt}^*\right) + \delta \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} \big[u_{jkt}' - u_{jkt}^*\big] - \psi_{jt} \big[d_{jt}' - d_{jt}^*\big]\right) \\ & \qquad + \lambda_{s} \phi_{ls} \left\{\delta d_{is}' \ln\left(\frac{(1 - \delta) d_{0s}^* + \delta d_{0s}'}{\delta d_{is}'}\right) - \sum_{k \in \mathcal{K}_{is}} u_{iks}^* - \delta \sum_{k \in \mathcal{K}_{is}} \big[u_{iks}' - u_{iks}^*\big]\right\} \\ & \qquad - \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} u^*_{jkt} - \psi_{jt} d^*_{jt}\right) \\ & = \ \ \delta \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} \big[u_{jkt}' - u_{jkt}^*\big] - \psi_{jt} \big[d_{jt}' - d_{jt}^*\big]\right) \\ & \qquad + \lambda_{s} \phi_{ls} \left\{\delta d_{is}' \ln\left(\frac{(1 - \delta) d_{0s}^* + \delta d_{0s}'}{\delta d_{is}'}\right) - \delta \sum_{k \in \mathcal{K}_{is}} \big[u_{iks}' - u_{iks}^*\big]\right\} \\ & = \ \ \int_{0}^{\delta} h'(v) \mathop\!\mathrm{d} v \end{align*} where the third equality follows from the result that $\sum_{k \in \mathcal{K}_{is}} u_{iks}^* = 0$, and $h : (0,1) \mapsto \mathbb{R}$ is given by \begin{align*} h(v) \ \ = \ \ & v \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} \big[u_{jkt}' - u_{jkt}^*\big] - \psi_{jt} \big[d_{jt}' - d_{jt}^*\big]\right) \\ & + \lambda_{s} \phi_{ls} \left\{v d_{is}' \ln\left(\frac{(1 - v) d_{0s}^* + v d_{0s}'}{v d_{is}'}\right) - v \sum_{k \in \mathcal{K}_{is}} \big[u_{iks}' - u_{iks}^*\big]\right\} \end{align*} Note that { \begin{align*} h'(v) \ \ = \ \ & \sum_{t = 0}^{T} \lambda_{t} \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{jt}} \phi_{kt} \big[u_{jkt}' - u_{jkt}^*\big] - \psi_{jt} \big[d_{jt}' - d_{jt}^*\big]\right) \\ & + \lambda_{s} \phi_{ls} \left\{d_{is}' \ln\left(\frac{(1 - v) d_{0s}^* + v d_{0s}'}{v d_{is}'}\right) - \frac{d_{is}' d_{0s}^*}{(1 - v) d_{0s}^* + v d_{0s}'} - \sum_{k \in \mathcal{K}_{is}} \big[u_{iks}' - u_{iks}^*\big]\right\} \ \ \to \ \ \infty \ \ \mbox{ as } \ \ v \downarrow 0 \end{align*} } Thus $h'(v) > 0$ for all $v > 0$ sufficiently small, and therefore for $\delta > 0$ sufficiently small the objective value of (ref) at $(\hat{d}, \hat{d}_{0}, \hat{u})$ is greater than the objective value at $(d^*, d_{0}^*, u^*)$. This contradiction establishes that $d_{jt}^* > 0$ for all $t \in \{0, 1, \ldots, T\}$ and $j \in \mathcal{J} \setminus \overline{\mathcal{J}}_{t}$. In conclusion, it has been shown that $d^* > 0$, $d_{0}^* > 0$ for any optimal solution $(d^*, d_{0}^*, u^*)$ of (ref). \end{proof} \subsection{Proof of Theorem (ref)} {\color{purple} \begin{manualtheorem}{(ref)} (ref) can be solved by solving (ref) and taking into account the following: \begin{enumerate} • If (ref) is infeasible, then (ref) is infeasible. • If (ref) is feasible, then: \begin{enumerate} • (ref) is bounded, and has an optimal solution. • (ref) is bounded, and has an optimal solution. • Let $(v^*, d^*, u^*)$ be an optimal solution of (ref). Let $x_{jkt}^* = u_{jkt}^* / d_{jt}^*$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$ such that $d_{jt}^* > 0$, and let $x_{jkt}^* = \underline{x}_{jkt}^*$ otherwise. Then $(v^*, d^*, x^*)$ is an optimal solution of (ref). \end{enumerate} \end{enumerate} \end{manualtheorem} } \begin{proof} First, consider any $(v,d,u)$ that is feasible to (ref). Consider any $j \in \mathcal{J}$ and $t \in \{0,1,\ldots,T\}$ such that $d_{jt}>0$ (which implies $v_{jt}>0$). By constraint ((ref)), we know \begin{align*} d_{jt}\ln\left(\frac{v_{jt}}{d_{jt}}\right) \ \ \geq \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt} \end{align*} Suppose that \begin{align*} d_{jt}\ln\left(\frac{v_{jt}}{d_{jt}}\right) \ \ > \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt} \end{align*} If $j \in \overline{\mathcal{J}}_{t}$, then by constraint ((ref)), we know \begin{align*} \sum_{k \in \mathcal{K}_{jt}} \overline{x}_{jkt} d_{jt} \ \ \geq \ \ d_{jt} \ln\left(\frac{v_{jt}}{d_{jt}}\right) \ \ \geq \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt} \end{align*} otherwise, $\sum_{k \in \mathcal{K}_{jt}} u_{jkt}$ is not upper bounded by any constraint other than ((ref)). In either case, we can increase $u_{jkt}$ for some $k$ while let $v_{jt}$ and $d_{jt}$ remain unchanged, and get a feasible solution with a better objective value than $(v,d,u)$. Thus, an optimal solution for (ref) satisfies \begin{align*} d_{jt}\ln\left(\frac{v_{jt}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt} \end{align*} for any $j \in \mathcal{J}$ and $t \in \{0,1,\ldots,T\}$ such that $d_{jt}>0$. Second, consider any $(v,d,x)$ that is feasible to (ref). Let $u_{jkt} = x_{jkt} d_{jt}$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$. Then the solution $(v,d,x)$ is feasible to (ref), with the same objective value as $(v,d,x)$ in (ref). On the other hand, Consider any $(v,d,u)$ that is feasible to (ref). Then (by the previous paragraph) there is a solution $(v,d,u')$ that satisfies \begin{align*} d_{jt}\ln\left(\frac{v_{jt}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt}' \end{align*} for any $j \in \mathcal{J}$ and $t \in \{0,1,\ldots,T\}$ such that $d_{jt}>0$, whose objective value is at least as good as $(v,d,u)$. Let $x_{jkt} = u_{jkt}' / d_{jt}$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$ such that $d_{jt} > 0$, and let $x_{jkt} = \underline{x}_{jkt}$ otherwise. Then $(v, d, x)$ is a feasible solution of (ref), whose objective value is at least as good as $(v,d,u)$ in (ref). Thus, we know that: \begin{enumerate} • (ref) is infeasible if and only if (ref) is infeasible. • (ref) is feasible and unbounded if and only if (ref) is feasible and unbounded. • (ref) is feasible and bounded if and only if (ref) is feasible and bounded. • (ref) has an optimal solution if and only if (ref) has an optimal solution. • Let $(v^*, d^*, u^*)$ be an optimal solution of (ref). Then \begin{align*} d_{jt}^*\ln\left(\frac{v_{jt}^*}{d_{jt}^*}\right) = \sum_{k \in \mathcal{K}_{jt}} u_{jkt}^* \end{align*} for any $j \in \mathcal{J}$ and $t \in \{0,1,\ldots,T\}$ such that $d_{jt}^*>0$. • Let $(v^*, d^*, u^*)$ be an optimal solution of (ref). Let $x_{jkt}^* = u_{jkt}^* / d_{jt}^*$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$ such that $d_{jt}^* > 0$, and let $x_{jkt}^* = \underline{x}_{jkt}^*$ otherwise. Then $(v^*, d^*, x^*)$ is an optimal solution of (ref). \end{enumerate} It left to show that an optimal solution exists for (ref) if (ref) is feasible. Indeed. Let problem \textsf{$\mathsf{FP_3^{MC}}$} be the same as problem (ref) with the resource constraints removed. Thus, \textsf{$\mathsf{FP_3^{MC}}$} is a collection of separate problems, one problem for each $t \in \{0, 1, \ldots, T\}$. Each of the separate problem have the following formulation: \begin{subequations} \begin{align} \max_{v, \, d, \, u} \quad & \sum_{j \in \mathcal{J}} \left(\sum_{k \in \mathcal{K}_{j}} \phi_{k} u_{jk} - \psi_{j} d_{j}\right) \tag{\textsf{$\mathsf{SP_1^{MC}}$}} \\ \text{s.t.} \quad & v_{j} \ \ = \ \ \theta_{j} + \sum_{i \in \mathcal{J}} \rho_{ij} (v_{i} - d_{i}) & \forall \ j \in \mathcal{J} \\ & \left(v_{j}, d_{j}, \sum_{k \in \mathcal{K}_{j}} u_{jk}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ j \in \mathcal{J} \\ & \left(d_{j}, v_{j}, - \sum_{k \in \mathcal{K}_{j}} \overline{x}_{jk} v_{j}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ j \in \overline{\mathcal{J}}_ \\ & u_{jk} \ \ \geq \ \ \underline{x}_{jk} d_{j} & \forall \ j \in \mathcal{J}, \ k \in \underline{\mathcal{K}}_{j} \\ & u_{jk} \ \ \leq \ \ \overline{x}_{jk} d_{j} & \forall \ j \in \mathcal{J}, \ k \in \overline{\mathcal{K}}_{j} \end{align} \end{subequations} and is feasible. The dual problem of (ref) can be written as: { \begin{subequations} \begin{align} \min_{\pi, \, \varpi, \, \overline{\nu}, \, \underline{\nu}, \, \eta} \quad & \sum_{j \in \mathcal{J}} \theta_{j} \eta_{j} \tag{\textsf{$\mathsf{SD_1^{MC}}$}} \\ \text{s.t.} \quad & \pi_{j1} + \varpi_{j2} - \varpi_{j3} \sum_{k \in \overline{\mathcal{K}}_j} \overline{x}_{jk} - \eta_j + \sum_{i \in \mathcal{J}} \rho_{ji} \eta_{i} \ \ = \ \ 0 & \forall \ j \in \overline{\mathcal{J}} \\ & \pi_{j1} - \eta_j + \sum_{i \in \mathcal{J}} \rho_{ji} \eta_{i} \ \ = \ \ 0 & \forall \ j \in \mathcal{J} \setminus \overline{\mathcal{J}} \\ & \pi_{j2} + \varpi_{j1} + \sum_{k \in \overline{\mathcal{K}}_j} \overline{\nu}_{jk} \overline{x}_{jk} - \sum_{k \in \mathcal{K}_j} \underline{\nu}_{jk} \underline{x}_{jk} - \sum_{i \in \mathcal{J}} \rho_{ji} \eta_{i} \ \ = \ \ \psi_{j} & \forall \ j \in \overline{\mathcal{J}} \\ & \pi_{j2} + \sum_{k \in \overline{\mathcal{K}}_j} \overline{\nu}_{jk} \overline{x}_{jk} - \sum_{k \in \mathcal{K}_j} \underline{\nu}_{jk} \underline{x}_{jk} - \sum_{i \in \mathcal{J}} \rho_{ji} \eta_{i} \ \ = \ \ \psi_{j} & \forall \ j \in \mathcal{J} \setminus \overline{\mathcal{J}} \\ & \pi_{j3} + \underline{\nu}_{jk} - \overline{\nu}_{jk} \ \ = \ \ - \phi_{k} & \forall \ j \in \mathcal{J}, \ k \in \overline{\mathcal{K}}_{j} \\ & \pi_{j3} + \underline{\nu}_{jk} \ \ = \ \ - \phi_{k} & \forall \ j \in \mathcal{J}, \ k \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j} \\ & \pi_{j} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ j \in \mathcal{J} \\ & \varpi_{j} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ j \in \overline{\mathcal{J}} \\ & \overline{\nu}_{jk} \ \ \ge \ \ 0 & \forall \ j \in \mathcal{J}, \ k \in \overline{\mathcal{K}}_{j}\\ & \underline{\nu}_{jk} \ \ \ge \ \ 0 & \forall \ j \in \mathcal{J}, \ k \in \mathcal{K}_{j} \end{align} \end{subequations} } The refined conic duality theorem (see ben2001lectures) states that (ref) has an optimal solution if its dual problem (ref) is bounded below and is “strictly feasible” (i.e. it has a feasible solution in the interior of the cones). Since (ref) is feasible, we know that (ref) is bounded below. Next we show that (ref) has a feasible solution such that the conic variables are all in the interior of $\mathcal{K}_{\text{exp}}^*$. First, let \begin{align*} \overline{\nu}_{jk} \ \ &= \ \ 0 & \forall \ j \in \mathcal{J}, \ k \in \overline{\mathcal{K}}_{j} \\ \underline{\nu}_{jk} \ \ &= \ \ \max_{k}\{\phi_{k}\} - \phi_{k} \ \ \geq \ \ 0 & \forall \ j \in \mathcal{J}, \ k \in \mathcal{K}_{j} \\ \pi_{j1} \ \ &= \ \ 1 + \max_{k}\{\phi_{k}\} \cdot \exp\left(-\frac{\psi_{j}}{\max_{k}\{\phi_{k}\}} - 1\right) \ \ > \ \ 0 & \forall \ j \in \mathcal{J} \\ \pi_{j2} \ \ &= \ \ \psi_{j} + \sum_{k \in \mathcal{K}_j} \underline{\nu}_{jk} \underline{x}_{jk} + \sum_{i \in \mathcal{J}} \rho_{ji} \eta_{i} \ \ \geq \ \ \psi_{j} & \forall \ j \in \mathcal{J} \\ \pi_{j3} \ \ &= \ \ -\max_{k}\{\phi_{k}\} \ \ < \ \ 0 & \forall \ j \in \mathcal{J} \\ \varpi \ \ &= \ \ 0 \end{align*} where $\eta = (1 - \rho)^{-1} \pi_{\cdot 1} \geq 0$ is a solution to constraints ((ref)) and ((ref)). (Recall that $I - \rho$ needs to be non-singular and have nonnegative entries for the MC model). Clearly, the solution we constructed is feasible. Meanwhile, for each $j \in \mathcal{J}$, we have \begin{align*} \pi_{j1} \ \ &= \ \ 1 + \max_{k}\{\phi_{k}\} \cdot \exp\left(-\frac{\psi_{j}}{\max_{k}\{\phi_{k}\}} - 1\right) \\ &\geq \ \ 1 + \max_{k}\{\phi_{k}\} \cdot \exp\left(-\frac{\pi_{j2}}{\max_{k}\{\phi_{k}\}} - 1\right) \\ &= \ \ 1 - \pi_{j3} \cdot \exp\left(\frac{\pi_{j2}}{\pi_{j3}} - 1\right) \\ &> \ \ - \pi_{j3} \cdot \exp\left(\frac{\pi_{j2}}{\pi_{j3}} - 1\right) \end{align*} Thus, $\pi_{j} >_{\mathcal{K}_{\text{exp}}^*} 0$ for all $j \in \mathcal{J}$. Then consider each $j \in \overline{\mathcal{J}}$. From the current solution, we increase $\varpi_{j1}$ and decrease $\varpi_{j3}$ by some small enough $\epsilon > 0$. To stay feasible, we need to decrease $\pi_{j1}$ by $\epsilon \sum_{k \in \overline{\mathcal{K}}_j} \overline{x}_{jk}$ and decrease $\pi_{j2}$ by $\epsilon$. Let $(\pi', \varpi', \overline{\nu}', \underline{\nu}', \eta')$ be the updated solution, which is also feasible. For any $\epsilon > 0$, we have $\varpi_{j}' >_{\mathcal{K}_{\text{exp}}^*} 0$. Meanwhile, if $\epsilon$ is small enough, then $\pi_{j}'$ will stay in the interior of $\mathcal{K}_{\text{exp}}^*$ (as it is close enough to $\pi_{j}$). Thus, (ref) has an optimal solution. Now, since (ref) is feasible, the dual of (ref) is bounded. Also, since (ref) is the same as \textsf{$\mathsf{FP_3^{MC}}$} with additional linear inequality constraints, the dual of (ref) has additional signed variables beyond the dual of \textsf{$\mathsf{FP_3^{MC}}$}. Then a feasible solution of the dual of \textsf{$\mathsf{FP_3^{MC}}$} in the interior of the dual cones, combined with these additional signed variables set to $0$, gives a feasible solution of the dual of (ref) in the interior of the dual cones. Then it follows from the conic duality theorem (Theorem 1.4.2 in ben2001lectures) that (ref) has an optimal solution. \end{proof} \subsection{Proof of Theorem (ref)} {\color{purple} \begin{manualtheorem}{(ref)} If the following conditions hold: Condition (i): for any feasible solution $(d, p, p_{0}, v_{\leq}, u_{>})$ to (ref) at which \begin{align*} & \left(\frac{1}{\gamma_{it}} - 1\right) p_{it} \ln\left(\frac{p_{0t}}{p_{it}}\right) + \sum_{j \in \mathcal{J}_i} d_{jt} \ln\left(\frac{p_{0t}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{it}'} v_{ikt} & \forall \ i \in \mathcal{I}_{\leq}, \ t = 0,1,\ldots,T \end{align*} the system \begin{align*} & \left(\frac{1}{\gamma_{it}} - 1\right) d_{jt} \ln\left(\frac{p_{0t}}{p_{it}}\right) + d_{jt} \ln\left(\frac{p_{0t}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt} & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \mathcal{J}_{i}, \ t = 0,1,\ldots,T \\ & v_{ikt} \ \ = \ \ \sum_{j \in \mathcal{J}_{ikt}'} u_{jkt} & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \underline{\mathcal{K}}_{it}', \ t = 0,1,\ldots,T \\ & u_{jkt} \ \ \geq \ \ \underline{x}_{jkt} d_{jt} & \forall \ j \in \mathcal{J}_{\leq}, \ k \in \underline{\mathcal{K}}_{jt}, \ t = 0,1,\ldots,T \nonumber \\ & u_{jkt} \ \ \leq \ \ \overline{x}_{jkt} d_{jt} & \forall \ j \in \mathcal{J}_{\leq}, \ k \in \overline{\mathcal{K}}_{jt}, \ t = 0,1,\ldots,T \nonumber \end{align*} has a solution $u_{\leq}$. Here $\mathcal{J}_{ikt}' := \{j \in \mathcal{J}_{i} \ : \ k \in \mathcal{K}_{jt} \}$. Condition (ii): $\overline{\mathcal{K}}_{jt} \subsetneq \mathcal{K}_{jt}$ for every $j \in \mathcal{J}_{>}$, i.e. $\sum_{k \in \mathcal{K}_{jt}} u_{jkt}$ is not upper bounded for any $j \in \mathcal{J}_{>}$. then (ref) can be solved by solving (ref) and taking into account the following possibilities: \begin{enumerate} • If (ref) is infeasible, then (ref) is infeasible. • If (ref) is feasible and unbounded, then (ref) is feasible and unbounded. • If (ref) is feasible and has an optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$, then $(d^*, p^*, x^*)$ with $x^*$ given by $x_{jkt}^* = u_{jkt}^* / d_{jt}^*$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$, is an optimal solution for (ref). (Here $u_{>}^*$ is part of the optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$ to (ref), while $u_{\leq}^*$ is obtained by solving the system in Condition (i), using $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$ as an input.) \end{enumerate} \end{manualtheorem} } \begin{proof} First, consider any feasible solution $(d,p,x)$ to (ref). Let \begin{align*} p_{0} \ \ &= \ \ 1 - \sum_{i \in \mathcal{I}} p_{i} \\ v_{ikt} \ \ &= \ \ \sum_{j \in \mathcal{J}_{ikt}'} x_{jkt} d_{jt} & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \underline{\mathcal{K}}_{it}', \ t = 0,1,\ldots,T \\ u_{jkt} \ \ &= \ \ x_{jkt} d_{jt} & \forall \ j \in \mathcal{J}_{>}, \ k \in \underline{\mathcal{K}}_{jt}, \ t = 0,1,\ldots,T \end{align*} Then $(d, p, p_{0}, v_{\leq}, u_{>})$ is a feasible solution to (ref) with the same objective value as $(d,p,x)$ in (ref). Second, consider any feasible solution $(d, p, p_{0}, v_{\leq}, u_{>})$ to (ref). Then we can find a solution $(d, p, p_{0}, v_{\leq}', u_{>}')$ (by increased some components in $v_{\leq}$ and $u_{>}$) whose objective value is at least as good as $(d, p, p_{0}, v_{\leq}, u_{>})$, such that \begin{align*} & \left(\frac{1}{\gamma_{it}} - 1\right) p_{it} \ln\left(\frac{p_{0t}}{p_{it}}\right) + \sum_{j \in \mathcal{J}_i} d_{jt} \ln\left(\frac{p_{0t}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{it}'} v_{ikt}' & \forall \ i \in \mathcal{I}_{\leq}, \ t = 0,1,\ldots,T \\ & \left(1 - \frac{1}{\gamma_{it}}\right) d_{jt} \ln\left(\frac{p_{it}}{d_{jt}}\right) + \left(\frac{1}{\gamma_{it}}\right) d_{jt} \ln\left(\frac{p_{0t}}{d_{jt}}\right) \ \ = \ \ \sum_{k \in \mathcal{K}_{jt}} u_{jkt}' & \forall \ i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i}, \ t = 0,1,\ldots,T \end{align*} (The argument above can be proved the same way as in the proof of Theorem (ref).) Let $u_{\leq}'$ be a solution of the system in Condition (i). Let \begin{align*} x_{jkt} \ \ &= \ \ \begin{cases} u_{jkt}' / d_{jt} & \mbox{if } d_{jt} > 0 \\ \mbox{anything that satisfies the upper and lower bound (if any)} & \mbox{if } d_{jt} = 0 \end{cases} \end{align*} for each $j \in \mathcal{J}_{>}$, $k \in \underline{\mathcal{K}}_{jt}$ and $t = 0,1,\ldots,T$. The $(d,p,x)$ is a feasible solution to (ref) with the same objective value as $(d, p, p_{0}, v_{\leq}', u_{>}')$ in (ref), which is at least as good as the objective value of $(d, p, p_{0}, v_{\leq}, u_{>})$. Thus, we know that: \begin{enumerate} • If (ref) is infeasible, then (ref) is infeasible. • If (ref) is feasible and unbounded, then (ref) is feasible and unbounded. • If (ref) is feasible and has an optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$, then $(d^*, p^*, x^*)$ with $x^*$ given by $x_{jkt}^* = u_{jkt}^* / d_{jt}^*$ for every $j \in \mathcal{J}$, $t \in \{0,1,\ldots,T\}$, and $k \in \mathcal{K}_{jt}$, is an optimal solution for (ref). (Here $u_{>}^*$ is part of the optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$ to (ref), while $u_{\leq}^*$ is obtained by solving the system in Condition (i), using $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$ as an input.) \end{enumerate} \end{proof} \subsection{Proof of Theorem (ref)} {\color{purple} \begin{manualtheorem}{(ref)} Assume that Condition (i) in Theorem (ref) holds. Then, (ref) can be solved by solving (ref) and taking into account the following: \begin{enumerate} • If (ref) is infeasible, then (ref) is infeasible. • If (ref) is feasible, then the following possibilities hold: \begin{enumerate} • If (ref) is unbounded (which happens if and only if for some $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} > \phi_{k_{2},t}$), then the following possibilities hold: \begin{enumerate} • If (ref) does not have a feasible solution $(d', p', p_{0}', v_{\leq}', u_{>}', e', f_{\leq}', g_{>}', r_{\leq}', s_{>}')$ with $d' > 0$, then (ref) is infeasible. • If (ref) has a feasible solution $(d', p', p_{0}', v_{\leq}', u_{>}', e', f_{\leq}', g_{>}', r_{\leq}', s_{>}')$ with $d' > 0$, then (ref) is unbounded. \end{enumerate} • If (ref) has an optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*, e^*, f_{\leq}^*, g_{>}^*, r_{\leq}^*, s_{>}^*)$ (which happens if and only if for each $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} \le \phi_{k_{2},t}$), then the following possibilities hold: \begin{enumerate} • If $d^* > 0$, then $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*)$ is an optimal solution for (ref). • If $d_{jt}^* = 0$ for some $j \in \mathcal{J}$ and $t \in \{0,1,\ldots,T\}$, then (ref) is infeasible. \end{enumerate} \end{enumerate} \end{enumerate} \end{manualtheorem} } \begin{proof} Same as Theorem (ref), Theorem (ref) can be proved by showing two facts: \begin{enumerate} • If (ref) is feasible, then (ref) has an optimal solution if and only if for each $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} \le \phi_{k_{2},t}$. • Suppose that (ref) has a feasible solution $(d', d_{0}', u')$ with $d' > 0$. Then, any optimal solution $(d^*, p^*, p_{0}^*, v_{\leq}^*, u_{>}^*, e^*, f_{\leq}^*, g_{>}^*, r_{\leq}^*, s_{>}^*)$ for (ref) satisfies $d^* > 0$, $d_{0}^* > 0$. \end{enumerate} The second result can be shown in the same way as in the proof of Lemma (ref). On the other hand, if there is a $j \in \mathcal{J}$, a $t \in \{0, 1, \ldots, T\}$, a $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and a $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, such that $\phi_{k_{1},t} > \phi_{k_{2},t}$, then (ref) is unbounded when feasible. This can be shown by constructing a sequence of feasible solutions with objective values going to infinity, same as in the proof of Lemma (ref). It left to show that if (ref) is feasible, then (ref) has an optimal solution when for each $j \in \mathcal{J}$, $t \in \{0, 1, \ldots, T\}$, $k_{1} \in \mathcal{K}_{jt} \setminus \overline{\mathcal{K}}_{jt}$, and $k_{2} \in \mathcal{K}_{jt} \setminus \underline{\mathcal{K}}_{jt}$, it holds that $\phi_{k_{1},t} \le \phi_{k_{2},t}$. Let problem \textsf{$\mathsf{FP_4^{NL}}$} be the same as problem (ref) with the resource constraints removed. Thus, \textsf{$\mathsf{FP_4^{NL}}$} is a collection of separate problems, one problem for each $t \in \{0, 1, \ldots, T\}$. Each of the separate problem have the following formulation: { \begin{subequations} \begin{align} \max_{\substack{d, \ p, \ p_{0}, \ v_{\leq}, \ u_{>} \\ e, \ f_{\leq}, \ g_{>}, \ r_{\leq}, \ s_{>}}} \quad & \sum_{i \in \mathcal{I}_{\leq}} \sum_{k \in \mathcal{K}_{i}'} \phi_{k} v_{ik} + \sum_{j \in \mathcal{J}_{>}} \sum_{k \in \mathcal{K}_{j}} \phi_{k} u_{jk} - \sum_{j \in \mathcal{J}} \psi_{j} d_{j} \tag{\textsf{$\mathsf{SP_1^{NL}}$}} \\ \text{s.t.} \quad & \left(\frac{1}{\gamma_{i}} - 1\right) r_{i} + \sum_{j \in \mathcal{J}_i} e_{j} \ \ = \ \ \sum_{k \in \mathcal{K}_{i}'} v_{ik} & \forall \ i \in \mathcal{I}_{\leq} \ \ ((\sigma_{\leq})_{i}) \\ & \left(\frac{1}{\gamma_{i}} - 1\right) s_{i} + f_{j} \ \ = \ \ - p_{0} \sum_{k \in \mathcal{K}_{j}} \overline{x}_{jk} & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \ \ ((\kappa_{\leq})_{j}) \\ & \left(1 - \frac{1}{\gamma_{i}}\right) g_{j} + \left(\frac{1}{\gamma_{i}}\right) e_{j} \ \ = \ \ \sum_{k \in \mathcal{K}_{j}} u_{jk} & \forall \ i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \ \ ((\kappa_{>})_{j}) \\ & \left(p_{0}, d_{j}, e_{j}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}, \ j \in \mathcal{J}_{i} \ \ (\pi_{j}) \\ & \left(p_{i}, d_{j}, g_{j}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \ \ ((\varpi_{>})_{j}) \\ & \left(d_{j}, p_{0}, f_{j}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \ \ ((\varpi_{\leq})_{j}) \\ & \left(p_{i}, p_{0}, s_{i}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}_{\leq} \ \ ((\omega_{\leq})_{i}) \\ & \left(p_{0}, p_{i}, r_{i}\right) \ \ \in \ \ \mathcal{K}_{\exp} & \forall \ i \in \mathcal{I}_{\leq} \ \ ((\tau_{\leq})_{i}) \\ & p_{0} + \sum_{i \in \mathcal{I}} p_{i} \ \ = \ \ 1 & \ \ (\eta_{0}) \\ & p_{i} \ \ = \ \ \sum_{j \in \mathcal{J}_{i}} d_{j} & \forall \ i \in \mathcal{I} \ \ (\eta_{j}) \\ & v_{ik} \ \ \geq \ \ \sum_{j \in \mathcal{J}_{i}} \underline{x}_{jk} d_{j} & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \underline{\mathcal{K}}_{i}' \ \ ((\underline{\mu}_{\leq})_{ik}) \\ & v_{ik} \ \ \leq \ \ \sum_{j \in \mathcal{J}_{i}} \overline{x}_{jk} d_{j} & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \overline{\mathcal{K}}_{i}' \ \ ((\overline{\mu}_{\leq})_{ik}) \\ & u_{jk} \ \ \geq \ \ \underline{x}_{jk} d_{j} & \forall \ j \in \mathcal{J}_{>}, \ k \in \underline{\mathcal{K}}_{j} \ \ ((\underline{\nu}_{>})_{jk}) \\ & u_{jk} \ \ \leq \ \ \overline{x}_{jk} d_{j} & \forall \ j \in \mathcal{J}_{>}, \ k \in \overline{\mathcal{K}}_{j} \ \ ((\overline{\nu}_{>})_{jk}) \end{align} \end{subequations} } and is feasible. The dual problem of (ref) can be written as: { \begin{subequations} \begin{align} \min_ \quad & \eta_{0} \tag{\textsf{$\mathsf{SD_1^{NL}}$}} \\ \text{s.t.} \quad & \sum_{i \in \mathcal{I}} \sum_{j \in \mathcal{J}_{i}} \pi_{j1} + \sum_{i \in \mathcal{I}_{\leq}} \sum_{j \in \overline{\mathcal{J}}_{i}} \varpi_{j2} + \sum_{i \in \mathcal{I}_{\leq}} \omega_{i2} \nonumber \\ & + \sum_{i \in \mathcal{I}_{\leq}} \tau_{i1} + \sum_{i \in \mathcal{I}_{\leq}} \sum_{j \in \overline{\mathcal{J}}_{i}} \left( \sum_{k \in \mathcal{K}_{j}} \overline{x}_{jk} \right) \kappa_{j} \ \ = \ \ \eta_{0} & \ \ (p_{0}) \nonumber \\ & \sum_{j \in \mathcal{J}_{i}} \varpi_{j1} + \eta_{i} \ \ = \ \ \eta_{0} & i \in \mathcal{I}_{>} \ \ (p_{i}) \nonumber \\ & \omega_{i1} + \tau_{i2} + \eta_{i} \ \ = \ \ \eta_{0} & i \in \mathcal{I}_{\leq} \ \ (p_{i}) \nonumber \\ & \pi_{j2} + \varpi_{j2} - \eta_{i} - \sum_{k \in \underline{\mathcal{K}}_{j}} \underline{\nu}_{jk} \underline{x}_{jk} + \sum_{k \in \overline{\mathcal{K}}_{j}} \overline{\nu}_{jk} \overline{x}_{jk} \ \ = \ \ \psi_{j} & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \ \ (d_{j}) \nonumber \\ & \pi_{j2} + \varpi_{j1} - \eta_{i} - \sum_{k \in \underline{\mathcal{K}}_{i}'} \underline{\mu}_{jk} \underline{x}_{jk} + \sum_{k \in \overline{\mathcal{K}}_{i}'} \overline{\mu}_{jk} \overline{x}_{jk} \ \ = \ \ \psi_{j} & i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \ \ (d_{j}) \nonumber \\ & \pi_{j2} - \eta_{i} - \sum_{k \in \underline{\mathcal{K}}_{i}'} \underline{\mu}_{jk} \underline{x}_{jk} + \sum_{k \in \overline{\mathcal{K}}_{i}'} \overline{\mu}_{jk} \overline{x}_{jk} \ \ = \ \ \psi_{j} & i \in \mathcal{I}_{\leq}, \ j \in \mathcal{J} \setminus \overline{\mathcal{J}}_{i} \ \ (d_{j}) \nonumber \\ & -\kappa_{j} \ \ = \ \ -\phi_{k} & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} , \ k \in \mathcal{K}_{j} \setminus (\underline{\mathcal{K}}_{j} \cap \overline{\mathcal{K}}_{j}) \ \ (u_{jk}) \nonumber \\ & -\kappa_{j} + \underline{\nu}_{jk} \ \ = \ \ -\phi_{k} & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} , \ k \in \underline{\mathcal{K}}_{j} \setminus \overline{\mathcal{K}}_{j} \ \ (u_{jk}) \nonumber \\ & -\kappa_{j} - \overline{\nu}_{jk} \ \ = \ \ -\phi_{k} & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} , \ k \in \overline{\mathcal{K}}_{j} \setminus \underline{\mathcal{K}}_{j} \ \ (u_{jk}) \nonumber \\ & -\kappa_{j} + \underline{\nu}_{jk} - \overline{\nu}_{jk} \ \ = \ \ -\phi_{k} & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} , \ k \in \underline{\mathcal{K}}_{j} \cap \overline{\mathcal{K}}_{j} \ \ (u_{jk}) \nonumber \\ & -\sigma_{i} \ \ = \ \ -\phi_{k} & i \in \mathcal{I}_{\leq}, \ k \in \mathcal{K}_{i}' \setminus (\underline{\mathcal{K}}_{i}' \cap \overline{\mathcal{K}}_{i}') \ \ (v_{ik}) \nonumber \\ & -\sigma_{i} + \underline{\mu}_{ik} \ \ = \ \ -\phi_{k} & i \in \mathcal{I}_{\leq}, \ k \in \underline{\mathcal{K}}_{i}' \setminus \overline{\mathcal{K}}_{i}' \ \ (v_{ik}) \nonumber \\ & -\sigma_{i} - \overline{\mu}_{ik} \ \ = \ \ -\phi_{k} & i \in \mathcal{I}_{\leq}, \ k \in \overline{\mathcal{K}}_{i}' \setminus \underline{\mathcal{K}}_{i}' \ \ (v_{ik}) \nonumber \\ & -\sigma_{i} + \underline{\mu}_{ik} - \overline{\mu}_{ik} \ \ = \ \ -\phi_{k} & i \in \mathcal{I}_{\leq}, \ k \in \underline{\mathcal{K}}_{i}' \cap \overline{\mathcal{K}}_{i}' \ \ (v_{ik}) \nonumber \\ & \pi_{j3} + \left(\frac{1}{\gamma_{i}}\right) \kappa_{j} \ \ = \ \ 0 & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \ \ (e_{j}) \nonumber \\ & \pi_{j3} + \sigma_{i} \ \ = \ \ 0 & i \in \mathcal{I}_{\leq}, \ j \in \mathcal{J}_{i} \ \ (e_{j}) \nonumber \\ & \varpi_{j3} + \kappa_{j} \ \ = \ \ 0 & i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \ \ (f_{j}) \nonumber \\ & \varpi_{j3} + \left(1 - \frac{1}{\gamma_{i}}\right) \kappa_{j} \ \ = \ \ 0 & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \ \ (g_{j}) \nonumber \\ & \tau_{i3} + \left(\frac{1}{\gamma_{i}} - 1\right) \sigma_{i} \ \ = \ \ 0 & i \in \mathcal{I}_{\leq} \ \ (r_{i}) \nonumber \\ & \omega_{i3} + \left(\frac{1}{\gamma_{i}} - 1\right) \sum_{j \in \overline{\mathcal{J}}_{i}} \kappa_{j} \ \ = \ \ 0 & i \in \mathcal{I}_{\leq} \ \ (s_{i}) \nonumber \\ & \pi_{j} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ i \in \mathcal{I}, \ j \in \mathcal{J}_{i} \nonumber \\ & (\varpi_{>})_{j} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \nonumber \\ & (\varpi_{\leq})_{j} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \nonumber \\ & (\omega_{\leq})_{i} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ i \in \mathcal{I}_{\leq} \nonumber \\ & (\tau_{\leq})_{i} \ \ \in \ \ \mathcal{K}_{\exp}^* & \forall \ i \in \mathcal{I}_{\leq} \nonumber \\ & (\underline{\mu}_{\leq})_{ik} \ \ \geq \ \ 0 & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \underline{\mathcal{K}}_{i}' \nonumber \\ & (\overline{\mu}_{\leq})_{ik} \ \ \geq \ \ 0 & \forall \ i \in \mathcal{I}_{\leq}, \ k \in \overline{\mathcal{K}}_{i}' \nonumber \\ & (\underline{\nu}_{>})_{jk} \ \ \geq \ \ 0 & \forall \ j \in \mathcal{J}_{>}, \ k \in \underline{\mathcal{K}}_{j} \nonumber \\ & (\overline{\nu}_{>})_{jk} \ \ \geq \ \ 0 & \forall \ j \in \mathcal{J}_{>}, \ k \in \overline{\mathcal{K}}_{j} \nonumber \end{align} \end{subequations} } The refined conic duality theorem (see ben2001lectures) states that (ref) has an optimal solution if its dual problem (ref) is bounded below and is “strictly feasible” (i.e. it has a feasible solution in the interior of the cones). Since (ref) is feasible, we know that (ref) is bounded below. Next we show that (ref) has a feasible solution such that the conic variables are all in the interior of $\mathcal{K}_{\text{exp}}^*$. As a preparation, note that given Condition (i) in Theorem (ref), the following two arguments are equivalent (either one applies the other): \begin{enumerate} • For any $j \in \mathcal{J}$, $\phi_{k_{1}} \le \phi_{k_{2}}$ for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$. • For any $i \in \mathcal{I}$, $\phi_{k_{1}} \le \phi_{k_{2}}$ for all $k_{1} \in \mathcal{K}_{i}' \setminus \overline{\mathcal{K}}_{i}'$, $k_{2} \in \mathcal{K}_{i}' \setminus \underline{\mathcal{K}}_{i}'$. \end{enumerate} For each $i \in \mathcal{I}_{>}$, $j \in \mathcal{J}$, choose $\kappa_{j}$, $\underline{\nu}_{jk}$ for all $k \in \underline{\mathcal{K}}_{j}$, and $\overline{\nu}_{jk}$ for all $k \in \overline{\mathcal{K}}_{j}$, by considering the following cases: \begin{enumerate} • If $\mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j} \neq \varnothing$, then choose $\kappa_{j} = - \min\left\{\phi_{k} \, : \, k \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}\right\}$. Since $\phi_{k} > 0$ for all $k$, it follows that $\kappa_{j} < 0$. Then, for each $k \in \mathcal{K}_{j}$, consider the following four cases. \begin{enumerate} • Suppose $k \in \mathcal{K}_{j} \setminus \left(\underline{\mathcal{K}}_{j} \cup \overline{\mathcal{K}}_{j}\right)$. Since $k \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it follows that $\kappa_{j} \le \phi_{k}$. Since $k \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$ and $\phi_{k_{1}} \le \phi_{k_{2}}$ for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it follows that $\phi_{k} \le \kappa_{j}$. Thus, $\phi_{k} = \kappa_{j}$. • Suppose $k \in \underline{\mathcal{K}}_{j} \setminus \overline{\mathcal{K}}_{j}$. Then choose $\underline{\nu}_{jk} = \kappa_{j} - \phi_{k}$. Since $k \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$ and $\phi_{k_{1}} \le \phi_{k_{2}}$ for all $k_{1} \in \mathcal{K}_{j} \setminus \overline{\mathcal{K}}_{j}$, $k_{2} \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it follows that $\phi_{k} \le \kappa_{j}$. Thus $\underline{\nu}_{jk} = \kappa_{j} - \phi_{k} \ge 0$. • Suppose $k \in \overline{\mathcal{K}}_{j} \setminus \underline{\mathcal{K}}_{j}$. Then choose $\overline{\nu}_{jk} = \kappa_{j} + \phi_{k}$. Since $k \in \mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j}$, it follows that $\kappa_{j} \le \phi_{k}$. Thus $\overline{\nu}_{jk} = \kappa_{j} + \phi_{k} \ge 0$. • Suppose $k \in \underline{\mathcal{K}}_{j} \cap \overline{\mathcal{K}}_{j}$. Then choose $\underline{\nu}_{jk} = \max\left\{0, \, \kappa_{j} - \phi_{k}\right\}$ and $\overline{\nu}_{jk} = \max\left\{0, \, \kappa_{j} + \phi_{k}\right\}$. \end{enumerate} • If $\mathcal{K}_{j} \setminus \underline{\mathcal{K}}_{j} = \varnothing$ (that is, $\mathcal{K}_{j} = \underline{\mathcal{K}}_{j}$), then choose $\kappa_{j} = - \max\left\{\phi_{k} \, : \, k \in \mathcal{K}_{j}\right\}$. Since $\phi_{k} > 0$ for all $k$, it follows that $\kappa_{j} < 0$. Then, for each $k \in \mathcal{K}_{j}$, consider the following two cases (only these two cases are possible). \begin{enumerate} • Suppose $k \in \underline{\mathcal{K}}_{j} \setminus \overline{\mathcal{K}}_{j}$. Then choose $\underline{\nu}_{jk} = \kappa_{j} - \phi_{k}$. Since $\phi_{k} \le \kappa_{j}$, it follows that $\underline{\nu}_{jk} = \kappa_{j} - \phi_{k} \ge 0$. • Suppose $k \in \underline{\mathcal{K}}_{j} \cap \overline{\mathcal{K}}_{j}$. Then choose $\underline{\nu}_{jk} = \max\left\{0, \, \kappa_{j} - \phi_{k}\right\}$ and $\overline{\nu}_{jk} = \max\left\{0, \, \kappa_{j} + \phi_{k}\right\}$. \end{enumerate} \end{enumerate} For each $i \in \mathcal{I}_{\leq}$, choose $\sigma_{i}$, $\underline{\mu}_{ik}$ for all $k \in \underline{\mathcal{K}}_{i}'$, and $\overline{\mu}_{ik}$ for all $k \in \overline{\mathcal{K}}_{i}'$, by considering the following cases: \begin{enumerate} • If $\mathcal{K}_{i}' \setminus \underline{\mathcal{K}}_{i}' \neq \varnothing$, then choose $\sigma_{i} = - \min\left\{\phi_{k} \, : \, k \in \mathcal{K}_{i}' \setminus \underline{\mathcal{K}}_{i}'\right\}$. Since $\phi_{k} > 0$ for all $k$, it follows that $\sigma_{i} < 0$. Then, for each $k \in \mathcal{K}_{i}'$, consider the following four cases. \begin{enumerate} • Suppose $k \in \mathcal{K}_{i}' \setminus \left(\underline{\mathcal{K}}_{i}' \cup \overline{\mathcal{K}}_{i}'\right)$. Since $k \in \mathcal{K}_{i}' \setminus \underline{\mathcal{K}}_{i}'$, it follows that $\sigma_{i} \le \phi_{k}$. Since $k \in \mathcal{K}_{i}' \setminus \overline{\mathcal{K}}_{i}'$ and $\phi_{k_{1}} \le \phi_{k_{2}}$ for all $k_{1} \in \mathcal{K}_{i}' \setminus \overline{\mathcal{K}}_{i}'$, $k_{2} \in \mathcal{K}_{i}' \setminus \underline{\mathcal{K}}_{i}'$, it follows that $\phi_{k} \le \sigma_{i}$. Thus, $\phi_{k} = \sigma_{i}$. • Suppose $k \in \underline{\mathcal{K}}_{i}' \setminus \overline{\mathcal{K}}_{i}'$. Then choose $\underline{\mu}_{ik} = \sigma_{i} - \phi_{k}$. Since $k \in \mathcal{K}_{i}' \setminus \overline{\mathcal{K}}_{i}'$ and $\phi_{k_{1}} \le \phi_{k_{2}}$ for all $k_{1} \in \mathcal{K}_{i}' \setminus \overline{\mathcal{K}}_{i}'$, $k_{2} \in \mathcal{K}_{i}' \setminus \underline{\mathcal{K}}_{i}'$, it follows that $\phi_{k} \le \sigma_{i}$. Thus $\underline{\mu}_{ik} = \sigma_{i} - \phi_{k} \ge 0$. • Suppose $k \in \overline{\mathcal{K}}_{i}' \setminus \underline{\mathcal{K}}_{i}'$. Then choose $\overline{\mu}_{ik} = \sigma_{i} + \phi_{k}$. Since $k \in \mathcal{K}_{i}' \setminus \underline{\mathcal{K}}_{i}'$, it follows that $\sigma_{i} \le \phi_{k}$. Thus $\overline{\mu}_{ik} = \sigma_{i} + \phi_{k} \ge 0$. • Suppose $k \in \underline{\mathcal{K}}_{i}' \cap \overline{\mathcal{K}}_{i}'$. Then choose $\underline{\mu}_{ik} = \max\left\{0, \, \sigma_{i} - \phi_{k}\right\}$ and $\overline{\mu}_{ik} = \max\left\{0, \, \sigma_{i} + \phi_{k}\right\}$. \end{enumerate} • If $\mathcal{K}_{i}' \setminus \underline{\mathcal{K}}_{i}' = \varnothing$ (that is, $\mathcal{K}_{i}' = \underline{\mathcal{K}}_{i}'$), then choose $\sigma_{i} = - \max\left\{\phi_{k} \, : \, k \in \mathcal{K}_{i}'\right\}$. Since $\phi_{k} > 0$ for all $k$, it follows that $\sigma_{i} < 0$. Then, for each $k \in \mathcal{K}_{i}'$, consider the following two cases (only these two cases are possible). \begin{enumerate} • Suppose $k \in \underline{\mathcal{K}}_{i}' \setminus \overline{\mathcal{K}}_{i}'$. Then choose $\underline{\mu}_{ik} = \sigma_{i} - \phi_{k}$. Since $\phi_{k} \le \sigma_{i}$, it follows that $\underline{\mu}_{ik} = \sigma_{i} - \phi_{k} \ge 0$. • Suppose $k \in \underline{\mathcal{K}}_{i}' \cap \overline{\mathcal{K}}_{i}'$. Then choose $\underline{\mu}_{ik} = \max\left\{0, \, \sigma_{i} - \phi_{k}\right\}$ and $\overline{\mu}_{ik} = \max\left\{0, \, \sigma_{i} + \phi_{k}\right\}$. \end{enumerate} \end{enumerate} In addition, let \begin{align*} & \pi_{j3} \ \ = \ \ - \left(\frac{1}{\gamma_{i}}\right) \kappa_{j} \ \ < \ \ 0 & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \nonumber \\ & \pi_{j3} \ \ = \ \ - \sigma_{i} \ \ < \ \ 0 & i \in \mathcal{I}_{\leq}, \ j \in \mathcal{J}_{i} \nonumber \\ & \varpi_{j3} \ \ = \ \ - \varpi_{j1} \ \ = \ \ - \left(1 - \frac{1}{\gamma_{i}}\right) \kappa_{j} \ \ < \ \ 0 & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \nonumber \\ & \varpi_{j3} \ \ = \ \ - \varpi_{j1} \ \ = \ \ - \kappa_{j} \ \ < \ \ 0 & i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \nonumber \\ & \omega_{i3} \ \ = \ \ - \omega_{i1} \ \ = \ \ - \left(\frac{1}{\gamma_{i}} - 1\right) \sum_{j \in \overline{\mathcal{J}}_{i}} \kappa_{j} \ \ < \ \ 0 & i \in \mathcal{I}_{\leq} \nonumber \\ & \tau_{i3} \ \ = \ \ - \left(\frac{1}{\gamma_{i}} - 1\right) \sigma_{i} \ \ < \ \ 0 & i \in \mathcal{I}_{\leq} \nonumber \end{align*} and let \begin{align*} & \pi_{j1} \ \ = \ \ C & i \in \mathcal{I}, \ j \in \mathcal{J}_{i} \nonumber \\ & \tau_{i1} \ \ = \ \ C & i \in \mathcal{I}_{\leq} \nonumber \\ & \varpi_{j2} \ \ = \ \ 0 & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \nonumber \\ & \varpi_{j2} \ \ = \ \ 0 & i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \nonumber \\ & \omega_{i2} \ \ = \ \ 0 & i \in \mathcal{I}_{\leq} \nonumber \\ & \eta_{0} \ \ = \ \ \sum_{i \in \mathcal{I}} \sum_{j \in \mathcal{J}_{i}} \pi_{j1} + \sum_{i \in \mathcal{I}_{\leq}} \tau_{i1} + \sum_{i \in \mathcal{I}_{\leq}} \sum_{j \in \overline{\mathcal{J}}_{i}} \left( \sum_{k \in \mathcal{K}_{j}} \overline{x}_{jk} \right) \kappa_{j} \nonumber \\ & \eta_{i} \ \ = \ \ \eta_{0} - \sum_{j \in \mathcal{J}_{i}} \varpi_{j1} & i \in \mathcal{I}_{>} \nonumber \\ & \tau_{i2} \ \ = \ \ \eta_{0} - \eta_{i} - \omega_{i1} \ \ = \ \ \sum_{j \in \mathcal{J}_{i}} \varpi_{j1} & i \in \mathcal{I}_{\leq} \ \ (p_{i}) \nonumber \\ & \pi_{j2} \ \ = \ \ \eta_{i} + \psi_{j} - \varpi_{j2} + \sum_{k \in \underline{\mathcal{K}}_{j}} \underline{\nu}_{jk} \underline{x}_{jk} - \sum_{k \in \overline{\mathcal{K}}_{j}} \overline{\nu}_{jk} \overline{x}_{jk} & i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \nonumber \\ & \pi_{j2} \ \ = \ \ \eta_{i} + \psi_{j} - \varpi_{j1} + \sum_{k \in \underline{\mathcal{K}}_{i}'} \underline{\mu}_{jk} \underline{x}_{jk} - \sum_{k \in \overline{\mathcal{K}}_{i}'} \overline{\mu}_{jk} \overline{x}_{jk} & i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \nonumber \\ & \pi_{j2} \ \ = \ \ \eta_{i} + \psi_{j} + \sum_{k \in \underline{\mathcal{K}}_{i}'} \underline{\mu}_{jk} \underline{x}_{jk} - \sum_{k \in \overline{\mathcal{K}}_{i}'} \overline{\mu}_{jk} \overline{x}_{jk} & i \in \mathcal{I}_{\leq}, \ j \in \mathcal{J} \setminus \overline{\mathcal{J}}_{i} \nonumber \end{align*} where $C$ is a positive number. Thus, all equality and inequality constraints in (ref) hold. Meanwhile, we can make $C$ large enough, such that \begin{align*} & \eta_{0} \ \ > \ \ 0 \\ & \eta_{i} \ \ > \ \ 0 & i \in \mathcal{I}_{>} \\ & \pi_{j1} \ \ \geq \ \ - \pi_{j3} \ \ > \ \ 0 \ \ ; \ \ \pi_{j2} \ \ \geq \ \ 0 & \forall \ i \in \mathcal{I}, \ j \in \mathcal{J}_{i} \nonumber \\ & \varpi_{j1} \ \ = \ \ - \varpi_{j3} \ \ > \ \ 0 \ \ ; \ \ \varpi_{j2} \ \ = \ \ 0 & \forall \ i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \nonumber \\ & \varpi_{j1} \ \ = \ \ - \varpi_{j3} \ \ > \ \ 0 \ \ ; \ \ \varpi_{j2} \ \ = \ \ 0 & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \nonumber \\ & \omega_{j1} \ \ = \ \ - \omega_{j3} \ \ > \ \ 0 \ \ ; \ \ \omega_{j2} \ \ = \ \ 0 & \forall \ i \in \mathcal{I}_{\leq} \nonumber & \tau_{j1} \ \ > \ \ - \tau_{j3} \exp\left( \tau_{j2}/\tau_{j3} - 1 \right) & \forall \ i \in \mathcal{I}_{\leq} \nonumber \end{align*} which implies \begin{align*} & \pi_{j} \ \ >_{\mathcal{K}_{\exp}^*} \ \ 0 & \forall \ i \in \mathcal{I}, \ j \in \mathcal{J}_{i} \nonumber \\ & (\varpi_{>})_{j} \ \ >_{\mathcal{K}_{\exp}^*} \ \ 0 & \forall \ i \in \mathcal{I}_{>}, \ j \in \mathcal{J}_{i} \nonumber \\ & (\varpi_{\leq})_{j} \ \ >_{\mathcal{K}_{\exp}^*} \ \ 0 & \forall \ i \in \mathcal{I}_{\leq}, \ j \in \overline{\mathcal{J}}_{i} \nonumber \\ & (\omega_{\leq})_{i} \ \ >_{\mathcal{K}_{\exp}^*} \ \ 0 & \forall \ i \in \mathcal{I}_{\leq} \nonumber \\ & (\tau_{\leq})_{i} \ \ >_{\mathcal{K}_{\exp}^*} \ \ 0 & \forall \ i \in \mathcal{I}_{\leq} \nonumber \end{align*} Thus, (ref) has a feasible solution such that the conic variables are all in the interior of $\mathcal{K}_{\text{exp}}^*$. Now, since (ref) is feasible, the dual of (ref) is bounded. Also, since (ref) is the same as \textsf{$\mathsf{FP_3^{NL}}$} with additional linear inequality constraints, the dual of (ref) has additional signed variables beyond the dual of \textsf{$\mathsf{FP_3^{NL}}$}. Then a feasible solution of the dual of \textsf{$\mathsf{FP_3^{NL}}$} in the interior of the dual cones, combined with these additional signed variables set to $0$, gives a feasible solution of the dual of (ref) in the interior of the dual cones. Then it follows from the conic duality theorem (Theorem 1.4.2 in ben2001lectures) that (ref) has an optimal solution. \end{proof}