{"id":"2abf46a1-e0c1-48d4-93c4-bda3270d7f32","arxiv_id":"2412.17021","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":3,"one_line_summary":"A competitive facility location problem with market expansion and a customer-satisfaction term is submodular under concave expansion, and a new inner-approximation method approximates it by MILPs with bounded error.","lead":"The paper models a facility-location game where adding facilities grows the whole market and also raises customer satisfaction, then offers algorithms with proven near-optimality guarantees. It introduces an inner-approximation scheme that turns the resulting nonconvex problem into a mixed-integer linear program with controlled error.","discovery_kind":"new_method","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Silent normalization U^c_n=1 in all MILP formulations and Theorem 5 means the presented inner-approximation solves a different problem than the stated ME-MCP with general competitor utilities.","rationale":"The paper's central contributions are (1) concavity/submodularity of the stated objective under g(0)-g'(0) ≤ 0, yielding a greedy (1-1/e) guarantee, and (2) an inner-approximation MILP with arbitrary precision. The concavity proof in Appendix A.1 is sound for general U^c_n: the key inequalities use z ≥ U^c_n and the condition on g, and they hold. The submodularity proof in Appendix A.2 has a genuine typo (it says Ψ'_n(z_n) ≤ 0, which is false; the intended statement is non-increasing) and the mean-value argument needs care about the ordering of the MVT points, but the result itself follows directly from concavity: for a concave function, f(x+d)-f(x) is non-increasing in x, so F(A∪{j}) - F(A) ≥ F(B∪{j}) - F(B) whenever A ⊆ B. Thus the submodularity claim is fixable and not the main threat. The truly load-bearing concern is the silent replacement of U^c_n by 1 in every MILP formulation. This is not a mere notational choice: Section 3 explicitly states that the standard normalization is invalid here because g(log z) is nonlinear. When U^c_n ≠ 1, the objective being maximized by (IA-MILP) and MILP-2 is different from the stated ME-MCP objective, and the Nε bound in Theorem 5 is proved for the wrong problem. The experiments use non-unit U^c_n, so the numerical evidence for PIA's superiority and near-optimality does not establish the claim for the problem the paper defines. This concern is fixable by replacing '1' with U^c_n throughout the MILP derivations and re-running the experiments, but as written the mismatch invalidates the main algorithmic guarantee. The reader's verdict is CONDITIONAL, and this concern supports that verdict; therefore no change to the verdict is needed.","tokens_in":32913,"tokens_out":9796,"duration_ms":85440,"concrete_test":"Take a single HM14 instance (e.g., N=50, m=25) with the published utility generation: v_ni = -θ c_ni for candidate sites and competitor utilities v^c_ni = -γθ c_ni for a randomly sampled S_c with |S_c| = ceil(m/10). Compute U^c_n = sum_{j in S_c} exp(v^c_nj) per customer. Solve (IA-MILP) exactly as printed (z_n = 1 + sum_i x_i V_ni) and the corrected version with z_n = U^c_n + sum_i x_i V_ni, using identical breakpoints and epsilon = 0.01. Compare the returned facility sets and the true F(S) values on the original ME-MCP. If the sets differ or the true F values differ by more than a numerical tolerance, the printed MILP does not solve the stated ME-MCP and Theorem 5's guarantee does not cover the experiments.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central algorithmic guarantee is for the ME-MCP with z_n = U^c_n + Σ_i x_i V_ni, and Section 3 explicitly warns that normalizing U^c_n to 1 is 'not applicable in our context' because it changes the argument of g(log z). Despite this, every MILP formulation silently replaces U^c_n by 1: Section 5.1 rewrites the problem with z_n = 1 + Σ x_i V_ni; Section 5.3.1 defines bounds L_n, U_n with '1 + ...' and Proposition 2 (IA-MILP) imposes z_n = Σ x_i V_ni + 1; the proof of Theorem 5 uses the same constraint; and MILP-2 in Section 6.1 again uses Σ x_i V_ni + 1. Consequently, (IA-MILP) and MILP-2 approximate the objective Ψ_n(z) = q_n g(log z)(z-1)/z + α_n log z rather than the stated Ψ_n(z) = q_n g(log z)(z-U^c_n)/z + α_n log z. The error bound in Theorem 5, |F(z) - F*| ≤ Nε, is proved only for this normalized problem and does not carry over to the stated ME-MCP when U^c_n ≠ 1. The experiments use randomly sampled competitor sets S_c, so U^c_n is not 1, meaning the reported PIA results may be for a different optimization problem. This is a load-bearing mismatch between the problem definition and the solution method, not a cosmetic normalization.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":33231,"tokens_out":14430,"duration_ms":123143,"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":[{"comment":"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.","section":"Section 3 vs. Sections 5.1, 5.3.1, 6.1"},{"comment":"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":"Appendix A.1, Theorem 1"},{"comment":"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.","section":"Section 6.1, MILP-2"},{"comment":"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.","section":"Appendix A.2, Theorem 2"}],"minor_comments":[{"comment":"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":"Section 3"},{"comment":"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":"Section 5.1"},{"comment":"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":"Section 6.1"},{"comment":"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].","section":"Section 6.1, MILP-2"},{"comment":"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":"Appendix A.6, proof of Theorem 6"},{"comment":"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.","section":"Section 7.1"},{"comment":"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''|.","section":"Theorem 6, item (ii)"}],"recommendation":"major_revision","confidential_remarks":"The paper's core modeling contribution is promising, but the disconnect between the general problem statement and the normalized formulations/algorithms is substantial and must be closed. The z<1 counterexample to Theorem 1 also needs a careful fix, e.g., an explicit domain assumption. I would not recommend rejection, as the issues appear addressable by correcting the formulations and proofs, but the current manuscript is not acceptable as is."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Two things you should know about arXiv:2412.17021. First, the paper is genuinely new: it adds market expansion (demand grows with the logsum) and a customer-satisfaction term to the competitive facility location problem, shows concavity and submodularity under a concave expansion function, and builds a piecewise-linear 'inner approximation' MILP with an error bound. The submodularity result and the Theorem 4 inner-vs-outer comparison are real contributions, and the non-concave extension with relaxed binaries is a practical touch.\n\nSecond, the paper has a load-bearing internal inconsistency. The problem is defined with z_n = U^c_n + sum_i x_i V_ni, and a footnote explicitly says normalizing U^c_n to 1 is not allowed because it changes the argument of g(log z). But every algorithmic section does exactly that: Section 5.1, Proposition 2, Theorem 5, MILP-2, Theorem 7, and the appendix proofs all replace z_n by 1 + sum_i x_i V_ni. The bounds L_n, U_n, the breakpoints, and the error guarantee N*epsilon are all computed for the normalized problem, so the theorems do not apply to the stated ME-MCP when U^c_n differs from 1. The experiments sample competitor sets, so U^c_n is not 1; the reported PIA numbers are for a different objective. This is fixable by replacing 1 with U^c_n throughout, but it is not cosmetic.\n\nThere are two smaller issues worth naming. Theorem 6 claims L^Psi_n and U^Psi_n are positive bounds on the second derivative of Psi_n; for a strictly concave function that derivative is non-positive, so the bounds need absolute values or a sign flip. The proof uses |Psi''| but the statement does not. In the Theorem 2 proof, the line 'Psi'_n(z_n) <= 0' is false as written; what is needed is that Psi' is non-increasing, which is true for concave Psi, so the submodularity argument survives after that correction. Also, several cross-references are still 'Theorem ??' or 'Section []', fine for a preprint but sloppy.\n\nBottom line: the core math is largely sound and the flaws are fixable, but the normalization mismatch must be resolved before the algorithms can be trusted as solving the stated problem. Give it a serious referee; major revision.","headline":"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.","tokens_in":33760,"tokens_out":4476,"would_cite":true,"duration_ms":39511,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90B80","90C11","90C26"],"pacs":[],"model":"deepseek-v4-flash","headline":"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…","keywords":["competitive facility location","market expansion","customer satisfaction","submodularity","greedy approximation","inner-approximation","mixed-integer linear programming","random utility model"],"falsifier":"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.","tokens_in":32685,"feed_emoji":"📍","tokens_out":5629,"duration_ms":42633,"temperature":0.7,"pith_summary":"This paper studies a competitive facility-location problem where adding facilities grows the entire market rather than just redistributing a fixed pool of customers, and where the firm also values customer utility, not only captured demand. Its central claim is that when the market-expansion function is concave and satisfies $g(0)-g'(0)\\le 0$, the objective is monotone and submodular, so a greedy algorithm that adds the best single location at each step returns a $(1-1/e)$-approximation. The paper then introduces an inner-approximation method: replace each concave component of the objective by a piecewise-linear function lying below it, which yields a MILP with no extra binary variables and an error bound of at most $N\\epsilon$. For general non-concave expansion functions the same idea yields a MILP with some extra binary variables, and the paper shows how to relax many of those binaries on intervals where the objective is concave. If correct, this provides the first guaranteed near-optimal methods for a dynamic-market variant that fixed-market techniques could not handle.","feed_headline":"Greedy siting now carries a (1-1/e) guarantee","feed_subtitle":"A concave market-growth model makes the objective submodular and turns the problem into one clean MILP.","key_machinery":"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$.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"Formulates the classical maximum capture problem under MNL random utilities, the baseline this paper extends with market expansion and customer utility.","marker":"Benati and Hansen, 2002"},{"why":"Supplies the multicut outer-approximation approach and the fixed-market state-of-the-art that serves as the OA comparator.","marker":"Mai and Lodi, 2020"},{"why":"Provides the $(1-1/e)$ guarantee for maximizing monotone submodular set functions, which yields Corollary 1.","marker":"Nemhauser et al., 1978"},{"why":"Establishes the outer-approximation framework whose cuts the paper contrasts with inner approximation and adapts for the concave case.","marker":"Duran and Grossmann, 1986"},{"why":"Introduces concave market-expansion demand functions that this paper generalizes to the RUM log-sum utility setting.","marker":"Aboolian et al., 2007a"},{"why":"Shows submodularity and local search for maximum capture under GEV models, the closest prior structural result the paper extends to dynamic markets.","marker":"Dam et al., 2022"},{"why":"Provides the MNL/RUM modeling foundation, including expected consumer surplus as the log-sum, used throughout the formulation.","marker":"Train, 2009"}],"fun_headline_variants":["Concave market growth enables greedy (1-1/e) siting","Inner-approximation turns MINLP into MILP with precision","Submodular objective yields (1-1/e) facility location","Customer-centric siting with guaranteed approximation","MILP via inner approximation for competitive siting"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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.","fun_headline_variants_meta":{"raw":{"variants":["Concave market growth enables greedy (1-1/e) siting","Inner-approximation turns MINLP into MILP with precision","Submodular objective yields (1-1/e) facility location","Customer-centric siting with guaranteed approximation","MILP via inner approximation for competitive siting"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000261,"raw_usage":{"total_tokens":1662,"prompt_tokens":1080,"completion_tokens":582,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":696,"completion_tokens_details":{"reasoning_tokens":500}},"tokens_in":696,"tokens_out":582,"duration_ms":5160,"temperature":1.0,"reasoning_tokens":500,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T05:52:30.087984+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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.","supporting_citations":[],"review_version":1}