Pith. sign in

REVIEW 2 major objections 5 minor 29 references

An open, reproducible branch-and-cut for the capacitated profitable tour problem: a component study

T0 review · 2 major / 5 minor · reviewed 2026-07-11 · grok-4.5

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

Pith's one-line read Capacity cuts, not connectivity or fancy extras, drive almost all the gains in a branch-and-cut solver for capacitated profitable tours.

desk verdict Honest open reimplementation of Jepsen et al. with a clean ablation: capacity cuts do almost all the work; everything else is inert on this suite. read the letter →

arxiv 2607.04497 v1 pith:ARKURCR5 submitted 2026-07-05 math.OC cs.DScs.MS

Simon Spoorendonk This is my paper · ORCID
classification math.OCcs.DScs.MS MSC 90C2790C5790C35
keywords profitabletourproblemelementaryshortestpathbranch-and-cutresource-constrainedcomputationalstudycapacitycutsopenreproduciblesoftware
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

This paper releases an open, fully reproducible branch-and-cut solver for the capacitated profitable tour problem and its open path version, rebuilt on a free mixed-integer programming stack. The author claims no new algorithm: the formulation and cut families follow earlier work. The real contribution is a careful component study that shows which pieces actually matter. Adding capacity-class cuts (rounded capacity and multistar inequalities) to a connectivity-only baseline is what moves the needle: solved instances rise from 52 to 64 of 76, and the search tree shrinks more than tenfold. Comb inequalities, rounded generalized multistar cuts, reduced-cost fixing, bound-based propagation, and a shortest-path-incompatibility cut add essentially nothing. The same study shows the branch-and-cut is complementary to dynamic-programming labelling: each method closes hard instances the other cannot. The open artifact and the negative results are meant as a reusable baseline so others need not rediscover what fails.

What carries the argument

Capacity-class cuts (rounded capacity inequalities and multistar/generalized large multistar inequalities) separated from a shared Gomory–Hu cut tree on the fractional support graph. These node-coupled inequalities tighten the knapsack-plus-circuit polytope; the ablation isolates them as the only family that measurably reduces the search tree and increases the number of solved instances.

What would settle it

Re-run the same gating ablation on a larger or more strongly capacity-binding set (or on a directed arc-resource reformulation of classical resource-constrained shortest-path benchmarks) and check whether comb, rounded-GLM, SPI, or reduced-cost fixing begin to separate violated cuts and shrink the tree; if they do, the inertness claim fails.

Watch

Extended reading notes

Core claim

On a common modern open stack, capacity-class cuts account for essentially the entire benefit of the branch-and-cut: they lift the number of instances solved from 52 to 64 of 76 and shrink the search tree more than tenfold, while comb cuts, rounded generalized large multistar cuts, reduced-cost fixing, bound-based propagation, and the shortest-path-incompatibility cut contribute nothing measurable. The branch-and-cut and dynamic-programming labelling remain complementary rather than one dominating the other.

Load-bearing premise

The 76 undirected, single-capacity pricing instances used for the ablation are representative enough that the conclusions about which cuts and fixing routines help or fail will hold for the wider class of capacitated profitable-tour and elementary shortest-path problems.

Editorial extensions

If this is right

  • A practical default for this problem class can keep only generalized subtour elimination plus rounded-capacity and multistar cuts; the remaining families can stay optional and nearly free.
  • Open, scriptable baselines make future component studies and extensions (per-arc resources, directed graphs) directly comparable instead of locked inside proprietary stacks.
  • Negative results on SPI and related node-precedence-style cuts discourage re-implementation of those families for the same instance regime.
  • Complementarity with labelling implies that hybrid or portfolio solvers can close more of the hard tail than either method alone.

Reading between the lines

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

  • Because the classical directed arc-resource benchmarks cannot be imported without a model change, the paper’s inertness conclusions are currently untested outside the undirected node-demand regime; an arc-resource reimplementation would be the natural next falsification test.
  • The near-zero separation counts for comb, RGLM and SPI suggest the failure is one of separator design relative to the incumbent, not necessarily of theoretical strength; alternative separation heuristics might revive them.
  • If capacity-class cuts remain decisive on larger instances, pricing engines inside column-generation vehicle-routing solvers could profitably expose the same cut families as user cuts rather than relying solely on labelling.
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.

Referee Report

2 major / 5 minor

Summary. The paper re-implements the CPTP (and open s–t path) branch-and-cut of Jepsen et al. (2014) on a fully open HiGHS stack, adding bound-based preprocessing, domain propagation, and reduced-cost fixing, and releases the formulation, separators, and benchmark scripts. It claims no new method. The empirical contribution is a component study on 76 SPPRCLIB and Roberti pricing instances: capacity-class cuts (RCI and multistar) account for essentially the entire gain over a GSEC-only baseline (solved count 52→64/76; SGM nodes 2290→214), while comb, RGLM, reduced-cost fixing, bound-based propagation, and the SPI cut (a García-style node-precedence variant) add nothing measurable. Head-to-head with PathWyse labelling shows complementarity rather than dominance. All results are regenerated from released logs.

Significance. If the ablation holds, the paper supplies a rare, fully open, rerunnable B&C baseline for CPTP/ESPPRC pricing and a clear ranking of which classical cut families actually pay off on modern open MIP software. The negative SPI result and the near-zero separation rates for comb/RGLM are useful negative knowledge. The open artifact (code, scripts, committed CSVs) is a concrete infrastructural contribution that others can extend to directed/arc-resource models. The claims are modest, tightly scoped, and directly supported by the released experiments; that is a strength, not a weakness, for a computational study.

major comments (2)
  1. §4.3 and Table 3 use a 300 s limit for the gating ablation, while the head-to-head comparison in §4.2 uses 3600 s. Several hard instances (e.g. M-n200-k17-12, E-n101-k14-158) sit near or at the 300 s wall in the ablation ladder. The ranking of capacity cuts vs. the rest is unlikely to reverse, but the paper should either re-run the ablation at 3600 s for the unsolved tail or explicitly justify that the 300 s ranking is stable (e.g. by reporting the same ranking on the subset solved under both limits).
  2. §4.1 correctly notes that classical Beasley–Christofides and García arc-resource directed instances cannot be imported without a model change. The inertness claims for comb, RGLM, SPI, and reduced-cost fixing are therefore scoped to undirected single node-demand pricing instances. The abstract and conclusion should state this scope limit more prominently so that readers do not over-generalize the null results to the broader ESPPRC class the introduction targets.
minor comments (5)
  1. Table 7 reports mean wall-clock under the 3600 s limit for the default configuration; the ablation tables use 300 s. A short note that the component shares are qualitatively the same under both limits would avoid confusion.
  2. §3.1: the SPI description (Held–Karp over |S|≤15) is clear, but a one-sentence remark that the separator never fires (Table 5) could be cross-referenced already in the method section so the negative result is foreshadowed.
  3. Figures 2–3 are informative; adding the number of instances solved by each solver in the caption would make the performance profile self-contained.
  4. The hyperplane branching machinery (§3.3) is described but never exercised. A single sentence that it is off by default and unused in the experiments would prevent readers from looking for results that are not there.
  5. Minor typography: “opens–t path” in the conclusion should be “open s–t path”; a few long sentences in §1 and §4.3 would benefit from splitting for readability.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: empirical ablation on fixed public instances; results do not reduce to inputs by construction.

full rationale

This is a computational component study, not a first-principles derivation. The load-bearing claim (capacity-class cuts drive essentially all measured gain: 52 o64/76 solved, SGM nodes 2290 o214; comb/RGLM/fixing/propagation/SPI add nothing) is an observed performance difference under controlled ablations on the fixed SPPRCLIB+Roberti suite, regenerated from released logs. It is not obtained by fitting a parameter and renaming the fit as a prediction, nor by defining X in terms of Y. Self-citations (Jepsen et al. 2014, of which the author is a co-author; the author’s own software archives) correctly identify the reimplemented method and the open artifact; they do not force the ablation ranking. The head-to-head with PathWyse and the negative SPI result are likewise measured, not definitional. Scope limits on instance representativeness are stated by the paper and do not create circularity. Score 0 is the honest finding.

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

The paper is an empirical reimplementation-and-ablation study. It inherits the standard CPTP IP model and cut validity arguments from Jepsen et al. (2014) and García (2009); it introduces no free parameters fitted to data and no new physical or mathematical entities. The only modelling choices that function as domain assumptions are the undirected single-node-demand formulation and the particular 76-instance suite.

assumptions (3)
  • domain assumption The undirected node-demand CPTP IP (degree, GSEC, knapsack) correctly models the capacitated profitable tour and its open s-t path variant.
    Stated in §2; validity of all subsequent cuts rests on this polytope description taken from Jepsen et al. (2014).
  • domain assumption Rounded capacity, multistar, GLM, RGLM, comb and SPI inequalities are valid for the node-capacitated circuit polytope.
    Cited from Jepsen et al. (2014) and García (2009); the paper reimplements rather than re-proves them (§3.1).
  • standard math Non-elementary capacity-aware labelling yields valid lower bounds for elimination and reduced-cost fixing.
    Standard resource-constrained shortest-path relaxation (Aneja et al., García); used in Algorithms 2–3.

how reviews work

0 comments
Cite this review

Pith. "Pith review of An open, reproducible branch-and-cut for the capacitated profitable tour problem: a component study." pith.science (2026). https://pith.science/paper/ARKURCR5

@misc{pith2026260704497,
  author       = {Pith},
  title        = {Pith review of: An open, reproducible branch-and-cut for the capacitated profitable tour problem: a component study},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/ARKURCR5}},
  note         = {Machine review of arXiv:2607.04497}
}
read the original abstract

We present an open, reproducible branch-and-cut (B&C) algorithm for the capacitated profitable tour problem (CPTP) and its open s-t path variant, the capacity-constrained elementary shortest-path problem. The solver re-implements the formulation and cut families of Jepsen et al. (2014) on a fully open mixed-integer programming stack (HiGHS; Huangfu and Hall, 2018), and adds bound-based preprocessing, domain propagation, and reduced-cost variable fixing. We claim no new method; the contribution is twofold. First, an open, reproducible artifact: to our knowledge the first branch-and-cut for this problem class on a fully open stack, with the formulation, every separator, and all benchmark scripts released, so the results below can be rerun and the solver reused and extended as a baseline. Second, a component study on this common modern stack, benchmarked against a dynamic-programming/labelling reference, that decomposes which components pay off and where the running time goes. We find that the capacity-class cuts account for essentially the entire benefit (adding them to a connectivity-only baseline lifts the number of instances solved from 52 to 64 of 76 and shrinks the search tree more than tenfold), while comb and rounded generalized-large-multistar cuts, reduced-cost fixing, and bound-based propagation add nothing measurable. We also report a negative result: the shortest-path-incompatibility (SPI) cut, a variant of the node-precedence inequalities of Garc\'ia (2009), finds no violated inequality on any instance. The solver and all experiments are released as open, reproducible software (Spoorendonk, 2026).

Figures

Figures reproduced from arXiv: 2607.04497 by the authors.

Figure 1
Figure 1. Where each component acts. Root preprocessing runs once (top); the separation oracle, domain propagation [PITH_FULL_IMAGE:figures/full_fig_p004_1.png] view at source ↗
Figure 2
Figure 2. Performance profile (Dolan–Moré) of runtime over the [PITH_FULL_IMAGE:figures/full_fig_p009_2.png] view at source ↗
Figure 3
Figure 3. Cactus plot: number of instances solved within a given wall-clock budget (log scale). [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

29 extracted references · 16 canonical work pages

  1. [1]

    Y . P. Aneja, V . Aggarwal, and K. P. K. Nair. Shortest chain subject to side constraints.Networks, 13(2):295–302,

  2. [2]

    doi: 10.1002/net.3230130212

    work page doi:10.1002/net.3230130212

  3. [3]

    Resource constrained shortest path problems in path planning for fleet management.Journal of Mathematical Modelling and Algorithms, 3(1):1–17, 2004

    Pasquale Avella, Maurizio Boccia, and Antonio Sforza. Resource constrained shortest path problems in path planning for fleet management.Journal of Mathematical Modelling and Algorithms, 3(1):1–17, 2004. doi: 10.1023/B:JMMA.0000026675.50719.ce

    work page doi:10.1023/b:jmma.0000026675.50719.ce 2004

  4. [4]

    New route relaxation and pricing strategies for the vehicle routing problem.Operations Research, 59(5):1269–1283, 2011

    Roberto Baldacci, Aristide Mingozzi, and Roberto Roberti. New route relaxation and pricing strategies for the vehicle routing problem.Operations Research, 59(5):1269–1283, 2011. doi: 10.1287/opre.1110.0975

    arXiv doi:10.1287/opre.1110.0975 2011

  5. [5]

    The circuit polytope: facets.Mathematics of Operations Research, 22(1):110–145, 1997

    Petra Bauer. The circuit polytope: facets.Mathematics of Operations Research, 22(1):110–145, 1997. doi: 10.1287/moor.22.1.110

    work page doi:10.1287/moor.22.1.110 1997

  6. [6]

    J. E. Beasley and N. Christofides. An algorithm for the resource constrained shortest path problem.Networks, 19 (4):379–394, 1989. doi: 10.1002/net.3230190402

    doi:10.1002/net.3230190402 1989

  7. [7]

    Exact branch-price-and-cut algorithms for vehicle routing.Transportation Science, 53(4):946–985, 2019

    Luciano Costa, Claudio Contardo, and Guy Desaulniers. Exact branch-price-and-cut algorithms for vehicle routing.Transportation Science, 53(4):946–985, 2019. doi: 10.1287/trsc.2018.0878

    doi:10.1287/trsc.2018.0878 2019

  8. [8]

    A computational study of solution approaches for the resource constrained elementary shortest path problem.Annals of Operations Research, 201(1):131–157, 2012

    Luigi Di Puglia Pugliese and Francesca Guerriero. A computational study of solution approaches for the resource constrained elementary shortest path problem.Annals of Operations Research, 201(1):131–157, 2012. doi: 10.1007/s10479-012-1162-x. 17

    work page doi:10.1007/s10479-012-1162-x 2012

Show all 29 references
  1. [9]

    E. A. Dinic. Algorithm for solution of a problem of maximum flow in networks with power estimation.Soviet Mathematics Doklady, 11:1277–1280, 1970

    1970

  2. [10]

    A note on the separation of subtour elimination constraints in elementary shortest path problems

    Michael Drexl. A note on the separation of subtour elimination constraints in elementary shortest path problems. European Journal of Operational Research, 229(3):595–598, 2013. doi: 10.1016/j.ejor.2013.03.009

    2013 doi

  3. [11]

    Solving elementary shortest-path problems as mixed-integer programs.OR Spectrum, 36(2):281–296, 2014

    Michael Drexl and Stefan Irnich. Solving elementary shortest-path problems as mixed-integer programs.OR Spectrum, 36(2):281–296, 2014. doi: 10.1007/s00291-012-0302-7

    2014 doi

  4. [12]

    An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems.Networks, 44(3): 216–229, 2004

    Dominique Feillet, Pierre Dejax, Michel Gendreau, and Cyrille Gueguen. An exact algorithm for the elementary shortest path problem with resource constraints: Application to some vehicle routing problems.Networks, 44(3): 216–229, 2004. doi: 10.1002/net.20033

    2004 doi

  5. [13]

    PhD thesis, Georgia Institute of Technology, Atlanta, GA, 2009

    Renan Garcia.Resource Constrained Shortest Paths and Extensions. PhD thesis, Georgia Institute of Technology, Atlanta, GA, 2009. Ph.D. thesis, School of Industrial and Systems Engineering

    2009

  6. [14]

    Very simple methods for all pairs network flow analysis.SIAM Journal on Computing, 19(1): 143–155, 1990

    Dan Gusfield. Very simple methods for all pairs network flow analysis.SIAM Journal on Computing, 19(1): 143–155, 1990. doi: 10.1137/0219009

    1990 doi

  7. [15]

    Michael Held and Richard M. Karp. A dynamic programming approach to sequencing problems.Journal of the Society for Industrial and Applied Mathematics, 10(1):196–210, 1962. doi: 10.1137/0110015

    1962 doi

  8. [16]

    Solving resource constrained shortest path problems with lp-based methods

    Markó Horváth and Tamás Kis. Solving resource constrained shortest path problems with lp-based methods. Computers & Operations Research, 73:150–164, 2016. doi: 10.1016/j.cor.2016.04.013

    2016 doi

  9. [17]

    Qi Huangfu and J. A. J. Hall. Parallelizing the dual revised simplex method.Mathematical Programming Computation, 10(1):119–142, 2018. doi: 10.1007/s12532-017-0130-5

    2018 doi

  10. [18]

    A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint

    Mads Jepsen, Bjørn Petersen, and Simon Spoorendonk. A branch-and-cut algorithm for the elementary shortest path problem with a capacity constraint. Technical Report 08/01, DIKU, Department of Computer Science, University of Copenhagen, 2008

    2008

  11. [19]

    Jepsen, Bjørn Petersen, Simon Spoorendonk, and David Pisinger

    Mads K. Jepsen, Bjørn Petersen, Simon Spoorendonk, and David Pisinger. A branch-and-cut algorithm for the capacitated profitable tour problem.Discrete Optimization, 14:78–96, 2014. doi: 10.1016/j.disopt.2014.08.001

    2014 doi

  12. [20]

    A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints.European Journal of Operational Research, 289(3):879–896, 2021

    Gonzalo Lera-Romero and Juan José Miranda-Bront. A branch and cut algorithm for the time-dependent profitable tour problem with resource constraints.European Journal of Operational Research, 289(3):879–896, 2021. doi: 10.1016/j.ejor.2019.07.014

    2021 doi

  13. [21]

    Letchford and Juan-José Salazar-González

    Adam N. Letchford and Juan-José Salazar-González. Projection results for vehicle routing.Mathematical Programming, 105(2–3):251–274, 2006. doi: 10.1007/s10107-005-0652-x

    2006 doi

  14. [22]

    Medaglia

    Leonardo Lozano, Daniel Duque, and Andrés L. Medaglia. An exact algorithm for the elementary shortest path problem with resource constraints.Transportation Science, 50(1):348–357, 2016. doi: 10.1287/trsc.2014.0582

    2016 doi

  15. [23]

    A generic exact solver for ve- hicle routing and related problems.Mathematical Programming, 183(1–2):483–523, 2020

    Artur Pessoa, Ruslan Sadykov, Eduardo Uchoa, and François Vanderbeck. A generic exact solver for ve- hicle routing and related problems.Mathematical Programming, 183(1–2):483–523, 2020. doi: 10.1007/ s10107-020-01523-z

    2020

  16. [24]

    Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints.Discrete Optimization, 3(3):255–273, 2006

    Giovanni Righini and Matteo Salani. Symmetry helps: Bounded bi-directional dynamic programming for the elementary shortest path problem with resource constraints.Discrete Optimization, 3(3):255–273, 2006. doi: 10.1016/j.disopt.2006.05.007

    2006 doi

  17. [25]

    A bucket graph-based labeling algorithm with application to vehicle routing.Transportation Science, 55(1):4–28, 2021

    Ruslan Sadykov, Eduardo Uchoa, and Artur Pessoa. A bucket graph-based labeling algorithm with application to vehicle routing.Transportation Science, 55(1):4–28, 2021. doi: 10.1287/trsc.2020.0985

    2021 doi

  18. [26]

    PathWyse: a flexible, open-source library for the resource constrained shortest path problem.Optimization Methods and Software, 39(2):298–320, 2024

    Matteo Salani, Saverio Basso, and Vincenzo Giuffrida. PathWyse: a flexible, open-source library for the resource constrained shortest path problem.Optimization Methods and Software, 39(2):298–320, 2024. doi: 10.1080/10556788.2023.2296978

    2024 doi

  19. [27]

    bucket-graph-spprc: an extensible C++ library for the shortest path problem with resource constraints, 2026

    Simon Spoorendonk. bucket-graph-spprc: an extensible C++ library for the shortest path problem with resource constraints, 2026. URLhttps://arxiv.org/abs/2606.30847

    2026 arXiv

  20. [28]

    cptp: a C++23 branch-and-cut solver for the capacitated profitable tour problem, 2026

    Simon Spoorendonk. cptp: a C++23 branch-and-cut solver for the capacitated profitable tour problem, 2026. URL https://doi.org/10.5281/zenodo.21205088. Software (v0.2.0), archived on Zenodo

    2026 doi

  21. [29]

    Integer programming formulations for the elementary shortest path problem.European Journal of Operational Research, 252(1):122–130, 2016

    Leonardo Taccari. Integer programming formulations for the elementary shortest path problem.European Journal of Operational Research, 252(1):122–130, 2016. doi: 10.1016/j.ejor.2016.01.003. 18

    2016 doi

Pith tools

Reviewed July 11, 2026 · model on record in the stance chip above.