On parametric formulations for the Asymmetric Traveling Salesman Problem

Diego Moran; Gustavo Angulo

REVIEW 1 major objections 4 minor 15 references

On parametric formulations for the Asymmetric Traveling Salesman Problem

T0 review · 1 major / 4 minor · reviewed 2026-08-12 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read 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.

desk verdict Solid theory paper that maps the parametric MTZ/DL/SCF formulation families and proves a clean closure hierarchy; worth a serious referee. read the letter →

arxiv 2411.13758 v1 pith:RSQMF4AO submitted 2024-11-21 math.OC

Gustavo Angulo , Diego Moran This is my paper · ORCID

classification math.OC MSC 90C2790C1090C57

keywords asymmetrictravelingsalesmanproblemparametricformulationsclosureMTZformulationDLsingle-commodityflowextendedpolyhedralcombinatorics

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

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.

What carries the argument

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.

What would settle it

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.

Watch

Extended reading notes

Core claim

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))$.

Load-bearing premise

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.

Editorial extensions

If this is right

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$.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

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.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

Colleague,

This 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.

The 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.

Soft 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.

Who 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.

Referee Report

1 major / 4 minor

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.

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 (1)

[§4.3, Proposition 22] 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.

minor comments (4)

[§4.1, Proposition 19] 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.
[§5.2, Proposition 29] 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.
[§4.4, Theorem 24] 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).
[§6, Proposition 33(5)] 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.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the closure hierarchy is a genuine derivation from independent parameter-set definitions, not a reduction of conclusions to inputs.

full rationale

The paper's central claims, Corollary 34 and Theorems 17, 24, and 31, are derived rather than assumed. The parameter sets D and B are defined by validity conditions (cycle sums at most 1 for d, and demands summing to 1 for b), and these conditions are not the same as the closure inequalities that are eventually obtained. For example, Theorem 17 derives the circuit inequalities from the intersection over the d-MTZ formulations, whereas D itself is defined only by sum-over-cycles bounds on d; no circuit inequality appears in the definition of D. Likewise, Theorem 31 derives the DFJ cut formulation from the intersection over b-SCF formulations, even though B is merely the simplex of positive demands summing to 1. The projection arguments use standard linear-programming projection lemmas (Lemma 9 and Gale's flow theorem), and the closure computations are carried out explicitly by intersecting finitely many easy-to-identify parameter vectors, so no fitted parameter is later renamed as a prediction. There is no load-bearing self-citation: the cited prior work by other authors serves as external grounding for classical formulations and projection tools, and the authors' own parametric constructions are proven from scratch via disjunctive programming and projection. The strict separations in Proposition 33 are demonstrated by explicit fractional points, not by appealing to a uniqueness theorem. The only observed blemish is a swapped right-hand side in the displayed statement of Proposition 19, but that typo is not used in the closure derivations and does not affect the logical chain. Overall, the derivation is self-contained against external benchmarks, and the central results do not reduce by construction to their own inputs.

Assumptions & free parameters 0 free parameters · 6 assumptions · 0 invented entities

No free parameters are fitted to data; the paper is a purely theoretical polyhedral study. The only parameters are the variables d and b that index the formulation families, and they range over explicit polytopes D and B rather than being optimized to data. All proofs rely on standard results from polyhedral combinatorics, flow theory, and robust optimization cited in the paper. The parametric families are mathematical constructions, not postulated physical entities, so no invented entities appear.

assumptions (6)

standard math Gale's flow theorem: a feasible circulation exists iff all cut demands are satisfied.
Invoked in Proposition 27 to derive the cut formulation of PSCF(b).
standard math Disjunctive programming convex-hull representation of Balas.
Used in Propositions 11 and 19 to compute the convex hull of the two-arc gadgets for d-MTZ and d-DL.
standard math Robust optimization lemma: intersection over a parameter set equals intersection over its convex hull closure.
Used in Section 2.1 to replace open parameter sets D and B by their polytope closures when computing closures.
standard math Difference-constraint projection lemma for cycle inequalities.
Lemma 9 is the key tool projecting the d-MTZ and d-DL extended formulations onto x-space.
standard math Longest Hamiltonian cycle is NP-hard.
Used in Proposition 7 to prove separation over D is NP-hard; supports the remark that enumerating vertices of D is intractable.
domain assumption ATSP is modeled on a complete directed graph with node 1 as root and n at least 4.
Every formulation and closure result assumes this setting, stated at the start of Section 1.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On parametric formulations for the Asymmetric Traveling Salesman Problem." pith.science (2026). https://pith.science/paper/RSQMF4AO

@misc{pith2026241113758,
  author       = {Pith},
  title        = {Pith review of: On parametric formulations for the Asymmetric Traveling Salesman Problem},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/RSQMF4AO}},
  note         = {Machine review of arXiv:2411.13758}
}

read the original abstract

The traveling salesman problem is a widely studied classical combinatorial problem for which there are several integer linear formulations. In this work, we consider the Miller-Tucker-Zemlin (MTZ), Desrochers-Laporte (DL) and Single Commodity Flow (SCF) formulations. We argue that the choice of some parameters of these formulations is arbitrary and, therefore, there are families of formulations of which each of MTZ, DL, and SCF is a particular case. We analyze these families for different choices of the parameters, noting that in general the formulations involved are not comparable to each other and there is no one that dominates the rest. Then we define and study the closure of each family, that is, the set obtained by considering all the associated formulations simultaneously. In particular, we give an explicit integer linear formulation for the closure of each of the families we have defined and then show how they compare to each other.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 14 canonical work pages

[1]

The traveling salesman problem: a computational study , volume 17

David L Applegate. The traveling salesman problem: a computational study , volume 17. Princeton university press, 2006

work page 2006
[2]

Disjunctive programming

Egon Balas. Disjunctive programming. Annals of discrete mathematics , 5:3–51, 1979

1979
[3]

Requiem for the Miller-Tucker-Ze mlin subtour elimination con- straints? European Journal of Operational Research , 236(3):820–832, 2014

Tolga Bekta¸ s and Luis Gouveia. Requiem for the Miller-Tucker-Ze mlin subtour elimination con- straints? European Journal of Operational Research , 236(3):820–832, 2014

work page 2014
[4]

Robust Optimization, volume 28 of Princeton Series in Applied Mathematics

Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimization, volume 28 of Princeton Series in Applied Mathematics . Princeton University Press, 2009

work page 2009
[5]

Solution of a large-scale traveling-salesman problem

George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America , 2(4):393–410, 1954

work page 1954
[6]

Improvements and ext ensions to the Miller-Tucker-Zemlin subtour elimination constraints

Martin Desrochers and Gilbert Laporte. Improvements and ext ensions to the Miller-Tucker-Zemlin subtour elimination constraints. Operations Research Letters, 10(1):27–36, 1991

work page 1991
[7]

A theorem on ﬂows in networks

David Gale. A theorem on ﬂows in networks. Paciﬁc J. Math , 7(2):1073–1082, 1957

work page 1957
[8]

The travelling salesman pro blem and related problems

Bezalel Gavish and Stephen C Graves. The travelling salesman pro blem and related problems. Technical report, Massachusetts Institute of Technology, Ope rations Research Center, 1978

work page 1978

Show all 15 references

[9]

The asymmetric travelling sale sman problem and a re- formulation of the Miller-Tucker-Zemlin constraints

Luis Gouveia and Jose Manuel Pires. The asymmetric travelling sale sman problem and a re- formulation of the Miller-Tucker-Zemlin constraints. European Journal of Operational Research , 112(1):134–146, 1999. 28

1999
[10]

Integer progr amming formulation of traveling salesman problems

Clair E Miller, Albert W Tucker, and Richard A Zemlin. Integer progr amming formulation of traveling salesman problems. Journal of the ACM (JACM) , 7(4):326–329, 1960

1960
[11]

A comparative analysis of sever al asymmetric traveling salesman problem formulations

Temel ¨Oncan, ˙I Kuban Altınel, and Gilbert Laporte. A comparative analysis of sever al asymmetric traveling salesman problem formulations. Computers & Operations Research, 36(3):637–654, 2009

2009
[12]

An analytical comparison o f diﬀerent formulations of the travelling salesman problem

Manfred Padberg and Ting-Yi Sung. An analytical comparison o f diﬀerent formulations of the travelling salesman problem. Mathematical Programming, 52(1):315–357, 1991

1991
[13]

Short combinatorial proof that the DFJ poly tope is contained in the MTZ polytope for the asymmetric traveling salesman problem

Mark Velednitsky. Short combinatorial proof that the DFJ poly tope is contained in the MTZ polytope for the asymmetric traveling salesman problem. Operations Research Letters, 45(4):323– 324, 2017

2017
[14]

Integer programming formulations of the trav eling salesman problem

Richard T Wong. Integer programming formulations of the trav eling salesman problem. In Proceedings of the IEEE international conference of circui ts and computers , volume 149, page
[152]

IEEE Press Piscataway NJ, 1980. 29

1980

Pith tools

Reviewed August 12, 2026 · model on record in the stance chip above.

[1] [1]

The traveling salesman problem: a computational study , volume 17

David L Applegate. The traveling salesman problem: a computational study , volume 17. Princeton university press, 2006

work page 2006

[2] [2]

Disjunctive programming

Egon Balas. Disjunctive programming. Annals of discrete mathematics , 5:3–51, 1979

1979

[3] [3]

Requiem for the Miller-Tucker-Ze mlin subtour elimination con- straints? European Journal of Operational Research , 236(3):820–832, 2014

Tolga Bekta¸ s and Luis Gouveia. Requiem for the Miller-Tucker-Ze mlin subtour elimination con- straints? European Journal of Operational Research , 236(3):820–832, 2014

work page 2014

[4] [4]

Robust Optimization, volume 28 of Princeton Series in Applied Mathematics

Aharon Ben-Tal, Laurent El Ghaoui, and Arkadi Nemirovski. Robust Optimization, volume 28 of Princeton Series in Applied Mathematics . Princeton University Press, 2009

work page 2009

[5] [5]

Solution of a large-scale traveling-salesman problem

George Dantzig, Ray Fulkerson, and Selmer Johnson. Solution of a large-scale traveling-salesman problem. Journal of the operations research society of America , 2(4):393–410, 1954

work page 1954

[6] [6]

Improvements and ext ensions to the Miller-Tucker-Zemlin subtour elimination constraints

Martin Desrochers and Gilbert Laporte. Improvements and ext ensions to the Miller-Tucker-Zemlin subtour elimination constraints. Operations Research Letters, 10(1):27–36, 1991

work page 1991

[7] [7]

A theorem on ﬂows in networks

David Gale. A theorem on ﬂows in networks. Paciﬁc J. Math , 7(2):1073–1082, 1957

work page 1957

[8] [8]

The travelling salesman pro blem and related problems

Bezalel Gavish and Stephen C Graves. The travelling salesman pro blem and related problems. Technical report, Massachusetts Institute of Technology, Ope rations Research Center, 1978

work page 1978