🧩 Constraint Solving POTD:Problem of the Day: Traveling Purchaser Problem (TPP)

[github-actions[bot]]

Constraint Solving Problem of the Day: The Traveling Purchaser Problem (TPP)

Problem Statement

The Traveling Purchaser Problem extends the classic Traveling Salesman Problem by combining routing with purchasing decisions.

Informal Description:
A purchaser needs to buy m different commodities from n suppliers. Each supplier is located at a different city, stocks a specific subset of commodities at varying prices, and has a non-zero profit margin. The purchaser starts at a depot, must visit a subset of cities to obtain all required items, and return home while minimizing the total cost—the sum of travel cost (distance × transportation rate) plus commodity purchase costs.

Concrete Instance:

• 5 cities (including depot)
• 4 commodities needed: A, B, C, D
• Suppliers (cities):
  • City 1 (depot): starting point
  • City 2: sells A (€5), C (€15)
  • City 3: sells B (€8), D (€20)
  • City 4: sells A (€6), B (€7), C (€12)
  • City 5: sells D (€18)

Travel distances (symmetric, in km):

    1   2   3   4   5
1   0  10  15   8  20
2  10   0  18  12  22
3  15  18   0  16  14
4   8  12  16   0  11
5  20  22  14  11   0

Transportation cost: €1.50 per km.

Input/Output:

• Input: Set of commodities to purchase, supplier locations with inventory and prices, distance matrix, transportation cost per km
• Output: A route visiting selected cities in order and a purchase plan (where to buy each commodity), minimizing total cost

Why It Matters

Procurement & Supply Chain: Companies procuring multiple parts from different vendors across geographic regions face this exact problem. For example, automotive suppliers assembling components from factories in different regions must decide which factories to visit and where to source each part.

Retail & Distribution: Online grocery or pharmacy platforms optimize delivery routes while choosing purchase sources dynamically based on inventory availability and pricing—especially during supply constraints.

Military Logistics: Field units requiring multiple supply types must route through supply depots efficiently, selecting the cheapest available source at each location they visit.

Modeling Approaches

Approach 1: Mixed-Integer Linear Programming (MIP)

Variables:

• x_ij ∈ {0,1}: binary variable indicating edge (i,j) in the tour
• y_ijc ∈ {0,1}: binary variable indicating commodity c is bought from supplier j when arriving from city i
• u_i ∈ R+: continuous variable for tour position (used in subtour elimination)

Constraints:

1. Tour structure: Each city visited exactly once (if at all)

   • Σ_j x_ij = 1 for all i ≠ depot (incoming edges)
   • Σ_i x_ij = 1 for all j ≠ depot (outgoing edges)

2. All commodities purchased: Each commodity bought from exactly one supplier

   • Σ_j Σ_i y_ijc = 1 for all commodities c

3. Buy only from visited cities: Can only purchase from city j if we travel to it

   • y_ijc ≤ x_ij for all i, j, c

4. Subtour elimination (Miller-Tucker-Zemlin):

   • u_i - u_j + n·x_ij ≤ n-1 for all i,j (prevents cycles not including depot)

Objective:

minimize Σ_ij d_ij · transport_cost · x_ij + Σ_ijc price_jc · y_ijc

Trade-offs: Strong propagation and relaxation bounds; scales to ~100 cities but requires sophisticated branch-and-cut solvers (Cplex, Gurobi). Formulation is symmetric and can exploit LP relaxation.

Approach 2: Constraint Programming (CP)

Variables:

• route[1..k]: sequence of visited cities (k ≤ n)
• source[c]: which city supplies commodity c
• cost_distance: total distance traveled
• cost_purchase: total purchase cost

Key Constraints:

1. alldifferent(route): no city visited twice
2. source[c] ∈ route: each commodity's source must be a visited city
3. available(source[c], c): city source[c] stocks commodity c
4. cost_distance = circuit(route, distance_matrix): TSP-like constraint on tour cost
5. cost_purchase = Σ_c price[source[c]][c]: sum of individual purchases

Objective:

minimize cost_distance * transport_rate + cost_purchase

Trade-offs: More expressive (built-in circuit global constraint for TSP structure); easier to layer business logic (inventory constraints, budget caps). Search-based, so can combine with local search metaheuristics. Scales well with fewer cities (10–50) but weaker relaxation bounds than MIP.

Approach 3: Hybrid CP + Local Search

Idea: Use CP to find a feasible solution quickly (greedy tour + assignment), then refine via neighborhood search.

Neighborhoods:

• 2-opt moves: swap edges in the current tour
• Source-swap: reassign a commodity to a different visited supplier (if feasible)
• City insertion/removal: try adding or removing a city from the route

Trade-offs: Fast, practical, anytime algorithm. Can find good solutions in seconds. Less complete than exact methods but scales to large instances.

Example Model (MiniZinc)

int: n;           % number of cities
int: m;           % number of commodities
set of int: CITIES = 1..n;
set of int: ITEMS = 1..m;
int: depot = 1;

array[CITIES,CITIES] of int: dist;
array[CITIES,ITEMS] of int: price;
array[CITIES,ITEMS] of 0..1: available;
int: transport_rate = 150;  % cents per km

% Decision variables
array[CITIES,CITIES] of var 0..1: x;  % tour edges
array[CITIES,ITEMS] of var 0..1: source;  % which city supplies each item
var int: total_cost;

% Each city visited at most once (simplified)
constraint forall(i in CITIES)(sum(j in CITIES)(x[i,j]) <= 1);
constraint forall(j in CITIES)(sum(i in CITIES)(x[i,j]) <= 1);

% Each commodity sourced from exactly one city
constraint forall(c in ITEMS)(sum(j in CITIES)(source[j,c]) = 1);

% Can only buy from a visited city (heuristic: visited iff outgoing edge exists)
constraint forall(c in ITEMS, j in CITIES)(
  source[j,c] = 1 -> sum(i in CITIES)(x[i,j]) = 1
);

% Item availability
constraint forall(c in ITEMS, j in CITIES)(
  source[j,c] = 1 -> available[j,c] = 1
);

% Cost calculation (simplified; distance in tour not explicitly modeled here)
constraint total_cost = 
  transport_rate * sum(i,j in CITIES)(dist[i,j] * x[i,j]) +
  sum(c in ITEMS, j in CITIES)(price[j,c] * source[j,c]);

solve minimize total_cost;

Key Techniques

1. Combining TSP Structure with Assignment

The TPP decomposes naturally: first solve a routing decision (which cities to visit), then solve an assignment problem (buy each commodity from the cheapest available supplier among visited cities). Many solvers use Benders decomposition to iteratively refine the tour and assignment.

2. Global Constraints & Propagation

• circuit or subtour_elimination: Ensures the route forms a valid cycle
• element constraint: Links route position to available inventory
• Arc consistency on the source-commodity-price relationship prunes infeasible purchases early

3. Symmetry Breaking

• Fix the depot as city 1 and enforce route[1] < route[2] < ... < route[k] to break rotational and reflective symmetries
• For commodities, impose a canonical order of purchase (e.g., always buy commodity 1 before commodity 2 if both are available at the same city)

4. Lower Bound via Relaxation

• LP relaxation of the MIP: Solve the continuous version (allow fractional x and y) to get a lower bound
• Minimum spanning tree + assignment: Connect all suppliers needed for required commodities via an MST, yielding a fast lower bound

Challenge Corner

Question 1: Variable elimination. In the MIP formulation above, could you eliminate the variables y_ijc entirely and instead express the constraint directly in terms of x_ij? How would you handle the assignment of commodities to cities?

Question 2: Dynamic pricing. Suppose the price of each commodity depends on the quantity purchased (bulk discount). How would you extend the CP model to capture this? Would the MIP still be solvable efficiently?

Question 3: Capacity constraints. Add a per-vehicle weight or volume limit: each city visited adds its required commodities' weight, and the total must fit. Which modeling approach (MIP, CP, hybrid) would you prefer? Why?

References

1. Ramírez-Rosales, R., et al. "Traveling Purchaser Problem: A Tutorial." Computers & Operations Research, 2019.

   • Comprehensive survey and complexity analysis; covers exact and heuristic algorithms.

2. Gendreau, M., & Potvin, J.-Y. (Eds.). Handbook of Metaheuristics (3rd ed.). Springer, 2019. Chapter on routing variants.

   • Practical metaheuristic strategies for TPP and VRP extensions.

3. Rossi, F., van Beek, P., & Walsh, T. (Eds.). Handbook of Constraint Programming. Elsevier, 2006.

   • Foundational reference for CP modeling and global constraints.

4. Glover, F., & Kochenberger, G. (Eds.). Handbook of Metaheuristics (2nd ed.). Springer, 2010.

   • Covers hybrid CP/local-search approaches for complex optimization.

---

Next Problem: Keep an eye out for a configuration or satisfiability problem next! Did this problem spark an idea for a variant you'd like to explore?

Generated by 🧩 Constraint Solving — Problem of the Day · copilot · haiku45 · ~9 AIC · ⌖ ~7 AIC · ⊞ 7.1K · ◷

• expires on Nov 8, 2026, 3:30 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 #74121.