Invited Talks

Since their original inception to represent Boolean functions for verification problems in the 1950s, decision diagrams have found wide applicability across academic disciplines and industry. This presentation discusses the use of decision diagrams as a compact representation of feasible solutions to constrained optimization problems, where solutions correspond to paths in a layered graph. By using relaxed and restricted decision diagrams of bounded size, one can balance the strength of the representation and computational effort.

We highlight three roles of decision diagrams in constrained optimization. First, they enable a model-and-solve approach for dynamic programming, where a DP model and a merging rule define the compilation of decision diagrams that yield primal and dual bounds within a state-based search. Second, in constraint programming, they strengthen constraint propagation through multi-valued decision diagrams and provide optimization bounds within the search process. Third, in integer programming, they yield arc-flow formulations and establish connections with Dantzig–Wolfe decomposition, leading to strong bounds and state-of-the-art computational results.

These approaches are illustrated on applications including machine scheduling, graph multi-coloring, and vehicle routing, where decision diagram-based methods have led to substantial improvements on benchmark instances. They have also been adopted in practice, both as a dual bounding component within a general-purpose optimization solver and in industrial applications for routing and scheduling.

Constraint Answer Set Programming (CASP) integrates the high-level modeling capabilities of Answer Set Programming (ASP) with the efficient numerical computation of Constraint Programming (CP). By partitioning the problem space, CASP leverages the complementary strengths of its underlying solvers: the ASP component facilitates rich relational modeling and non-monotonic reasoning, specifically the handling of defaults and exceptions, while the CP component manages variables over expansive numeric domains via specialized propagators

However, this synthesis introduces significant semantic challenges regarding the interaction between stable model semantics and classical constraint theory. Central to ASP is the ability to differentiate between founded and unfounded atoms, a departure from the classical treatment of variables in SAT where truth is typically a matter of assignment rather than derivation. As CASP systems have evolved, diverse interpretations of foundedness have emerged regarding how these logical requirements should extend to constraints and numeric variables.

This talk examines the semantic foundations of several CASP systems to illustrate these nuances. In particular, we present /flingo/, a CASP system designed to preserve the declarative richness of ASP within constraint satisfaction problems. By supporting default values, undefined variables, non-deterministic assignments, and aggregates directly within numeric constraints, /flingo/ restores the expressive power often lost in traditional CASP translations. We explore how this approach allows for a more natural integration of numeric attributes without sacrificing the foundational principles of ASP.