Case examine: the travelling salesman downside
Constraint Programming is a way of alternative for fixing a Constraint Satisfaction Downside. On this article, we are going to see that additionally it is effectively suited to small to medium optimization issues. Utilizing the well-known travelling salesman downside (TSP) for example, we are going to element all of the steps resulting in an environment friendly mannequin.
For the sake of simplicity, we are going to think about the symmetric case of the TSP (the gap 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 the moment growing as a facet venture. NuCS is launched beneath the MIT license.
Quoting Wikipedia :
Given an inventory of cities and the distances between every pair of cities, what’s the shortest potential route that visits every metropolis precisely as soon as and returns to the origin metropolis?
That is an NP-hard downside. Any further, let’s think about that there are n cities.
Probably the most naive formulation of this downside is to determine, for every potential edge between cities, whether or not it belongs to the optimum answer. The scale of the search house 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 seek 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 are going to benchmark our fashions with the next small TSP situations: 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 potential 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). Which means the price 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 offered 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 supplied 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 need to be totally different. The predecessors mannequin (the final n variables) defines, for every node, its predecessor within the circuit. The predecessors need to be totally different.
Each fashions are related with the foundations (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 extra constraints for forbidding sub-cycles (we can’t 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 process.
Let’s think about a node i, as seen earlier than prices[i] is the listing of potential prices for the successors of i. If j is the successor of i then the related price is prices[i]ⱼ. That is applied 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 are able to outline the whole price by summing the intermediate prices and we get:
def __init__(self, prices: Checklist[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 whole price
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)
answer = solver.reduce(downside.total_cost)
The optimum answer 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 offered 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 gives a heuristic based mostly on remorse (distinction between greatest and second greatest prices) for choosing the variable. We’ll then select the worth that minimizes the price.
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
)
answer = solver.reduce(downside.total_cost)
With these new heuristics, the optimum answer 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 will hold bettering 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
)
answer = solver.reduce(downside.total_cost)
The optimum answer 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 usually optimization) depends on a branch-and-bound algorithm. The backtracking mechanism permits to discover the search house by making decisions (branching). Elements of the search house are pruned by bounding the target variable.
When minimizing a variable t, one can add the extra constraint t < s every time an intermediate answer 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:
answer = solver.reduce(downside.total_cost, mode=PRUNE)
The optimum answer 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 could find all of the corresponding code right here.
There are after all many different tracks that we may discover to enhance these outcomes:
- design a redundant constraint for the whole price
- enhance the branching by exploring new heuristics
- use a distinct consistency algorithm (NuCS comes with shaving)
- compute decrease and higher bounds utilizing different strategies
The travelling salesman downside has been the topic of in depth examine and an considerable literature. On this article, we hope to have satisfied the reader that it’s potential to seek out optimum options to medium-sized issues in a really quick time, with out having a lot information of the travelling salesman downside.