Constraint Programming is a method of selection for fixing a Constraint Satisfaction Drawback. On this article, we’ll see that it’s also nicely suited to small to medium optimization issues. Utilizing the well-known travelling salesman downside (TSP) for example, we’ll element all of the steps resulting in an environment friendly mannequin.
For the sake of simplicity, we’ll contemplate the symmetric case of the TSP (the gap between two cities is similar in every wrong 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 below the MIT license.
Quoting Wikipedia :
Given a listing 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. Any more, let’s contemplate that there are n cities.
Probably 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 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 significantly 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’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 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). 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 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 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((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 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 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 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 activity.
Let’s contemplate a node i, as seen earlier than prices[i] is the checklist of attainable 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 will outline the whole price 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 a listing 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(
(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)
resolution = solver.decrease(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 gives 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 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
)
resolution = solver.decrease(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.decrease(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 usually 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 take into consideration the brand new bounds of the goal variable
Let’s now attempt the PRUNE mode:
resolution = solver.decrease(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 will discover 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 methods
The travelling salesman downside has been the topic of intensive examine and an plentiful literature. On this article, we hope to have satisfied the reader that it’s attainable 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.
