TSP_MTZ_Formulation_Skill

Workflow 1 (Integer Programming with MTZ)

Modeling stage

Strategy Overview

This workflow models the TSP as a Mixed-Integer Program (MIP) using binary arc selection variables and integer position variables for subtour elimination via the Miller-Tucker-Zemlin (MTZ) constraints. It is a direct, portable formulation suitable for general-purpose MIP/CP-SAT solvers.

Step 1 - Define Sets and Parameters

• Define a set of nodes to be visited, typically indexed from 0 to N-1.
• Define a cost matrix parameter, cost[i][j], representing the travel cost from node i to node j. Ensure the matrix is square and self-loop costs are set to a large value or zero as appropriate.

Step 2 - Create Decision Variables

• Create binary decision variables x[i][j] for each ordered pair of distinct nodes. x[i][j] = 1 indicates the tour includes the arc from i to j.
• Create integer position variables u[i] for each node, representing its order in the tour. Bound them appropriately (e.g., 0 to N-1).

Step 3 - Formulate Degree Constraints

• For each node i, add a constraint ensuring exactly one outgoing arc: sum_{j != i} x[i][j] == 1.
• For each node j, add a constraint ensuring exactly one incoming arc: sum_{i != j} x[i][j] == 1.

Step 4 - Implement MTZ Subtour Elimination

• For all pairs of nodes i, j (where i and j are not the designated start node), add the MTZ constraint: u[i] - u[j] + N * x[i][j] <= N - 1.
• Fix the position of the start node to break symmetry: u[start_node] = 0.

Step 5 - Define the Objective Function

• Formulate the objective to minimize total travel cost: minimize sum_{i,j} cost[i][j] * x[i][j].

Formulation Template

{
  "sets": [
    "nodes: list of node indices (e.g., [0, 1, ..., N-1])"
  ],
  "parameters": [
    "cost: a |nodes| x |nodes| matrix of travel costs"
  ],
  "decision_variables": [
    "x[i][j]: binary, 1 if arc i->j is used",
    "u[i]: integer, position of node i in the tour"
  ],
  "objective": {
    "sense": "min",
    "expression": "sum_{i in nodes} sum_{j in nodes} cost[i][j] * x[i][j]"
  },
  "constraints": [
    "single_departure(i): sum_{j in nodes, j != i} x[i][j] == 1, for all i",
    "single_arrival(j): sum_{i in nodes, i != j} x[i][j] == 1, for all j",
    "mtz(i,j): u[i] - u[j] + |nodes| * x[i][j] <= |nodes| - 1, for all i,j where i != start_node, j != start_node, i != j",
    "start_position: u[start_node] == 0",
    "no_self_loop: x[i][i] == 0, for all i"
  ]
}