Constraint Programming is a method of alternative for fixing a Constraint Satisfaction Drawback. On this article, we’ll see that additionally it is nicely suited to small to medium optimization issues. Utilizing the well-known travelling salesman problem (TSP) for example, 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 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 presently growing as a aspect mission. 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 resolve, for every potential edge between cities, whether or not it belongs to the optimum answer. The scale of the search area is 2ⁿ⁽ⁿ⁻¹⁾ᐟ² which is roughly 8.8e130 for n=30 (a lot higher 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 massive).
Within the following, we’ll 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 that 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 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 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((checklist(vary(n)), ALG_ALLDIFFERENT, []))
self.add_propagator((checklist(vary(n, 2 * n)), ALG_ALLDIFFERENT, []))
for i in vary(n):
self.add_propagator((checklist(vary(n)) + [n + i], ALG_PERMUTATION_AUX, [i]))
self.add_propagator((checklist(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 completely different. The predecessors mannequin (the final n variables) defines, for every node, its predecessor within the circuit. The predecessors need to be completely 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 further 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((checklist(vary(n)), ALG_NO_SUB_CYCLE, []))
self.add_propagator((checklist(vary(n, 2 * n)), ALG_NO_SUB_CYCLE, []))
The TSP mannequin
With the assistance of the circuit downside, modelling the TSP is a straightforward process.
Let’s think about a node i, as seen earlier than prices[i] is the checklist of potential prices for the successors of i. If j is the successor of i then the related value 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 will outline the entire value 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 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(
(checklist(vary(self.succ_costs, self.succ_costs + n)) + [self.total_cost], ALG_AFFINE_EQ, [1] * n + [-1, 0])
)
self.add_propagator(
(checklist(vary(self.pred_costs, self.pred_costs + n)) + [self.total_cost], ALG_AFFINE_EQ, [1] * n + [-1, 0])
)
Observe 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 resolution variables would be the successors and predecessors.
solver = BacktrackSolver(downside, decision_domains=decision_domains)
answer = solver.decrease(downside.total_cost)
The optimum answer is present in 248s on a MacBook Professional M2 working 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 provides a heuristic primarily based on remorse (distinction between finest and second finest prices) for choosing the variable. We’ll 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
)
answer = solver.decrease(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 maintain enhancing by designing a custom 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.decrease(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 area by making decisions (branching). Elements of the search area are pruned by bounding the target variable.
When minimizing a variable t, one can add the extra constraint t < s each 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 bear in mind the brand new bounds of the goal variable
Let’s now attempt the PRUNE mode:
answer = solver.decrease(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 beneath summarizes our experiments:
You’ll find all of the corresponding code here.
There are in fact many different tracks that we may discover to enhance these outcomes:
- design a redundant constraint for the entire value
- enhance the branching by exploring new heuristics
- use a distinct 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 potential to seek out optimum options to medium-sized issues in a really brief time, with out having a lot information of the travelling salesman downside.
