HLPL / VerTeX Modelling Language Documentation

← examples

# Traveling Salesman Problem (TSP)
# Finds the shortest tour visiting all nodes exactly once and returning to start
# Uses MTZ (Miller-Tucker-Zemlin) constraints to eliminate subtours

model ts
set N = {1, 2, 3, 4, 5, 6, 7}                              # Nodes (cities)
set E = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13}       # Edges in the graph

set sigma(N) = load_sigma()                                 # Neighbors of each node

const d = {5, 3, 6, 4, 4, 3, 1, 2, 3, 1, 3, 1, 2}, forall e in E  # Distance of edge e

bin x, forall i in N, forall j in N                        # 1 if arc (i,j) is in tour
int 0 <= u <= infty, forall n in N                         # MTZ variables for subtour elimination

# Objective: Minimize total tour distance (considering edges are undirected)
min sum_{e in E}{d_{e} * x_{alpha(e), beta(e)} + d_{e} * x_{beta(e), alpha(e)}}

# Each node has exactly one outgoing arc
constr sum_{j in sigma(i)}{x_{i,j}} = 1, forall i in N

# Each node has exactly one incoming arc
constr sum_{j in sigma(i)}{x_{j,i}} = 1, forall i in N

# MTZ subtour elimination constraints
constr u_{i} - u_{j} + |N| * x_{i,j} <= |N| - 1, forall i in N setminus {1}, forall j in sigma(i) setminus {1}

# Bounds on MTZ variables
constr u_{n} <= |N| - 1, forall n in N setminus {1}
constr u_{n} >= 1, forall n in N setminus {1}
end

import elytica as e
import json

def load_sigma():
    """Load adjacency list for each node (neighbors)"""
    S = {
        1: [2, 3, 7],
        2: [1, 3, 4],
        3: [1, 2, 4, 5, 7],
        4: [2, 3, 5, 6],
        5: [3, 4, 6, 7],
        6: [4, 5, 7],
        7: [1, 3, 5, 6]
    }
    return S

def alpha(edge: int):
    """Get source node of edge"""
    A = {1: 1, 2: 1, 3: 1, 4: 2, 5: 2, 6: 3, 7: 3, 8: 3, 9: 5, 10: 4, 11: 4, 12: 5, 13: 7}
    return A[edge]

def beta(edge: int):
    """Get target node of edge"""
    B = {1: 2, 2: 3, 3: 7, 4: 4, 5: 3, 6: 4, 7: 5, 8: 7, 9: 7, 10: 6, 11: 5, 12: 6, 13: 6}
    return B[edge]

def main():
    e.init_model("ts")
    e.run_model("ts")

    N = e.get_model_set("ts", "N")

    print("\n" + "="*60)
    print("TRAVELING SALESMAN PROBLEM SOLUTION")
    print("="*60)

    # Collect tour edges
    tour_edges = []
    print("\nTour Edges:")
    print("-"*60)
    for i in N:
        for j in N:
            val = e.get_variable_value("ts", f"x{i},{j}")
            if val > 0.5:
                tour_edges.append({"from": i, "to": j})
                print(f"  {i} -> {j}")

    # Collect MTZ variables (for debugging/verification)
    print("\n" + "-"*60)
    print("MTZ Variables (order in tour):")
    print("-"*60)
    mtz_values = {}
    for i in N:
        u_val = e.get_variable_value("ts", f"u{i}")
        if u_val is not None:
            mtz_values[i] = u_val
            if i != 1:  # Node 1 is the depot, u_1 is not constrained
                print(f"  u[{i}] = {u_val:.2f}")

    # Reconstruct ordered tour starting from node 1
    ordered_tour = [1]
    current = 1
    visited = {1}

    while len(ordered_tour) < len(N):
        for edge in tour_edges:
            if edge["from"] == current and edge["to"] not in visited:
                ordered_tour.append(edge["to"])
                visited.add(edge["to"])
                current = edge["to"]
                break

    # Add return to start
    ordered_tour.append(1)

    # Get objective value
    obj_value = e.get_best_primal_bound("ts")

    print("\n" + "-"*60)
    print(f"Ordered Tour: {' -> '.join(map(str, ordered_tour))}")
    print(f"\nTotal Distance: {obj_value:.2f}")
    print("="*60)

    # Prepare results for output
    results = {
        "objective_value": obj_value,
        "tour_edges": tour_edges,
        "ordered_tour": ordered_tour,
        "mtz_values": mtz_values
    }

    e.write_results(json.dumps(results, indent=2))

    return 0

Read this through MCP: read with path: "examples/tsp", or resource hlpl://examples/tsp.