On Solving the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts

Derek H. Smith; Roberto Montemanni

REVIEW 2 major objections 6 minor 19 references

On Solving the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts

T0 review · 2 major / 6 minor · reviewed 2026-08-07 · deepseek-v4-flash

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

Pith's one-line read A compact CP-SAT model solves conflicting-arc shortest paths as well as the best prior solvers.

desk verdict A compact CP-SAT model for SP-EDAC that runs competitively on the standard benchmarks; the AddCircuit encoding is sound, but the headline improvements rest on uncontrolled comparisons and need verification. read the letter →

arxiv 2506.03326 v1 pith:7RPRJ3QB submitted 2025-06-03 math.OC

Roberto Montemanni , Derek H. Smith This is my paper

classification math.OC MSC 90C3590C1090C27

keywords shortestpathproblemexclusive-disjunctionarcconflictsSP-EDACCP-SATAddCircuitOR-Toolsmixedintegerlinearprogrammingsoftconstraints

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 paper studies SP-EDAC, a shortest-path problem in which arcs come in conflict pairs: for each pair, a penalty is paid if exactly one of the two arcs is used, and the goal is to minimize path cost plus penalties. The authors argue that this problem can be solved effectively by a compact mixed-integer linear program fed to the open-source CP-SAT solver, without the dynamic generation of cutting constraints that earlier exact models needed. On the standard benchmark instances, they report solution quality comparable to the previous state of the art, improved best-known bounds on several groups, and first-time closure of all small-world instances with k=0.30 and all random instances with d=0.3 and n=400. The practical point is that a simple, static model can be competitive with more sophisticated implementations.

What carries the argument

The load-bearing device is the AddCircuit constraint (9), a CP-SAT construct that forces the selected arcs to form a single directed circuit over the graph. It is adapted to model a path: for every vertex not serving as source or destination, a self-loop variable x_ii=1 means the vertex is skipped; the constant x_ts=1 closes the s-t path into a circuit by forcing the artificial arc (t,s). This mechanism lets the model drop constraints (2) and (3), the flow-balance equalities and the exponentially many subtour elimination inequalities, and replace them with a single compact global constraint. The conflict-penalty part of the objective is linearized via variables y_ijkl whose activation is controlled by inequalities (4)-(6), following the Glover-Woolsey conversion.

What would settle it

Take a small random SP-EDAC instance, enumerate all simple s-t paths by brute force, and check whether every solution returned by the CP-SAT model corresponds to one of these paths; a single returned solution containing a disconnected cycle or using a self-loop that leaves a vertex unreachable would disprove the encoding. Equivalently, on instances where the previous exact solvers certify an optimal value, any CP-SAT solution strictly below that certified optimum would show the circuit model is not actually enforcing the same feasible set.

Watch

Extended reading notes

Core claim

The central claim is that the set of feasible s-t paths in SP-EDAC can be encoded exactly by a CP-SAT AddCircuit constraint over the whole vertex set, with self-loop variables x_ii for vertices not in {s,t} and a forced arc x_ts=1, replacing both flow balance and subtour elimination constraints. The paper maintains that this compact encoding, combined with a strengthened linearization of the conflict penalties, yields a model whose exact solutions match or improve those of the earlier ILP, MILP, and matheuristic approaches, while avoiding the implementation burden of user-generated cutting constraints.

Load-bearing premise

The load-bearing premise is that the solver's circuit constraint, together with the self-loops and the forced closing arc, encodes exactly the set of valid paths and nothing else, so if the circuit semantics permitted extra cycles or invalid path structures the model would solve a different problem.

Editorial extensions

If this is right

If the AddCircuit encoding is exactly equivalent to simple s-t paths, then SP-EDAC has a static, compact model that needs no lazy subtour-elimination callbacks, making it easier to embed in a generic solver workflow.
Because the model is compact, it can be handed directly to any constraint-programming or MILP solver that supports circuit-type constraints, not only to engines with advanced lazy-constraint machinery.
The benchmark improvements imply that previous exact methods were leaving some optimality gaps mostly because of constraint-generation overhead, not because the problem is inherently harder there.
Closing the d=0.3, n=400 random and k=0.30 small-world groups provides new certified optimal values that future algorithms can be tested against.

Reading between the lines

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

The same AddCircuit path-encoding trick could transfer to other path problems with soft pairwise penalties, such as forbidden-pairs variants, where a single global circuit constraint may replace lazy separation.
A natural stress test is to push the compact model to larger n or to conflict densities beyond the current benchmark grid; the paper suggests performance degrades on low-density graphs, so sparse large instances are the place to look for a crossover.
If CP-SAT's circuit propagator is tuned for assignment-style problems, the model may exploit propagation strength that a generic MILP solver would not, meaning the result is partly about the propagator, not just the formulation.
Since the benchmark comparison used a faster machine and multithreading, a fairer head-to-head on identical hardware and single-thread settings would quantify how much of the gain is algorithmic.

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

Short version: this is a useful, honest engineering paper, not a breakthrough. What is new is the computational demonstration that a compact CP-SAT model with AddCircuit matches or beats the published MILP and matheuristic numbers on the standard SP-EDAC benchmarks. The MILP objective and penalty linearization are correct, and the AddCircuit encoding is the standard one. The stress-test worry about multiple disjoint cycles doesn't land: OR-Tools' AddCircuit enforces a single circuit through all nodes, self-loops are the skips, and the forced arc (t,s) closes an s-t path. So the modeling spine is sound.

What the paper does well: it removes the need for dynamic subtour-elimination constraints, reports systematic averages across the standard instance families, and is candid about hardware and time limits. The comparison, however, is against published results, not a rerun on the same machine: different CPU, multithreading allowed, shorter time limit. The authors flag this and try to compensate, but it is not a controlled comparison. The "closed for the first time" claims therefore should be treated as indicative until a reimplementation or the instance files confirm them. No code, data, or per-instance tables are shipped, which makes verification harder than it should be.

The modeling contribution is incremental — the structure comes from [3] and AddCircuit is a standard tool — but the paper is honest about that. The main value is for researchers working on conflict-constrained path problems or on CP-SAT formulations of routing variants. The citation pattern is clean; self-citations are just prior CP-SAT applications, not load-bearing.

Verdict: this deserves a serious referee. The math checks out, the empirical claim is plausible but under-controlled; a referee should ask for code and data, or a same-machine rerun of MILP, before the first-time closures are accepted. I would not cite it for my own work, not being in the area, but I would send it to someone working on this problem.

Referee Report

2 major / 6 minor

Summary. The paper studies the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts (SP-EDAC), where a penalty is incurred for each conflicting pair of arcs when both or neither are selected. The authors formulate a compact mixed-integer linear program and solve it with Google OR-Tools CP-SAT, replacing the classical flow and subtour-elimination constraints with an AddCircuit constraint plus self-loop variables. Computational experiments on the benchmark instances of Cerulli et al. [3] are reported, claiming comparable or better performance than previous exact and heuristic solvers, including first-time closure of some instance groups.

Significance. If the modeling and experiments are correct, the paper makes a practical contribution: it shows that a generic open-source CP-SAT solver with a compact circuit-based formulation can be competitive with, and in some cases improve upon, dedicated solvers that rely on dynamically generated constraints. The formulation is clearly presented, and the objective function correctly charges the penalty for the two violation patterns. However, the two most load-bearing elements—the exact circuit semantics of the AddCircuit encoding and the fairness of the cross-machine experimental comparison—require substantial clarification before the claims can be fully accepted.

major comments (2)

[Section IV-A, Eq. (9)-(11)] The paper does not formally establish that AddCircuit(x_ij | i,j in V) together with the self-loop variables x_ii (10) and the forced arc x_ts=1 (11) exactly encodes the set of simple s-t paths. The semantics of the OR-Tools AddCircuit constraint must be stated precisely: does it enforce a single directed cycle over all nodes (with self-loops acting as length-one cycles allowed only in a specified way), or does it allow a set of disjoint cycles? If it enforces a Hamiltonian cycle over all of V, then almost all self-loop variables would be forced to 0 and the model would not represent SP-EDAC. If it permits multiple disjoint cycles, the solver could add a separate cycle that avoids conflict penalties and return an invalid solution with artificially low cost. Since the optimality certificates behind the 'closed for the first time' claims depend entirely on this encoding, the authors should provide a proof of equivalence (or a precise citation to the solver documentation) and validate the encoding on small instances against brute-force enumeration.
[Section IV-C] The experimental comparison against the results of [3] is not controlled: the reported times and gaps were obtained on different CPUs (Intel Core i7 12700F vs. Intel Xeon E5), with different solver versions, different time limits (1800 s vs. 3600 s), and multithreading enabled only for CP-SAT. The statement that the faster CPU 'should compensate' for the shorter time limit is not quantified. Consequently, the observed improvements on best-known results and the first-time closures may be caused by hardware or solver-version differences rather than by the modeling approach. The paper should either run the competing methods (or the same/similar models) on the same machine with identical settings, or provide a detailed analysis of the effect of these differences, and in either case should make per-instance results available for independent verification.

minor comments (6)

[Section II] In the set definition for conflicts, "{(i, j).(k, l)}" should be "{(i,j),(k,l)}".
[Section III] The word "Inequalites" is a typo for "Inequalities".
[Section IV-A] The phrase "forces some of the arcs to conform like a loop touching a subset of the vertices" is unclear; consider rewording to describe the circuit as a permutation with self-loops allowed for nodes not on the path.
[Figure 1] The caption says "capacities" where it should say "costs".
[Section IV-C] The column headers "Sec Best" and "Sec Tot" are not defined; please clarify that they are seconds to best solution and total seconds, respectively.
[Reproducibility] No code or data repository is mentioned; given the first-time closure claims, a reproducibility statement with instance-level results and solver configuration would greatly strengthen the paper.

Circularity Check

0 steps flagged · score 1.0 of 10

No significant circularity: the CP-SAT compact model is independently specified and its benchmark claims are tested against the external results of Cerulli et al., with self-citations only as motivation.

full rationale

The derivation chain is not circular. The SP-EDAC model is explicitly built from the external formulation of Cerulli et al. [3] (Section III), with standard flow conservation (2), subtour elimination (3), and linearization of the conflict penalties (4)-(6). The CP-SAT adaptation in Section IV-A replaces (2)-(3) with the solver's AddCircuit constraint (9), self-loop variables (10), and the forced arc x_ts = 1 (11); this is a modeling choice whose correctness depends on OR-Tools' documented circuit semantics, not on a result derived from the paper's own target claims. No parameter is fitted to reproduce a known optimum, and no 'prediction' is constructed from the benchmark outputs; the reported improvements and first-time closures are independent empirical outcomes compared against the published tables of [3]. The paper's self-citations [10]-[12] are cited only as motivation for trying CP-SAT, and [15]-[16] are cited only to note that AddCircuit is commonly used for generalized TSPs; neither is load-bearing for the mathematical equivalence or for the computational conclusions. The only substantive concern, namely whether AddCircuit's circuit semantics exactly encode simple s-t paths via self-loops, is a correctness/external-verification risk rather than a circularity, because the paper does not define the solver semantics in terms of its own conclusion. The central claim therefore retains independent content: the compact model is tested against external state-of-the-art solvers, and no step reduces by definition to its inputs.

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

The central claim rests on the correctness of the CP-SAT AddCircuit encoding for paths, the availability and comparability of the benchmark instances from [3], and the standard assumption of nonnegative weights so that optimal paths are simple. No invented entities or fitted parameters are introduced.

assumptions (3)

domain assumption AddCircuit constraint (9) with self-loops (10) and x_ts=1 (11) exactly represents the set of simple s-t paths.
Section IV-A replaces flow and subtour constraints with the circuit constraint; correctness of the encoding is assumed from the solver documentation and established practice.
domain assumption The benchmark instances used are the same as those in [3] and are available from the literature.
Section IV-B describes the instance generation parameters but does not provide a data source or verify that the exact instances used in [3] were obtained.
standard math Arc costs and penalties are nonnegative, so an optimal simple path exists and the circuit or subtour constraints do not exclude optimal solutions.
Arc costs are defined in Z_+^0 and penalties are positive by problem definition; this justifies restricting to simple paths.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On Solving the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts." pith.science (2026). https://pith.science/paper/7RPRJ3QB

@misc{pith2026250603326,
  author       = {Pith},
  title        = {Pith review of: On Solving the Shortest Paths with Exclusive-Disjunction Arc Pairs Conflicts},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/7RPRJ3QB}},
  note         = {Machine review of arXiv:2506.03326}
}

read the original abstract

A variant of the well-known Shortest Path Problem is studied in this paper, where pairs of conflicting arcs are provided, and for each conflicting pair a penalty is paid once neither or both of the arcs are selected. This configures a set of soft-constraints. The problem, which can be used to model real applications, looks for a path from a given origin to a given destination that minimizes the cost of the arcs traversed plus the penalties incurred. In this paper, we consider a compact mixed integer linear program representing the problem and we solve it with the open-source solver CP-SAT, part of the Google OR-Tools computational suite. An experimental campaign on the instances available from the literature indicates that the approach we propose achieves results comparable with those of state-of-the-art solvers, notwithstanding it is a compact model, while the other approaches require the generation of dynamic constraints in order for the models to be competitive. Some best-known results have been improved in this study, and some instances have been closed for the first time.

Figures

Figures reproduced from arXiv: 2506.03326 by the authors.

Discussion (0). Sign in to comment.

Reference graph

Works this paper leans on

19 extracted references · 14 canonical work pages

[3]

Shortest paths with exclusive-disjunction arc pairs conflicts,

R. Cerulli, G. Guerriero, E. Scalzo, and C. Sorgente, “Shortest paths with exclusive-disjunction arc pairs conflicts,” Computers & Operations Research, vol. 152, p. 106158, 2023

2023
[1]

Mehlhorn and P

K. Mehlhorn and P. Sanders, Shortest Paths. Springer, 2008

work page 2008
[2]

A note on two problems in connexion with graphs,

E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik , vol. 1, pp. 269–271, 1959

work page 1959
[4]

On two problems in the generation of program test paths,

H. Gabow, S. Maheshwari, and L. Osterweil, “On two problems in the generation of program test paths,” IEEE Transactions on Software Engineering, vol. SE-2, no. 3, pp. 227–231, 1976

work page 1976
[5]

Optimal software test planning through automated network analysis,

K. W. Krause, M. A. Goodwin, and R. W. Smith, “Optimal software test planning through automated network analysis,” TRW Systems Group, pp. 18–22, 1973

work page 1973
[6]

Impossible pair constrained test path generation in a program,

P. K. Srimani and B. P. Sinha, “Impossible pair constrained test path generation in a program,” Information Sciences , vol. 28, no. 2, pp. 87– 103, 1982

work page 1982
[7]

On the path avoiding forbidden pairs polytope,

M. Blanco, R. Bornd ¨orfer, M. Br¨uckner, N. D. Ho`ang, and T. Schlechte, “On the path avoiding forbidden pairs polytope,” Electronic Notes in Discrete Mathematics , vol. 50, pp. 343–348, 2015, lAGOS’15 – VIII Latin-American Algorithms, Graphs and Optimization Symposium. [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S1571065315002127

work page 2015
[8]

Ferone, P

D. Ferone, P. Festa, and M. Salani, Branch and Bound and Dynamic Programming Approaches for the Path Avoiding F orbidden Pairs Prob- lem. Cham: Springer International Publishing, 2021, pp. 227–235

work page 2021

Show all 19 references

[9]

Google OR-Tools - CP-SAT,

L. Perron and F. Didier, “Google OR-Tools - CP-SAT,” Google, 2025, https://developers.google.com/optimization/cp/cp solver/ [Accessed: 2025-03-18]

2025
[10]

Solving the parallel drone schedul- ing traveling salesman problem via constraint programming,

R. Montemanni and M. Dell’Amico, “Solving the parallel drone schedul- ing traveling salesman problem via constraint programming,” Algo- rithms, vol. 16, no. 1, p. 40, 2023

2023
[11]

Parallel drone scheduling vehicle routing problems with collective drones,

R. Montemanni, M. Dell’Amico, and A. Corsini, “Parallel drone scheduling vehicle routing problems with collective drones,” Computers & Operations Research , vol. 163, p. 106514, 2024

2024
[12]

Solving a home healthcare routing and scheduling problem with real-world features,

R. Montemanni, “Solving a home healthcare routing and scheduling problem with real-world features,” in Proceedings of the 9th Interna- tional Conference on Machine Learning and Soft Computing . Springer, to appear, 2025

2025
[13]

Converting the 0-1 polynomial programming problem to a 0-1 linear program,

F. Glover and E. Woolsey, “Converting the 0-1 polynomial programming problem to a 0-1 linear program,” Operations Research, vol. 22, no. 1, pp. 180–182, 1974

1974
[14]

Solution of a large- scale traveling-salesman problem,

G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson, “Solution of a large- scale traveling-salesman problem,” Journal of the Operations Research Society of America , vol. 2, no. 4, pp. 465–462, 1954

1954
[15]

Ant colony systems for large sequential ordering problems,

R. Montemanni, D. H. Smith, and L. M. Gambardella, “Ant colony systems for large sequential ordering problems,” in IEEE Swarm Intel- ligence Symposium. SIS 2007 . IEEE, 2007, pp. 60–67

2007
[16]

Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi- parallel Monte Carlo sampling,

D. Weyland, R. Montemanni, and L. M. Gambardella, “Heuristics for the probabilistic traveling salesman problem with deadlines based on quasi- parallel Monte Carlo sampling,” Computers & Operations Research , vol. 40, no. 7, pp. 1661–1670, 2013

2013
[17]

Collective dynamics of ‘small-world’ net- works,

D. Watts and S. Strogatz, “Collective dynamics of ‘small-world’ net- works,” Nature, vol. 393, pp. 440–442, 1998

1998
[18]

Renormalization group analysis of the small- world network model,

M. Newman and D. Watts, “Renormalization group analysis of the small- world network model,” Physics Letters A , vol. 263, no. 4, pp. 341–346, 1999

1999
[19]

IBM CPLEX Optimizer,

IBM, “IBM CPLEX Optimizer,” 2024, https://www.ibm.com/de-de/ analytics/cplex-optimizer [Accessed: 2024-03-14]

2024

Pith tools

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

[1] [3]

Shortest paths with exclusive-disjunction arc pairs conflicts,

R. Cerulli, G. Guerriero, E. Scalzo, and C. Sorgente, “Shortest paths with exclusive-disjunction arc pairs conflicts,” Computers & Operations Research, vol. 152, p. 106158, 2023

2023

[2] [1]

Mehlhorn and P

K. Mehlhorn and P. Sanders, Shortest Paths. Springer, 2008

work page 2008

[3] [2]

A note on two problems in connexion with graphs,

E. W. Dijkstra, “A note on two problems in connexion with graphs,” Numerische Mathematik , vol. 1, pp. 269–271, 1959

work page 1959

[4] [4]

On two problems in the generation of program test paths,

H. Gabow, S. Maheshwari, and L. Osterweil, “On two problems in the generation of program test paths,” IEEE Transactions on Software Engineering, vol. SE-2, no. 3, pp. 227–231, 1976

work page 1976

[5] [5]

Optimal software test planning through automated network analysis,

K. W. Krause, M. A. Goodwin, and R. W. Smith, “Optimal software test planning through automated network analysis,” TRW Systems Group, pp. 18–22, 1973

work page 1973

[6] [6]

Impossible pair constrained test path generation in a program,

P. K. Srimani and B. P. Sinha, “Impossible pair constrained test path generation in a program,” Information Sciences , vol. 28, no. 2, pp. 87– 103, 1982

work page 1982

[7] [7]

On the path avoiding forbidden pairs polytope,

M. Blanco, R. Bornd ¨orfer, M. Br¨uckner, N. D. Ho`ang, and T. Schlechte, “On the path avoiding forbidden pairs polytope,” Electronic Notes in Discrete Mathematics , vol. 50, pp. 343–348, 2015, lAGOS’15 – VIII Latin-American Algorithms, Graphs and Optimization Symposium. [Online]. Available: https://www.sciencedirect.com/science/article/pii/ S1571065315002127

work page 2015

[8] [8]

Ferone, P

D. Ferone, P. Festa, and M. Salani, Branch and Bound and Dynamic Programming Approaches for the Path Avoiding F orbidden Pairs Prob- lem. Cham: Springer International Publishing, 2021, pp. 227–235

work page 2021