🧩 Constraint Solving POTD:Problem of the Day: Chinese Postman Problem

[github-actions[bot]]

Problem Statement

The Chinese Postman Problem (CPP) asks: Given an undirected weighted graph representing a road network, find the shortest closed walk that traverses every edge at least once.

In other words, a postman must deliver mail to every street in a city (represented as edges in a graph) and return to the starting point. Unlike the Traveling Salesman Problem, which visits cities (nodes), the postman must traverse streets (edges). If all streets form an Eulerian circuit (all nodes have even degree), a solution uses each edge exactly once. Otherwise, some edges must be traversed more than once.

Concrete Instance

Consider a small town with 5 intersections connected as follows:

     A ---5--- B
    / \        |
   3   7       4
  /     \      |
 E ------6--- C
  \           /
   8        2
    \       /
     ------D

• Edges: A–B (5), A–C (7), A–E (3), B–C (4), C–D (2), D–E (8), E–C (6)
• Task: Find the shortest closed walk starting at A that traverses every edge at least once.

Input & Output

• Input: An undirected weighted graph G = (V, E) with edge weights w: E → R+
• Output: A closed walk (sequence of edges) that covers every edge at least once, minimizing total distance traveled

---

Why It Matters

Urban Planning & Waste Management: Garbage collection vehicles must service every street in a district. Route planners use CPP to minimize fuel and time.

Network Maintenance: Utility inspectors must inspect every cable, pipe, or transmission line. CPP ensures no infrastructure is overlooked and costs are minimized.

Postal & Delivery Services: The problem is named for the Chinese postman problem—an iconic application where mail carriers must cover all streets.

Street Sweeping & Snow Removal: Municipalities use CPP to plan sweeping or snow-removal routes, ensuring full coverage with minimal redundancy.

---

Modeling Approaches

Approach 1: Graph Augmentation + Eulerian Path (Combinatorial)

Paradigm: Network flow / matching on auxiliary graphs

The key insight: if all vertices have even degree, an Eulerian circuit exists covering each edge exactly once. For vertices with odd degree, we must find a minimum-weight perfect matching on odd-degree vertices and duplicate edges along matching paths.

Model:

1. Identify all odd-degree vertices in G.
2. Compute shortest paths between every pair of odd-degree vertices.
3. Find a minimum-weight perfect matching on the odd-degree vertices.
4. Duplicate edges along the matching paths.
5. Compute an Eulerian tour on the augmented graph.

Decision variables: Matching edges in the auxiliary graph.

Constraints:

• Each odd-degree vertex must be matched to exactly one other odd-degree vertex.
• Matching edges are paired (undirected matching).

Trade-offs:

• Expressiveness: Elegant and provably optimal.
• Propagation: Matching algorithms run in polynomial time (Edmonds' blossom algorithm).
• Scalability: Excellent; works for hundreds of vertices.

---

Approach 2: Integer Linear Programming (ILP)

Paradigm: Mixed-Integer Linear Programming

Model CPP as finding a set of edges to duplicate such that the augmented graph is Eulerian.

Model:

Decision variables:
  x_e ∈ Z+, ∀e ∈ E    (number of times edge e is traversed)

Objective:
  Minimize: Σ_{e ∈ E} w_e · x_e

Constraints:
  For all e ∈ E:
    x_e ≥ 1                     (traverse each edge at least once)
  
  For all v ∈ V:
    Σ_{e incident to v} x_e is even    (all-even-degree constraint)

Trade-offs:

• Expressiveness: Direct formulation, easy to extend with additional constraints (e.g., vehicle capacity, time windows).
• Propagation: General ILP solvers may take longer than specialized matching algorithms on large instances.
• Scalability: Practical for thousands of vertices but slower than combinatorial methods for very large graphs.

---

Example Model (MiniZinc)

% Chinese Postman Problem in MiniZinc
int: n_vertices;
int: n_edges;
array[1..n_edges, 1..2] of int: edges;  % edge endpoints
array[1..n_edges] of int: weights;

% Decision variables: how many times each edge is traversed
array[1..n_edges] of var int: traversals;

% Each edge must be traversed at least once
constraint forall(e in 1..n_edges) (traversals[e] >= 1);

% Degree balance: each vertex must have even traversal count
constraint forall(v in 1..n_vertices) (
  (sum(e in 1..n_edges where edges[e,1] = v or edges[e,2] = v) (traversals[e])) mod 2 = 0
);

% Minimize total distance
minimize sum(e in 1..n_edges) (weights[e] * traversals[e]);

solve minimize;

---

Key Techniques

1. Matching on Odd-Degree Vertices

Edmonds' blossom algorithm (or its variants) finds a minimum-weight perfect matching on the odd-degree vertices in polynomial time. This is the bottleneck in the combinatorial approach—once the matching is known, augmenting the graph and finding an Eulerian tour is straightforward.

2. Degree-Balance Constraints

In the ILP approach, ensuring every vertex has even degree in the augmented graph is the critical constraint. Efficient propagation exploits the fact that this is a global, linear constraint.

3. Symmetry Breaking

In some variants (e.g., directed CPP), multiple optimal tours may exist. Symmetry-breaking constraints or tie-breaking rules stabilize solutions—for example, preferring solutions that use lexicographically smaller edge duplication sets.

---

Challenge Corner

Open Question: How would you modify the CPP model to handle the Chinese Postman Problem with Required Vertices? In this variant, the postman must also visit (pass through) a specific set of required vertices, not just traverse edges. How would you blend edge-coverage and vertex-visit constraints? Can you still use the matching-based approach, or does the problem become fundamentally different?

---

References

1. van Beek, P. & Walsh, T. (2006). Handbook of Constraint Programming, Chapter 2: Foundations of Constraint Satisfaction. Elsevier.
2. Edmonds, J. (1965). "Maximum matching and a polyhedron with 0,1-vertices." Journal of Research of the National Bureau of Standards, 69B(1–2), 125–130.
3. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2009). Introduction to Algorithms (3rd ed.), Chapter 25: All-Pairs Shortest Paths. MIT Press. [Useful for shortest-path precomputation in CPP.]
4. Papadimitriou, C. H. (1976). "On the complexity of edge traversing." Journal of the ACM, 23(3), 544–554.

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · 7.3 AIC · ⌖ 5.4 AIC · ⊞ 6K · ◷

• expires on Oct 11, 2026, 5:26 AM UTC-08:00

[github-actions[bot]]

This discussion has been marked as outdated by Constraint Solving — Problem of the Day.

A newer discussion is available at Discussion #65835.