Extending Structured Declarative Language with Constraint Programming via MiniZinc

Oct 4, 2026

Structured Declarative Language (SDL) is presented as a high-level specification language for combinatorial search and optimization, originally semantically defined by translating SDL programs into Answer Set Programming (ASP). This paper introduces an SDL extension that supports dual-target compilation into either ASP or MiniZinc for constraint programming. The work bridges the semantic gap between ASP’s non-monotonic stable-model semantics and CP’s monotonic classical satisfiability by mapping SDL constructs to constraint satisfaction formulations, addressing negation-as-failure and recursive definitions. Case studies include Nurse Scheduling and Operating Room Scheduling.

LanguageEnglish

CategoryResearch & Report

FormatPDF

Pages15

Reading Time38 min

AccessFree to download

Abstract

1. Introduction

Paradigms: ASP vs CP

SDL as a maintainability-oriented abstraction

Compilation to MiniZinc and semantic bridging

Case Studies

Extending Structured Declarative Language with Constraint Programming via MiniZinc Mario Alviano1 , Carmine Dodaro1 , Thomas Eiter2, Tobias Geibinger2 and Ilaria R. Vasile 1,∗ 1 DeMaCS, University of Calabria, 87036 Rende (CS), Italy 2 Institute of Logic and Computation, TU Wien, 1040 Vienna, Austria Abstract Structured Declarative Language (SDL) was introduced as a high-level specification language for combinatorial search and optimization problems, with its semantics originally defined through translation into Answer Set Programming (ASP) . In this paper, we present an extension of SDL, enabling dual-target compilation: SDL programs can now be translated to either ASP or MiniZinc, a standard modeling language for Constraint Programming (CP) . This extension addresses the semantic gap between the non-monotonic, stable-model semantics of ASP and the monotonic, classical satisfiability interpretation of CP. By mapping SDL constructs to constraint satisfaction formulations, specifically addressing challenges like negation as failure and recursive definitions, we preserve the flexibility and readability of SDL while unlocking the numerical and scheduling efficiency of CP solvers. We demonstrate the viability and coherence of this approach through complex real-world use cases, including the Nurse Scheduling Problem and Operating Room Scheduling. Keywords Knowledge Representation, Constraint Programming, MiniZinc, Answer Set Programming, Combinatorial Search and Optimization 1. Introduction Declarative approaches are widely adopted for modeling complex combinatorial optimization problems due to their high level of abstraction. However, in practice, the comparative evaluation of different solving technologies on the same problem specification remains challenging. The landscape of combinatorial problem solving is largely dominated by two well-established paradigms: Answer Set Programming (ASP) [4, 8] and Constraint Programming (CP) [13] . Despite their conceptual overlap and shared goals, the two paradigms rely on fundamentally different theoretical foundations. ASP is rooted in non-monotonic reasoning under stable model semantics and excels at modeling problems with complex dependencies, recursion, and incomplete information. On the other hand, CP is grounded in classical satisfiability and monotonic interpretation, relying on powerful domain filtering and constraint propagation techniques, and is particularly effective for problems involving large finite domains, arithmetic reasoning, and scheduling constraints. This divergence creates a practical modeling gap. The choice of solving technology is often dictated by the structural characteristics of the problem instance, yet selecting a solver typically forces the modeler to adopt a specific modeling language. As a result, evaluating the same problem across different paradigms often requires developing and maintaining multiple encodings, increasing complexity and the risk of inconsistencies. To address the maintainability issues of declarative encodings, recently the Structured Declarative Language (SDL) has been introduced [1] . Designed as a higher-level abstraction, SDL alleviates wellknown limitations of ASP-based encodings [5], such as positional notation, rigid arity, and cascading CILC 2026: The 41st Italian Conference on Computational Logic, June 23 –25, 2026, Ferrara, Italy ∗Corresponding author. [Envelope-Open](Envelope-Open mario.alviano@unical.it)[ mario.alviano@unical.it](Envelope-Open mario.alviano@unical.it) (M. Alviano); [carmine.dodaro@unical.it](carmine.dodaro@unical.it) (C. Dodaro); [thomas.eiter@tuwien.ac.at](thomas.eiter@tuwien.ac.at) (T. Eiter); [tobias.geibinger@tuwien.ac.at](tobias.geibinger@tuwien.ac.at) (T. Geibinger); [vasileilaria@gmail.com](vasileilaria@gmail.com) (I. R. Vasile) GLOBE https://alviano.net/ (M. Alviano); [https://www.cdodaro.eu](https://www.cdodaro.eu) (C. Dodaro) Orcid 0000-0002-2052-2063 (M. Alviano); 000

FAQs

What extension to SDL is proposed in the paper?

The paper extends SDL to enable dual-target compilation, translating SDL programs either to ASP or to MiniZinc for constraint programming. This maintains SDL’s readability while leveraging different solver paradigms.

How does the approach address the semantic gap between ASP and constraint programming?

It maps SDL constructs into constraint satisfaction formulations that fit CP’s monotonic classical interpretation. Key adaptations include reformulating negation as failure and eliminating recursion via rank-based non-recursive constraint encodings.

Which case studies are used to validate the method?

The validation relies on two case studies: the Nurse Scheduling Problem (NSP) and Operating Room Scheduling (ORS). The results show that a single SDL specification can derive correct models for both settings.

Oct 4, 2026

Upload by miaandmiso