The SEBD Grand Tour 🍾

The SEBD grand tour, 1993–2026 — with provenance and a certificate.
From Bertram Ludäscher & two AI toolchains, the morning of the SEBD'26 closing talk.

AI prose Thirty-four editions ago, SEBD — founded by Domenico Saccà — began in Gizzeria Lido; this year it reached Senigallia, where the closing talk was about trustworthy AI results: answers that arrive with evidence, not just confidence. The morning of the talk, as a small self-referential demo, we asked: what is the shortest grand tour visiting every SEBD edition, from the first to the thirty-fourth? This page is the keepsake version of that demo — and, in the spirit of the talk, it does not ask you to believe it. Every number below carries the means to check it. Let it make you smile — and let you verify.

primary source The 34 editions and their host cities come from the DBLP index of SEBD proceedings (2026 Senigallia supplied by hand — DBLP doesn't have the future yet). Their coordinates come from OpenStreetMap/Nominatim, checked place by place on 2026-08-01 — see the coordinate audit for why that sentence used to read differently, and what it cost.

The page has two parts. Part I is the provenance: how the answer came about, from DBLP through two AI toolchains to a post-talk audit that found four wrong coordinates. Part II is the evidence: a tree of what the final claim actually rests on, and how to check each piece yourself. The two are related but not the same, and the difference is the point of the page.

The question (Q)

Visit all 34 SEBD editions exactly once, starting at edition 1 (Gizzeria Lido, 1993) and ending at edition 34 (Senigallia, 2026), minimizing total distance. Cities that hosted twice — Rimini, Venice, Villasimius — count once per edition, which is why everything downstream is keyed by edition number, not city name. modeling choice

The answer (A)

AI-generated, verified The optimal tour is 3,527 km — versus 15,209 km in chronological order (76.8% shorter; time travel is inefficient travel). The visiting order, by edition number:

1 29 21 25 24 15 26 19 11 16 12 32 28 33 22 3 23 8
27 10 4 30 17 7 13 5 31 9 20 2 18 6 14 34

modeling choice Honesty about the metric: distances are straight lines on an equirectangular km-plane (reference parallel 42°N, R = 6371 km), rounded to whole kilometres — not roads, not rail, and pointedly not ferries, though the Sicily and Sardinia editions cross open water. Because that projection is a genuine plane embedding, the underlying real-valued metric satisfies the triangle inequality exactly. The rounded matrix we actually ship inherits it only to within the rounding: 22 of the 35,904 ordered triples violate it, every one of them by a single kilometre. Nothing downstream cares — the certificate below is a claim about the shipped integer matrix, whatever its geometry — but a page about checkable claims should not round a number and keep the adjective. Should you actually take the trip, budget extra for the sea legs.

Two toolchains, three numbers

The lineage graph — where every artifact came from

And how do you know this graph reflects what actually happened? Mostly, you don't — and it would be against the spirit of this page to pretend otherwise. The graph is self-reported: drawn by the same agent that did the work, from its own derivation log (meta-provenance.org). It is a record, not a tamper-evident trace — nothing cryptographic binds the arrows to the events. Three things still separate it from a just-so story: every node names an artifact that exists and is consistent with its claimed inputs (click and compare); an independent toolchain reached the same visiting order from the same edition list (the GPT bundle, with its own provenance.json and file hashes) — though emphatically not from the same coordinates, which each toolchain estimated for itself and which disagreed on 17 of 34 rows, the disagreement that eventually exposed our data error; and the whole pipeline is re-runnable from DBLP forward, so the graph's claims are reproducible even if its history is unprovable. What would upgrade it: append-only signed logs. (Hashes over the Claude-side artifacts used to be listed here as missing; they now ship as SHA256SUMS.) honest limitation

primary source One trust moment deserves telling straight: the first attempt to gather the editions used an AI web-summarizer, which quietly dropped the older editions. It was distrusted and discarded; the list was re-derived from the raw DBLP HTML instead. The data on this page was never "just known" by an AI — it was fetched, checked (34 editions = 2026−1993+1), and its lineage recorded. The blow-by-blow derivation log is meta-provenance.org.

The coordinate audit — where this page was wrong

Until 2026-08-01 this page claimed its coordinates were "town centroids, accurate to a couple of km," and invited you to spot-check them against any map. Nobody had. When someone finally did — geocoding all 34 stops against OpenStreetMap/Nominatim — four were wrong, one of them badly:

The errors are not random, which is the interesting part. All four stops are coastal frazioni — a Lido, a Marina, a beach hamlet — and in every case the coordinate had drifted inland toward the parent comune that shares the name. That is exactly the failure mode you would predict of a language model recalling a place from its name rather than looking it up, and exactly what a gazetteer catches in one pass. The other 30 stops came back within 1.5 km. primary source

What it cost: the certified optimum was 3,541 km and is now 3,527 km; the chronological comparison moved 15,245 → 15,209 km. What it did not cost: the visiting order is unchanged, and every structural claim on this page — the sandwich argument, the six cuts, the 16 co-optima — survived verbatim. A certificate proves the tour is shortest for the numbers it was given. It has nothing whatever to say about whether those numbers describe Italy. That is not a flaw in the method; it is the precise boundary of what the method claims, and this page spent two weeks demonstrating it by accident.

The GPT bundle, for its part, had Torre Canne and Squillace Lido right all along, and Castellaneta Marina wrong by 10.0 km and Gizzeria Lido by 3.5 km — so neither toolchain was trustworthy on coordinates, and neither was checkable without a third source. verified

The evidence (E) — what you actually have to believe

Part I traced how each artifact came about. The tree below asks a different question: which of those artifacts does the claim depend on? Read it bottom-up. The yellow leaves are what you must take on trust; above them sit data files you can open and checks you can re-run; the pink root is the claim. Nodes with a thick border are clickable and open the file they name.

The tree's central distinction is between found and trusted. The 2-opt search found the tour; HiGHS found the proofs, first the cutting-plane run and then the 226-leaf certificate. All of them appear only as grey, dashed helpers. Nothing above them depends on their being correct, because two short Prolog checkers re-verify what they produced, and since 2026-10-16 a second checker, written in Python by another AI agent, re-verifies the lower bound on its own. That is why the trust base is small: seven leaves, most of them about arithmetic and checker code.

Some things are deliberately not in the support structure. The ChatGPT bundle corroborates the result but supports nothing; remove it and the claim still stands. The AI-recalled coordinates appear only as what OpenStreetMap corrected: the one leaf that failed, and the reason for the coordinate audit. And most of Part I is absent altogether. The lineage graph records how things happened; the tree records what the claim depends on. The evidence would stand even if the history were misreported.

The sections below take the tree apart: the two green claims (the sandwich), the blue checks (the trust table), the certificate branch (a proof with no solver in it), and the yellow leaves (known gaps).

Why believe "optimal" without trying every tour?

A fair objection: nobody enumerated the alternatives. With endpoints fixed, the 32 intermediate editions can be ordered in 32! ≈ 2.6 × 10³⁵ ways. At a billion tours checked per second, exhaustive search would take about 8 × 10¹⁸ years — some 600 million times the age of the universe. Exhaustion is not merely slow; it is not a thing that happens. verified (arithmetic you can redo on a napkin)

The proof works differently — it is a sandwich, not a search. Two independent facts are produced:

• An upper bound: a concrete valid tour of length 3,527 km exists (check it: sum its legs — verify.pl does exactly this).
• A lower bound: no tour — seen or unseen — can be shorter than 3,527 km.

The lower bound comes from relaxation: drop the requirement "the edges form one connected tour" and demand only "every stop touches exactly 2 edges." (A path has two endpoints of degree 1, so exact_tsp.py first closes ours into a cycle with a zero-cost dummy stop joined to editions 1 and 34 — degree 2 then forces both free edges in, and the cheapest cycle is exactly the cheapest path.) Every real tour satisfies these weaker constraints, so the minimum over this larger set can only be ≤ the best tour — a valid bound. The first relaxation yields 2,881 km, but its "solution" is six disconnected mini-loops. So a subtour-elimination cut is added — a linear inequality saying "at least 2 edges must cross this mini-loop's boundary," which is self-evidently true of every genuine tour, so the bound stays valid — and the relaxation is re-solved. Six iterations (2881 → 3273 → 3439 → 3475 → 3477 → 3527) replace 10³⁵ evaluations; at 3,527 the relaxation's own solution is a single tour, so lower = upper = optimum. This is the Dantzig–Fulkerson–Johnson method (1954), the engine inside the record-holding Concorde TSP solver. verified

And a footnote the proof itself supplies: the optimal value is unique, the optimal tour is not. Rimini (editions 2, 18), Venice (9, 20), and Villasimius (28, 32) each repeat at identical coordinates, so swapping any twin pair changes nothing — 2³ = 8 relabellings of any optimal tour. This page used to stop there and admit it had not checked for others. It has now been enumerated, which took about a minute: re-solve with a no-good cut forbidding each optimum already found, until the solver's best answer exceeds 3,527. It does so at 3,529, and the complete list is 16 optimal tours — two genuinely different routes, each in 8 twin-relabellings. Note the status of that count: it was reported by the enumeration run on 2026-08-01, but the enumeration script is not in the published bundle and nothing here certifies the count; the certificate proves the optimal value, not the number of tours that attain it. The second route differs only at the very end, arriving Rimini → Portonovo → Ancona → Senigallia instead of Rimini → Ancona → Portonovo → Senigallia; Ancona and Portonovo are 9 km apart and the detour cancels exactly. verified

Which is why, if you run exact_tsp.py yourself, its last line prints a visiting order that is not the one published above. Both are in the 16. The solver reports whichever optimum it reaches first; the route file records the one the heuristic found. Nothing is wrong — but it is exactly the kind of discrepancy that should be stated in advance rather than discovered by a suspicious reader.

"But how do I trust the code?"

The right question — and the answer is that the workflow is arranged so you have to trust remarkably little of it — the blue nodes of the tree. Sorted from easiest to hardest:

That is the asymmetry the talk turns on: the solver may be a thousand lines of heuristics and floating point — irrelevant, because what it emits is a witness whose checking burden is tiny. How the tour was found (2-opt? simulated annealing? divine inspiration?) never enters the argument. Trust the certificate, not the solver.

A proof with no solver in it

"Trust the certificate, not the solver" was, until 2026-08-04, an aspiration on this page: the tour was checkable by hand, but optimality still went through HiGHS. That residual is now closed. In evidence/certificate/ there is a proof object that needs no solver, no linear algebra, no floating point — only integer arithmetic:

cd evidence/certificate
swipl -q -g run -t halt check_certificate.pl

Actual output on 2026-08-04 (macOS, SWI-Prolog 9.0.4, 0.6 s):

PASS (1) 563 edges = 561 published distances + 2 dummy edges
PASS (2) node 35 joins only stops 1 and 34, at zero cost
PASS (3) all 34 cuts are proper subsets (2 =< |S| =< 33)
PASS (4) the 226 leaves form a complete binary tree -- exhaustive
PASS (5) all 226 leaves bound every tour above 3526 km, so >= 3527 km
PASS (6) the published route is a valid 1..34 tour of 3527 km

VERIFIED: no tour of the 34 SEBD editions is shorter than 3527 km,
and a tour of exactly 3527 km exists.  3527 km is optimal.

The whole thing rests on one inequality. Give every stop a number y_v (any numbers) and every subtour cut a weight z_S ≥ 0 (any weights), and give each edge a reduced cost

d_e  =  c_e - y_u - y_v - (sum of z_S over the cuts that edge e crosses)

Then every tour costs at least

2*(sum of all y_v)  +  2*(sum of all z_S)  +  (sum of min(0, d_e) over all edges)

Why: every stop has exactly two tour edges, every tour crosses every cut at least twice, and a 0/1 variable can only hurt you where d_e is negative. Three lines of algebra — and, crucially, no assumption about where the numbers came from. A certificate that would break if its numbers came from a liar is not a certificate. verified (the inequality) — but see a second opinion: the checker did not enforce the inequality's preconditions until 2026-10-16.

One such inequality is not enough, and the shortfall is worth knowing: the best bound any single page of potentials can give — 35 numbers and 7 cuts, the full Held–Karp relaxation — is 3,447 km, some 80 km short. So the proof becomes a case analysis: a binary tree splitting on "this edge is used / is not used," where each branch is closed by its own inequality. Ours has 226 leaves, maximum depth 16, a pool of 34 cuts, about 16,000 integers, 99 KB. verified

That size is the finding, and it sharpens the talk's thesis rather than softening it: a napkin proves the tour exists; a small book proves that nothing beats it; and checking the small book still takes 0.6 seconds against 8 × 10¹⁸ years of exhaustive search. Note what check (4) does — it verifies the case analysis has no hole. A missing leaf is not an error in a proof; it is an unexamined case, which is exactly the failure a plausible-looking certificate would hide.

And to answer the obvious suspicion — does the checker actually bite, or does it pass everything? Six tampered copies were run against it:

One tampering is accepted, and should be: nudge a potential by a few units and you still have a valid proof, just a different one. A checker that rejected that would be policing provenance, not validity. verified (all seven runs; see README.org)

What is still trusted, stated plainly: SWI-Prolog's integer arithmetic; the checker itself (short enough to read, but written by the same agent that wrote the generator — and, as the next section shows, short enough to read is not the same as correct); and, as ever, the 561 distances, which are a claim about a model, not about Italy.

A second opinion — the checker had a hole

On 2026-10-16 another AI agent, OpenAI Codex, reviewed the abstract and this page without being told what we already knew. It read the checker, found what it does not check, and built a forgery that exploits it: give every leaf of the certificate a 36th “potential” for a node that does not exist, and claim the chronological route of 15,209 km. The bound counts the extra number; no edge ever subtracts it. The 2026-08-04 checker printed: verified (reproduced here)

VERIFIED: no tour of the 34 SEBD editions is shorter than 15209 km,
and a tour of exactly 15209 km exists.  15209 km is optimal.

The inequality was never wrong; the checker failed to enforce its preconditions (exactly 35 potentials, a model fixed in advance) and loaded the certificate as program code rather than data. verify.pl had a smaller gap of the same kind: it summed the stored legs without checking that they follow the visiting order. Six well-chosen tamperings, all rejected, had not been enough to show that the checker bites — a familiar lesson about tests written by the author of the code.

What survived, and why we know: the 3,527 km result stands. The unchanged certificate passes the hardened checker, and also a second checker Codex wrote for the review — Python, standard library, integer arithmetic, a different author in a different language, now shipped as independent_check.py. That is exactly the step the gaps ledger had listed as “the next honest step” since August. verified

What changed (2026-10-16): the checker now reads the certificate as data, fixes the model's size itself, and runs a new check (0) on the shape of every fact before anything else; verify.pl computes the length from the visiting order and checks each stored leg against it. The forgery and four related ones are now regression tests that must fail (tests/run_tests.py; run with --original to watch the August checker accept three of them). Every changed file, with hashes before and after, is logged in certificate/CORRECTIONS.org and Claude-artifacts/CORRECTIONS.org; the originals are kept beside them.

The same review also caught four errors in this page's prose: a table that gave the post-audit length as if it had been reported on the morning of the talk, a sentence that had the direction of the coordinate error backwards, a spreadsheet cross-check pointing at the other toolchain's distance table, and an overstated rounding bound. All four are corrected above and marked where they were. And it qualified one claim rather than correcting it: the count of 16 co-optimal tours is reported, not certified.

So the second opinion did what the page says second witnesses are for. The first time (the coordinates, 2026-08-01) a disagreeing source caught bad data; this time a disagreeing reader caught a bad checker. In both cases the certified claim survived, and in both cases only because someone other than its author looked.

How to distrust this page

Please do. Both artifact bundles are included under evidence/, byte-for-byte as hashed in August, with documented exceptions: the map script and its renderings (2026-10-12), and the two checkers after the second review (2026-10-16). Each bundle's CORRECTIONS.org (Claude-artifacts, certificate) says which files, why, and with which hashes before and after; the originals are kept beside them. Re-run the checkers; don't take our word:

# 1. Check the tour certificate (SWI-Prolog) — recomputes the length
#    from the distance table and validates the permutation:
cd evidence/Claude-artifacts
swipl -q -g run -t halt verify.pl

Actual output on 2026-08-01 (macOS, SWI-Prolog):

PASS: valid 1..34 permutation; recomputed = published = 3527 km

# 2. Prove optimality yourself (Python + scipy/HiGHS, <1 s):
python3 exact_tsp.py

Actual output on 2026-08-01 (tail):

  iter  6: cost   3527.0  subtours 1

=== EXACT RESULT ===
proven optimum (lower = upper bound): 3527 km
recovered optimal path length check : 3527 km   (start 1, end 34)
heuristic tour (route_optimized.pl) : 3527 km
==> heuristic is OPTIMAL: True
optimal order: 1 29 21 25 24 15 26 19 11 16 12 28 32 33 22 3 23 8 27
10 4 30 17 7 13 5 31 9 20 2 18 14 6 34

That last line is one of the other 15 optimal tours, not the one published above — see the co-optimality footnote. Both are 3,527 km.

# 3. Check optimality WITHOUT trusting any solver (SWI-Prolog, 0.6 s):
cd ../certificate
swipl -q -g run -t halt check_certificate.pl

Actual output on 2026-08-04 — six checks, quoted in full above, ending:

VERIFIED: no tour of the 34 SEBD editions is shorter than 3527 km,
and a tour of exactly 3527 km exists.  3527 km is optimal.

Since 2026-10-16 the hardened checker prints one more line first, and its timing on that day was 0.36 s:

PASS (0) well-formed: 35 nodes, 563 edges, 34 cuts, 226 leaves, 35 potentials each

This is the one to run if you believe only arithmetic. Try breaking it, too — and then run the breaking we already tried:

# 3b. Tampering tests, and a second checker by another author (Python 3, no packages):
python3 tests/run_tests.py
python3 independent_check.py

Actual output on 2026-10-16: 13 of 13 tests behave as expected. (eleven forgeries rejected, the original files and one harmless nudge accepted), then:

Independent Python check: 563 edges, 34 proper cuts, 226 leaves, 35 potentials per leaf; complete tree; all exact integer bounds > 3526.
Minimum scaled bound: 3526500 scale: 1000 maximum tree depth: 16

# 4. Reproduce the independent GPT bundle (fixed seed 20260618),
#    and check its file hashes:
cd ../GPT-artifacts
shasum -a 256 -c SHA256SUMS
./run.sh

Actual output on 2026-08-01: all 11 files OK, then:

Chronological total: 15263.9 km
Optimized total:     3546.9 km

— and the freshly reproduced route tables matched the shipped ones exactly. (The GPT bundle is untouched by the coordinate correction: it was always keyed to its own coordinate estimates, and its numbers stand exactly as first published.)

# 4. Check the Claude bundle's own hashes (added 2026-08-01):
cd ../Claude-artifacts
shasum -a 256 -c SHA256SUMS

Actual output on 2026-08-01: all 23 files OK. On 2026-10-12 the map script and its two renderings were corrected and their three entries re-stamped (see CORRECTIONS.org); re-run that day, all 23 files OK again. Note what that does and does not show. A hash list proves the files match the list, not that the list is original: whoever edits a file can re-stamp its hash. So the original three files and the original SHA256SUMS are kept in original-2026-08-01/, where they still check.

Still suspicious? Good — that's the right instinct. The distance tables are plain text (561 Prolog facts for the certified tour; 561 CSV rows for the GPT toolchain's own, different distances); sum any tour by hand. If this page and its evidence ever disagree, believe the evidence.

Known gaps — and whether they matter

A trust artifact should list what it doesn't establish. Most gaps are leaves of the evidence tree; the one that isn't is worth noticing. Our ledger:

Legend — what kind of claim is this?

Appendix: a side experiment from the ASP world

One cross-check deserves a footnote: a generic clingo (answer-set programming) encoding of the tour problem (tsp.lp) reached only 6,709 km after 90 seconds — corroborating, never competing. That feebleness is a known encoding issue, not an ASP one: Bertagnon & Gavanelli (Univ. Ferrara) give new TSP encodings in clingo[DL] — constraint ASP over difference logic — that are orders of magnitude faster, with a further geometric speedup for exactly our case, Euclidean instances with known coordinates (J. Logic and Computation 36(2), 2026, open access). primary source (the paper's claim).

In this page's spirit, we ran the experiment rather than just citing it (2026-07-18, same laptop; files in evidence/DL-experiment/) — and report an honest negative: our adaptation of the paper's SDLT and DLEB encodings (sdlt.lp, dleb.lp, transcribed from Listings 1+5+6 and 1+7+8) returned UNKNOWN in every 90-second run — unable even to confirm a tour of 3,541 km exists, where naive clingo at least reached 7,592 km. (Those two runs used the pre-correction distance table; the corrected instance re-runs naive clingo to 6,709 km, but clingo-dl is no longer installed on this machine, so the SDLT/DLEB runs have not been repeated and their numbers are quoted as of 2026-07-18. stale) This does not refute the paper; it measures the gap between citing a method and reproducing one. Known differences: our clingo-dl 1.5 build lacks the --minimize-variable option their tooling uses (we substituted an outer binary search on the bound); our instance is a path-TSP closed by a zero-cost dummy node; and we implemented none of their geometric (convex-hull) enhancements. Any of these may be decisive — finding out is a conversation to have with the authors, which seems fitting for a memento. AI-generated, verified (the runs happened as described) unverified (any explanation of why)