Traveling Salesman

Version:

Experience level: Intermediate
Reasoning types: Prescriptive
Industry: Supply Chain
Tags: RoutingMILP
Experience level: Intermediate
Reasoning types: Prescriptive
Industry: Supply Chain
Tags: RoutingMILP
Experience level: Intermediate
Reasoning types: Prescriptive
Industry: Logistics
Tags: routingmixed-integer-programmingcombinatorial-optimizationgraph

What this template is for

The traveling salesman problem (TSP) asks for the shortest closed route that visits every location exactly once. It shows up in real-world settings like routing a delivery vehicle, ordering inspection stops, or sequencing tool paths.

The challenge is combinatorial: as the number of locations grows, the number of possible tours explodes, so “try all routes” quickly becomes impractical. This template uses RelationalAI’s prescriptive reasoning (optimization) capabilities to model the TSP as a mixed-integer linear program (MILP) and solve for the shortest tour.

Who this is for

You want an end-to-end example of prescriptive reasoning (optimization) with RelationalAI.
You’re comfortable with basic Python and the idea of constraints + an objective.
You want to see a standard TSP MILP formulation (MTZ subtour elimination).

What you’ll build

A small semantic model of nodes and directed edges loaded from CSV.
A MILP with a binary decision variable for selecting edges in the tour.
Subtour elimination constraints using the Miller–Tucker–Zemlin (MTZ) ordering formulation.
A solver run using the HiGHS backend that prints the selected tour edges.

What’s included

Model + solve script: traveling_salesman.py
Sample data: data/distances.csv
Dependencies: pyproject.toml

Prerequisites

Access

A Snowflake account that has the RAI Native App installed.
A Snowflake user with permissions to access the RAI Native App.

Tools

Python >= 3.10

Quickstart

Follow these steps to run the template with the included sample data.

Download the ZIP file for this template and extract it:
Terminal window
```
curl -O https://private.relational.ai/templates/zips/v0.13/traveling_salesman.zip
unzip traveling_salesman.zip
cd traveling_salesman
```
You can also download the template ZIP using the “Download ZIP” button at the top of this page.

Create and activate a virtual environment

python -m venv .venv
source .venv/bin/activate
python -m pip install -U pip

Install dependencies

From this folder:
Terminal window
```
python -m pip install .
```
Configure Snowflake connection and RAI profile
Terminal window
```
rai init
```
Run the template
Terminal window
```
python traveling_salesman.py
```
Expected output

The exact tour may differ based on the data, but you should see a feasible solver status, the tour distance (objective), and a table of selected edges:
```
Status: OPTIMAL
Shortest tour distance: 8.50

Selected edges (tour):
 i  j  dist
 1  3   2.5
 2  1   2.0
 3  4   2.5
 4  2   1.5
```

Template structure

.
├─ README.md
├─ pyproject.toml
├─ traveling_salesman.py      # main runner / entrypoint
└─ data/
   └─ distances.csv           # directed edge distances

Start here: traveling_salesman.py

Sample data

Data files are in data/.

`distances.csv`

Defines the directed distance (travel cost) for each edge . For an undirected instance, you typically include both directions as separate rows.

Column	Meaning
`i`	Origin node identifier (integer)
`j`	Destination node identifier (integer)
`dist`	Distance/cost for traveling from `i` to `j` (float)

Model overview

The optimization model is built around two concepts.

`Edge`

A directed edge with a distance and a binary decision variable indicating whether the edge is selected in the tour.

Property	Type	Identifying?	Notes
`i`	int	Part of compound key	Loaded as the key from `data/distances.csv.i`
`j`	int	Part of compound key	Loaded as the key from `data/distances.csv.j`
`dist`	float	No	Loaded from `data/distances.csv.dist`
`x_edge`	float	No	Binary decision variable (0/1) indicating if edge is used

`Node`

A node (city/location) derived from the edge endpoints, with an integer “order” variable used by MTZ subtour elimination.

Property	Type	Identifying?	Notes
`v`	int	Yes	Derived from `Edge.i` to create the node set
`u_node`	float	No	Integer decision variable used to prevent subtours

How it works

This section walks through the highlights in traveling_salesman.py.

Import libraries and configure inputs

First, the script imports the Semantics APIs (Model, data, define, require, sum, where) and sets up DATA_DIR for local CSV loading:

from pathlib import Path

import pandas
from pandas import read_csv

from relationalai.semantics import (
    Model,
    count,
    data,
    define,
    require,
    select,
    sum,
    where,
)
from relationalai.semantics.reasoners.optimization import Solver, SolverModel


# --------------------------------------------------
# Configure inputs
# --------------------------------------------------

DATA_DIR = Path(__file__).parent / "data"

# Disable pandas inference of string types. This ensures that string columns
# in the CSVs are loaded as object dtype. This is only required when using
# relationalai versions prior to v1.0.
pandas.options.future.infer_string = False

Define concepts and load CSV data

Next, it defines an Edge concept keyed by (i, j), loads distances.csv via data(...).into(...), and derives the Node set from edge start nodes:

# --------------------------------------------------
# Define semantic model & load data
# --------------------------------------------------

# Create a Semantics model container.
model = Model("tsp", config=globals().get("config", None), use_lqp=False)

# Edge concept: directed edge (i -> j) with an associated distance.
Edge = model.Concept("Edge")
Edge.dist = model.Property("{Edge} has {dist:float}")

# Load edge distance data from CSV.
distances_csv = read_csv(DATA_DIR / "distances.csv")
data(distances_csv).into(Edge, keys=["i", "j"])

# Node concept: node identifiers derived from edge start nodes.
Node = model.Concept("Node")
define(Node.new(v=Edge.i))

Define decision variables

With the base entities in place, the template creates a SolverModel and registers two decision variables: Edge.x_edge to choose edges in the tour, and Node.x_u_node as an MTZ ordering variable:

# --------------------------------------------------
# Model the decision problem
# --------------------------------------------------

# Pre-compute the number of nodes (used by the MTZ formulation).

node_count = count(Node.ref())

Node_i = Node
Node_j = Node.ref()

s = SolverModel(model, "cont")

# Edge.x_edge decision variable: 1 if the edge is selected, 0 otherwise.
Edge.x_edge = model.Property("{Edge} is selected if {x:float}")
s.solve_for(Edge.x_edge, type="bin", name=["x", Edge.i, Edge.j])

# Node.x_u_node decision variable: ordering variable used for MTZ subtour elimination.
Node.x_u_node = model.Property("{Node} has auxiliary value {u:float}")
s.solve_for(Node.x_u_node, type="int", name=["u", Node.v], lower=1, upper=node_count)

Add constraints (degree constraints + MTZ subtour elimination)

Then it adds the standard TSP constraints: (1) symmetry breaking by fixing the start node’s order, (2) one incoming and one outgoing selected edge per node, and (3) MTZ subtour elimination to prevent disconnected cycles:

# Constraint: fix u=1 for node 1 (symmetry breaking).
start_node = require(Node.x_u_node == 1).where(Node.v == 1)
s.satisfy(start_node)

# Constraint: exactly one incoming and one outgoing edge per node.
incoming_flow = sum(Edge.x_edge).where(Edge.j == Node.v).per(Node)
outgoing_flow = sum(Edge.x_edge).where(Edge.i == Node.v).per(Node)
flow_balance = require(incoming_flow == 1, outgoing_flow == 1)
s.satisfy(flow_balance)

# Constraint: MTZ subtour elimination.
mtz = where(
    Edge.i > 1,
    Edge.j > 1,
  Node_i.v == Edge.i,
  Node_j.v == Edge.j
).require(
  Node_i.u_node - Node_j.u_node + node_count * Edge.x_edge <= node_count - 1
)
s.satisfy(mtz)

Minimize total distance and print the selected tour

Finally, it minimizes total distance, solves with HiGHS, and filters the selected edges with Edge.x_edge > 0.5 for printing:

# Objective: minimize total distance.
total_dist = sum(Edge.dist * Edge.x_edge)
s.minimize(total_dist)

# --------------------------------------------------
# Solve and check solution
# --------------------------------------------------

solver = Solver("highs")
s.solve(solver, time_limit_sec=60)

print(f"Status: {s.termination_status}")
print(f"Shortest tour distance: {s.objective_value:.2f}")

tour = select(Edge.i, Edge.j, Edge.dist).where(Edge.x_edge > 0.5).to_df()

print("\nSelected edges (tour):")
print(tour.to_string(index=False))

Customize this template

Use your own data

Replace data/distances.csv with your own edge list.
Ensure the file includes columns i, j, and dist.
For an undirected graph, include both directions (both and ).
Make sure every node appears at least once in the i column. (In this template, nodes are derived from Edge.i.)

Tune parameters

Increase the solver time limit by changing time_limit_sec=60 in traveling_salesman.py.
Change the symmetry-breaking start node by editing the constraint where(Node.v == 1).

Extend the model

Add rules to forbid certain edges (road closures) by requiring Edge.x_edge == 0 for those pairs.
Add additional objective terms (e.g., time, tolls) by extending the dist field or adding new edge attributes.

Troubleshooting

Why does authentication/configuration fail?

Run rai init to create/update raiconfig.toml.
If you have multiple profiles, set RAI_PROFILE or switch profiles in your config.

Why does the script fail to connect to the RAI Native App?

Verify the Snowflake account/role/warehouse and rai_app_name are correct in raiconfig.toml.
Ensure the RAI Native App is installed and you have access.

Why do I get ModuleNotFoundError?

Confirm your virtual environment is active (source .venv/bin/activate).
Reinstall dependencies from this folder: python -m pip install ..
Verify you’re using Python >= 3.10.

Why does reading data/distances.csv fail?

Confirm the file exists at data/distances.csv.
Verify the CSV has headers i, j, dist.
Ensure i and j are integers and dist is numeric.

Why do I get Status: INFEASIBLE or no tour?

Check that each node has at least one outgoing edge and at least one incoming edge in distances.csv.
For undirected instances, ensure you included both directions for each pair.
Start by testing a small, fully connected instance to validate the pipeline.

Why is the selected edge table empty?

The script prints edges with Edge.x_edge > 0.5. If the solve did not reach a feasible solution, the filter may remove everything.
Check the printed status and consider increasing time_limit_sec.

What this template is for

Who this is for

You want an end-to-end example of prescriptive reasoning (optimization) with RelationalAI.
You’re comfortable with basic Python and the idea of constraints + an objective.
You want to see a standard TSP MILP formulation (MTZ subtour elimination).

What you’ll build

A small semantic model of nodes and directed edges loaded from CSV.
A MILP with a binary decision variable for selecting edges in the tour.
Subtour elimination constraints using the Miller–Tucker–Zemlin (MTZ) ordering formulation.
A solver run using the HiGHS backend that prints the selected tour edges.

What’s included

Model + solve script: traveling_salesman.py
Sample data: data/distances.csv
Dependencies: pyproject.toml

Prerequisites

Access

A Snowflake account that has the RAI Native App installed.
A Snowflake user with permissions to access the RAI Native App.

Tools

Python >= 3.10

Quickstart

Follow these steps to run the template with the included sample data.

Download the ZIP file for this template and extract it:
Terminal window
```
curl -O https://private.relational.ai/templates/zips/v0.14/traveling_salesman.zip
unzip traveling_salesman.zip
cd traveling_salesman
```
You can also download the template ZIP using the “Download ZIP” button at the top of this page.

Create and activate a virtual environment

python -m venv .venv
source .venv/bin/activate
python -m pip install -U pip

Install dependencies

From this folder:
Terminal window
```
python -m pip install .
```
Configure Snowflake connection and RAI profile
Terminal window
```
rai init
```
Run the template
Terminal window
```
python traveling_salesman.py
```
Expected output

The exact tour may differ based on the data, but you should see a feasible solver status, the tour distance (objective), and a table of selected edges:
```
Status: OPTIMAL
Shortest tour distance: 8.50

Selected edges (tour):
 i  j  dist
 1  3   2.5
 2  1   2.0
 3  4   2.5
 4  2   1.5
```

Template structure

.
├─ README.md
├─ pyproject.toml
├─ traveling_salesman.py      # main runner / entrypoint
└─ data/
   └─ distances.csv           # directed edge distances

Start here: traveling_salesman.py

Sample data

Data files are in data/.

`distances.csv`

Defines the directed distance (travel cost) for each edge . For an undirected instance, you typically include both directions as separate rows.

Column	Meaning
`i`	Origin node identifier (integer)
`j`	Destination node identifier (integer)
`dist`	Distance/cost for traveling from `i` to `j` (float)

Model overview

The optimization model is built around two concepts.

`Edge`

A directed edge with a distance and a binary decision variable indicating whether the edge is selected in the tour.

Property	Type	Identifying?	Notes
`i`	int	Part of compound key	Loaded as the key from `data/distances.csv.i`
`j`	int	Part of compound key	Loaded as the key from `data/distances.csv.j`
`dist`	float	No	Loaded from `data/distances.csv.dist`
`x_edge`	float	No	Binary decision variable (0/1) indicating if edge is used

`Node`

A node (city/location) derived from the edge endpoints, with an integer “order” variable used by MTZ subtour elimination.

Property	Type	Identifying?	Notes
`v`	int	Yes	Derived from `Edge.i` to create the node set
`x_u_node`	float	No	Integer decision variable used to prevent subtours

How it works

This section walks through the highlights in traveling_salesman.py.

Import libraries and configure inputs

First, the script imports the Semantics APIs (Model, data, define, require, sum, where) and sets up DATA_DIR for local CSV loading:

from pathlib import Path

import pandas
from pandas import read_csv

from relationalai.semantics import (
    Model,
    count,
    data,
    define,
    require,
    select,
    sum,
    where,
)
from relationalai.semantics.reasoners.optimization import Solver, SolverModel


# --------------------------------------------------
# Configure inputs
# --------------------------------------------------

DATA_DIR = Path(__file__).parent / "data"

# Disable pandas inference of string types. This ensures that string columns
# in the CSVs are loaded as object dtype. This is only required when using
# relationalai versions prior to v1.0.
pandas.options.future.infer_string = False

Define concepts and load CSV data

Next, it defines an Edge concept keyed by (i, j), loads distances.csv via data(...).into(...), and derives the Node set from edge start nodes:

# --------------------------------------------------
# Define semantic model & load data
# --------------------------------------------------

# Create a Semantics model container.
model = Model("tsp", config=globals().get("config", None))

# Edge concept: directed edge (i -> j) with an associated distance.
Edge = model.Concept("Edge")
Edge.dist = model.Property("{Edge} has {dist:float}")

# Load edge distance data from CSV.
distances_csv = read_csv(DATA_DIR / "distances.csv")
data(distances_csv).into(Edge, keys=["i", "j"])

# Node concept: node identifiers derived from edge start nodes.
Node = model.Concept("Node")
define(Node.new(v=Edge.i))

Define decision variables

With the base entities in place, the template creates a SolverModel and registers two decision variables: Edge.x_edge to choose edges in the tour, and Node.x_u_node as an MTZ ordering variable:

# --------------------------------------------------
# Model the decision problem
# --------------------------------------------------

# Pre-compute the number of nodes (used by the MTZ formulation).
node_count = count(Node.ref())

NodeFrom = Node
NodeTo = Node.ref()

s = SolverModel(model, "cont")

# Edge.x_edge decision variable: 1 if the edge is selected, 0 otherwise.
Edge.x_edge = model.Property("{Edge} is selected if {x:float}")
s.solve_for(Edge.x_edge, type="bin", name=["x", Edge.i, Edge.j])

# Node.x_u_node decision variable: ordering variable used for MTZ subtour elimination.
Node.x_u_node = model.Property("{Node} has auxiliary value {u:float}")
s.solve_for(Node.x_u_node, type="int", name=["u", Node.v], lower=1, upper=node_count)

Add constraints (degree constraints + MTZ subtour elimination)

# Constraint: fix u=1 for node 1 (symmetry breaking).
start_node = require(Node.x_u_node == 1).where(Node.v == 1)
s.satisfy(start_node)

# Constraint: exactly one incoming and one outgoing edge per node.
incoming_flow = sum(Edge.x_edge).where(Edge.j == Node.v).per(Node)
outgoing_flow = sum(Edge.x_edge).where(Edge.i == Node.v).per(Node)
flow_balance = require(incoming_flow == 1, outgoing_flow == 1)
s.satisfy(flow_balance)

# Constraint: MTZ subtour elimination.
mtz = where(
    Edge.i > 1,
    Edge.j > 1,
    NodeFrom.v == Edge.i,
    NodeTo.v == Edge.j
).require(
    NodeFrom.x_u_node - NodeTo.x_u_node + node_count * Edge.x_edge <= node_count - 1
)
s.satisfy(mtz)

Minimize total distance and print the selected tour

Finally, it minimizes total distance, solves with HiGHS, and filters the selected edges with Edge.x_edge > 0.5 for printing:

# Objective: minimize total distance.
total_dist = sum(Edge.dist * Edge.x_edge)
s.minimize(total_dist)

# --------------------------------------------------
# Solve and check solution
# --------------------------------------------------

solver = Solver("highs")
s.solve(solver, time_limit_sec=60)

print(f"Status: {s.termination_status}")
print(f"Shortest tour distance: {s.objective_value:.2f}")

tour = select(Edge.i, Edge.j, Edge.dist).where(Edge.x_edge > 0.5).to_df()

print("\nSelected edges (tour):")
print(tour.to_string(index=False))

Customize this template

Use your own data

Replace data/distances.csv with your own edge list.
Ensure the file includes columns i, j, and dist.
For an undirected graph, include both directions (both and ).
Make sure every node appears at least once in the i column. (In this template, nodes are derived from Edge.i.)

Tune parameters

Increase the solver time limit by changing time_limit_sec=60 in traveling_salesman.py.
Change the symmetry-breaking start node by editing the constraint where(Node.v == 1).

Extend the model

Add rules to forbid certain edges (road closures) by requiring Edge.x_edge == 0 for those pairs.
Add additional objective terms (e.g., time, tolls) by extending the dist field or adding new edge attributes.

Troubleshooting

Why does authentication/configuration fail?

Run rai init to create/update raiconfig.toml.
If you have multiple profiles, set RAI_PROFILE or switch profiles in your config.

Why does the script fail to connect to the RAI Native App?

Verify the Snowflake account/role/warehouse and rai_app_name are correct in raiconfig.toml.
Ensure the RAI Native App is installed and you have access.

Why do I get ModuleNotFoundError?

Confirm your virtual environment is active (source .venv/bin/activate).
Reinstall dependencies from this folder: python -m pip install ..
Verify you’re using Python >= 3.10.

Why does reading data/distances.csv fail?

Confirm the file exists at data/distances.csv.
Verify the CSV has headers i, j, dist.
Ensure i and j are integers and dist is numeric.

Why do I get Status: INFEASIBLE or no tour?

Check that each node has at least one outgoing edge and at least one incoming edge in distances.csv.
For undirected instances, ensure you included both directions for each pair.
Start by testing a small, fully connected instance to validate the pipeline.

Why is the selected edge table empty?

The script prints edges with Edge.x_edge > 0.5. If the solve did not reach a feasible solution, the filter may remove everything.
Check the printed status and consider increasing time_limit_sec.

What this template is for

The traveling salesman problem (TSP) is one of the most studied problems in combinatorial optimization: given a set of cities and the distances between them, find the shortest tour that visits every city exactly once and returns to the starting city. TSP has practical applications in route planning, circuit board drilling, delivery logistics, and many other domains.

This template solves a small TSP instance using the Miller-Tucker-Zemlin (MTZ) formulation, which eliminates subtours through auxiliary ordering variables rather than exponentially many subtour-elimination constraints. The model uses binary decision variables for edge selection and integer auxiliary variables for node ordering, solved as a mixed-integer program with HiGHS.

The MTZ formulation is compact and well-suited for small to medium instances. For larger problems, more sophisticated formulations (cutting planes, branch-and-cut) would be needed, but this template provides a clear, self-contained starting point for understanding TSP modeling with RelationalAI.

Who this is for

Operations researchers learning TSP formulations
Logistics planners building route optimization prototypes
Students studying combinatorial optimization
Developers exploring mixed-integer programming with RelationalAI

What you’ll build

An MTZ-based TSP formulation with binary edge variables and integer ordering variables
Degree constraints ensuring exactly one in-edge and one out-edge per node
Subtour elimination via MTZ auxiliary variables
Optimal tour extraction from solver results

What’s included

traveling_salesman.py — main script with ontology, MTZ formulation, and solver call
data/edges.csv — 12 directed edges between 4 nodes with distances
pyproject.toml — Python package configuration

Prerequisites

Access

A Snowflake account that has the RAI Native App installed.
A Snowflake user with permissions to access the RAI Native App.

Tools

Python >= 3.10

Quickstart

Download ZIP:
Terminal window
```
curl -O https://docs.relational.ai/templates/zips/v1/traveling_salesman.zip
unzip traveling_salesman.zip
cd traveling_salesman
```
You can also download the template ZIP using the “Download ZIP” button at the top of this page.

Create venv:

python -m venv .venv
source .venv/bin/activate
python -m pip install --upgrade pip

Install:
Terminal window
```
python -m pip install .
```
Configure:
Terminal window
```
rai init
```
Run:
Terminal window
```
python traveling_salesman.py
```

Expected output:

Status: OPTIMAL
Tour distance: 8.50

Tour edges:
 from  to
    1   2
    2   4
    4   3
    3   1

Template structure

.
├── README.md
├── pyproject.toml
├── traveling_salesman.py
└── data/
    └── edges.csv

How it works

1. Load the edge data and derive nodes. Edges with distances are loaded from CSV. Nodes are derived from edge endpoints:

Edge = model.Concept("Edge", identify_by={"i": Integer, "j": Integer})
Edge.dist = model.Property(f"{Edge} has {Float:dist}")

Node = model.Concept("Node", identify_by={"v": Integer})
model.define(Node.new(v=Edge.i))

2. Define decision variables. Binary variables x[i,j] select edges in the tour. Integer auxiliary variables u[v] enforce node ordering for subtour elimination:

Edge.x = model.Property(f"{Edge} is selected if {Float:x}")
problem.solve_for(Edge.x, type="bin", name=["x", Edge.i, Edge.j])

Node.u = model.Property(f"{Node} has auxiliary value {Float:u}")
problem.solve_for(Node.u, name=["u", Node.v], type="int", lower=1, upper=node_count)

3. Add degree constraints. Every node must have exactly one incoming and one outgoing edge:

node_flow = sum(Edge.x).per(Node)
problem.satisfy(model.require(
    node_flow.where(Edge.j == Node.v) == 1,
    node_flow.where(Edge.i == Node.v) == 1
))

4. Add MTZ subtour elimination. If edge (i,j) is in the tour, then the ordering of j must be at least one more than i. This prevents disconnected subtours:

problem.satisfy(model.where(
    Ni := Node, Nj := Node.ref(),
    Edge.i > 1, Edge.j > 1,
    Ni.v(Edge.i), Nj.v(Edge.j),
).require(
    Ni.u - Nj.u + node_count * Edge.x <= node_count - 1
))

5. Minimize total tour distance:

total_dist = sum(Edge.dist * Edge.x)
problem.minimize(total_dist)

Customize this template

Use your own distance data by replacing edges.csv with your city-to-city distance matrix (as a list of directed edges).
Scale to more cities by adding nodes and edges. The MTZ formulation works well for up to ~50 nodes.
Add asymmetric costs — the formulation already supports directed edges with different forward/reverse distances.
Add time windows by introducing arrival time variables and constraints per node.
Visualize the tour by plotting nodes and selected edges with matplotlib.

Troubleshooting

Solver returns INFEASIBLE

Ensure edges.csv contains edges in both directions for every pair of nodes (the graph must be strongly connected).
Verify that node indices are consistent: every node referenced in an edge must appear as both a source and a destination.

Import error for relationalai

Confirm your virtual environment is active: which python should point to .venv.
Reinstall dependencies: python -m pip install ..

Authentication or configuration errors

Run rai init to create or update your RelationalAI/Snowflake configuration.
If you have multiple profiles, set export RAI_PROFILE=<your_profile>.

Slow solve times for larger instances

The MTZ formulation has O(n^2) subtour elimination constraints, which can be slow for large n.
Consider reducing the time_limit_sec parameter and accepting near-optimal solutions.
For production-scale TSP (100+ cities), consider specialized TSP solvers or cutting-plane approaches.