{"id":"05bc53ce-c77f-4eb0-8226-52ba10fd3948","arxiv_id":"2603.13214","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"Four MIP formulations, polyhedral comparisons, iterative lifting, and a branch-and-cut algorithm solve the p-α-closest-center problem exactly and certify optimality on 17 of 40 prior VNS instances.","lead":"The paper defines the p-α-closest-center problem and supplies the first exact MIP formulations plus a branch-and-cut solver for it and the p-second-center problem. Exact optima for robust facility placement under multi-facility failure risk become available for the first time on standard benchmarks.","discovery_kind":"extension","skeptic_critique":{"model":"grok-4.5","headline":"No significant objection identified","rationale":"The reader's overall ACCEPT / HIGH-confidence assessment is correct: the manuscript supplies the first exact treatment of a natural robust p-center variant, complete with formulations, polyhedral analysis, convergent lifting theory, and a working solver that closes 17 previously open instances. The only material limitations (no public code, many larger instances still open) are already acknowledged by the reader and do not undermine the central claim. The single weakest-assumption point raised by the reader concerns numerical tolerances inside the theoretical lifting loops of Sections 5-6. That observation is accurate but does not affect the implemented algorithm or the 17 optimality certificates, which rest on ordinary MIP solving of (F1) strengthened by the separated inequalities of Section 7. Hence the concern is real but non-load-bearing; the verdict remains ACCEPT with high confidence.","tokens_in":36492,"tokens_out":494,"duration_ms":5678,"concrete_test":"Re-run the 17 instances that Table 1 marks as optimally solved by 1HSL, forcing CPLEX to use a relative MIP gap of 1e-9 and an absolute gap of 1e-6; if every instance still reports the same UB = LB pair within the 1800 s limit, the certificates remain valid under tighter numerical tolerances.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The paper's central claim is that a B&C based on (F1) plus the described enhancements is the first exact method for pαCCP / pSCP and certifies optimality of the VNS solutions on 17 of the 40 p-median instances. All supporting pieces (formulations, polyhedral relations in Prop. 17 and Prop. 18, lifting characterizations in Thms. 21/24/32, and the tabulated computational results) are elementary MIP arguments or direct numerical evidence; none of them rests on an unstated or fragile assumption that would invalidate the claim if slightly perturbed. The reader's weakest-assumption remark about LP tolerances in the iterative lifting procedures is technically correct but non-load-bearing: the implemented B&C never relies on those iterative procedures for its optimality certificates (it uses only the extended lifted inequalities (20) separated at the root, together with ordinary CPLEX branching). Consequently the residual-gap worry does not threaten the 17 proven optima.","agreement_with_reader":"partial"},"referee_report":{"model":"grok-4.5","summary":"The paper introduces the p-α-closest-center problem (pαCCP), a natural generalization of the classical p-center problem (α=1) and the recently studied p-second-center problem (α=2). It supplies four MIP formulations (F1–F3-V), valid and optimality-preserving inequalities, a polyhedral comparison of their LP relaxations (Proposition 17) and semi-relaxations (Proposition 18), and iterative lifting schemes whose best attainable lower bounds are characterized via fractional α-set-cover LPs (Theorems 21, 24, 32). A branch-and-cut algorithm based on (F1), enhanced by variable fixing, cut separation, and heuristics, is shown to prove optimality for 17 of the 40 p-median instances previously attacked only by the VNS of Ristić et al. (2023b).","tokens_in":36724,"tokens_out":652,"duration_ms":5261,"significance":"The work supplies the first exact method for both the pαCCP and the p-second-center problem, together with a clean polyhedral analysis that relates the new formulations to one another and to classical set-cover ideas. The computational certificates of optimality for 17 previously open instances constitute a concrete advance. The lifting characterizations (Theorems 21, 24, 32) and the explicit feasible-solution mappings used in the polyhedral proofs are elementary but carefully executed MIP arguments; they give a solid theoretical foundation for the subsequent algorithmic development.","major_comments":[],"minor_comments":[{"comment":"In the abstract and introduction the phrase “minimizes the average distance” appears; the objective is in fact the maximum of the sum of the α closest distances. A single clarifying sentence would avoid possible confusion.","section":null},{"comment":"Section 7.1: the parameters maxNumSepRoot, maxNoImprovements, numLiftedCustomers, etc., are listed but never justified beyond “preliminary computations.” A short sensitivity table or a sentence on how they were chosen would improve reproducibility.","section":null},{"comment":"Tables 1–3 report many “–” entries for lower bounds under setting 1; a footnote explaining that the LP relaxation could not be solved within the time limit would make the tables self-contained.","section":null},{"comment":"A few typographical inconsistencies remain (e.g., “Morover” in the proof of Proposition 29, occasional missing spaces after commas in mathematical mode). A final proof-reading pass would remove them.","section":null}],"recommendation":"accept","confidential_remarks":"The manuscript is a solid, self-contained contribution that fits the journal well. The reader’s residual-gap remark about LP tolerances in the iterative lifting procedures is technically correct but non-load-bearing for the claimed optimality certificates, which rely only on the separated extended lifted inequalities and ordinary branching. I see no reason to withhold acceptance."},"author_rebuttal":null,"desk_editor":{"model":"grok-4.5","letter":"This is the first exact method for the p-α-closest-center problem (and therefore for the p-second-center problem). The four MIP models, the LP-dominance results (Prop. 17), the characterization of the lifted bounds via fractional α-set cover, and the branch-and-cut that certifies 17 of the 40 p-median instances previously attacked only by VNS are all new and cleanly executed.\n\nWhat works: the polyhedral arguments are elementary but careful (explicit mappings and dual arguments in Lemmas 12–16 and Theorems 21/24/32). The computational tables report every upper/lower bound, node count and runtime; the 17 optimality claims match the numbers. The starting heuristic plus variable fixing and the extended lifted cuts at the root are the ingredients that actually move the needle. The comparison with the 2023 VNS is fair and useful.\n\nSoft spots are minor and do not undercut the claims. The iterative lifting theory is elegant but the implemented B&C never relies on solving the fractional set-cover LPs to exact optimality at every iteration; it only separates the extended lifted inequalities (20) at the root. Larger instances still time out, and no code is released, but neither fact invalidates the 17 certificates or the polyhedral results. The paper stays inside discrete location science; impact outside that community is modest.\n\nAnyone working on robust or fault-tolerant facility location will want the formulations and the computational baseline. It is ready for a serious referee; I would accept it for peer review without hesitation.","headline":"Solid first exact treatment of a natural robust p-center variant; the formulations, polyhedral comparisons and 17 certified optima are real and usable.","tokens_in":37314,"tokens_out":410,"would_cite":true,"duration_ms":5594,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C11","90B80","90C57"],"pacs":[],"model":"grok-4.5","headline":"Four MIP formulations and a branch-and-cut algorithm solve the p-α-closest-center problem exactly, proving optimality for 17 of 40 prior VNS benchmarks.","keywords":["p-center problem","p-α-closest-center","mixed-integer programming","branch-and-cut","lifted inequalities","facility location","min-max objective"],"falsifier":"On any of the 40 p-median instances for which the branch-and-cut reports optimality, recompute the objective of the claimed optimal facility set by enumerating the α-distance of every customer; if that value exceeds the reported optimum, the claim is false.","tokens_in":37393,"feed_emoji":"📍","tokens_out":798,"duration_ms":7389,"temperature":0.7,"pith_summary":"The paper defines the p-α-closest-center problem: open exactly p facilities so that the largest sum of distances from any customer to its α nearest open facilities is minimized. When α equals 1 this recovers the classical p-center problem; when α equals 2 it recovers the recently studied p-second-center problem, for which only a heuristic was previously known. Four mixed-integer programming formulations are introduced, strengthened by valid and optimality-preserving inequalities, and compared through a polyhedral study that shows three of them share the same LP-relaxation strength while the fourth is weaker. Iterative lifting procedures that incorporate successive lower bounds are proved to converge to well-characterized fractional set-cover bounds. A branch-and-cut solver built on the strongest compact formulation, equipped with heuristics, variable fixing and cut separation, solves 52 of 93 literature instances to proven optimality and certifies the previously reported heuristic solutions for 17 of the 40 p-median instances.","feed_headline":"Exact solver certifies 17 of 40 p-second-center instances","feed_subtitle":"Four MIPs and iterative lifting turn a pure heuristic problem into a solvable integer program","key_machinery":"The four MIP formulations (F1)–(F3-V) together with the lifted inequalities (14) and (19) whose iterative application converges to the fractional α-set-cover radii LB♯3, LB♯3V and LB♯1.","core_discovery":"The p-α-closest-center problem admits four mixed-integer formulations whose linear-programming relaxations satisfy ν(F1-R)=ν(F2-R)=ν(F3-V-R)≥ν(F3-R), and whose semi-relaxations already recover the integer optimum. Iterative lifting of the assignment inequalities produces best lower bounds LB♯1=LB♯3V≥ LB♯3 that are exactly the critical radii of two fractional α-set-cover problems. A practical branch-and-cut algorithm based on formulation (F1) and these inequalities proves optimality for 17 of the 40 instances previously solved only heuristically.","pith_inferences":[],"forward_implications":[],"fun_headline_variants":["B&C with four MIPs certifies 17 of 40 p-α-closest-center instances","Iterative lifting plus branch-and-cut solves 17 former VNS-only cases","Four MIP formulations prove optimal for 17 of 40 p-α-center benchmarks","Valid inequalities and B&C turn pαCCP into 17 exact optima","Semi-relaxations recover integer optima for 17 of 40 p-second-center instances"],"cache_read_input_tokens":128,"weakest_assumption_plain":"The iterative lifting procedures reach their theoretically optimal lower bounds only when every intermediate fractional set-cover LP is solved to exact optimality; any numerical tolerance can leave a residual gap that is never closed.","fun_headline_variants_meta":{"raw":{"variants":["B&C with four MIPs certifies 17 of 40 p-α-closest-center instances","Iterative lifting plus branch-and-cut solves 17 former VNS-only cases","Four MIP formulations prove optimal for 17 of 40 p-α-center benchmarks","Valid inequalities and B&C turn pαCCP into 17 exact optima","Semi-relaxations recover integer optima for 17 of 40 p-second-center instances"]},"model":"grok-4.5","effort":"low","cost_usd":0.006932,"raw_usage":{"total_tokens":1846,"prompt_tokens":988,"num_sources_used":0,"completion_tokens":119,"cost_in_usd_ticks":69320000,"prompt_tokens_details":{"text_tokens":988,"audio_tokens":0,"image_tokens":0,"cached_tokens":128},"completion_tokens_details":{"audio_tokens":0,"reasoning_tokens":739,"accepted_prediction_tokens":0,"rejected_prediction_tokens":0}},"tokens_in":988,"tokens_out":119,"duration_ms":7058,"temperature":1.0,"reasoning_tokens":739,"cache_read_input_tokens":128,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-07-14T21:48:34.272125+00:00","model_set":{"reader":"grok-4.5"},"falsifier":"On any of the 40 p-median instances for which the branch-and-cut reports optimality, recompute the objective of the claimed optimal facility set by enumerating the α-distance of every customer; if that value exceeds the reported optimum, the claim is false.","supporting_citations":[],"review_version":1}