Global constraints are one of the features that make Constraint Programming an efective solution scheme. The first global constraint, named alldiferent, is also one of the most used. In order to solve in Constraint Programming routing problems, such as the Hamiltonian Circuit Problem, the Travelling Salesperson Problem and many of their variants, an efective solution is to use a constraint model containing alldiferent and the circuit constraint, necessary to avoid sub-circuits. In this paper, we propose a combination of alldiferent and circuit that reuses the data structures of the alldiferent constraint to perform further propagation for the circuit constraint. The new combination introduces negligible overhead, and experimental results show that it can be efective when solving the Hamiltonian Circuit Problem.
In the field of Constraint Programming ( CP), global constraints such as alldifferent and circuit play a crucial role in reducing the search space and improving the eficiency while solving a wide range of Constraint Optimization Problems (COPs). These constraints are particularly relevant in complex applications like scheduling, timetabling, vehicle routing, and problems in graph theory.
The alldifferent constraint is essential for ensuring that all variables within a set assume distinct values. The circuit constraint enforces the existence of a Hamiltonian cycle within a graph.
Despite their practical utility, these constraints pose significant computational challenges, especially when combined in problems such as the Hamiltonian Cycle Problem (HCP), a well-known NP-complete problem. Achieving eficient constraint propagation while maintaining computational tractability of the propagation is a core issue in CP.
While significant advances have been made in the propagation techniques for both the alldifferent and circuit constraints individually, much less attention has been devoted to the potential synergies between these constraints when combined. For example, in problems like the HCP, both constraints are naturally present: the alldifferent constraint is used to ensure that each node in the cycle has a unique successor, while the circuit constraint ensures that these successors form a valid cycle without subtours.
In this paper, we propose a novel approach that integrates alldifferent and circuit constraints more deeply, with a focus on achieving better pruning during propagation, which in turn leads to improved overall performance. Our approach is motivated by the observation that by leveraging the underlying structure of Hall sets, typically used in the propagation of alldifferent, we can obtain additional pruning in the context of circuit constraint.
We provide a theoretical overview that analyzes the computational complexity of the integrated approach. Although it is well-known that the combination of alldifferent and circuit constraints generates an NP-complete problem, we show a combined propagation that is polynomial and, although it does not achieve Generalized Arc-Consistency, it provides an improvement in the solution time.
Finally, we provide an extensive experimental evaluation, comparing our integrated approach against existing methods on a variety of problem instances of the HCP.
Definition 2.1. (Constraint Satisfaction Problem) A Constraint Satisfaction Problem (CSP) is a triple P = ⟨ , , ⟩ where is a set of decision variables {1, 2, . . . , }, is a set of domains {1, 2, . . . , } and a set of constraints {1, 2, . . . , }.
Each domain is the set of all possible values that can be assigned to the variable . Each constraint consists of a pair ⟨, ⟩ where is a relation between the variables participating in the constraint. The set is called the scope of . results in a subset of the cartesian product of the domain of the variables in .
Let = (, ) be a graph, where is a set of nodes and is a set of edges. A path in is a sequence 0 - = 0 0,1 1 . . . − 1, such that 1. 0 , 1 , . . . , ∈ and are all distinct, and 2. 0,1 , . . . , − 1, ∈ .
Since a path is uniquely identified by the sequence of its nodes (or of its edges) in the proper order, to simplify the notation we will often write paths as sequences of nodes. Given a path 0 - , the sequence obtained by appending ,0 to a path 0 - is also called a circuit .
Definition 2.2. Given a graph , the HCP is the problem of finding a cycle in that passes through all
nodes, without taking twice the same edge.
2.1. State of the Art for alldifferent and circuit constraints
The alldifferent constraint is one of the most used constraints in Constraint Logic Programming
(CLP), and was subject of several works [
The first work on the alldifferent constraint [
Definition 2.3 (Generalized Arc-Consistency). A constraint (1, . . . , ) is Generalized Arc-Consistent (or Hyper-Arc Consistent) if for each variable ∈ {1, . . . , } and for each value ∈ there exist values
1 ∈ 1 , . . . , − 1 ∈ − 1 , +1 ∈ +1 , . . . , ∈ such that (1, . . . , − 1, , +1, . . . , ) ∈ .
The complexity [
Leconte [8] proposed a faster propagation scheme, with complexity (2), which achieved a lowerlevel of consistency, named range-consistency. As for Arc-Consistency, the idea of range-consistency is that each element in the domain of each variable should have supporting values in the domains of the other variables; however, in Range-Consistency the supporting values are sought in the minimal interval that encloses the domain, instead of the actual domain. This reduces the number of checks that are necessary to enforce such level of consistency, as it is no longer necessary to check all values in the domain, but only the extremes are considered. The downside is that Arc-Consistency can detect inconsistency in more instances.
Definition 2.4 (Range-Consistency). A constraint (1, . . . , ) is Generalized Range-Consistent if for each variable ∈ {1, . . . , } and for each value ∈ there exist values 1 ∈ [min(1 ), max(1 )], . . . , − 1 ∈ [min(− 1 ), max(− 1 )], +1 ∈ [min(+1 ), max(+1 )], . . . , ∈ [min( ), max( )] such that (1, . . . , − 1, , +1, . . . , ) ∈ .
Puget [
Further works on this version [
All the current implementations of alldifferent achieving Range or Bound-Consistency are based on the Hall theorem [9]; before introducing it, we define the domain of a set of variables: Definition 2.6 (Domain of a set of variables). Given a set of variables , for each ∈ let be the domain of variable . We indicate with = ⋃︀∈ .
Clearly, if there is a set of variables such that the number of variables in is higher than the
number of available values | | for those variables, the alldifferent constraint is unsatisfiable; the
following theorem states that also the vice-versa holds:
Theorem 2.1 ([
The implementations of alldifferent based on Range or Bound-Consistency difer mainly on the
method used to find Hall intervals:
Definition 2.7 (Hall interval [
Clearly, if there is a Hall interval , then the set of variables () absorbs all the values of , meaning that all values in can be safely removed from the domains of all other variables. This is exactly the propagation used by the algorithms based on Range or Bound-Consistency for the alldifferent constraint.
Also the algorithms that achieve Arc-Consistency [
One of the most successful constraint models for the HCP is the successor representation. To each node of the graph, a variable Next is associated; its domain is the set of nodes that can be reached in one step from . The intuitive meaning of this representation is that in a solution (i.e., in an Hamiltonian cycle), the successor of the the node is the node assigned to Next .
The constraint model for the successor representation contains an alldifferent constraint on the set of Next variables (since no two nodes can have the same successor in an Hamiltonian path) and a circuit constraint [10] on the Next variables. The circuit constraint ensures that there are no sub-tours.
One simple implementation of the circuit constraint (and, indeed, the implementation implemented in the ECLPS Constraint Logic Programming language [11]) is based on the following reasoning: if in a partial assignment, a path has already been assigned, starting from an initial node and ending in a last node , then Next ̸= , i.e. the successor of the last node cannot be the initial node . Clearly, this condition is valid only for partial assignments, not for complete ones (i.e., not for complete solutions), i.e. when the length of the partial path is strictly less than the number of nodes in the graph.
Caseau and Laburthe [12] propose a propagation technique for the circuit constraint through a simple and efective rule called nocycle. This rule is applied to prevent intermediate cycles during the solving of small Traveling Salesperson Problems (TSPs). Their method involves detecting paths of mandatory edges with lengths of at most − 1 and eliminating the edge between the two endpoints of such paths to ensure circuit completeness. Additionally, they enhance the constraint-solving approach by utilizing assignment-based and spanning tree relaxations to filter out infeasible values, demonstrating how these techniques contribute to more efective propagation for the TSP and similar problems.
Kaya and Hooker [13] propose a new filtering approach to the circuit constraint based on separator graphs. Their method focuses on removing non-Hamiltonian edges by identifying and analyzing subgraphs using a vertex separator. To identify nonhamiltonian edges, Kaya and Hooker introduce a lfow-based method that constructs capacitated flow graphs. These graphs are built for both out-degree and in-degree constraints, ensuring that each vertex in the Hamiltonian cycle has exactly one successor and one predecessor. If the flow on a given edge is zero and there is no augmenting path, that edge is nonhamiltonian and can be safely removed from the graph’s domain. Their algorithm achieves a complexity of (||5) for each separator .
Francis and Stuckey [14] further explore various propagation techniques for the circuit constraint in the context of lazy clause generation solvers. They emphasize the importance of adding explanations and they studied its efect on the circuit constraint and its variants. The technique involves transforming each propagation step into a clause, which provides an explanation for domain reductions, helping the solver avoid previously encountered conflicts. Their research highlights the trade-of between the complexity of propagation algorithms and the reusability of explanations. While simpler algorithms generate smaller explanations, more powerful algorithms, such as Strongly Connected Components (SCC) based propagation, can yield significant performance gains by pruning the search space more efectively.
Isoart and Régin [15, 16] propose to improve the propagation of the Weighted Circuit Constraint (WCC) (a constraint tailored to solve the Travelling Salesperson Problem) by exploiting some properties of Hamiltonian graphs (i.e., graphs that admit an Hamiltonian circuit) based on finding -cutsets. More precisely, a graph can be cut into two subgraphs by removing a set of edges, named a cutset; a cutset of cardinality is called a -cutset. In order for the graph to be Hamiltonian, there cannot exist a 1-cutset (also called a bridge) as there would be two separate parts connected only by one edge. Isoart and Régin develop eficient algorithm to detect cutsets of size up to three, and, reasoning on the cardinality of a cutset, are able to detect mandatory edges (edges that must necessarily belong to any Hamiltonian circuit) and edges that cannot belong to any Hamiltonian cycle.
Integrating the circuit and alldifferent constraints could unleash the possibility of further pruning. On the other hand, it is worth noting that the problem consisting only of the alldifferent and circuit constraints is known as the Hamiltonian Circuit problem, which is a well-known NPcomplete problem [17]. But if a problem consisting of only one constraint is NP-complete, then also obtaining Generalized Arc-Consistency (GAC) of such a constraint is NP-complete [18]. This wellknown result strongly reduces the hope to find a polynomial algorithm for GAC propagation of such a constraint. On the other hand, constraint propagation is executed in each node of the search space, and usually, in order for a propagation to be efective, a strong requirement is that it is achieved in polynomial time. For this reason, it is sensible to forego obtaining GAC of the hamiltonian constraint; this does not mean that efective pruning cannot be obtained for such a constraint: indeed a constraint is efective if the amount of pruning it performs (i.e., the reduction of the search space) compensates for the time spent in reasoning. E.g., one of the most successful constraints in CP is the cumulative constraint, for which there exist various implementations, none of which obtains GAC, since its cost would be NP-hard.
All the implementations of alldifferent amount to finding Hall sets eficiently, possibly trading speed for finding Hall sets with the number of Hall sets found.
Once these sets are known, it might be worthy to exploit them also for improving the propagation of the circuit constraint.
Theorem 4.1. Let = {ℎ1, . . . , ℎ} be a set of nodes, Next the corresponding variables in the successor representation, and Next the corresponding domain. If Next = and || < , then the HCP has no solution.
Proof. Edges from the set can only be connected to edges in the set , which coincides with , so the set is isolated. As || < , the set does not contain all nodes in the graph, so there are nodes that are unreachable from .
Note that a set satisfying Theorem 4.1 is, by definition, a Hall set.
Thus, it makes sense to exploit the eficient techniques developed in the literature to find Hall sets to get also additional pruning for the circuit constraint. Moreover, those same techniques used to ifnd Hall sets are already embedded in the propagation algorithm of the alldifferent constraint, that is usually employed together with circuit in the same constraint model. Stated otherwise, since the alldifferent constraint already needs to search for Hall sets, it makes sense to get additional pruning, due to the need to remove sub-circuits.
Once a Hall set satisfying the condition of Theorem 4.1 is found, a proof is obtained that the current branch of the search tree does not lead to any solution, so a failure is raised. While failing early can save a lot of computation time, the CLP on Finite Domains (CLP(FD)) philosophy encourages to delete inconsistent values from the domains in order to focus the search on the promising parts of the search tree.
The following theorem provides a mean for eliminating values from domains before a failure.
Of course, the starting point of a circuit is unimportant.
Theorem 4.2. Let = {ℎ1, . . . , ℎ} be a set of nodes with cardinality < such that Next (the domain of the corresponding variables) is a Hall set. Assume that | ∖ Next | = 1; let ℎ be the only element in = ∖ Next . Since Next is a Hall set, || = |Next |, so there will be only one element in = Next ∖ ; let be that element.
Then, there is no Hamiltonian Circuit of the graph = (, ) such that the successor of is . Proof. Let = ∩ Next ; by the assumptions in the theorem, = ∪ {ℎ} and Next = ∪ {}.
By definition of Next , the successor of each node in is one element in = ∪ {}. Since no two nodes can have the same successor, the successor of ℎ cannot be , otherwise the successors of all the elements in would be other elements in , making the set an isolated subset (see Figure 1).
Theorem 4.3. Let = {ℎ1, . . . , ℎ} be set of nodes with cardinality < , and let Next be a Hall set.
Let = ∩ Next , = ∖ Next and = Next ∖ .
Then, in any Hamiltonian Circuit: 1. The successor of an element in is either an element in or in . 2. The successor of an element in is either en element in or in .
3. The successor of an element in ∖ is in ∖ or in .
Proof. Note that since Next is a Hall set, the successor of each element in ∖ cannot be in the set Next (this is exactly the propagation performed by the alldifferent constraint); this proves item 3.
Items 1 and 2 follow immediately from the definition of Next .
A possible propagation algorithm of the hamiltonian constraint could be summarised as follows: 1: ℱ ← alldifferent ◁ execute the alldifferent propagator; such propagator also returns a family ℱ of Hall sets. 2: if |ℱ | > 1 then 3: for all ∈ ℱ do 4: ← ∖ Next 5: if || = 1 then 6: ← Next ∖ 7: let = {} 8: let = {} 9: Next ̸= 10: end if 11: end for 12: end if
The complexity of this propagator is dominated by the invocation of the alldifferent constraint, that amounts at (2.5) or ( log ) depending on the achieved level of consistency. The set differences ∖ and ∖ can be computed in linear time, if the sets and are sorted, so the complexity of the hamiltonian constraint does not increase with respect to the alldifferent constraint.
A second level of pruning can be obtained in the same situation (i.e., when | ∖ Next | = 1 and is a Hall set) by considering that from the initial node one cannot get to the final node of a Hall set unless all the nodes in the set are visited. The propagator can be implemented in a similar way to the circuit constraint: when a partial path inside the Hall set has been assigned (i.e., a sequence of variables have become ground and they represent a partial path), reaching the final node is forbidden unless all the nodes in have been visited. The following pseudo-code depicts the algorithm performed by the propagator; it is invoked with ____(, , 0, , Next ), where is the initial node in the Hall set (as in the previous algorithm), is the output node.
In this section, we present the experiments conducted on the integration of the alldifferent and circuit constraints, as previously introduced.
The experiments focus on evaluating the performance of three diferent constraint models: alldiff_circuit, and two variants of the newly proposed constraint, namely hcc_nopath, and hcc_path, for solving the Hamiltonian Cycle Problem. All algorithms are implemented in the ECLPS CLP language [11].
The three constraint models difer in their approach as follows:
• alldiff_circuit: this model uses the alldifferent and circuit constraints from the
ECLPS libraries. Specifically, the alldifferent implementation is the one inspired by the
algorithm proposed by Régin [
All tests were run on ECLPS v. 7.1beta, build #13, on AMD EPYC 9454 running at 2.75GHz, using only one core and with 4GB of reserved memory. The ECLPS Constraint Programming System is distributed as open-source software1.
We evaluated the efectiveness of the proposed constraints on two types of graph: uniform and clustered. In uniform graphs, a fixed number of nodes, denoted as , and a connection probability are specified. For each pair of distinct nodes, a directed edge is established between them with probability , excluding self-loops, meaning no edge connects a node to itself. Clustered graphs, on the other hand, are characterized by the number of clusters . Nodes are equally distributed among the clusters, with each cluster consisting of / nodes. Within each cluster, nodes are interconnected by directed edges with probability . Additionally, each cluster is connected to two other clusters by exactly four directed edges, two edges for each cluster, ensuring a cyclic structure.
The values used for ranged from 100 to 1000, in increments of 100, while for , ranged from 0.05 to 0.95 in increments of 0.05. For each combination of these parameters, 20 random graphs were generated, for a total of 3,800 uniform graphs. For the clustered graphs, we tested four diferent values of : 5, 10, 20 and 30 that is added to the combinations of and of uniform graphs. In this way, the total number of clustered graphs tested was 15,200.
Results for uniform graph are shown in Figure 2. The -axis represents the probability threshold , which afects the graph’s density. The -axis is divided into two metrics: the diference in the number of solved instances relative to the reference algorithm alldiff_circuit (shown with bars - higher is better), and the CPU time required for execution measured in seconds (shown with lines - lower is better). Each point on the lines represents the geometric mean of the solving time of the instances generated with that specific probability threshold.
The reference algorithm, alldiff_circuit, consistently performs with slightly lower execution times compared to the two new variants hcc_nopath and hcc_path, across most of the probability thresholds. The number of successfully solved instances also does not difer drastically among the algorithms, though alldiff_circuit leads by a small margin. This performance diference may be attributed to the absence of conditions under which the constraint propagation of hcc_nopath and hcc_path can be efectively performed. This could be due to the structure of the uniform graphs themselves, or the variable selection (the variable with the smallest domain size is selected first) and value selection (values are tried in increasing order) strategies employed, which may not favor the propagation conditions necessary for optimization.
This hypothesis is supported by the results obtained on the clustered graphs, presented in Figure 3. The analysis was conducted in a manner consistent with that used for uniform graphs to ensure comparability. As the probability threshold increases, both our variants achieve similar and significant reductions in solving time, ranging from 20% to 28%, compared to the reference algorithm alldiff_circuit. This decrease in solving time is accompanied by a higher number of solved instances, with a 5% increase when = 0.95.
Among our two variants, no significant diferences are observed in their solving times as both exhibit comparable improvements with respect to alldiff_circuit. However, while both demonstrate better performance, the hcc_nopath variant shows a slightly smaller increase in the number of solved instances.
Finally, we examined the behavior of our algorithms as the number of clusters in the graph varied. The results, shown in Figure 4, focus on instances with a probability > 0.5, given their relevance assessed from previous analyses. The data shows a clear trend where fewer clusters result in a 26% reduction in average solving time. However, as the number of clusters increases, approximating the structure of a uniform graph, the efectiveness of our constraints decreases.
0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95
Probability 20 10 0 0.05 0.1 0.15 0.2 0.25 0.3 0.35 0.4 0.45 0.5 0.55 0.6 0.65 0.7 0.75 0.8 0.85 0.9 0.95
Probability
In this paper, we proposed a combination of the famous alldifferent and circuit constraints that reuses the data structures used to propagate the alldifferent in order to obtain further pruning for the circuit constraint. The negligible overhead makes it a viable combination to improve the propagation.
Experimental results on the Hamiltonian Circuit Problem show that several instances are more 50 40 20 10 0 25 20 5 0 ] s [ e 30 iTm
U P
C eficiently solved by the combination than by the two separate constraints; the speedup is more significant in instances having a clustered structure.
In future work, we plan to investigate other types of integrations in routing problems; particularly promising could be the integration with constraints tailored to improve the pruning of Euclidean Travelling Salesperson problems [20, 21]. We also plan to extend the experimentation, compare with other implementations of the two constraints considered in this research, and study how the search strategy influences the efectiveness of the solution process.
Research funded by the Italian Ministry of University and Research through PNRR - M4C2 - Investimento 1.3 (Decreto Direttoriale MUR n. 341 del 15/03/2022), Partenariato Esteso PE00000013 - "FAIR - Future Artificial Intelligence Research" - Spoke 8 "Pervasive AI", funded by the European Union under the NextGeneration EU programme". Alessandro Bertagnon and Marco Gavanelli are members of the Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM). [8] M. Leconte, A bounds-based reduction scheme for diference constraints, in: Constraint-96, Second
International Workshop on Constraint-based Reasoning, Key West, Florida, 1996. [9] P. Hall, On representatives of subsets, Journal of the London Mathematical Society 10 (1935) 26–30. [10] N. Beldiceanu, E. Contejean, Introducing global constraints in CHIP, Math. Comput. Model. 20 (1994) 97–123. [11] J. Schimpf, K. Shen, Eclipse - from LP to CLP, TPLP 12 (2012) 127–156. [12] Y. Caseau, F. Laburthe, Solving small TSPs with constraints, in: L. Naish (Ed.), Logic Programming, Proceedings of the Fourteenth International Conference on Logic Programming, Leuven, Belgium, July 8-11, 1997, MIT Press, 1997, pp. 316–330. [13] L. G. Kaya, J. N. Hooker, A filter for the circuit constraint, in: F. Benhamou (Ed.), Principles and Practice of Constraint Programming - CP 2006, 12th International Conference, CP 2006, Nantes, France, September 25-29, 2006, Proceedings, volume 4204 of Lecture Notes in Computer Science, Springer, 2006, pp. 706–710. [14] K. G. Francis, P. J. Stuckey, Explaining circuit propagation, Constraints 19 (2014) 1–29. URL: https://doi.org/10.1007/s10601-013-9148-0. doi:10.1007/s10601-013-9148-0. [15] N. Isoart, J. Régin, Integration of structural constraints into TSP models, in: T. Schiex, S. de Givry (Eds.), Principles and Practice of Constraint Programming - 25th International Conference, CP 2019, Stamford, CT, USA, September 30 - October 4, 2019, Proceedings, volume 11802 of Lecture Notes in Computer Science, Springer, 2019, pp. 284–299. URL: https://doi.org/10.1007/978-3-030-30048-7_17. doi:10.1007/978-3-030-30048-7\_17. [16] N. Isoart, J. Régin, A linear time algorithm for the k-cutset constraint, in: L. D. Michel (Ed.), 27th International Conference on Principles and Practice of Constraint Programming, CP 2021, Montpellier, France (Virtual Conference), October 25-29, 2021, volume 210 of LIPIcs, Schloss Dagstuhl - Leibniz-Zentrum für Informatik, 2021, pp. 29:1–29:16. URL: https://doi.org/10.4230/ LIPIcs.CP.2021.29. doi:10.4230/LIPICS.CP.2021.29. [17] R. M. Karp, Reducibility among Combinatorial Problems, Springer US, Boston, MA, 1972, pp. 85–103.
URL: https://doi.org/10.1007/978-1-4684-2001-2_9. doi:10.1007/978-1-4684-2001-2_9. [18] C. Bessiere, E. Hebrard, B. Hnich, T. Walsh, The complexity of global constraints, in: D. L.
McGuinness, G. Ferguson (Eds.), Proceedings of the Nineteenth National Conference on Artificial Intelligence, Sixteenth Conference on Innovative Applications of Artificial Intelligence, July 25-29, 2004, San Jose, California, USA, AAAI Press / The MIT Press, 2004, pp. 112–117. URL: http://www.aaai.org/Library/AAAI/2004/aaai04-018.php. [19] A. Bertagnon, M. Gavanelli, F. Zanotti, ASPECT: Answer Set rePresentation as vEctor graphiCs in laTex, in: A. Dovier, A. Formisano (Eds.), Proceedings of the 38th Italian Conference on Computational Logic, Udine, Italy, June 21-23, 2023, volume 3428 of CEUR Workshop Proceedings, CEUR-WS.org, 2023. URL: https://ceur-ws.org/Vol-3428/paper3.pdf. [20] A. Bertagnon, M. Gavanelli, Improved filtering for the euclidean traveling salesperson problem in CLP(FD), in: The Thirty-Fourth AAAI Conference on Artificial Intelligence, AAAI 2020, The Thirty-Second Innovative Applications of Artificial Intelligence Conference, IAAI 2020, The Tenth AAAI Symposium on Educational Advances in Artificial Intelligence, EAAI 2020, New York, NY, USA, February 7-12, 2020, AAAI Press, 2020, pp. 1412–1419. doi:10.1609/AAAI.V34I02.5498. [21] E. Bellodi, A. Bertagnon, M. Gavanelli, R. Zese, Improving the eficiency of euclidean TSP solving in constraint programming by predicting efective nocrossing constraints, in: M. Baldoni, S. Bandini (Eds.), AIxIA 2020 - Advances in Artificial Intelligence - XIXth International Conference of the Italian Association for Artificial Intelligence, Virtual Event, November 25-27, 2020, Revised Selected Papers, volume 12414 of Lecture Notes in Computer Science, Springer, 2020, pp. 318–334. doi:10.1007/978-3-030-77091-4\_20.