{"id":"a48864b3-8e2f-4535-a052-cf4a4d8d221a","arxiv_id":"2411.13758","paper_version":1,"verdict":"ACCEPT","confidence":"HIGH","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"For the MTZ, Desrochers-Laporte, and single-commodity flow formulations, the paper defines parametric families and proves their closures form a strict chain, with the flow closure being strongest.","lead":"This paper introduces parameterized families of three classic integer programming formulations for the asymmetric traveling salesman problem, and computes the strongest formulation obtained by taking all parameter choices at once. It proves a strict hierarchy among these combined formulations, which clarifies which compact formulation should be preferred.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"No significant objection identified; the strict closure hierarchy and explicit formulations are supported by the proofs.","rationale":"The reader's ACCEPT is justified. I independently re-derived the key validity argument: for d in D, the cycle-sum condition bounds every simple path in A1 because any path can be closed by an arc back to its start, so normalized potentials with M=1 exist for every tour; the analogous flow for b in B is obtained by sending the unit of commodity along the tour. The closure characterizations are consistent, and the strictness constructions in Proposition 33 work: each constructed point is in the larger closure because the only cycles in C1 in its support are the designated cycle, its reverse, and 2-cycles, all of which satisfy the relevant inequalities. The n=4 special case is handled by Observation 10. No step in the proof of Corollary 34 appears unsupported. I noted a minor typo in Proposition 19's displayed inequalities, but it is not used in the main argument, so it does not affect the verdict.","tokens_in":25105,"tokens_out":42548,"duration_ms":367606,"concrete_test":"Take the n=6 instance, S={2,3,4,5}, and check the point constructed in Prop. 33.5 satisfies every P_DL inequality from Theorem 24; if it does, the strict inclusion Cl(PSCF(B)) ⊊ Cl(PDL(D)) underpinning Cor. 34 is confirmed.","verdict_should_be":"UNCHANGED","load_bearing_attack":"No load-bearing concern identified. The central claim (Cor. 34) rests on the characterization of D and B as exactly the parameter sets for which the normalized M=1 constraints are valid. I checked this premise: for any tour, assigning potentials as accumulated sums along the tour makes every d-MTZ constraint hold precisely because each path segment plus its closing arc is a cycle in C1, so the cycle-sum bound d(C) <= 1 supplies the needed slack; the same reasoning covers d-DL, and the b-SCF flow exists by sending the unit of flow along the tour and splitting it according to b. The closure computations (Thms 17, 24, 31) are internally consistent, and the strictness constructions in Prop. 33 satisfy the relevant inequalities for all cycles in C1; the n=4 collapse to 2-cycle constraints is correct. The only blemish I found is a swapped right-hand side in the displayed statement of Prop. 19 (the two DL convex-hull inequalities should have RHS 1-d_ij and 1-d_ji respectively, not the reverse); this is a typo and is not used in the closure proofs.","agreement_with_reader":"agree"},"referee_report":{"model":"deepseek-v4-flash","summary":"The paper introduces parametric generalizations of the MTZ, Desrochers–Laporte, and single-commodity-flow formulations of the ATSP: d-MTZ, d-DL, and b-SCF, with parameter sets D and B chosen so that the normalized M=1 constraints define valid ATSP formulations. For each family it computes the projection onto the x-variables (Propositions 12, 20, 27), gives facet characterizations, establishes generic incomparability of different parameter choices, and characterizes the closure of each family: Cl(P_MTZ(D)) is the circuit polytope (Theorem 17), Cl(P_DL(D)) is a lifted-circuit formulation (Theorem 24), and Cl(P_SCF(B)) is the DFJ cut formulation (Theorem 31). The main conclusion is Corollary 34: for n≥5 the closures form the strict hierarchy P_SCF ⊂ P_DL ⊂ P_DL(VMTZ) ⊂ P_MTZ.","tokens_in":25260,"tokens_out":34360,"duration_ms":370724,"significance":"If the main results hold, the paper provides a clean theoretical classification of three classical parametric ATSP formulations and shows that the SCF closure is strictly the strongest. The treatment is largely self-contained: the projection results rely on a clean difference-constraint lemma, the closure computations use small, explicitly identified subsets of the parameter polytope rather than its NP-hard vertex set, and the final hierarchy is supported by explicit separating points. The paper also gives explicit finite ILP descriptions for all three closures, recovering DFJ, RMTZ, and MCF as limiting cases. These are concrete, checkable contributions rather than purely existential statements. The central closure results appear to me to be correct; the main issues are localized to secondary comparison statements.","major_comments":[{"comment":"Proposition 22 is false as stated for n=4. When n=4, Propositions 20 and 21 together with Observation 10 imply that PDL(d) is simply {x ∈ PAP : x_ij + x_ji ≤ 1 for all ij ∈ A1}, independent of d. Take, for example, d ∈ D sufficiently small and δ defined by δ_23 = δ_34 = δ_42 = ε with ε < 1/3, so that d + δ ∈ D and the 3-cycle sum of δ is nonzero; then PDL(d) = PDL(d + δ), contradicting the asserted incomparability. The proof also invokes Proposition 21 for the cycle Ĉ, although that proposition requires |Ĉ| ≤ n − 2 while the hypothesis only gives |Ĉ| ≥ 3. The result can be repaired by adding the assumption n ≥ 5 and by using the fact that a nonzero cycle sum for an anti-symmetric δ implies a nonzero 3-cycle sum, so that a cycle of length at most n − 2 with nonzero δ-sum exists; this repair needs to be made explicitly in the text.","section":"§4.3, Proposition 22"}],"minor_comments":[{"comment":"In the displayed statement of Proposition 19 the two right-hand sides are swapped: the first inequality should have right-hand side 1 − d_ij and the second should have right-hand side 1 − d_ji. This is a typo and does not affect the later closure proofs.","section":"§4.1, Proposition 19"},{"comment":"In the proof of Proposition 29, the argument involving S = {2,3} proves PSCF(b′) ⊄ PSCF(b), not PSCF(b) ⊄ PSCF(b′). The missing direction follows from the set S′ by taking a point on the facet of PSCF(b) and observing that it violates the tighter inequality of PSCF(b′); the proposition’s conclusion is true, but the proof as written needs this correction.","section":"§5.2, Proposition 29"},{"comment":"In the proof of Theorem 24, the displayed identity 'Cl(PDL(D)) = Cl(PDL(D))' should read 'Cl(PDL(D)) = Cl(PDL(\\bar D))' (or an equivalent statement using the closure of D).","section":"§4.4, Theorem 24"},{"comment":"In part 5 of Proposition 33, the violated clique inequality is written with right-hand side |Č| − 1, but since the sum is over A(S) the right-hand side should be |S| − 1; the two are numerically equal when |S| = |Č|, but the notation should be made consistent.","section":"§6, Proposition 33(5)"}],"recommendation":"major_revision","confidential_remarks":"I agree with the reader that the closure results and the proof of Corollary 34 are sound. The reason I recommend major revision rather than acceptance is Proposition 22, which is false as stated for n=4 and has a proof gap even for larger n. The fix appears local—restrict to n≥5 and state the needed 3-cycle argument—so I expect the revision to be straightforward, but the current published statement cannot stand as written."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nThis is a solid theory paper and the reader's ACCEPT is right. What's new: the authors define parametric families of MTZ, DL, and SCF formulations, compute their projections, and characterize the closures. Corollary 34 -- for n≥5, Cl(PSCF(B)) ⊊ Cl(PDL(D)) ⊊ Cl(PDL(VMTZ)) ⊊ Cl(PMTZ(D)) -- is a genuine result that organizes known equivalences (RMTZ, L1RMTZ, MCF, DFJ) into one hierarchy. The proofs are mostly detailed and the projection formulas are explicit.\n\nThe paper does well by being self-contained and careful with validity conditions. The sets D and B are exactly the right parameter domains for the normalized M=1 constraints; the stress-test check on the cycle-sum slack is correct. The paper also honestly flags the n=4 special case and the technical condition in Prop. 22.\n\nSoft spots are minor. The MTZ closure result is not deeply surprising given Padberg-Sung's projection formula; the real work is in the DL and SCF closures and the strictness constructions. There is a typo in the displayed statement of Prop. 19: the two RHS constants are swapped (should be 1-d_ij and 1-d_ji). It is only in the statement, not used later, but should be fixed. A few other typos: 'PSCF(d)' in the intro, 'd' vs 'b' in Section 5.2 discussion. The proof of Theorem 24's reverse inclusion is compressed; a referee should ask for a slightly expanded argument. No computational experiments, but the paper does not claim them; the final remarks sketch a dynamic parameter-selection scheme without testing it, which is fine for an IP theory paper.\n\nWho is this for? Researchers working on ATSP formulations and extended formulations. It is not a breakthrough in the sense of resolving an open question or offering a new algorithm, but it gives a useful map and a clean hierarchy. I would cite it. The citation pattern is appropriate, no self-citation issues. I'd send it to a serious referee.","headline":"Solid theory paper that maps the parametric MTZ/DL/SCF formulation families and proves a clean closure hierarchy; worth a serious referee.","tokens_in":25811,"tokens_out":3583,"would_cite":true,"duration_ms":889185,"reading_group":"yes","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["90C27","90C10","90C57"],"pacs":[],"model":"deepseek-v4-flash","headline":"The paper proves that the closures of the parametric MTZ, DL, and SCF families of ATSP formulations coincide with three classic polyhedra and, for n ≥ 5, are strictly ordered from strongest SCF to weakest MTZ.","keywords":["asymmetric traveling salesman problem","parametric formulations","closure","MTZ formulation","DL formulation","single-commodity flow","extended formulations","polyhedral combinatorics"],"falsifier":"Fix $n = 5$ and let $C$ be the directed 3-cycle $2 \\to 3 \\to 4 \\to 2$. Set $x_{ij} = 2/3$ on the arcs of $C$, $x_{ji} = 1/3$ on the three reverse arcs, $x_{15} = x_{51} = 1$, and all other $x$ entries $0$. Corollary 34 predicts this point lies in $\\operatorname{Cl}(P_{\\mathrm{MTZ}}(D))$ but violates the inequality $\\sum_{ij \\in C}(x_{ij} + x_{ji}) - x_{24} - x_{32} \\le 2$ that defines $\\operatorname{Cl}(P_{\\mathrm{DL}}(V_{\\mathrm{MTZ}}))$; computing the LP membership of this one point in the four closures would immediately refute the strict-chain claim if the predicted pattern fails.","tokens_in":24879,"feed_emoji":"🧮","tokens_out":14348,"duration_ms":141317,"temperature":0.7,"pith_summary":"The classic MTZ, DL, and SCF formulations of the asymmetric traveling salesman problem each carry constants — potential scale for MTZ and DL, demand vector for SCF — that are fixed by convention but can be varied while keeping the formulation valid. The paper treats these constants as free parameters, defines the closure of each family as the intersection of all resulting relaxations, and gives an exact linear description of each closure. The MTZ closure is the circuit-inequality polytope, the DL closure is a lifted-circuit polytope, and the SCF closure is the DFJ cut polytope. For $n \\ge 5$ the closures form a strict chain, with the SCF closure the smallest (strongest) and the MTZ closure the largest (weakest), and for $n = 4$ they coincide. This settles how much strength each classical formulation can attain by tuning its free parameters.","feed_headline":"Strongest ATSP relaxation comes from the SCF closure","feed_subtitle":"Intersecting every choice of free parameters in three classic ATSP formulations yields a strict strength order.","key_machinery":"The load-bearing tool is a projection lemma that converts potential-difference constraints $u_i - u_j \\le \\beta_{ij}$ into cycle inequalities: after eliminating the $u$ variables, every directed cycle $C$ yields one inequality obtained by summing the right-hand sides around $C$. This is applied to d-MTZ and d-DL, while for SCF the projection uses Gale's flow theorem to produce cut inequalities. The second central mechanism is a robust-optimization observation: the closure of a family over all parameters in a polytope equals the closure over the vertices of that polytope, so the continuum of choices $d \\in D$ or $b \\in B$ reduces to finitely many extreme parameter vectors. The paper identifies small vertex subsets — $V_{\\mathrm{MTZ}} = \\{d^k : k \\in N_1\\}$, $V_{\\mathrm{DL}} = \\{d^{kl} : kl \\in A_1\\}$, and $V_{\\mathrm{SCF}} = \\{b^k : k \\in N_1\\}$ — that already generate the full closures, and it verifies the normalized inequalities themselves through convex-hull computations on local two-arc polytopes.","core_discovery":"On the paper's own terms, let $D = \\{d > 0 : \\sum_{ij \\in C} d_{ij} \\le 1 \\text{ for every directed cycle } C\\}$ and $B = \\{b > 0 : \\sum_{i \\in N_1} b_i = 1\\}$. For every $d \\in D$, the normalized d-MTZ inequalities $u_i - u_j + d_{ij} \\le 1 - x_{ij}$ and the d-DL inequalities $u_i - u_j + x_{ij} + (1 - d_{ij} - d_{ji})x_{ji} \\le 1 - d_{ij}$ give valid ATSP formulations, and for every $b \\in B$ the b-SCF flow system with demands $b$ gives a valid formulation. The central discovery is that the closures of these families have explicit polyhedral descriptions: $\\operatorname{Cl}(P_{\\mathrm{MTZ}}(D))$ is the circuit-inequality polytope $\\{x \\in P_{\\mathrm{AP}} : \\sum_{ij \\in C} x_{ij} \\le |C| - 1 \\text{ for all cycles } C\\}$, $\\operatorname{Cl}(P_{\\mathrm{DL}}(D))$ is the lifted-circuit system $\\{x \\in P_{\\mathrm{AP}} : \\sum_{ij \\in C}(x_{ij} + x_{ji}) - x_{lk} \\le |C| - 1 \\text{ for all } C \\text{ with } |C| \\ge 3 \\text{ and } kl \\in C,\\ x_{ij} + x_{ji} \\le 1\\}$, and $\\operatorname{Cl}(P_{\\mathrm{SCF}}(B))$ is the DFJ cut polytope $\\{x \\in P_{\\mathrm{AP}} : \\sum_{ij \\in \\delta^+(S)} x_{ij} \\ge 1 \\text{ for all } S \\subseteq N_1,\\ |S| \\ge 2\\}$. Consequently the closures are strictly ordered for $n \\ge 5$: $\\operatorname{Cl}(P_{\\mathrm{SCF}}(B)) \\subsetneq \\operatorname{Cl}(P_{\\mathrm{DL}}(D)) \\subsetneq \\operatorname{Cl}(P_{\\mathrm{DL}}(V_{\\mathrm{MTZ}})) \\subsetneq \\operatorname{Cl}(P_{\\mathrm{MTZ}}(D))$.","pith_inferences":["Beyond the paper's final remarks, a practical reading is that a solver could start from one parameter vector and add constraints from additional parameter vectors only when they cut off the current fractional point; the closure is reached exactly when the current point survives every parameter choice. The paper sketches such a dynamic scheme but does not implement it.","The strict polyhedral chain does not by itself say how often the gap matters for integer solutions; a natural experiment is to compare the four closures on random ATSP instances and measure how much each inclusion changes the optimum of the linear relaxation.","Since separating over the full parameter polytope $D$ is NP-hard, the easy vertex sets $V_{\\mathrm{MTZ}}$, $V_{\\mathrm{DL}}$, and $V_{\\mathrm{SCF}}$ may be the only computationally practical way to realize the closures, rather than merely a convenient choice."],"forward_implications":["For $n \\ge 5$, the strength order of the closures is strict: $\\operatorname{Cl}(P_{\\mathrm{SCF}}(B)) \\subsetneq \\operatorname{Cl}(P_{\\mathrm{DL}}(D)) \\subsetneq \\operatorname{Cl}(P_{\\mathrm{DL}}(V_{\\mathrm{MTZ}})) \\subsetneq \\operatorname{Cl}(P_{\\mathrm{MTZ}}(D))$, so the SCF family is the only one whose closure reaches the DFJ cut polytope.","Every single member of a parametric family is at best as strong as its closure, and the closures can be realized by the small vertex sets $V_{\\mathrm{MTZ}}$, $V_{\\mathrm{DL}}$, and $V_{\\mathrm{SCF}}$, each of which yields an explicit integer linear extended formulation for the ATSP.","For $n = 4$ the four closures coincide, so the parametric distinctions only become visible from five nodes upward.","The MTZ closure is exactly the circuit-inequality polytope, the same as the RMTZ reformulation, while the full DL closure is a lifted-circuit system that is strictly stronger than the L1RMTZ reformulation for $n \\ge 5$."],"supporting_citations":[{"why":"Supplies the robust-optimization lemma (Lemma 2) that the closure over a parameter polytope equals the closure over its vertices, which reduces the infinite intersections to finite vertex sets.","marker":"[4]"},{"why":"Defines the DFJ cut and clique inequalities that the SCF closure $\\operatorname{Cl}(P_{\\mathrm{SCF}}(B))$ recovers exactly in Theorem 31.","marker":"[5]"},{"why":"Defines the Desrochers-Laporte formulation that the d-DL family parameterizes and lifts.","marker":"[6]"},{"why":"Gale's flow theorem gives the cut description of $P_{\\mathrm{SCF}}(b)$ in Proposition 27, on which the SCF closure proof rests.","marker":"[7]"},{"why":"Defines the single-commodity flow formulation that the b-SCF family generalizes.","marker":"[8]"},{"why":"Introduces the RMTZ and L1RMTZ reformulations used to identify $\\operatorname{Cl}(P_{\\mathrm{MTZ}}(D))$ with the circuit polytope and $\\operatorname{Cl}(P_{\\mathrm{DL}}(V_{\\mathrm{MTZ}}))$ with the lifted-circuit system.","marker":"[9]"},{"why":"Defines the Miller-Tucker-Zemlin formulation that the d-MTZ family parameterizes.","marker":"[10]"},{"why":"Provides the weak circuit and weak clique projections of MTZ and SCF that the parametric families generalize.","marker":"[12]"},{"why":"Is the spirit of the projection lemma (Lemma 9) that eliminates potential variables to obtain cycle inequalities for d-MTZ and d-DL.","marker":"[13]"}],"fun_headline_variants":["SCF closure beats MTZ and DL in ATSP strength","ATSP: SCF closure equals DFJ cuts, top relaxation","Closure of SCF family yields strongest ATSP formulation","No single ATSP formulation beats the SCF closure"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The load-bearing premise is that scaling the free constants to $M = 1$ is harmless: every valid normalized parameter must lie in $D$ (positive arc weights with cycle sums at most $1$) or $B$ (positive demands summing to $1$), and every parameter in those sets keeps the constraints valid for every tour.","fun_headline_variants_meta":{"raw":{"variants":["SCF closure beats MTZ and DL in ATSP strength","ATSP: SCF closure equals DFJ cuts, top relaxation","Closure of SCF family yields strongest ATSP formulation","No single ATSP formulation beats the SCF closure"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000617,"raw_usage":{"total_tokens":3001,"prompt_tokens":1222,"completion_tokens":1779,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":838,"completion_tokens_details":{"reasoning_tokens":1710}},"tokens_in":838,"tokens_out":1779,"duration_ms":12747,"temperature":1.0,"reasoning_tokens":1710,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-12T15:55:22.446747+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Fix $n = 5$ and let $C$ be the directed 3-cycle $2 \\to 3 \\to 4 \\to 2$. Set $x_{ij} = 2/3$ on the arcs of $C$, $x_{ji} = 1/3$ on the three reverse arcs, $x_{15} = x_{51} = 1$, and all other $x$ entries $0$. Corollary 34 predicts this point lies in $\\operatorname{Cl}(P_{\\mathrm{MTZ}}(D))$ but violates the inequality $\\sum_{ij \\in C}(x_{ij} + x_{ji}) - x_{24} - x_{32} \\le 2$ that defines $\\operatorname{Cl}(P_{\\mathrm{DL}}(V_{\\mathrm{MTZ}}))$; computing the LP membership of this one point in the four closures would immediately refute the strict-chain claim if the predicted pattern fails.","supporting_citations":[{"cited_title":"Robust Optimization, volume 28 of Princeton Series in Applied Mathematics","cited_arxiv_id":null,"evidence_quote":"Supplies the robust-optimization lemma (Lemma 2) that the closure over a parameter polytope equals the closure over its vertices, which reduces the infinite intersections to finite vertex sets."},{"cited_title":"Solution of a large-scale traveling-salesman problem","cited_arxiv_id":null,"evidence_quote":"Defines the DFJ cut and clique inequalities that the SCF closure $\\operatorname{Cl}(P_{\\mathrm{SCF}}(B))$ recovers exactly in Theorem 31."},{"cited_title":"Improvements and ext ensions to the Miller-Tucker-Zemlin subtour elimination constraints","cited_arxiv_id":null,"evidence_quote":"Defines the Desrochers-Laporte formulation that the d-DL family parameterizes and lifts."},{"cited_title":"A theorem on flows in networks","cited_arxiv_id":null,"evidence_quote":"Gale's flow theorem gives the cut description of $P_{\\mathrm{SCF}}(b)$ in Proposition 27, on which the SCF closure proof rests."},{"cited_title":"The travelling salesman pro blem and related problems","cited_arxiv_id":null,"evidence_quote":"Defines the single-commodity flow formulation that the b-SCF family generalizes."},{"cited_title":"The asymmetric travelling sale sman problem and a re- formulation of the Miller-Tucker-Zemlin constraints","cited_arxiv_id":null,"evidence_quote":"Introduces the RMTZ and L1RMTZ reformulations used to identify $\\operatorname{Cl}(P_{\\mathrm{MTZ}}(D))$ with the circuit polytope and $\\operatorname{Cl}(P_{\\mathrm{DL}}(V_{\\mathrm{MTZ}}))$ with the lifted-circuit system."},{"cited_title":"Integer progr amming formulation of traveling salesman problems","cited_arxiv_id":null,"evidence_quote":"Defines the Miller-Tucker-Zemlin formulation that the d-MTZ family parameterizes."},{"cited_title":"An analytical comparison o f different formulations of the travelling salesman problem","cited_arxiv_id":null,"evidence_quote":"Provides the weak circuit and weak clique projections of MTZ and SCF that the parametric families generalize."},{"cited_title":"Short combinatorial proof that the DFJ poly tope is contained in the MTZ polytope for the asymmetric traveling salesman problem","cited_arxiv_id":null,"evidence_quote":"Is the spirit of the projection lemma (Lemma 9) that eliminates potential variables to obtain cycle inequalities for d-MTZ and d-DL."}],"review_version":1}