{"id":"30c1ed86-283b-4354-b626-c8fdad68f53c","arxiv_id":"2412.15608","paper_version":1,"verdict":"REJECT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"high","formal_verification":"none","parameter_count":4,"one_line_summary":"A two-stage robust model with dynamic service placement and an autoregressive uncertainty set, solved by an iterative decomposition claimed to be exact.","lead":"This paper develops a two-stage robust optimization model for edge service placement where demand uncertainty follows spatio-temporal correlation patterns. It proposes a decomposition algorithm claimed to solve the resulting tri-level problem exactly, which could help service providers cut operating costs.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Extreme-point optimality of worst-case demand is unsupported for MILP recourse, so the claimed finite exact convergence of ROD is not established.","rationale":"The reader's weakest assumption is exactly the extreme-point condition, and I agree it is load-bearing. The paper's central contribution is an algorithm that provably solves a tri-level ARO with integer recourse exactly in finite iterations. The proof of Prop IV.2 depends on D2 having finitely many extreme points and on the worst-case lambda being among them; otherwise the cuts added to the outer master only cover a subset of potentially optimal scenarios. The assertion that worst-case occurs at g=+/-1 would be true if the second-stage value function were convex in lambda. For fixed (q,z), the LP value function is convex, and its maximum over a polytope is at an extreme point. But the recourse minimizes over (q,z), producing the minimum of many convex functions; this lower envelope is generally nonconvex and its maximum can be strictly interior. This invalidates the proof of exactness and the algorithm's global convergence guarantee. The reference [4] addresses continuous recourse, so it cannot justify the integer-recourse case. I also noted a secondary error: the McCormick envelope stated before (27) is not the convex hull of delta=g*sigma (e.g., for g=1 it forces delta=-sigma), which would make the Inner-MP an incorrect relaxation even if the extreme-point assumption held. The numerical experiments do not mitigate this, since they only report convergence to a fixed gap on random instances, not verification against a global optimum. A small counterexample would settle the issue.","tokens_in":22814,"tokens_out":11855,"duration_ms":105361,"concrete_test":"Build a one-time-slot, two-AP, one-EN instance with a fixed service placement cost so that the second-stage value function is V(lambda)=min(c1*lambda1 + F, c2*lambda2 + F), with D2 defined by g in [-1,1] and |g1|+|g2|<=1. Compute the true maximum of V over D2 by brute-force enumeration of all (q,z) and by global optimization; compare with the maximum over the extreme points of D2. If the true maximum occurs at an interior point (e.g., g=(0.5,0.5)), the extreme-point equivalence (18) is false. Then run ROD on this instance; if it converges to the extreme-point value rather than the true optimum, the exactness claim is demonstrably incorrect.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The proof of exact finite convergence (Prop. IV.2) and the equivalence to (18) require that the worst-case demand for the second-stage MILP is an extreme point of the uncertainty set D2. The paper asserts this before eq. (26): 'the worst-case scenarios can be achieved when g is either -1 or 1 [4]'. This is valid only when the recourse value function is convex in the uncertain parameters, as in continuous LP recourse, where maximizing a convex function over a polytope attains at a vertex. Here the recourse contains binary variables z and q, so the value function is the minimum of finitely many convex (LP) value functions, which is generally nonconvex. Maximizing a nonconvex function over a polytope does not in general attain at an extreme point; it can occur in the interior. The citation to [4] does not cover integer recourse. Consequently, the finite enumeration over extreme points in (18) may omit the true worst case, the inner-loop generated lambda* may be interior, and the claim that repeated extreme points imply optimality fails. The central exactness result is therefore unsupported.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper proposes a two-stage multi-period robust optimization model for edge service placement and resource reservation under demand uncertainty. The first stage decides resource reservations before demand is known, while the second stage chooses dynamic service placement, service download, resource adjustment, and workload allocation after observing demand. The uncertainty is modeled by a dynamic set D2 that incorporates spatio-temporal correlation through a multivariate autoregressive structure. Because the second-stage problem contains binary recourse variables, the paper develops an iterative decomposition algorithm called ROD, which alternates between an outer master problem and an inner max-min subproblem, and claims finite convergence to an exact optimal solution of the tri-level problem P1. Numerical experiments compare the proposed D-ARO-DUS model against static uncertainty-set and static placement benchmarks.","tokens_in":23099,"tokens_out":12768,"duration_ms":122949,"significance":"The modeling direction is relevant and timely: dynamic service placement with integer recourse and a data-driven spatio-temporal uncertainty set addresses a practically important gap in edge service placement. The numerical study is extensive, uses real traffic traces, reports runtimes, and includes sensitivity analyses. However, the paper's central theoretical contribution, namely the claim that ROD converges finitely to an exact optimum, is not established. The proof relies on an extreme-point optimality property that is false in general for mixed-integer recourse, and the McCormick linearization used in the inner master problem is mis-specified. If the exactness claim cannot be repaired, the algorithm remains a heuristic, and the paper's main advertised advantage over existing decomposition methods is unsupported.","major_comments":[{"comment":"The assertion that 'the worst-case scenarios can be achieved when g is either -1 or 1 [4]' is not valid for the mixed-integer recourse problem considered here. For fixed first-stage decisions, the inner value function Q(ŝ,λ) = min_{q,z,x,y} cost is the minimum of finitely many convex LP value functions and is therefore generally nonconvex in λ. Maximizing a nonconvex function over a polytope need not attain its maximum at an extreme point. Monotonicity in λ does not rescue the argument: a nondecreasing concave function such as Q(λ)=min{λ1,λ2}, which can arise as a binary-choice recourse value function, attains its maximum at the interior point (1/2,1/2) on the face conv{(1,0),(0,1)}. The citation to [4] concerns continuous recourse, not integer recourse. Consequently, the equivalence between P1 and the finite enumeration in (18) is not established, and the finite-convergence proof of Proposition IV.2, which assumes that each iteration generates a new extreme point of D2, does not cover the true worst case. This is a load-bearing gap for the paper's main exactness claim.","section":"Section IV-C, equations after (26) and (27i)"},{"comment":"The displayed set M(δ,g,σ) is claimed to be the convex hull of the bilinear set {(δ,g,σ): δ=σg, g∈[-1,1], σ∈[0,M]}, but the inequalities given do not describe that convex hull. For example, with g=1 and σ=1, the constraints δ ≥ -σ - M(1-g) and δ ≤ -σ + M(1-g) force δ = -1, whereas the true relation δ=σg gives δ = 1. Similarly, for g=-1 the constraints do not force δ=-σ. The standard McCormick convex hull for this set includes the constraints δ ≥ M g + σ - M and δ ≤ M g - σ + M, among others; the paper's formulation is not equivalent. Since Inner-MP in (27) relies on this linearization to produce an MILP reformulation of Q(ŝ), the inner master problem is not a valid exact reformulation, and the upper bounds produced by Step 2 of Algorithm 2 are not trustworthy. This error directly affects the numerical results produced by the ROD algorithm.","section":"Section IV-E, proof of Proposition IV.2"},{"comment":"The proof of Proposition IV.2 states that 'D2 is a finite set with K elements' and bounds the number of iterations by K, the number of extreme points of D2. This is a category error: D2 is a convex polytope with infinitely many points; it has only finitely many extreme points. More importantly, the proof assumes without support that the λ produced by the inner loop is always an extreme point of D2. If the true worst-case demand is interior, the algorithm may add cuts for non-extreme points that do not appear in the enumerated set D*, and the finite-repetition argument cannot be applied. Thus, even if the extreme-point property held for the continuous-relaxation case, the proof as written would still not establish finite exact convergence for the integer-recourse problem.","section":"Section IV-E, proof of Proposition IV.2"}],"minor_comments":[{"comment":"Equation (33b) appears to have two typos: the term should be Σ_{s=1}^L A_s^i λtilde_i^{t-s}, not Σ_{s=1}^L A_s^i λtilde_i^t, and the B_i g_i^t term that appears in (16b) is missing here. Please align the two definitions.","section":"Section V-B, Eq. (33b)"},{"comment":"In the Inner-SP constraints, the demand constraint should sum workload over edge nodes j, i.e., x_{i,0}^t + Σ_j x_{i,j}^t ≥ λ_i^{t,*}; the displayed expression sums over i, which is inconsistent with (10).","section":"Section IV-C, Eq. (23d)"},{"comment":"The sentence 'the network delay between AP i and the cloud is denoted bywe di,0' contains a typo ('bywe').","section":"Section III-A, paragraph after Fig. 2"},{"comment":"Several citations use 'el at.' instead of 'et al.', for example in the sentences citing [8], [9], [11], and [18]; the reference list itself should also be checked for consistent formatting.","section":"Section II and Introduction"},{"comment":"The first-stage constraints are indexed by l in (19c), although s is a single first-stage decision common to all cuts. This makes the formulation ambiguous; either the index should be removed or the notation should be clarified so that s is not replicated per cut.","section":"Section IV-B, Eq. (19c)"},{"comment":"The comparison between D-ARO-DUS and D-ARO-SUS in the α-sweep is not fully explained: it is unclear how the manually adjusted deviation α relates to the parameters of the dynamic uncertainty set, and whether the comparison holds the amount of information used by both models equal. A short explanation would improve reproducibility.","section":"Section V-D, Figs. 11(a)-(b)"}],"recommendation":"reject","confidential_remarks":"For the editor: I found no indication of circular reasoning or fabrication; the numerical work appears honestly reported. The obstacle is technical: the paper's central exactness theorem rests on an extreme-point assertion that is false for MILP recourse, and the bilinear linearization used in the algorithm is incorrect. These are not presentation issues, and the second is easily verifiable from the text. The modeling contribution is useful, and a resubmission that either proves the extreme-point property for this specific recourse structure or weakens the claim to a heuristic with numerical validation on small instances could be reconsidered."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"The headline: this is a genuinely new model wrapped around an exactness claim that does not actually hold as proven. The model contribution is real; the algorithm proof is the soft spot.\n\nWhat's actually new: dynamic service placement with binary recourse inside a two-stage robust optimization with an autoregressive spatio-temporal uncertainty set. I don't know of prior work combining those two. The cost model (reservation, buy-more/sell-back, placement, download, delay) is sensible, and the time series estimation from Shanghai Telecom traces is a solid data-driven touch. The numerical comparisons against static uncertainty and static placement show consistent cost reductions, so the empirical case is at least suggestive.\n\nWhere it gets shaky: the proof of finite exact convergence (Prop. IV.2) depends on the worst-case demand being an extreme point of D2. That's true when the second-stage value function is convex in λ, which is the continuous-recourse case. Here the second stage has binary variables, so the value function is the minimum of finitely many LP value functions and is generally nonconvex. A global maximum of a nonconvex function over a polytope can lie strictly inside a face, so the enumeration over extreme points in (18) can miss it. The citation to [4] does not cover integer recourse. This is not a cosmetic gap; it is the load-bearing part of the claimed exactness. Also, the McCormick relaxation in the inner master (the set Mδ,g,σ) is written incorrectly for δ = σg, and the text treats g as binary at one point while D2 defines it as continuous in [-1,1]. That needs cleanup.\n\nOne more thing: the paper does not appear to be circular. AR parameters come from separate historical data, baselines are compared fairly, and no parameter is tuned to produce the savings. The runtime analysis is honest.\n\nOverall: this is a paper for the robust-optimization and edge-computing community. The model will attract citations if the proof is repaired. Right now, my recommendation is to send it to peer review with a clear signal that the exactness theorem must either be fixed or downgraded to 'practical convergence.' If the authors can prove the extreme-point property under a restricted class (or handle interior optima with a valid-inequality strategy), the paper would be solid. As is, the abstract overstates.","headline":"Genuinely new model combining dynamic placement with an autoregressive uncertainty set, but the finite exact convergence claim for ROD is not proven because the worst-case MILP-recourse demand need not be an extreme point of D2.","tokens_in":23541,"tokens_out":3587,"would_cite":true,"duration_ms":31678,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90C15","90C47","90C90"],"pacs":[],"model":"deepseek-v4-flash","headline":"This paper claims that a two-stage robust edge service placement problem with integer recourse variables can be solved exactly by an iterative decomposition algorithm with finite convergence, and that dynamic spatio-temporal uncertainty…","keywords":["edge service placement","adjustable robust optimization","integer recourse","dynamic uncertainty set","spatio-temporal correlation","workload allocation","column-and-constraint generation","finite convergence"],"falsifier":"Solve a one-period, one-EN, two-AP instance of the inner problem with $\\Gamma=1$, so the uncertainty set is a line segment between two extreme demands, and place the service-placement cost so that placing or not placing the service is optimal exactly at an interior demand value; if the worst-case value occurs at that interior point rather than at an endpoint, ROD's repeated-extreme-point argument no longer applies to that instance.","tokens_in":22630,"feed_emoji":"📡","tokens_out":5025,"duration_ms":33043,"temperature":0.7,"pith_summary":"This paper claims that edge service providers can reserve computing resources for an entire planning horizon while keeping the right to move services and buy or sell capacity after demand is observed, and that this flexibility is worth the added computational difficulty. The authors formulate the problem as a two-stage multi-period adjustable robust optimization with binary service-placement variables in the second stage, producing a tri-level min-max-min program with integer recourse. They prove that their iterative decomposition algorithm, ROD, converges to an exact optimal solution in a finite number of iterations. If the claim holds, service providers can use spatio-temporal demand correlations to shrink the uncertainty set and lower operating costs without sacrificing worst-case service guarantees.","feed_headline":"Exact algorithm solves robust edge placement under correlated demand","feed_subtitle":"Dynamic uncertainty set and integer recourse yield lower-cost edge operations with a finite convergence guarantee.","key_machinery":"The two load-bearing objects are the dynamic uncertainty set $\\mathcal{D}_2$ and the ROD decomposition. $\\mathcal{D}_2$ models the demand deviation at each access point as a multivariate auto-regressive process of order $L$ with a spatial coupling term, so the set of possible future demands shrinks as historical deviations are revealed; this is what makes the robust solution less conservative. ROD splits the tri-level problem into an outer column-and-constraint generation loop over the extreme points of $\\mathcal{D}_2$ and an inner loop that handles the binary service-placement and download variables. The inner loop's master problem is reformulated into a single-level MILP using strong duality for the continuous recourse and McCormick envelopes for the bilinear products between dual variables and demand deviations. The convergence argument rests on $\\mathcal{D}_2$ being a compact convex polytope with finitely many extreme points: any repeated extreme point forces the upper and lower bounds to coincide.","core_discovery":"The central claim is that a two-stage robust edge service placement problem with integer recourse variables can be solved exactly, not just approximately, by decomposing it into an outer loop over extreme demand scenarios and an inner loop that iteratively enumerates the binary placement decisions that matter. Given first-stage resource reservation $s$, the inner loop alternates between a mixed-integer subproblem that fixes the worst-case demand and a master problem that finds the next worst-case demand by strong duality and McCormick linearization; when the inner loop finishes it returns a true worst-case demand and cost for that $s$. The outer loop then adds this demand as a cut to the reservation master problem and repeats. The paper proves this terminates finitely, bounded by the number of extreme points of the dynamic uncertainty set, and that at termination the reservation decision is optimal for the original tri-level problem. The paper further claims that using a dynamic uncertainty set built from an auto-regressive model of demand, rather than a static polyhedral set, reduces conservatism and total cost in numerical experiments with real demand traces.","pith_inferences":["An implication the authors do not pursue is that the same outer/inner decomposition applies to other two-stage robust problems with binary recourse, such as facility location or network function placement, whenever the uncertainty set is a polytope with integer budget.","The extreme-point assumption before eq. (26) is the step we would test first: if a worst-case demand can occur inside a face of $\\mathcal{D}_2$ when the binary placement decision changes there, the finite-convergence proof would need an additional argument beyond repeated extreme points.","One could calibrate $\\mathcal{D}_2$ online from streaming demand and re-run ROD at each re-optimization horizon; the convergence guarantee would still hold per instance, and the value of updating the auto-regressive coefficients could be measured empirically.","A direct comparison with distributionally robust or stochastic benchmarks would quantify how much of the cost saving comes from the correlation structure versus from the integer-recourse dynamic placement itself; the paper separates these only partially through the D-ARO-SUS benchmark."],"forward_implications":["Service providers can plan day-ahead resource reservations that are provably optimal under the modeled uncertainty, not just heuristic.","Dynamic service placement, where services are downloaded from nearby edge nodes after demand is known, becomes computationally tractable despite binary recourse variables.","Using spatio-temporal correlations systematically reduces the uncertainty set and lowers total cost relative to static uncertainty sets at the same robustness budget.","The algorithm's runtime depends on network size and uncertainty budget, and the paper reports that a looser optimality gap for large networks cuts runtime substantially.","The model extends to multiple resource types and additional placement constraints, as the authors note."],"supporting_citations":[{"why":"Supplies the two-stage robust edge service placement and sizing model that serves as the static benchmark S-ARO.","marker":"[3]"},{"why":"Shows why strong duality is preferred over KKT for the inner reformulation and provides the resilience-aware robust model this work builds on.","marker":"[4]"},{"why":"Column-and-constraint generation is the outer-loop template for iterating over extreme demand scenarios.","marker":"[7]"},{"why":"McCormick envelopes linearize the bilinear terms between dual variables and demand deviations in the inner master problem.","marker":"[25]"},{"why":"The multivariate time-series techniques used to estimate the auto-regressive coefficients and spatial covariance for the dynamic uncertainty set.","marker":"[30]"}],"fun_headline_variants":["Exact algorithm solves robust edge placement under correlated demand","Robust edge placement: exact solution via iterative decomposition","Dynamic uncertainty sets enable exact robust edge placement","Finite convergence guaranteed for robust edge placement algorithm","Exact two-stage robust edge placement with integer recourse"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The worst-case demand for the second-stage problem with binary service-placement decisions is assumed to occur at an extreme point of the dynamic uncertainty set, even though the second-stage value function is not convex in demand.","fun_headline_variants_meta":{"raw":{"variants":["Exact algorithm solves robust edge placement under correlated demand","Robust edge placement: exact solution via iterative decomposition","Dynamic uncertainty sets enable exact robust edge placement","Finite convergence guaranteed for robust edge placement algorithm","Exact two-stage robust edge placement with integer recourse"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000641,"raw_usage":{"total_tokens":2949,"prompt_tokens":942,"completion_tokens":2007,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":558,"completion_tokens_details":{"reasoning_tokens":1934}},"tokens_in":558,"tokens_out":2007,"duration_ms":12218,"temperature":1.0,"reasoning_tokens":1934,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-11T11:18:40.721709+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Solve a one-period, one-EN, two-AP instance of the inner problem with $\\Gamma=1$, so the uncertainty set is a line segment between two extreme demands, and place the service-placement cost so that placing or not placing the service is optimal exactly at an interior demand value; if the worst-case value occurs at that interior point rather than at an endpoint, ROD's repeated-extreme-point argument no longer applies to that instance.","supporting_citations":[{"cited_title":"Two-stage robust edge service placement and sizing under demand uncertainty,","cited_arxiv_id":null,"evidence_quote":"Supplies the two-stage robust edge service placement and sizing model that serves as the static benchmark S-ARO."},{"cited_title":"Resilient edge service placement under demand and node failure uncertainties,","cited_arxiv_id":null,"evidence_quote":"Shows why strong duality is preferred over KKT for the inner reformulation and provides the resilience-aware robust model this work builds on."},{"cited_title":"Solving two-stage robust optimization problems using a column-and-constraint generation method,","cited_arxiv_id":null,"evidence_quote":"Column-and-constraint generation is the outer-loop template for iterating over extreme demand scenarios."},{"cited_title":"Computability of global solutions to factorable nonconvex programs: Part i—convex underestimating problems,","cited_arxiv_id":null,"evidence_quote":"McCormick envelopes linearize the bilinear terms between dual variables and demand deviations in the inner master problem."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"The multivariate time-series techniques used to estimate the auto-regressive coefficients and spatial covariance for the dynamic uncertainty set."}],"review_version":1}