Extending Structured Declarative Language with Constraint Programming via MiniZinc

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 Pro- gramming (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.