AMO-aware Aggregates in Answer Set Programming

Mario Alviano, Carmine Dodaro, Salvatore Fiorentino, Marco MarateaIJCAI 2024

Introduction

Answer Set Programming (ASP) has emerged as a powerful paradigm for solving complex combinatorial problems. Central to its modeling capabilities are "aggregates," such as SUM, which allow users to express constraints on the total weight of a set of true atoms. However, a common pattern in combinatorial optimization involves the interaction between these sums and "At-Most-One" (AMO) constraints—rules ensuring that at most one option from a set can be selected (e.g., a node in a graph having at most one color).

Current state-of-the-art ASP solvers typically treat SUM aggregates and AMO constraints independently. This separation prevents the solver from recognizing how mutual exclusivity restricts the possible total sum, leading to significant overestimations of the search space and inefficient pruning. This paper introduces AMOSUM, a novel linguistic construct designed to bridge this gap by making aggregates "AMO-aware."

The AMOSUM Construct

The core contribution is the AMOSUM aggregate, which explicitly links weights to partitions governed by AMO constraints.

Syntax and Semantics

A standard SUM aggregate is expressed as SUM{weight: literal} >= bound. The proposed extension adds a partition tag: AMOSUM{weight : literal [partition]} >= bound This syntax informs the solver that all literals sharing the same partition ID are mutually exclusive.

The "Max" vs. "Sum" Insight

The fundamental breakthrough lies in how the solver estimates the remaining sum. In a standard aggregate, if literals $x$ and $y$ are both available, the solver assumes their potential contribution is $weight(x) + weight(y)$. If $x$ and $y$ are in an AMO relationship, however, their maximum combined contribution is actually $\max(weight(x), weight(y))$. By utilizing this tighter bound, the AMOSUM propagator can prune branches of the search tree much earlier than standard methods.

Implementation: AMOWASP

The authors implemented this logic in AMOWASP, a system built on the WASP solver using a Python-based propagator interface. The propagator employs three primary inference rules:

  1. AMO Inference: Enforces mutual exclusivity within partitions.
  2. Enhanced SUM Inference: Uses the "max" rule to provide tighter estimates for reaching the bound.
  3. Partition Falsification: Immediately falsifies all literals in a partition if even its maximum weight is insufficient to satisfy the aggregate.

Experimental Evaluation

The performance of AMOWASP was evaluated against CLINGO and the native WASP solver across three benchmarks: a Synthetic Benchmark (SB), Graph Coloring (GC), and Knapsack (K).

Synthetic Benchmark and Conflict Reduction

The Synthetic Benchmark was designed to test the pruning power of the AMOSUM propagator. While standard solvers like CLINGO and WASP struggled with millions of conflicts as problem size and weight complexity increased, AMOWASP solved all 24 instances with zero conflicts.

Conflict counts for CLINGO and WASP on the synthetic benchmark across different partition sizes.

Key Results

The advantages of AMO-awareness become even more apparent in complex combinatorial problems.

  • Graph Coloring: AMOWASP solved 72 instances, far exceeding CLINGO (53) and WASP (18).
  • Knapsack: AMOWASP solved 76 instances, compared to 48 for CLINGO and 12 for WASP.
Cactus plots showing execution time vs. solved instances for Graph Coloring and Knapsack benchmarks.

As shown in the cactus plots, AMOWASP maintains a low execution time for a much larger number of instances, demonstrating its scalability. The performance gain is particularly significant when constraints are "tight," where the interplay between the sum and mutual exclusivity is most restrictive.

Conclusion and Future Work

By making aggregates aware of AMO constraints, the AMOSUM construct significantly enhances the efficiency of ASP solvers for weighted combinatorial problems. While the current Python-based implementation introduces some overhead for small instances, the massive reduction in search space (often by orders of magnitude) proves the value of this approach. Future work includes developing a native C++ implementation and extending the logic to support "At-Most-K" constraints and other complex aggregate structures.

Summary updated

BibTeX
@inproceedings{alviano2024amo,
  author = {Mario Alviano and Carmine Dodaro and Salvatore Fiorentino and Marco Maratea},
  title = {{AMO-aware Aggregates in Answer Set Programming}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2024},
}

Loading related content...

Figure