Structured Declarative Language (SDL) emerges as a powerful tool for addressing the complexities of combinatorial search and optimization problems. In this paper, we introduce SDL as a higher-level abstraction that provides a clear and intuitive specification language, with its semantics defined through translation into Answer Set Programming (ASP). SDL ofers several advantages over directly writing in ASP, including flexibility in attribute handling, improved code readability, and enhanced error tolerance. Key features of SDL include the irrelevance of attribute order, seamless management of attribute arity changes, and the use of qualifying names for attribute access. Additionally, SDL incorporates features such as automatic attribute tracking and type diferentiation, contributing to a more intuitive and reliable problem-solving process.
Combinatorial search and optimization represent foundational concepts within the realm of computer science and mathematics, focusing on the exploration of vast solution spaces to identify optimal configurations or arrangements. These problems arise across several domains, ranging from logistics and scheduling [1, 2] to telecommunications and bioinformatics [3, 4]. At its core, combinatorial search involves the systematic exploration of all possible combinations or permutations of a given set of elements to identify a solution that satisfies specified criteria. However, the sheer size and complexity of solution spaces in combinatorial problems often render brute-force search infeasible. Consequently, the field of optimization emerges as a crucial discipline, aiming to devise eficient algorithms and methodologies to navigate these vast solution spaces and identify optimal or near-optimal solutions.
Answer Set Programming (ASP) [5, 6] provides a robust framework for addressing the complexity inherent in combinatorial search and optimization problems. Its declarative nature and expressive syntax make it particularly well-suited for modeling and solving problems with discrete decision variables and combinatorial constraints. One of the key advantages of ASP is its ability to handle non-monotonic reasoning, allowing for the representation of incomplete or uncertain information and the formulation of default assumptions. This feature is crucial in combinatorial optimization, where decisions often need to be made under uncertainty or with partial information. Furthermore, ASP ofers powerful modeling constructs for expressing complex combinatorial constraints and objectives, including aggregates and weak constraints [7]. These constructs enable the concise representation of diverse optimization problems, ranging from scheduling and planning to resource allocation and configuration [ 8, 9, 10]. Additionally, ASP solvers leverage eficient algorithms and optimization techniques to search for solutions within large solution spaces [11]. These solvers employ advanced search strategies, constraint propagation, and conflict analysis to eficiently explore the search space and identify optimal or near-optimal solutions.
However, when working with a long-standing ASP codebase, several challenges and limitations may arise, impacting maintenance, readability, and robustness. Here are some downsides of ASP, particularly concerning long-standing codebases: • Propagating Changes: In a long-standing ASP codebase, the interdependencies between diferent parts of the code can create challenges when making modifications. Changes made to one section may necessitate updates in other areas to maintain consistency and functionality. Due to the declarative nature of ASP, where rules and facts are interconnected, it is often dificult to predict the ripple efects of a change, leading to a laborious process of identifying and updating afected components. This can introduce overhead in maintenance eforts and increase the risk of introducing unintended errors. • Use of Object Variables: ASP allows the use of object variables to refer to terms, providing flexibility in rule formulation. However, in a long-standing codebase, the extensive use of object variables can lead to ambiguity and confusion. Object variables may be reused across diferent rules or sections of the code, making it challenging to track their meaning and scope. This ambiguity increases the likelihood of errors, such as unintentional variable reuse or misinterpretation of variable bindings, particularly when making changes or debugging the code. • Lack of Semantic Annotations: ASP lacks built-in mechanisms for semantically annotating terms or sub-terms within rules. In a long-standing codebase, this absence of clear semantic annotations can hinder code readability and comprehension. Developers may struggle to discern the intended purpose or meaning of certain terms, leading to confusion and potential misinterpretation. Without explicit semantic annotations, understanding the logic and semantics of complex rules becomes more reliant on developer expertise and manual inspection, increasing the risk of errors and hindering code maintenance and evolution.
Example 1. Consider atoms of the following forms: cab(cab_id, driver) to represent cabs and associated drivers; customer(cust_id, name, title) to represent customers and their data; assign(cust_id, cab_id) to assign cabs to customers. Suppose the above atoms are used in the following rules (possibly part of a larger codebase): % assign one cab to every customer {assign(C,C') : cab(C',D)} = 1 :- customer(C,N,T). % don't assign more than one customer to each cab :- cab(C,D), #count{C' : assign(C',C)} > 1.
If the number or order of attributes associated with any of the above atoms change, all the codebase must be adapted. For example, if the association between cabs and drivers is moved in a diferent predicate, both rules above must be modified, even if neither one nor the other really use such an association. Also note that object variables are often associated with short names, and it is easy to clash with an already used name; in the first rule above, we had to use C' for the cab because C was already used for the customer (and we named variables of the second rule in a diferent order). Moreover, there is no clear way to distinguish the several attributes in an atom or rule, and one can unintentionally switch attributes and obtain wrong results; is the first attribute of assign a customer or a cab? ■
Addressing these downsides in a long-standing ASP codebase requires careful attention to code organization, documentation, and best practices. Strategies such as modularization, clear naming conventions, and documentation of variable bindings can help mitigate the challenges associated with propagating changes and managing object variables. Additionally, establishing conventions for semantic annotation or leveraging external documentation tools can enhance code readability and maintainability, facilitating the long-term management of the codebase. In this context, our contribution lies in the development and definition of Structured Declarative Language (SDL) as a higher-level abstraction specifically tailored to address the challenges of combinatorial search and optimization. SDL serves as a specification language that provides a clear and concise way to express optimization problems in a declarative manner, while its semantics are defined through a translation into ASP. This approach ofers several advantages over directly writing in ASP: 1. Abstraction and Simplification: SDL abstracts away the complexities of ASP syntax, providing a more intuitive and concise representation of combinatorial optimization problems. By defining problems at a higher level of abstraction, SDL facilitates clearer problem specification and solution understanding. 2. Qualifying Names for Attribute Access: SDL enables access to attributes and their components through qualifying names, enhancing code readability and comprehension. This feature provides clarity in referencing attributes and reduces ambiguity, making it easier for developers to understand and modify SDL code. In fact, qualifying names add flexibility in attribute handling, allowing for seamless modification of attribute order and arity. The order of attributes becomes irrelevant, and modifications to arity do not necessitate alterations in rules where the afected attributes are not utilized. This enhances code maintainability and reduces the risk of errors during code evolution. 3. Automatic Attribute Tracking: SDL includes an automatic system for tracking the origin of attributes, such as in edge(node(X), node(Y)). This facilitates error detection and debugging by providing insights into attribute usage and dependencies. In particular, SDL ensures automatic adherence to the typical contract of the equivalence relation within attribute handling, maintaining consistency and integrity in problem representation. Indeed, unlike ASP, where objects cannot distinguish between diferent types of strings and integers, SDL provides the capability to diferentiate between various types of objects. For instance, SDL allows for explicit diferentiation between an attribute representing a node ID and an attribute representing a paper ID (node(X) vs paper(X), instead of two integers).
Example 2 (Continuing Example 1). In SDL, the reported portion of the codebase is encoded as follows (syntax and semantics of SDL are defined in Sections 3–4): record Cab: record Customer: record Assign: id: int, driver: str; id: int, name: str, title: str; customer: Customer, cab: Cab; guess from Customer exactly 1
Assign from Cab
where Assign.customer == Customer and Assign.cab == Cab; deny from Cab having
count {Assign.customer from Assign where Assign.cab == Cab} > 1; The structure of the processed data is declared by the record instructions, so to associate names with attributes. The number and order of attributes is completely irrelevant, as attributes are accessed via qualified names such as Assign.customer (or also Assign.customer.title). Every instruction only depends on the record parts that are explicitly mentioned, so for example the guess and deny instructions above stay the same if the title attribute from Customer is removed. The attributes of Assign are tracked to their origin, that is, Customer and Cab, so that it is unlikely to misuse one for the other. ■
Overall, our contribution of SDL as an abstraction layer for combinatorial search and optimization not only simplifies problem specification but also enhances code maintainability, readability, and error tolerance. By providing a clear and intuitive language for expressing optimization problems, SDL empowers users to tackle complex combinatorial challenges more efectively and eficiently.
All sets and sequences considered in this paper are finite if not diferently specified. Let P, F, V be ifxed nonempty sets of predicate names, function names and variables. Function and predicate names are associated an arity, a non-negative integer; set F includes at least one function name of arity 0. Terms are inductively defined as follows: variables are terms; if ∈ F has arity , and 1, . . . , are terms, then (1, . . . , ) is a term (parentheses are omitted if = 0). A ground term is a term with no variables. An atom is of the form (1, . . . , ), where ∈ P has arity . A ground atom is an atom with no variables. A literal is an atom possibly preceded by the default negation symbol not; they are referred to as positive and negative literals. A conjunction conj () is a possibly empty sequence of literals involving the terms . An aggregate is of one of the forms #sum{,1, ′1 : conj 1(1); · · · ; ,, ′ : conj ()} ⊙ #min{,1, ′1 : conj 1(1); · · · ; ,, ′ : conj ()} ⊙ #max{,1, ′1 : conj 1(1); · · · ; ,, ′ : conj ()} ⊙ where ≥ 1, ⊙ ∈ { <, ≤ , ≥ , >, =, ̸=} is a binary comparison operator, eachconj () is a conjunction, each ′ is a possibly empty sequence of terms, and and each , are terms. Let be syntactic sugar for A choice is of the form
#count{′1 : conj 1(1); · · · ; ′ : conj ()} ⊙
#sum{1, ′1 : conj 1(1); · · · ; 1, ′ : conj ()} ⊙ .
(
head :– body . where head is an atom or a choice or a penalty, and body is a possibly empty sequence of literals and aggregates. (Symbol :– is omitted if body is empty.) For a rule , let () denote the atom or choice or penalty in the head of ; let Σ(), +() and − () denote the sets of aggregates, positive and negative literals in the body of ; let () denote the set Σ() ∪ +() ∪ − (). If () is a penalty, let cost () denote its cost and let level () denote its level; in this case, is also called a weak constraint. Example 3. Consider the following set of rules representing the encoding for the Maximal Clique problem: 1 : 2 : 3 : 4 : 5 : 0 ≤ { in(X )} ≤ 1 edge(Y , X )
⊥ ( ) [1@1] :– node(X ). :– edge(X , Y ). :– in(X ), in(Y ), X < Y , not edge(X , Y ). :– #count{ : ()} = .
:– node(X ), not in(X ). 1 is a choice, 2 and 4 are rules where #count{ : ()} = is an aggregate, 3 is strong constraint, and 5 is a weak constraint, with cost (5) = 1, and level (5) = 1. ■
A variable occurring in +() is a global variable. Other variables occurring among the terms of
some aggregate in Σ() of the form (
The language of ASP supports a richer syntax. For the purpose of this article, we mention the
possibility to combine terms in expressions and compare expressions with binary comparators with the
natural interpretation. Moreover, each atom occurring in a choice of the form (
:– node(
An interpretation is a set of ground atoms. (Note that we are only considering finite interpretations,
as those involving an infinite number of atoms are not relevant for our work.) For an interpretation ,
relation |= · is defined as follows: for a ground atom (), |= () if () ∈ , and |= not () if
() ∈/ ; for a conjunction conj (), |= conj () if |= for all ∈ conj (); for an aggregate of the
form (
∑︁
∈instantiate(Π) : |=()
cost () · level()
■
(
For a rule of the form (
The reduct of Π w.r.t. is the program comprising the expanded rules of instantiate(Π) true w.r.t. , that is, whose body is reduct (Π , ) :=
⋃︁ ∈instantiate( ), |=() expand (, ).
An answer set of Π is an interpretation such that |= Π and no ⊂ satisfies |= reduct (Π , ).
Example 5 (Continuing Example 4). AS (Π run ) comprises the following set of answer sets:
A1 :
A2 :
A3 :
A4 :
{node(
To ease the presentation of the language, we group the supported instructions in three groups, namely structure instructions, query instructions and model instructions.
Structure instructions are used to declare the shape of processed data. There is only one kind of structure instruction, defined next. A record structure is declared as
record RecordName: Attributes; where RecordName is a unique name and Attributes is a comma-separated list of key-value pairs of the form attribute_name : attribute_type. In the scope of its record, every attribute_name is a unique name. Every attribute_type is either a primitive type among int and str, or a record name (diferent from RecordName).
Query instructions are used to shape the output to produce when the specification is evaluated. There is only one kind of query instruction, defined next. An output directive has the form show RecordNames; where RecordNames is a comma-separated list of record names.
Example 6 (Continuing Example 3). Consider the following structure and query instructions: record Node: id: int; record Edge: first: Node, second: Node; record In: node: Node; record Size: value: int; show In, Size; They shape the records and output for Maximal Clique.
Within each model instruction, a record name alias has the form
RecordName as alias
where alias is a possibly diferent name to identify RecordName in the model instruction. When alias
is equal to RecordName, the record name alias can be simply written as RecordName. A signed record
name alias is a record name alias possibly preceded by the keyword not.
(
Attributes of a record can be accessed using the dot operator as in many object-oriented programming languages, that is, starting with the alias of the record and using a dot (.) followed by the attribute name. If the attribute value is a record, its attributes can be accessed as well with another dot operation. In the following, by value we refer to the alias of a record, a dot operation or an immediate value (integer and string constants). Values can be combined to form value expressions in the common way, by using binary operators (i.e., +, -, *, /) and parentheses. In the following, we use the terms integer expression and string expression based on the type of the result of the expression. A Boolean expression has the form
ValueExpression ⊙ ValueExpression′ where ⊙ is a binary comparator (i.e., <, <=, >=, >, ==, !=), and ValueExpression, ValueExpression′ are value expressions (of the same type).
A simple from fragment has the form
from SignedRecordNameAliases where BooleanExpressions where SignedRecordNameAliases is a comma-separated list of signed record name aliases, and BooleanExpressions is an and-separated list of Boolean expressions. If BooleanExpressions is empty, the simple from fragment can be written as follows: from SignedRecordNameAliases .
An aggregate element has the form
ValueExpressions SimpleFromFragment where ValueExpressions is a comma-separated list of value expressions, and SimpleFromFragment is an optional simple from fragment. An aggregate has the form
AggregationFunction {AggregateElements} ⊙ ValueExpression
where AggregationFunction is one of sum, count, min, max; AggregateElements is a
semicolonseparated list of aggregate elements; ⊙ is a binary comparator; and ValueExpression is a value
expression. If AggregationFunction is sum, the first value expression in every aggregate element must be an
integer expression. If AggregationFunction is either sum or count, then ValueExpression must be
an integer expression. A from fragment has either the form (
from SignedRecordNameAliases where BooleanExpressions having Aggregates where Aggregates is an and-separated list of aggregates.
A definition has the form
define RecordNameAlias FromFragment ; where RecordNameAlias is a record name alias and FromFragment is a from fragment. Example 7 (Continuing Example 6). Consider the following definitions: define Edge as self from Edge as other where self.first == other.second and self.second == other.first; define Size having count {In.node from In} == Size.value; The first definition is intended to enforce the symmetric closure of the In elements.
Edge. The second definition counts
■
A cardinality restriction has one of the forms
exactly IntegerExpression
at least IntegerExpression
(
guess FromFragment CardinalityRestriction GuessElements ; where FromFragment is an optional from fragment, CardinalityRestriction is an optional cardinality restriction, and GuessElements is a space-separated list of guess elements.
Example 8 (Continuing Example 6). Consider the following guess instruction: guess from Node at most 1
In where Node == In.node; It is intended to guess a subset of Node in the record In.
A deny instruction has one of the forms deny FromFragment ; deny FromFragment or pay Cost at Level ; where FromFragment is a from fragment, RecordNameAliases is a or-separated list of record name aliases, and Cost and Level are integer expressions.
Example 9 (Continuing Example 6). Consider the following deny instructions: deny from In as in1, In as in2, not Edge where in1.node == Edge.first and in2.node == Edge.second and in1.node < in2.node; deny from Node, not In where In.node == Node or pay 1 at 1; The first instruction is intended to ensure that In nodes are connected. The second instruction is intended to penalize nodes outside of the In selection. ■
Each record name occurring in a specification must be declared by exactly one record structure
instruction of the form (
■ (22) (23) restricts the mapping of Base (a record name alias or a sequence of dot operations) as follows: if RecordName(1, . . . , ) is the mapping of Base, and AttributeName is the -th attribute of the record RecordName, then Base.AttributeName is mapped to . Expressions are mapped naturally (with the identity mapping).
Example 10 (Continuing Example 6). Record Node is mapped as node(ID), whereas record Edge is mapped as edge(node(ID1), node(ID2)), where ID, ID1 and ID2 are fresh variables. The dot operation Edge.first is mapped to node(ID1), and Edge.first.id is mapped to variable ID1. ■
A simple from fragment of the form (
A from fragment of the form (
A guess element of the form (20) is mapped to atom : condition, where atom is the mapping of
RecordNameAlias and condition is the mapping of SimpleFromFragment (if any, and the tautology
0 = 0 otherwise). A guess expression of the form (21) is mapped to a rule of the form (
is the mapping of FromFragment . The mapping of (23) is obtained similarly, but head is the penalty [@], where is the mapping of Cost and is the mapping of Level . For instance, the deny instructions from Example 9 are essentially mapped to 3 and 5 shown in Example 3.
Given a specification , the program comprising the rules obtained by applying the above mappings on the structure and model instructions in is denoted Π . Program Π can be processed by modern ASP systems to address common computational tasks, among them answer set search and enumeration. The answer sets of Π are filtered according to the query instructions in . Essentially, only atoms whose predicate name occurs in some output directive are shown, and all other atoms are hidden. Let AS () and AS * () be obtained from AS (Π ) and AS * (Π ) by removing all atoms whose predicate does not occur in any output directive of .
Example 12 (Continuing Examples 6–9). The specification is essentially mapped to the Π run program,
whose answer sets are shown in Example 5. Actually, the mapping includes a few function names
to track the meaning and scope of terms. Hence, the actual program defining the semantics of the
specification is the following:
node(
node(SF) == node(OS), node(SS) == node(OF). size(Value) :- #count{node(Id) : in(node(Id))} = Value.
0 <= {in(node(Id')) : node(Id) == node(Id')} <= 1 :- node(Id).
According to the query instructions in the specification, the answer sets are filtered as follows:
{in(node(
In this section, we show some practical applications of SDL by presenting case studies showcasing its usage in modeling various combinatorial problems, namely Graph Coloring, Hamiltonian Path, and Nurse Scheduling. The SDL specifications reported in this section, along with their translations to ASP, are available at https://github.com/dodaro/SDL/tree/main/examples.
The Graph Coloring problem is a classic combinatorial problem in graph theory. Given an undirected graph, the goal is to assign colors to its vertices in such a way that two adjacent vertices do not share the same color. The following is a SDL specification for solving the Graph Coloring problem: record Node: id: int; record Edge: first: Node, second: Node; record Color: value: str; record Assign: node: Node, color: Color; guess from Node exactly 1 Assign from Color
where Assign.node == Node and Assign.color == Color; deny from Assign as a1, Assign as a2, Edge where a1.node != a2.node and a1.color == a2.color and
Edge.first == a1.node and Edge.second == a2.node; show Assign; The definition of the records is provided in lines 1–4. Lines 5–9 define how colors are assigned to nodes, with each node being assigned exactly one color. Lines 10–13 are used to prohibit the assignments where two diferent connected nodes share the same color. Finally, line 14 is used to filter the output to records Assign.
The Hamiltonian cycle problem is a well-known problem in graph theory that involves finding a cycle that traverses every vertex in a graph exactly once, returning to the starting vertex.
The following is a SDL specification for solving the Hamiltonian Cycle problem: record Node: id: int; record Arc: first: Node, second: Node; record InCycle: first: Node, second: Node; record Reached: node: Node; record Start: node: Node; guess from Node
exactly 1
InCycle from Arc where InCycle.first == Arc.first and
InCycle.second == Arc.second and
Node == Arc.first; deny from Node having count {
InCycle.first from InCycle where Node == InCycle.second } != 1; define Reached from Start
where Start.node == Reached.node; define Reached as r1 from Reached as r2, InCycle
where r2.node == InCycle.first and r1.node == InCycle.second; deny from Node, not Reached
where Node == Reached.node; show InCycle;
The definition of the records is outlined in lines 1 through 5. Lines 6–12 establish criteria for selecting arcs to be included in the path, ensuring that each node has precisely one outgoing arc within the path. Lines 13–16 are used to prohibit any node from having two or more incoming arcs within the path. Lines 17–22 define delineate the conditions under which nodes are considered reached. Specifically, the starting node is always reached (lines 17–19), and a node X is reached if there exists an arc in the path from a previously reached node Y to X (lines 20–22). Lines 23–24 assert that each node must be reached. Finally, line 25 is used to filter the output to records InCycle.
The Nurse Scheduling problem (NSP) consists of allocating nurses to shifts, satisfying some requirements (here we focus on the variant analyzed in [12]). The schedule spans one year. There are three working shifts, namely morning (id 1) lasting 7 hours, afternoon (id 2) lasting 7 hours, and night (id 3) lasting 10 hours. There are three non-working shifts, namely special rest after two consecutive nights (id 4), rest (id 5), and holiday (id 6). Moreover, the schedule must comply with hospital, nurse and balance requirements. Hospital requirements specify cardinality restrictions on the number of nurses in each shift. Nurse requirements impose cardinality restrictions on the number of working hours per year, ensuring that each nurse receives 30 days of holidays, and that the starting time of a shift is at least 24 hours later than the previous shift. Additionally, each nurse must have at least two rest days within each fourteen-day window. Moreover, after two consecutive working nights, one special rest day is allocated, distinct from the regular rest days. Balance requirements specify cardinality restrictions on the number of times a nurse can be assigned to morning, afternoon, and night shifts. Below we provide a SDL specification.
record Nurse: id: int; record Day: id: int; record Shift: id: int, hours: int; record HoursLimits: min: int, max: int; record DayLimits: shift: Shift, min: int, max: int; record NurseLimits: shift: Shift, min: int, max: int; record Assign: nurse: Nurse, shift: Shift, day: Day; 1 2 3 4 5 6 7 8 9 10 1 2 3 4 5 6 7 8 9 10 The definition of the records is outlined in lines 1–7, line 8 is used to filter the output as seen before, and lines 9–11 are used to assign nurses to exactly one shift for each day. Hospital requirements are encoded as follows: deny from Day, NurseLimits having count {
Assign.nurse from Assign
where Assign.shift == NurseLimits.shift and Assign.day == Day } > NurseLimits.max; deny from Day, NurseLimits having count {
Assign.nurse from Assign
where Assign.shift == NurseLimits.shift and Assign.day == Day } < NurseLimits.min; Above, lines 1–5 enforce that for each day and shift, the number of working nurses does not exceed a given threshold. Similarly, lines 6–10 are used to enforce that the number of working nurses is not below a specified minimum. Nurse requirements are encoded as follows: deny from Nurse, HoursLimits having sum {
Shift.hours, Assign.day from Assign, Shift
where Assign.nurse == Nurse and Assign.shift == Shift } > HoursLimits.max; deny from Nurse, HoursLimits having sum {
Shift.hours, Assign.day from Assign, Shift
where Assign.nurse == Nurse and Assign.shift == Shift } < HoursLimits.min; deny from Nurse having count {
Assign.day from Assign
where Assign.nurse == Nurse and Assign.shift.id == 6 } != 30; deny from Nurse, Assign as a1, Assign as a2 where a1.nurse == Nurse and a2.nurse == Nurse and a2.shift.id < a1.shift.id and a1.day.id == a2.day.id+1 and a2.shift.id <= 3 and a1.shift.id <= 3; deny from Nurse, Day where Day.id <= 352 having count {
Assign.day from Assign where Assign.nurse == Nurse and Assign.shift.id == 5 and
Assign.day.id >= Day.id and Assign.day.id < Day.id+14 deny from Assign as a1, Assign as a2, Assign as a3
where a1.nurse.id == a2.nurse.id and a1.nurse.id == a3.nurse.id and a1.shift.id == 4 and a2.shift.id == 3 and a3.shift.id == 3 and a2.day.id == a1.day.id-2 and a3.day.id == a1.day.id-1; Above, lines 1–5 (resp. 6–10) enforce that a nurse does not exceed a maximum (resp. minimum) number of working hours per year. Lines 11–15 ensure that each nurse is allocated precisely 30 days of holidays per year (recall that the shift id for holidays is 6). Lines 16–17 guarantee that the starting time of a shift is at least 24 hours later than the previous shift. Lines 18–23 establish that each nurse receives a minimum of two rest days within every fourteen-day period (recall that the shift for rest is 5). Finally, lines 24–29 ensure that a nurse is assigned to a special rest day shift if only if they were assigned to the night shift during the previous two days (recall that the shift ids for night and special rest day are 3 and 4, respectively). Balance requirements are encoded as follows: deny from Nurse, DayLimits having count {
Assign.day from Assign where Assign.shift == DayLimits.shift and
Assign.nurse == Nurse } > DayLimits.max; deny from Nurse, DayLimits having count {
Assign.day from Assign where Assign.shift == DayLimits.shift and
Assign.nurse == Nurse } < DayLimits.min; Above, lines 1–4 (resp. 5–8) ensure that a nurse cannot be assigned to a given shift for a number of days greater (resp. lower) than a predetermined threshold.
Numerous frameworks and methodologies have been developed to address combinatorial search and optimization problems, often leveraging declarative programming paradigms. Among these, ASP and OntoDLV [13] stand out as significant contributors to the field of knowledge representation and reasoning. ASP represents a declarative programming paradigm tailored for solving combinatorial search and optimization problems. ASP solvers, including clingo [11] and dlv [14], employ eficient algorithms and optimization techniques to explore solution spaces. ASP’s expressive syntax and non-monotonic reasoning capabilities make it suitable for modeling complex problem domains and reasoning about incomplete or uncertain information. OntoDLV extends the dlv system by integrating support for reasoning with ontologies expressed in Description Logics (DL). This integration enables OntoDLV to provide a powerful platform for ontology-driven reasoning and query answering. By combining DL-based ontology reasoning with ASP, OntoDLV ofers enhanced expressiveness and reasoning capabilities. It facilitates seamless integration of ontological knowledge with ASP rules, particularly beneficial in domains such as the semantic web, bioinformatics, and data integration.
While ASP and OntoDLV have significantly contributed to combinatorial optimization, our work on SDL introduces distinctive features and advantages. SDL serves as a higher-level abstraction specifically designed to address combinatorial search and optimization challenges. It ofers a clear and intuitive specification language with semantics defined through translation into ASP. SDL simplifies problem specification by abstracting away complexities of ASP syntax, enhancing code readability and comprehension. Notably, SDL provides flexibility in attribute handling, including irrelevance of attribute order and seamless management of attribute arity changes. It ofers qualifying names for attribute access, improving code maintainability. Additionally, SDL incorporates features for enhanced error tolerance, such as automatic attribute tracking and type diferentiation, thereby facilitating a more intuitive and reliable problem-solving process.
Regarding the downsides of ASP mentioned in the introduction, we observe that OntoDLV can refer attributes by their name, so that the order of attributes is often immaterial. Moreover, changing the structure of a record does not necessarily require to modify portions of the knowledge base that are not directly interested by the change. However, OntoDLV heavily depends on the use of object variables, which SDL can completely avoid thanks to the use of qualifying names. Finally, while OntoDLV opted for extending the syntax of ASP with additional constructs, SDL introduces a new structured language. Hence, in order to use OntoDLV, a programmer must first have a clear understanding of ASP syntax, which is instead not required to use SDL (as a full understanding of relational algebra is not required to be proficient with SQL).
Finally, we mention that the syntax of SDL is inspired by SQL [15]. Specifically, both languages share keywords such as from, where, as, having count, and having sum. However, SQL is designed for managing and manipulating relational databases, enabling users to create, read, update, and delete data, as well as perform tasks like querying for specific information, adding new records, updating existing data, and generating reports. In contrast, SDL is used to specify and describe complex combinatorial and optimization problems.
In this paper, we have introduced Structured Declarative Language (SDL) as a higher-level abstraction specifically designed to address the intricacies of combinatorial search and optimization. By providing a clear and intuitive specification language, SDL ofers a powerful framework for expressing optimization problems in a declarative manner, while its semantics are defined through translation into Answer Set Programming (ASP). Throughout our exploration of SDL, we have highlighted several key advantages that distinguish it from directly writing in ASP. The flexibility in attribute handling, including the irrelevance of attribute order and the seamless management of attribute arity changes, enhances code maintainability and reduces the risk of errors during code evolution. Additionally, the use of qualifying names for attribute access improves code readability and comprehension, facilitating easier understanding and modification of SDL code. Furthermore, SDL incorporates features to enhance error tolerance and robustness in problem specification, such as automatic attribute tracking and diferentiation between object types. These features contribute to a more intuitive and reliable problemsolving process, empowering users to tackle complex combinatorial challenges with greater eficiency and confidence. As future work, further research and development eforts can focus on extending the capabilities of SDL, refining its syntax, and exploring additional optimization techniques to address an even broader range of real-world challenges. Moreover, in this paper, we have shown the semantics of SDL through its translation to ASP. For future work, we plan to define a formal semantics for SDL and develop additional translations to alternative formalisms, such as Constraint Programming [16] and Satisfiability Modulo Theories [ 17]. Finally, we mention that a preliminary implementation of a tool for translating SDL to ASP is available at https://github.com/dodaro/SDL.
This work was partially supported by Italian Ministry of University and Research (MUR) under PRIN project PRODE “Probabilistic declarative process mining”, CUP H53D23003420006 under PNRR project FAIR “Future AI Research”, CUP H23C22000860006, under PNRR project Tech4You “Technologies for climate change adaptation and quality of life improvement”, CUP H23C22000370006, and under PNRR project SERICS “SEcurity and RIghts in the CyberSpace”, CUP H73C22000880001; by Italian Ministry of Health (MSAL) under POS projects CAL.HUB.RIA (CUP H53C22000800006) and RADIOAMICA (CUP H53C22000650006); by Italian Ministry of Enterprises and Made in Italy under project STROKE 5.0 (CUP B29J23000430005); and by the LAIA lab (part of the SILA labs). Mario Alviano and Carmine Dodaro are members of Gruppo Nazionale Calcolo Scientifico-Istituto Nazionale di Alta Matematica (GNCS-INdAM).