REVIEW 4 minor
Investigating mixed-integer programming approaches for the $p$-$\alpha$-closest-center problem
T0 review · 0 major / 4 minor · reviewed 2026-07-14 · grok-4.5
Pith's one-line read 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.
desk verdict Solid first exact treatment of a natural robust p-center variant; the formulations, polyhedral comparisons and 17 certified optima are real and usable. 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 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.
What would settle it
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.
Extended reading notes
Core claim
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.
Load-bearing premise
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.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
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).
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.
minor comments (4)
- 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 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.
- 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.
- 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.
Circularity Check
No significant circularity; all MIP formulations, polyhedral relations, lifting characterizations and optimality certificates are derived self-containedly from first principles.
full rationale
The paper introduces four MIP formulations of the newly defined pαCCP, proves LP-relaxation relationships (Proposition 17) and semi-relaxation exactness (Proposition 18) by direct feasible-solution mappings, and characterises the fixed points of its iterative lifting procedures as the optimal values of ordinary fractional α-set-cover LPs (Theorems 21, 24, 32). Those LPs are defined independently of the original pαCCP optimum; the iteration simply solves them. The branch-and-cut algorithm that certifies 17 optima never relies on the iterative procedures for its certificates—it separates only the extended lifted inequalities (20) at the root together with ordinary CPLEX branching. Self-citations to the authors’ earlier p-centre and α-neighbour papers supply reusable separation and lifting techniques that are re-proved in full for the present setting; they are not load-bearing premises. No fitted parameters, self-definitional identities, uniqueness theorems imported from prior work, or ansatzes appear. The derivation chain is therefore free of circular reduction.
Assumptions & free parameters
assumptions (3)
- domain assumption Distances dij ≥ 0 for all customer-facility pairs; the input sets I and J are finite.
- domain assumption Exactly p facilities may be opened (cardinality constraint).
- standard math Linear programming duality and strong duality for the separation and dual set-cover LPs.
invented entities (2)
-
p-α-closest-center problem (pαCCP)
-
Four MIP formulations (F1)–(F3-V) together with their lifted inequalities
Cite this review
Pith. "Pith review of Investigating mixed-integer programming approaches for the $p$-$\alpha$-closest-center problem." pith.science (2026). https://pith.science/paper/CWOQC2BP
@misc{pith2026260313214,
author = {Pith},
title = {Pith review of: Investigating mixed-integer programming approaches for the $p$-$\alpha$-closest-center problem},
year = {2026},
howpublished = {\url{https://pith.science/paper/CWOQC2BP}},
note = {Machine review of arXiv:2603.13214}
}
abstract
In this work, we introduce and study the $p$-$\alpha$-closest-center problem ($p\alpha$CCP), which generalizes the $p$-second-center problem, a recently emerged variant of the classical $p$-center problem. In the $p\alpha$CCP, we are given sets of customers and potential facility locations, distances between each customer and potential facility location as well as two integers $p$ and $\alpha$. The goal is to open facilities at $p$ of the potential facility locations, such that the maximum $\alpha$-distance between each customer and the open facilities is minimized. The $\alpha$-distance of a customer is defined as the sum of distances from the customer to its $\alpha$ closest open facilities. If $\alpha$ is one, the $p\alpha$CCP is the $p$-center problem, and for $\alpha$ being two, the $p$-second-center problem is obtained, for which the only existing algorithm in literature is a variable neighborhood search (VNS). We present four mixed-integer programming (MIP) formulations for the $p\alpha$CCP, strengthen them by adding valid and optimality-preserving inequalities and conduct a polyhedral study to prove relationships between their linear programming relaxations. Moreover, we present iterative procedures for lifting some valid inequalities to improve initial lower bounds on the optimal objective function value of the $p\alpha$CCP and characterize the best lower bounds obtainable by this iterative lifting approach. Based on our theoretical findings, we develop a branch-and-cut algorithm (B&C) to solve the $p\alpha$CCP exactly. We improve its performance by a starting and a primal heuristic, variable fixings and separating inequalities. In our computational study, we investigate the effect of the various ingredients of our B&C on benchmark instances from related literature. Our B&C is able to prove optimality for 17 of the 40 instances from the work on the VNS heuristic.
Reviewed July 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.