REVIEW 4 major objections 7 minor 21 references
Competitive Facility Location with Market Expansion and Customer-centric Objective
T0 review · 4 major / 7 minor · reviewed 2026-08-11 · deepseek-v4-flash
Pith's one-line read Under a concave market-expansion function, the competitive facility location objective becomes submodular, so greedy placement guarantees a (1-1/e) approximation, and a chord-based inner approximation converts the problem into an MILP…
desk verdict The paper's submodularity and inner-approximation ideas are sound, but every MILP silently normalizes competitor utility U^c_n to 1, so the guarantees apply to a different problem than the stated ME-MCP. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the univariate component $\Psi_n(z_n)=q_n g(\log z_n)(1-U^c_n/z_n)+\alpha_n\log z_n$, whose concavity is established by a second-derivative condition on $g$ and the sign of $g(0)-g'(0)$. Concavity of this component in $z_n$ yields submodularity of the set function through a mean-value-theorem comparison of marginal gains, unlocking the greedy guarantee. The inner-approximation machinery replaces each concave $\Psi_n$ by a piecewise-linear function $\Gamma_n$ written as a minimum over chords between breakpoints; because the objective is linear in the chord variables, the approximate problem becomes a MILP with no additional integer variables, and breakpoints are chosen by binary search so that the maximum chord-to-curve gap is at most $\epsilon$.
What would settle it
Take an instance with $U^c_n=2$ for one customer type, solve the IA-MILP as written in the paper (which uses $U^c_n=1$), evaluate the returned location set under the true objective $F$, and compare the gap to the bound $N\epsilon$ from Theorem 5; if the measured gap exceeds $N\epsilon$, the guarantee as stated fails for that instance.
Extended reading notes
Core claim
The paper discovers that the objective $F(S)=\sum_{n} q_n g\!\left(\log\!\left(U^c_n+\sum_{i\in S} V_{ni}\right)\right)\frac{\sum_{i\in S} V_{ni}}{U^c_n+\sum_{i\in S} V_{ni}} + \sum_n \alpha_n \log\!\left(U^c_n+\sum_{i\in S} V_{ni}\right)$, despite its nonlinearity, is concave in the choice-probability coordinates and submodular as a set function when $g$ is non-decreasing and concave with $g(0)-g'(0)\le 0$. This gives a polynomial-time greedy heuristic with a hard $(1-1/e)$ performance certificate. The paper further proves that an inner piecewise-linear approximation of each univariate component $\Psi_n(z_n)$, with optimally placed breakpoints, produces a MILP whose optimal value is within $\sum_{n} \max_{z\in[L_n,U_n]}|\Psi_n(z)-\Gamma_n(z)|$ of the true optimum, and that this inner approximation achieves the same error bound with no more segments than any outer approximation.
Load-bearing premise
The MILP formulations and numerical experiments silently set the competitor's baseline utility $U^c_n$ to 1 in the $z_n$ constraints and breakpoint bounds, even though Section 3 states that this normalization is not applicable once market expansion depends on the log of the total utility; the stated error guarantees therefore apply to a normalized version of the problem rather than to the general ME-MCP.
Editorial extensions
If this is right
- Greedy location search now carries a hard $(1-1/e)$ performance certificate for the market-expansion objective, not just for fixed-market capture.
- In the concave case the problem can be solved to arbitrary precision as a single MILP with no extra integer variables, with explicit optimal breakpoints and $O(1/\sqrt{\epsilon})$ segments.
- The inner approximation is never worse than an outer approximation with the same number of segments, so the new method dominates tangent-line approaches used for concave demand.
- For sigmoidal (non-concave) expansion functions, the problem still admits an $\epsilon$-optimal MILP, with many binary variables provably relaxable on concave stretches.
- Larger market-expansion slopes reduce curvature and therefore reduce MILP size, making the method faster precisely in regimes where market saturation kicks in quickly.
Reading between the lines
- If the normalization gap is fixed by carrying $U^c_n$ explicitly through the breakpoint bounds, the same machinery should extend to arbitrary competitor baselines; the paper's own warning in Section 3 suggests the current MILP statement is narrower than the general model.
- The inner-versus-outer dominance is proven for univariate piecewise-linear approximation; the same dominance may hold for multidimensional cutting-plane versions, but that is not established here.
- The breakpoint-optimality result offers a practical design tool: curvature estimates from real adoption curves could drive adaptive discretizations in other discrete-choice location models with log-sum terms.
- A natural stress test is to compare the inner-approximation method against outer-approximation on instances built from real electric-vehicle charging data where $U^c_n$ is not 1 and the expansion function is sigmoidal.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies a competitive facility location problem under an MNL choice model, where total customer demand expands with the logsum (expected maximum utility) and the objective also rewards customer utility. The authors formulate ME-MCP as a mixed-integer nonlinear program, prove concavity and submodularity of the objective for a class of concave market-expansion functions (yielding a (1-1/e) greedy approximation), develop a piecewise-linear inner-approximation that is reformulated as an MILP with an N-epsilon error bound, extend the approach to general non-concave market-expansion functions via an MILP with additional binary variables, and report experiments on HM14, ORlib, and NYC instances.
Significance. If the main claims hold, the paper would provide the first constant-factor approximation guarantee for a competitive facility location model with market expansion and a customer-centric term, as well as a MILP-based approximation scheme for the non-concave case. The inner-approximation error comparison in Theorem 4 is a clean and useful observation. The paper is also notable for its extensive benchmark experiments, including a large NYC instance, and for including proofs of the main theorems in the appendix. However, the issues identified in the major comments directly affect whether the stated problem is the one being solved and whether the claimed guarantees apply, so the current version is not publishable without substantial revision.
major comments (4)
- [Section 3 vs. Sections 5.1, 5.3.1, 6.1] The paper explicitly states in Section 3 that normalizing U^c_n to 1 is 'not applicable in our context' because it changes the argument of g(log z). Yet the algorithmic and theoretical core silently assumes U^c_n=1: Eq. (4) in Section 5.1, the bounds L_n and U_n in Section 5.3.1, the constraint z_n = sum_i x_i V_ni + 1 in Proposition 2, the proof of Theorem 5, the constraint (13) in MILP-2, and the proof of Theorem 7 all set z_n = 1 + sum_i x_i V_ni. Consequently, (IA-MILP) and MILP-2 approximate the objective q_n g(log z)(z-1)/z + alpha_n log z rather than the stated q_n g(log z)(z-U^c_n)/z + alpha_n log z. The N-epsilon guarantee of Theorem 5 is proved only for the normalized problem. Since the experiments sample competitor sets S_c randomly, U^c_n is generally not 1, so the reported PIA results may solve a different optimization problem. This is load-bearing: the headline algorithmic guarantee for ME-MCP with general U^c_n is not established. The fix is to replace 1 by U^c_n throughout (and adjust L_n, U_n accordingly), or to explicitly restrict the problem to U^c_n=1.
- [Appendix A.1, Theorem 1] The proof of Theorem 1 concludes that g'(log z) - g(log z) <= g'(0) - g(0) <= 0 by arguing that this difference is decreasing in z. For a decreasing function, however, the inequality at z=1 only gives the desired conclusion for z >= 1; for z < 1 the function is larger than at z=1, not smaller. In fact the theorem as stated is false without a z>=1 assumption: for g(t)=1-e^{-t}, U^c_n=0.5, and z=0.6, the first term H(z)=g(log z)(z-U^c_n)/z equals (z-1)(z-0.5)/z^2 and has H''(0.6)=9.26>0, so even with alpha_n=0 the claimed concavity fails. Since z = U^c_n + sum_i V_ni can be below 1 when utilities are negative (e.g., v_ni = -theta c_ni with large distances), the model needs an explicit domain restriction z_n >= 1 (or t=log z in the domain of g) or a corrected concavity condition.
- [Section 6.1, MILP-2] The piecewise-linear representation in MILP-2 is internally inconsistent. The text states that 'any z in [L_n,U_n] can be expressed as z_n = sum_k (c^k_{n+1}-c^k_n) r^k_n', omitting the offset L_n; the correct representation is z_n = L_n + sum_k (c^k_{n+1}-c^k_n) r^k_n. The two constraints in MILP-2, sum_k (c^k_{n+1}-c^k_n) r^k_n = sum_i x_i V_ni + 1 and z_n = sum_k (c^k_{n+1}-c^k_n) r^k_n, together imply z_n = sum_i x_i V_ni + 1 and also z_n = z_n - L_n, so L_n must be 0, which contradicts the earlier definition L_n = 1 + sum of the C smallest V_ni. As written, MILP-2 is not a well-defined approximation of ME-MCP, and the equivalence argument in the proof of Theorem 7 does not repair this inconsistency.
- [Appendix A.2, Theorem 2] The proof of submodularity in Theorem 2 defines z^A_n = 1 + sum_{i in A} V_ni and z^B_n = 1 + sum_{i in B} V_ni, again silently setting U^c_n=1 even though the theorem statement allows general U^c_n. Additionally, the sentence 'since Psi_n(z_n) is concave, Psi'_n(z_n) <= 0' is incorrect: concavity implies the derivative is nonincreasing, not nonpositive. The inequality Psi'(z^A_n) >= Psi'(z^B_n) that follows is correct for concave functions (with z^A_n <= z^B_n), but the stated justification should be corrected, and the proof should be written with general U^c_n.
minor comments (7)
- [Section 3] In the compact ME-MCP display, 'z_n = U^c_n + sum_i x_i V_ni 1' contains a stray '1'; it should read 'z_n = U^c_n + sum_i x_i V_ni'.
- [Section 5.1] The outer-approximation text contains notation slips: 'Phi(z_n) <= Psi_n(z_n) + Psi'_n(z_n)(z_n - z_n)' should use a generic point, e.g., 'Psi_n(z) <= Psi_n(\bar z) + Psi'_n(\bar z)(z - \bar z)', and 'Phi' should be 'Psi'.
- [Section 6.1] The sentence 'if Psi_n(z_n) is concave, we show in Appendix B that one can use methods similar to those described in Subsection 5.3.2' should refer to the convex case; Appendix B is explicitly for convex functions, and the preceding sentence already handled concave intervals.
- [Section 6.1, MILP-2] The variable declaration 'r_nk, z_n in [0,1]' is incorrect for z_n; z_n is a continuous variable ranging in [L_n,U_n], and only the weights r_nk are in [0,1].
- [Appendix A.6, proof of Theorem 6] The midpoint gap used to derive the lower bound in (32)-(33) is (c^k_{n+1}-c^k_n)^2/8 times |Psi''(c)|, not /4; the constant in the lower-bound formula for K_n should be adjusted accordingly. This does not affect the qualitative O(1/sqrt(epsilon)) statement.
- [Section 7.1] The text says 'we set the trade-off parameter lambda to 1', but no lambda is defined in the model; the customer-centric weights are alpha_n, so the sentence should either define lambda or refer to alpha_n.
- [Theorem 6, item (ii)] The statement that 'since Psi_n(z) is strictly concave in z, both L^Psi_n and U^Psi_n take positive values' is imprecise: for a strictly concave function Psi''<0, an upper bound on Psi'' is typically negative, and the intended objects are bounds on |Psi''|.
Circularity Check
No circular derivation; concavity, submodularity, and inner-approximation bounds are proved from assumptions. The U_c^n=1 inconsistency is a correctness gap, not circularity.
full rationale
No load-bearing circular step was found. Theorem 1 obtains concavity of Ψ_n from the stated assumptions on g by direct second-derivative computation (Appendix A.1); Theorem 2 derives submodularity from that concavity via the mean value theorem; Corollary 1 invokes Nemhauser et al. (1978), an external result. The inner-approximation guarantees (Theorems 5 and 7) are standard error-bound arguments: they compare the approximated objective eF = Σ Γ_n with the true F, use Γ_n ≤ Ψ_n (inner approximation), and apply triangle inequality; the bound |F−F*| ≤ Σ max|Ψ_n−Γ_n| is proved, not assumed. Breakpoint optimality (Theorem 6) is proved by contradiction using monotonicity of Λ_n; Theorem 8's relaxation proof constructs an adjusted solution and uses concavity on the relevant intervals. No fitted parameter is later called a prediction. Self-citations (Mai and Lodi 2020; Dam et al. 2021/2022/2023; Le et al. 2024) appear in the literature review and as baseline methods; the core theorems do not rest on their conclusions. The notable internal inconsistency is non-circular: footnote 1 says normalizing U_c^n to 1 is 'not applicable in our context as it would affect the total expected utility U_n^c + Σ_{i∈S} V_ni,' yet IA-MILP (Proposition 2), the proof of Theorem 5, MILP-2, and MILP-3 all impose z_n = Σ_i x_i V_ni + 1. Theorems 5 and 7 are therefore proved for the normalized model, not for the general ME-MCP with U_c^n ≠ 1 as stated. This is a modeling/validity gap rather than a circular reduction: the MILP does not encode the same objective it claims to approximate, but the error bounds are genuine derivations from the normalized formulation.
Assumptions & free parameters
free parameters (3)
- customer-centric weights alpha_n =
lambda=1 reported in experiments; alpha_n otherwise unspecified
- market expansion parameters (alpha, beta) =
g(t)=1-e^{-t} in concave tests; g(t)=1/(1+e^{-5(t-4)}) in non-concave tests
- approximation tolerance epsilon =
0.01 in main comparisons; swept from 1e-5 to 1.0 in Section 7.2
assumptions (5)
- domain assumption Customers choose facilities according to the Multinomial Logit model with utilities v_ni + epsilon_ni
- domain assumption Market expansion function g is nondecreasing and concave in t, with g(0)-g'(0)<=0 in the concave regime
- domain assumption In the general regime, g is twice differentiable and Psi_n'' has finitely many zeros in [L_n,U_n]
- ad hoc to paper The algorithm sections assume U^c_n=1 for all n
- standard math Standard results on submodular functions and greedy approximation (Nemhauser et al. 1978)
Cite this review
Pith. "Pith review of Competitive Facility Location with Market Expansion and Customer-centric Objective." pith.science (2026). https://pith.science/paper/EP6R25Q3
@misc{pith2026241217021,
author = {Pith},
title = {Pith review of: Competitive Facility Location with Market Expansion and Customer-centric Objective},
year = {2026},
howpublished = {\url{https://pith.science/paper/EP6R25Q3}},
note = {Machine review of arXiv:2412.17021}
}
abstract
We study a competitive facility location problem, where customer behavior is modeled and predicted using a discrete choice random utility model. The goal is to strategically place new facilities to maximize the overall captured customer demand in a competitive marketplace. In this work, we introduce two novel considerations. First, the total customer demand in the market is not fixed but is modeled as an increasing function of the customers' total utilities. Second, we incorporate a new term into the objective function, aiming to balance the firm's benefits and customer satisfaction. Our new formulation exhibits a highly nonlinear structure and is not directly solved by existing approaches. To address this, we first demonstrate that, under a concave market expansion function, the objective function is concave and submodular, allowing for a $(1-1/e)$ approximation solution by a simple polynomial-time greedy algorithm. We then develop a new method, called Inner-approximation, which enables us to approximate the mixed-integer nonlinear problem (MINLP), with arbitrary precision, by an MILP without introducing additional integer variables. We further demonstrate that our inner-approximation method consistently yields lower approximations than the outer-approximation methods typically used in the literature. Moreover, we extend our settings by considering a\textit{ general (non-concave)} market-expansion function and show that the Inner-approximation mechanism enables us to approximate the resulting MINLP, with arbitrary precision, by an MILP. To further enhance this MILP, we show how to significantly reduce the number of additional binary variables by leveraging concave areas of the objective function. Extensive experiments demonstrate the efficiency of our approaches.
Figures
Reference graph
Works this paper leans on
-
[1]
= Ψn(t1) − Ψn(a) t1 − a = Θn(t1); Ψ ′ n(ta
-
[2]
= Ψn(t2) − Ψn(a) t2 − a = Θn(t2), The above remark implies that Λn(t1|a) = Ψn(ta
-
[3]
− Ψn(a) − Ψn(t1) − Ψn(a) t1 − a (ta 1 − a) = Ψn(ta
-
[4]
− Θn(t1)(ta 1 − a) − Ψa(a) = Ψn(ta
-
[5]
− Ψ′ n(ta 1)(ta 1 − a) − Ψa(a) (30) Λn(t2|a) = Ψn(ta
-
[6]
− Ψn(a) − Ψn(t2) − Ψn(a) t2 − a (ta 2 − a) = Ψn(ta
-
[7]
− Θn(t2)(ta 2 − a) − Ψa(a) = Ψn(ta
-
[8]
− Ψ′ n(ta 2)(ta 2 − a) − Ψa(a) (31) Moreover, we observe that, since Θ n(t) is (strictly) decreasing in t, Ψ′ n(ta
Show all 21 references
-
[9]
Combine this with the fact that Ψ ′ n(t) is (strictly) decreasing in t, we have ta 1 < ta
> Ψ′ n(ta 2). Combine this with the fact that Ψ ′ n(t) is (strictly) decreasing in t, we have ta 1 < ta
-
[10]
t we get U ′(t) = Ψ′ n(t) − Ψ′ n(t) − Ψ ′′ n(t)(t − a) (b) > 0, ∀t > a where (b) is because Ψ ′′ n(t) < 0 (it is strictly concave in t)
To prove that Λn(t2|a) > Λn(t1|a), let us consider the following function: U (t) = Ψn(t) − Ψ′ n(t)(t − a) Taking the first-order derivative of U (t) w.r.t. t we get U ′(t) = Ψ′ n(t) − Ψ′ n(t) − Ψ ′′ n(t)(t − a) (b) > 0, ∀t > a where (b) is because Ψ ′′ n(t) < 0 (it is strictly...
-
[11]
Inner-approximation
< U(ta 2) Combine this with (30) and (31) we get Λ n(t1|a) < Λn(t2|a) as desired. A.6 Proof of Theorem 6 Proof. To prove (i), by contradiction let us assume that max k∈[K] Λn(c′ k+1|c′ k) ≤ ϵ (denoted as Assumption (A) for later reference). Under this assumption, let us choose...
2015
-
[12]
= Ψn(t1) − Ψn(a) t1 − a = eΘn(t1); Ψ ′ n(ta
-
[13]
= Ψn(t2) − Ψn(a) t2 − a = eΘn(t2), 45 The above remark implies that eΛn(t1|a) = Ψn(a) + Ψn(t1) − Ψn(a) t1 − a (ta 1 − a) − Ψn(ta
-
[14]
+ eΘn(t1)(ta 1 − a) + Ψa(a) = −Ψn(ta
-
[15]
+ Ψ′ n(ta 1)(ta 1 − a) + Ψa(a) (41) eΛn(t2|a) = −Ψn(ta
-
[16]
+ Ψn(a) + Ψn(t2) − Ψn(a) t2 − a (ta 2 − a) = −Ψn(ta
-
[17]
+ eΘn(t2)(ta 2 − a) + Ψa(a) = −Ψn(ta
-
[18]
+ Ψ′ n(ta 2)(ta 2 − a) + Ψa(a) (42) Moreover, since eΘn(t) is (strictly) increasing in t, Ψ′ n(ta
-
[19]
Combine this with the fact that Ψ ′ n(t) is (strictly) increasing in t, we have ta 1 < ta
< Ψ′ n(ta 2). Combine this with the fact that Ψ ′ n(t) is (strictly) increasing in t, we have ta 1 < ta
-
[20]
t we get U ′(t) = −Ψ′ n(t) + Ψ′ n(t) + Ψ ′′ n(t)(t − a) (b) > 0, ∀t > a where (b) is because Ψ ′′ n(t) > 0 (it is strictly convex in t)
To prove that eΛn(t2|a) > eΛn(t1|a), let us consider the following function: U (t) = Ψ′ n(t)(t − a) − Ψn(t) Taking the first-order derivative of U (t) w.r.t. t we get U ′(t) = −Ψ′ n(t) + Ψ′ n(t) + Ψ ′′ n(t)(t − a) (b) > 0, ∀t > a where (b) is because Ψ ′′ n(t) > 0 (it is stric...
-
[21]
Thanks to the assertions in Lemma 3, we can derive the breakpoints cn 1 ,
< U(ta 2) Combine this with (41) and (42) we get eΛn(t1|a) < eΛn(t2|a) as desired. Thanks to the assertions in Lemma 3, we can derive the breakpoints cn 1 , . . . , cn Kn following a procedure akin to that outlined in Section 5.3.2. Initially, we set the first point as cn 1 = ...
Reviewed August 11, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.