Case research: the travelling salesman downside
Constraint Programming is a method of selection for fixing a Constraint Satisfaction Drawback. On this article, we’ll see that it’s also effectively suited to small to medium optimization issues. Utilizing the well-known travelling salesman downside (TSP) for instance, we’ll element all of the steps resulting in an environment friendly mannequin.
For the sake of simplicity, we’ll think about the symmetric case of the TSP (the space between two cities is identical in every other way).
All of the code examples on this article use NuCS, a quick constraint solver written 100% in Python that I’m at present creating as a aspect undertaking. NuCS is launched below the MIT license.
Quoting Wikipedia :
Given an inventory of cities and the distances between every pair of cities, what’s the shortest attainable route that visits every metropolis precisely as soon as and returns to the origin metropolis?
That is an NP-hard downside. To any extent further, let’s think about that there are n cities.
Essentially the most naive formulation of this downside is to resolve, for every attainable edge between cities, whether or not it belongs to the optimum resolution. The dimensions of the search area is 2ⁿ⁽ⁿ⁻¹⁾ᐟ² which is roughly 8.8e130 for n=30 (a lot better than the variety of atoms within the universe).
It’s a lot better to search out, for every metropolis, its successor. The complexity turns into n! which is roughly 2.6e32 for n=30 (a lot smaller however nonetheless very giant).
Within the following, we’ll benchmark our fashions with the next small TSP cases: GR17, GR21 and GR24.
GR17 is a 17 nodes symmetrical TSP, its prices are outlined by 17 x 17 symmetrical matrix of successor prices:
[
[0, 633, 257, 91, 412, 150, 80, 134, 259, 505, 353, 324, 70, 211, 268, 246, 121],
[633, 0, 390, 661, 227, 488, 572, 530, 555, 289, 282, 638, 567, 466, 420, 745, 518],
[257, 390, 0, 228, 169, 112, 196, 154, 372, 262, 110, 437, 191, 74, 53, 472, 142],
[91, 661, 228, 0, 383, 120, 77, 105, 175, 476, 324, 240, 27, 182, 239, 237, 84],
[412, 227, 169, 383, 0, 267, 351, 309, 338, 196, 61, 421, 346, 243, 199, 528, 297],
[150, 488, 112, 120, 267, 0, 63, 34, 264, 360, 208, 329, 83, 105, 123, 364, 35],
[80, 572, 196, 77, 351, 63, 0, 29, 232, 444, 292, 297, 47, 150, 207, 332, 29],
[134, 530, 154, 105, 309, 34, 29, 0, 249, 402, 250, 314, 68, 108, 165, 349, 36],
[259, 555, 372, 175, 338, 264, 232, 249, 0, 495, 352, 95, 189, 326, 383, 202, 236],
[505, 289, 262, 476, 196, 360, 444, 402, 495, 0, 154, 578, 439, 336, 240, 685, 390],
[353, 282, 110, 324, 61, 208, 292, 250, 352, 154, 0, 435, 287, 184, 140, 542, 238],
[324, 638, 437, 240, 421, 329, 297, 314, 95, 578, 435, 0, 254, 391, 448, 157, 301],
[70, 567, 191, 27, 346, 83, 47, 68, 189, 439, 287, 254, 0, 145, 202, 289, 55],
[211, 466, 74, 182, 243, 105, 150, 108, 326, 336, 184, 391, 145, 0, 57, 426, 96],
[268, 420, 53, 239, 199, 123, 207, 165, 383, 240, 140, 448, 202, 57, 0, 483, 153],
[246, 745, 472, 237, 528, 364, 332, 349, 202, 685, 542, 157, 289, 426, 483, 0, 336],
[121, 518, 142, 84, 297, 35, 29, 36, 236, 390, 238, 301, 55, 96, 153, 336, 0],
]
Let’s take a look on the first row:
[0, 633, 257, 91, 412, 150, 80, 134, 259, 505, 353, 324, 70, 211, 268, 246, 121]
These are the prices for the attainable successors of node 0 within the circuit. If we besides the primary worth 0 (we do not need the successor of node 0 to be node 0) then the minimal worth is 70 (when node 12 is the successor of node 0) and the maximal is 633 (when node 1 is the successor of node 0). Because of this the fee related to the successor of node 0 within the circuit ranges between 70 and 633.
We’re going to mannequin our downside by reusing the CircuitProblem supplied off-the-shelf in NuCS. However let’s first perceive what occurs behind the scene. The CircuitProblem is itself a subclass of the Permutation downside, one other off-the-shelf mannequin provided by NuCS.
The permutation downside
The permutation downside defines two redundant fashions: the successors and predecessors fashions.
def __init__(self, n: int):
"""
Inits the permutation downside.
:param n: the quantity variables/values
"""
self.n = n
shr_domains = [(0, n - 1)] * 2 * n
tremendous().__init__(shr_domains)
self.add_propagator((listing(vary(n)), ALG_ALLDIFFERENT, []))
self.add_propagator((listing(vary(n, 2 * n)), ALG_ALLDIFFERENT, []))
for i in vary(n):
self.add_propagator((listing(vary(n)) + [n + i], ALG_PERMUTATION_AUX, [i]))
self.add_propagator((listing(vary(n, 2 * n)) + [i], ALG_PERMUTATION_AUX, [i]))
The successors mannequin (the primary n variables) defines, for every node, its successor within the circuit. The successors must be totally different. The predecessors mannequin (the final n variables) defines, for every node, its predecessor within the circuit. The predecessors must be totally different.
Each fashions are linked with the principles (see the ALG_PERMUTATION_AUX constraints):
- if succ[i] = j then pred[j] = i
- if pred[j] = i then succ[i] = j
- if pred[j] ≠ i then succ[i] ≠ j
- if succ[i] ≠ j then pred[j] ≠ i
The circuit downside
The circuit downside refines the domains of the successors and predecessors and provides further constraints for forbidding sub-cycles (we cannot go into them right here for the sake of brevity).
def __init__(self, n: int):
"""
Inits the circuit downside.
:param n: the variety of vertices
"""
self.n = n
tremendous().__init__(n)
self.shr_domains_lst[0] = [1, n - 1]
self.shr_domains_lst[n - 1] = [0, n - 2]
self.shr_domains_lst[n] = [1, n - 1]
self.shr_domains_lst[2 * n - 1] = [0, n - 2]
self.add_propagator((listing(vary(n)), ALG_NO_SUB_CYCLE, []))
self.add_propagator((listing(vary(n, 2 * n)), ALG_NO_SUB_CYCLE, []))
The TSP mannequin
With the assistance of the circuit downside, modelling the TSP is a simple activity.
Let’s think about a node i, as seen earlier than prices[i] is the listing of attainable prices for the successors of i. If j is the successor of i then the related value is prices[i]ⱼ. That is carried out by the next line the place succ_costs if the beginning index of the successors prices:
self.add_propagators([([i, self.succ_costs + i], ALG_ELEMENT_IV, prices[i]) for i in vary(n)])
Symmetrically, for the predecessors prices we get:
self.add_propagators([([n + i, self.pred_costs + i], ALG_ELEMENT_IV, prices[i]) for i in vary(n)])
Lastly, we will outline the entire value by summing the intermediate prices and we get:
def __init__(self, prices: Listing[List[int]]) -> None:
"""
Inits the issue.
:param prices: the prices between vertices as an inventory of lists of integers
"""
n = len(prices)
tremendous().__init__(n)
max_costs = [max(cost_row) for cost_row in costs]
min_costs = [min([cost for cost in cost_row if cost > 0]) for cost_row in prices]
self.succ_costs = self.add_variables([(min_costs[i], max_costs[i]) for i in vary(n)])
self.pred_costs = self.add_variables([(min_costs[i], max_costs[i]) for i in vary(n)])
self.total_cost = self.add_variable((sum(min_costs), sum(max_costs))) # the entire value
self.add_propagators([([i, self.succ_costs + i], ALG_ELEMENT_IV, prices[i]) for i in vary(n)])
self.add_propagators([([n + i, self.pred_costs + i], ALG_ELEMENT_IV, prices[i]) for i in vary(n)])
self.add_propagator(
(listing(vary(self.succ_costs, self.succ_costs + n)) + [self.total_cost], ALG_AFFINE_EQ, [1] * n + [-1, 0])
)
self.add_propagator(
(listing(vary(self.pred_costs, self.pred_costs + n)) + [self.total_cost], ALG_AFFINE_EQ, [1] * n + [-1, 0])
)
Notice that it isn’t essential to have each successors and predecessors fashions (one would suffice) however it’s extra environment friendly.
Let’s use the default branching technique of the BacktrackSolver, our determination variables would be the successors and predecessors.
solver = BacktrackSolver(downside, decision_domains=decision_domains)
resolution = solver.reduce(downside.total_cost)
The optimum resolution is present in 248s on a MacBook Professional M2 operating Python 3.12, Numpy 2.0.1, Numba 0.60.0 and NuCS 4.2.0. The detailed statistics supplied by NuCS are:
{
'ALG_BC_NB': 16141979,
'ALG_BC_WITH_SHAVING_NB': 0,
'ALG_SHAVING_NB': 0,
'ALG_SHAVING_CHANGE_NB': 0,
'ALG_SHAVING_NO_CHANGE_NB': 0,
'PROPAGATOR_ENTAILMENT_NB': 136986225,
'PROPAGATOR_FILTER_NB': 913725313,
'PROPAGATOR_FILTER_NO_CHANGE_NB': 510038945,
'PROPAGATOR_INCONSISTENCY_NB': 8070394,
'SOLVER_BACKTRACK_NB': 8070393,
'SOLVER_CHOICE_NB': 8071487,
'SOLVER_CHOICE_DEPTH': 15,
'SOLVER_SOLUTION_NB': 98
}
Specifically, there are 8 070 393 backtracks. Let’s attempt to enhance on this.
NuCS provides a heuristic primarily based on remorse (distinction between greatest and second greatest prices) for choosing the variable. We are going to then select the worth that minimizes the fee.
solver = BacktrackSolver(
downside,
decision_domains=decision_domains,
var_heuristic_idx=VAR_HEURISTIC_MAX_REGRET,
var_heuristic_params=prices,
dom_heuristic_idx=DOM_HEURISTIC_MIN_COST,
dom_heuristic_params=prices
)
resolution = solver.reduce(downside.total_cost)
With these new heuristics, the optimum resolution is present in 38s and the statistics are:
{
'ALG_BC_NB': 2673045,
'ALG_BC_WITH_SHAVING_NB': 0,
'ALG_SHAVING_NB': 0,
'ALG_SHAVING_CHANGE_NB': 0,
'ALG_SHAVING_NO_CHANGE_NB': 0,
'PROPAGATOR_ENTAILMENT_NB': 12295905,
'PROPAGATOR_FILTER_NB': 125363225,
'PROPAGATOR_FILTER_NO_CHANGE_NB': 69928021,
'PROPAGATOR_INCONSISTENCY_NB': 1647125,
'SOLVER_BACKTRACK_NB': 1647124,
'SOLVER_CHOICE_NB': 1025875,
'SOLVER_CHOICE_DEPTH': 36,
'SOLVER_SOLUTION_NB': 45
}
Specifically, there are 1 647 124 backtracks.
We are able to preserve enhancing by designing a customized heuristic which mixes max remorse and smallest area for variable choice.
tsp_var_heuristic_idx = register_var_heuristic(tsp_var_heuristic)
solver = BacktrackSolver(
downside,
decision_domains=decision_domains,
var_heuristic_idx=tsp_var_heuristic_idx,
var_heuristic_params=prices,
dom_heuristic_idx=DOM_HEURISTIC_MIN_COST,
dom_heuristic_params=prices
)
resolution = solver.reduce(downside.total_cost)
The optimum resolution is now present in 11s and the statistics are:
{
'ALG_BC_NB': 660718,
'ALG_BC_WITH_SHAVING_NB': 0,
'ALG_SHAVING_NB': 0,
'ALG_SHAVING_CHANGE_NB': 0,
'ALG_SHAVING_NO_CHANGE_NB': 0,
'PROPAGATOR_ENTAILMENT_NB': 3596146,
'PROPAGATOR_FILTER_NB': 36847171,
'PROPAGATOR_FILTER_NO_CHANGE_NB': 20776276,
'PROPAGATOR_INCONSISTENCY_NB': 403024,
'SOLVER_BACKTRACK_NB': 403023,
'SOLVER_CHOICE_NB': 257642,
'SOLVER_CHOICE_DEPTH': 33,
'SOLVER_SOLUTION_NB': 52
}
Specifically, there are 403 023 backtracks.
Minimization (and extra typically optimization) depends on a branch-and-bound algorithm. The backtracking mechanism permits to discover the search area by making decisions (branching). Components of the search area are pruned by bounding the target variable.
When minimizing a variable t, one can add the extra constraint t < s at any time when an intermediate resolution s is discovered.
NuCS supply two optimization modes corresponding to 2 methods to leverage t < s:
- the RESET mode restarts the search from scratch and updates the bounds of the goal variable
- the PRUNE mode modifies the selection factors to keep in mind the brand new bounds of the goal variable
Let’s now strive the PRUNE mode:
resolution = solver.reduce(downside.total_cost, mode=PRUNE)
The optimum resolution is present in 5.4s and the statistics are:
{
'ALG_BC_NB': 255824,
'ALG_BC_WITH_SHAVING_NB': 0,
'ALG_SHAVING_NB': 0,
'ALG_SHAVING_CHANGE_NB': 0,
'ALG_SHAVING_NO_CHANGE_NB': 0,
'PROPAGATOR_ENTAILMENT_NB': 1435607,
'PROPAGATOR_FILTER_NB': 14624422,
'PROPAGATOR_FILTER_NO_CHANGE_NB': 8236378,
'PROPAGATOR_INCONSISTENCY_NB': 156628,
'SOLVER_BACKTRACK_NB': 156627,
'SOLVER_CHOICE_NB': 99143,
'SOLVER_CHOICE_DEPTH': 34,
'SOLVER_SOLUTION_NB': 53
}
Specifically, there are solely 156 627 backtracks.
The desk under summarizes our experiments:
You’ll find all of the corresponding code right here.
There are in fact many different tracks that we might discover to enhance these outcomes:
- design a redundant constraint for the entire value
- enhance the branching by exploring new heuristics
- use a unique consistency algorithm (NuCS comes with shaving)
- compute decrease and higher bounds utilizing different methods
The travelling salesman downside has been the topic of in depth research and an considerable literature. On this article, we hope to have satisfied the reader that it’s attainable to search out optimum options to medium-sized issues in a really quick time, with out having a lot data of the travelling salesman downside.
