# Evolutionary System Design with Answer Set Programming
## 4 Encoding the System Synthesis Problem with ASP Modulo Difference Constraints
### General Problem Encoding
Two communications are in conflict whenever they share at least one link and do not depend on each other. We use the same alphanumeric ordering as for resource conflicts. Finally, Line 19 decides the priority between two tasks or communications that are in conflict. Again, the choice rule only allows for deciding that an alphanumerically smaller task or communication is executed first, but we take the absence of this priority to mean the opposite. ```
1 depends(T,T'):-send(T,T'). 2 depends((T,T'),(T',T'')):-send(T,T'),send(T',T'). 3 depends_trans(T,T'):-depends(T,T'). 4 depends_trans(T,T'):-depends_trans(T,T'),depends(T,T'). 5
6 conflict(T,T'):-task(T),task(T'),T<T',
7 bind(T,R),bind(T',R),
9 notdepends_trans(T',T),
10 notdepends_trans(T,T'). 11
12 conflict((T,T'),(T',T'')):-send(T,T'),send(T',T''),
13(T,T')<(T',T''),
141#sum{1:route((T,T'),R,R'),
15 route((T',T',T'),R,R'),
16 notdepends_trans((T,T'),(T',T'')),
17 notdepends_trans((T',T'),(T,T')). 19{priority(C,C')}:-conflict(C,C'). ```  
Listing 6 gives our scheduling encoding. We facilitate scheduling via difference constraints, where the name of a task or communication is the name of the integer variable that represents their starting time in scheduling \(s\). In the following, we argue on the ground level and with the mathematical entities of the system synthesis problem. That is, every T and T' in the encoding is instantiated by all tasks \(\{t,t^{\prime}\}\subseteq\mathbb{T}\), as well as every C and C' is instantiated with all communications \(\{c,c^{\prime}\}\subseteq\mathbb{D}\). Lines 1 to 2 implement Condition 1 on a valid scheduling; they derive difference constraint &&diff(0-\(t\))<=0 ensuring \(0\leq s(t)\) and &&diff(\(t\)-0)<=\(p-e(b(t),t)\) ensuring \(s(t)+e(b(t),t)\leq p\) for \(t\in\mathbb{T}\). Lines 4 and 5 handle dependencies between tasks and communications. Specifically, Line 4 encodes Condition 2 by deriving difference constraint &&diff(\(t\)-\((t,t^{\prime})\)<=\(-e(b(t),t)\) for every dependency, which means that \(s(t)+e(b(t),t)\leq s((t,t^{\prime}))\) for \((t,t^{\prime})\in\mathbb{D}\). Similarly, Line 5 handles Condition 3 via difference constraint &&diff(\(t\),\(t^{\prime}\)-\(f\))<=\(-|r((t,t^{\prime}))|*rd\), where the number of hops is used to determine \(|r((t,t^{\prime}))|\). Then, we have \(s((t,t^{\prime}))+|r((t,t^{\prime}))|*rd\leq s(t^{\prime})\) for \((t,t^{\prime})\in\mathbb{D}\). Lines 8 to 13 handle conflict resolution between tasks. For two conflicting tasks \(\{t,t^{\prime}\}\subseteq\mathbb{T}\) with \(t\
eq t^{\prime}\) so that \(b(t)=b(t^{\prime})\), we obtain either difference constraint &&diff(\(t\)-\(t^{\prime}\))<=\(-e(b(t),t)\) enforcing \(s(t)+e(b(t),t)\leq s(t^{\prime})\) if \(t\) is prioritized over \(t^{\prime}\) or difference constraint &&diff(\(t^{\prime}\)-\(t\))<=\(-e(b(t^{\prime}),t^{\prime})\) and therefore \(s(t^{\prime})+e(b(t^{\prime}),t^{\prime})\leq s(t)\) if there is no prioritization. Note that the conflict relation is symmetrical; thus, we only need to consider one ordering of the task names to obtain Condition 4. A drawback when compared wtih symmetrical conflict and priority atoms is having to duplicate the rules that derives the difference constraints in the encoding; however, the number of rule instantiations overall is halved. Similarly, Lines 15 to 18 resolve communication conflicts. For two conflicting communications \(\{d,d^{\prime}\}\subseteq\mathbb{D}\) with \(d\
eq d^{\prime}\), i.e., we have \(r(d)=(\dots,r,r^{\prime},\dots)\) and \(r(d^{\prime})=(\dots,r,r^{\prime},\dots)\), we derive either difference constraint &&diff(\(d\)-\(d^{\prime}\))<=\(-|r(d)|*rd\) leading to \(s(d)+|r(d)|*rd\leq s(d^{\prime})\) if \(d\) has priority over \(d^{\prime}\) or difference constraint &&diff(\(d^{\prime}\)-\(d\))<=\(-|r(d^{\prime})|*rd\) giving rise to \(s(d^{\prime})+|r(d^{\prime})|*rd\leq s(d)\) if no priority exists.