routing-subtour-elimination
Subtour-elimination methods for TSP, VRP, pickup/dropoff routing, and routing MIPs with binary arc variables
Install / Use
npx skills add benchflow-ai/skillsbench --skill routing-subtour-eliminationInstalls into whichever agent you are using.
SKILL.md
Installable skill definition
Quality Score
Category
Development & EngineeringSupported Platforms
Tags
Our assessment of routing-subtour-elimination
routing-subtour-elimination scores 85/100 on our quality scale, 2543rd of 4,700 Development & Engineering skills we index.
Its SKILL.md is 8.5 KB long, well organised into 8 sections with 8 code examples: a thorough specification that gives an agent plenty to work with.
With 1,813 GitHub stars, it is one of the more widely adopted skills in the catalogue.
Maintenance, license and trust
- The repository was last updated about 4 months ago. That is recent enough to be usable, but agent tooling moves fast, so check the instructions against your agent's current version.
- Our last check on 2026-11-04 found the source still online.
- It is released under the Apache-2.0 license, a permissive license that allows use, modification and commercial use with attribution.
- Its trust signals score 98/100, with no cautions. These come from repository metadata, not a code audit — read the skill file before letting an agent act on it.
Safety scan
No issues foundOur scan of the whole file found no instruction hijacking, hidden characters, credential access, data exfiltration or destructive commands. An AI review of the same text found nothing harmful.
AI review by kimi-k2.7-code on 2026-10-01. Automated pattern scan on 2026-09-30. It catches known dangerous patterns, not every risk — read a skill before letting an agent act on it.
routing-subtour-elimination compared with similar skills
All 4 of these similar skills score higher than routing-subtour-elimination; compare them before choosing.
| Skill | Score | Stars | Updated | Format |
|---|---|---|---|---|
| routing-subtour-elimination (this skill)by benchflow-ai | 85 | 1.8k | 4mo ago | SKILL.md |
| taste-skillby Leonxlnx | 100 | 116.8k | 8d ago | CLAUDE.md |
| ai-job-searchby ai-job-search-dev | 100 | 72.1k | today | CLAUDE.md |
| claude-howtoby luongnv89 | 100 | 47.3k | 2d ago | CLAUDE.md |
| lobehubby lobehub | 100 | 85.6k | today | MCP Server |
Frequently asked questions
- How do I install routing-subtour-elimination?
- Run
npx skills add benchflow-ai/skillsbench --skill routing-subtour-elimination. The install tabs above show the steps for each supported agent. - Which AI agents does routing-subtour-elimination work with?
- It is written for Universal, as a SKILL.md file. Other agents that read the same format can often use it too.
- Is routing-subtour-elimination safe to use?
- Our scan of the whole file found no instruction hijacking, hidden characters, credential access, data exfiltration or destructive commands. An AI review of the same text found nothing harmful. It is Apache-2.0-licensed and scores 98/100 on trust signals. Skills are instructions an agent will follow, so read the file before installing it and do not approve commands you do not understand.
- Is routing-subtour-elimination still maintained?
- The repository was last updated about 4 months ago. That is recent enough to be usable, but agent tooling moves fast, so check the instructions against your agent's current version.
Skill content
View source on GitHubname: routing-subtour-elimination description: Subtour-elimination methods for TSP, VRP, pickup/dropoff routing, and routing MIPs with binary arc variables. Use when route-continuity constraints may permit disconnected cycles and the model needs MTZ constraints, flow-based connectivity constraints, DFJ subset cuts, or lazy/iterative subtour cuts.
Routing Subtour Elimination
In routing MIPs, degree and continuity constraints are not enough. A vehicle can have one depot-to-depot path and a separate closed cycle among stations. Add subtour-elimination constraints whenever binary arc variables decide routes.
Use this base notation:
START = "depot_start"
END = "depot_end"
vehicles = range(K)
stations = range(n)
from_nodes = [START, *stations]
to_nodes = [*stations, END]
arcs = [(i, j) for i in from_nodes for j in to_nodes if i != j and not (i == START and j == END)]
x = {(v, i, j): model.addVar(vtype="B", name=f"x_{v}_{i}_{j}") for v in vehicles for i, j in arcs}
Required Base Route Constraints
Subtour elimination assumes each selected station has matching inbound and outbound route arcs.
for v in vehicles:
model.addCons(quicksum(x[v, START, j] for j in stations) == 1)
model.addCons(quicksum(x[v, i, END] for i in stations) == 1)
for i in stations:
incoming = quicksum(x[v, j, i] for j in from_nodes if j != i)
outgoing = quicksum(x[v, i, j] for j in to_nodes if j != i)
model.addCons(incoming == outgoing)
model.addCons(outgoing <= 1)
The subtour methods below prevent station-only cycles that are disconnected from START.
1. MTZ Order Constraints
MTZ adds an order variable for each vehicle-station pair. If vehicle v travels from station i to station j, then order[v, j] must be greater than order[v, i].
order = {
(v, i): model.addVar(vtype="C", lb=1, ub=max(1, n), name=f"order_{v}_{i}")
for v in vehicles
for i in stations
}
for v in vehicles:
for i in stations:
for j in stations:
if i != j:
model.addCons(order[v, i] - order[v, j] + n * x[v, i, j] <= n - 1)
Pros:
- Compact:
O(K n^2)constraints andO(K n)extra variables. - Easy to implement in common Python optimization APIs.
- Good default for small and medium benchmark instances.
Cons:
- LP relaxation is weak compared with cutset or flow formulations.
- Can be slow for larger VRPs.
- Order variables are artificial; do not interpret them as service times unless you also model time.
Use MTZ first when correctness and implementation speed matter more than best possible MIP strength.
2. Single-Commodity Flow Connectivity
Add an artificial connectivity flow that starts at the depot and sends one unit to every visited station. This flow is not physical vehicle load.
visit = {
(v, i): quicksum(x[v, i, j] for j in to_nodes if j != i)
for v in vehicles
for i in stations
}
flow_arcs = [(i, j) for i in [START, *stations] for j in stations if i != j]
f = {
(v, i, j): model.addVar(vtype="C", lb=0, ub=n, name=f"conn_flow_{v}_{i}_{j}")
for v in vehicles
for i, j in flow_arcs
}
for v in vehicles:
total_visits = quicksum(visit[v, i] for i in stations)
model.addCons(quicksum(f[v, START, j] for j in stations) == total_visits)
for i, j in flow_arcs:
model.addCons(f[v, i, j] <= n * x[v, i, j])
for i in stations:
incoming_flow = quicksum(f[v, h, i] for h in [START, *stations] if h != i)
outgoing_flow = quicksum(f[v, i, j] for j in stations if j != i)
model.addCons(incoming_flow - outgoing_flow == visit[v, i])
Pros:
- Stronger connectivity logic than MTZ in many models.
- Static constraints, no callback needed.
- Works with optional station visits.
Cons:
- Adds
O(K n^2)continuous variables. - Do not reuse truck load as the connectivity flow when the vehicle can both pick up and drop off. Physical load can increase and decrease; connectivity flow should monotonically distribute artificial units.
- More memory than MTZ.
Use this when MTZ gives weak incumbents or slow progress and the instance is still modest in size.
3. DFJ Subset Cuts
For every nonempty proper subset S of stations, selected station-to-station arcs inside S cannot form a closed cycle:
sum_{i in S, j in S, i != j} x[v,i,j] <= |S| - 1
For very small n, static enumeration is possible:
from itertools import combinations
for v in vehicles:
for r in range(2, n):
for S_tuple in combinations(stations, r):
S = set(S_tuple)
model.addCons(
quicksum(x[v, i, j] for i in S for j in S if i != j) <= len(S) - 1
)
Pros:
- Strong, direct subtour elimination.
- No artificial order or flow variables.
Cons:
- Exponential number of constraints.
- Static enumeration is only acceptable for small station counts.
Use static DFJ only for tiny instances or as a debugging baseline.
4. Lazy or Iterative Cut Separation
The strongest practical pattern is to solve with base route constraints, detect subtours in incumbents, add only the violated DFJ cuts, and continue.
In solvers with convenient lazy callbacks, add cuts during branch-and-bound. Some Python solver APIs require callback or constraint-handler plumbing for true lazy enforcement, so iterative cut separation is often simpler for portable benchmark code:
def selected_arcs(model, x, v, arcs):
return [(i, j) for i, j in arcs if model.getVal(x[v, i, j]) > 0.5]
def station_cycles_without_start(selected, stations):
succ = {i: j for i, j in selected}
cycles = []
seen = set()
for start in stations:
if start in seen or start not in succ:
continue
path = []
cur = start
pos = {}
while cur in succ and cur not in pos and cur not in seen:
pos[cur] = len(path)
path.append(cur)
cur = succ[cur]
seen.update(path)
if cur in pos:
cycle = path[pos[cur]:]
if START not in cycle and END not in cycle:
cycles.append(cycle)
return cycles
while True:
model.optimize()
if model.getNSols() == 0:
raise RuntimeError(f"no feasible solution; status={model.getStatus()}")
cuts_added = 0
for v in vehicles:
selected = selected_arcs(model, x, v, arcs)
for cycle in station_cycles_without_start(selected, stations):
if len(cycle) >= 2:
S = set(cycle)
model.freeTransform()
model.addCons(
quicksum(x[v, i, j] for i in S for j in S if i != j) <= len(S) - 1
)
cuts_added += 1
if cuts_added == 0:
break
Pros:
- Adds only cuts that are needed.
- Often stronger than MTZ.
- Avoids exponential static SEC generation.
Cons:
- Iterative resolve can be slower than a true callback.
- Requires reliable subtour detection.
- More moving parts than MTZ.
Use this when static MTZ is too weak and the solver environment does not make lazy callbacks convenient.
Method Choice
| Method | Best For | Avoid When |
| --- | --- | --- |
| MTZ | Quick, compact, small/medium MIPs | Large hard VRPs where relaxation strength matters |
| Single-commodity flow | Stronger static connectivity, optional visits | Memory is tight, or n is large |
| Multi-commodity flow | Very strong small routing models | Most practical benchmark tasks; too many variables |
| Static DFJ | Tiny instances, debugging | More than roughly 15-18 stations without careful filtering |
| Lazy/iterative DFJ cuts | Strong routing models with many possible SECs | Solver API/callback complexity is too risky |
For pickup/dropoff rebalancing, start with MTZ or artificial connectivity flow. Do not use physical truck load as the only subtour-elimination mechanism because pickup/dropoff load can increase and decrease and may not prove route connectivity.
Validation
After solving, reconstruct each route by following selected arcs:
def extract_route(selected):
outgoing = dict(selected)
route = [START]
cur = START
seen = {START}
while cur != END:
if cur not in outgoing:
raise RuntimeError(f"route disconnected at {cur!r}")
cur = outgoing[cur]
if cur in seen and cur != END:
raise RuntimeError(f"cycle detected at {cur!r}")
route.append(cur)
seen.add(cur)
return route
Fail fast if a selected solution has a disconnected cycle, repeated station, missing depot start, or missing depot end.
Related Skills
taste-skill
116.8kAgent skills that give coding agents taste: art direction, reference images and a browser check instead of generic AI pages
ai-job-search
72.1kThe job search that runs on your machine. AI job application framework built on Claude Code: evaluate postings, tailor CVs, write cover letters, prep interviews. Fork it and own it.
claude-howto
47.3kA visual, example-driven guide to Claude Code — from basic concepts to advanced agents, with copy-paste templates that bring immediate value.
lobehub
85.6k🤯 LobeHub - Super-Agents on Your Team. Add super-agents to the chats your team already uses.They take on work by themselves and get better every week.
Languages
Trust signals
From repository metadata: license, adoption, age and documentation. Not a code audit — see the Safety scan above for what the skill file itself contains.
