Compact MDDs for Pseudo-Boolean Constraints with At-Most-One Relations in Resource-Constrained Scheduling Problems

Miquel Bofill, Jordi Coll, Josep Suy, Mateu VillaretIJCAI 2017 · DOI

TL;DR

This paper introduces a novel way to represent Pseudo-Boolean (PB) constraints, common in scheduling problems, by exploiting implicit "at-most-one" (AMO) relationships between their variables. This leads to significantly more compact representations (Multi-Decision Diagrams or MDDs) and, consequently, smaller SAT encodings, resulting in state-of-the-art performance on challenging scheduling benchmarks.

What Problem Does This Paper Address?

Resource-Constrained Project Scheduling Problems (RCPSPs) are notoriously difficult optimization problems. A key challenge in solving them is efficiently encoding the complex constraints, particularly those related to resource usage. Traditional methods often represent these constraints using Pseudo-Boolean (PB) constraints, which are then translated into SAT (Satisfiability) problems. However, these PB constraint encodings can become very large, hindering the performance of SAT solvers. This paper addresses the issue of overly large PB constraint encodings by recognizing that in many scheduling problems, variables within these PB constraints implicitly satisfy "at-most-one" (AMO) relationships. The authors aim to leverage these implicit AMO relations to create more compact representations, thereby improving the efficiency of solving these scheduling problems.

Methods

The core innovation lies in the introduction of "AMO-PB constraints" and their representation using Multi-Decision Diagrams (MDDs).

  • AMO-PB Constraints: These are PB constraints where the variables within specific terms (AMO-products) are known to satisfy an at-most-one relationship. This means that if an AMO relation is violated, the entire term is effectively undefined or irrelevant, allowing for a more specialized representation.
  • Multi-Decision Diagrams (MDDs): The paper extends the concept of Binary Decision Diagrams (BDDs) to MDDs. While BDDs represent Boolean functions, MDDs can handle multi-valued decisions. In this context, an MDD node represents an AMO-product, and its outgoing edges correspond to selecting one variable from the AMO-product to be true, or selecting none (the "else" case). This structure naturally encodes the AMO property.
  • MDD Construction Algorithm: A generalized algorithm is presented to construct Reduced Ordered Multi-Decision Diagrams (ROMDDs) for AMO-PB constraints. This algorithm leverages dynamic programming and interval analysis to efficiently build the MDD, ensuring it's canonical and compact.
  • SAT Encoding: The constructed MDDs are then translated into SAT encodings. The paper adapts existing monotonic MDD encoding techniques to handle the "else" case in their MDDs, resulting in efficient SAT formulations.
  • Exploiting Implicit AMO Relations: A crucial aspect is how AMO relations are identified. For RCPSP, precedence constraints in the project graph naturally induce AMO relations among variables representing activity execution at specific time points. For extensions like MRCPSP and RCPSP/t, additional implicit AMO relations arise from activity modes and time-dependent resource usage.

Datasets

The authors evaluated their approach on benchmark datasets for the Resource-Constrained Project Scheduling Problem (RCPSP) and its extensions:

  • RCPSP: Datasets from PSPLib (j30, j60, j90, j120).
  • Multi-Mode RCPSP (MRCPSP): Datasets from PSPLib (j30, m50) and MMLIB50.
  • RCPSP with Time-Dependent Resource Capacities and Requests (RCPSP/t): Datasets j30 and j120.

Key Insights and Ideas

  • Implicit AMO relations are a goldmine for compression: The paper demonstrates that many scheduling constraints, when formulated as PB constraints, have variables that are implicitly constrained by at-most-one relationships due to problem structure (e.g., precedences).
  • MDDs are a natural fit for AMO-PB constraints: By designing MDDs where nodes represent AMO-products and edges represent variable selections, the paper creates a compact and efficient representation that directly mirrors the constraint structure.
  • Significant reduction in encoding size: The core benefit is a dramatic reduction in the number of Boolean variables and clauses in the SAT encoding, often by an order of magnitude, which directly translates to faster solving times.
  • State-of-the-art performance: The proposed approach, termed APB, achieves competitive or superior performance compared to existing exact solvers on challenging scheduling benchmarks, even certifying optimality for new instances.
  • Generalizability: The technique is applicable to any problem where PB constraints and implicit AMO relations co-exist, suggesting broader applicability beyond scheduling.

Key Results

  • Encoding Size Reduction: The number of Boolean variables in the encodings was reduced by an order of magnitude, and the number of clauses was roughly halved, compared to standard PB encodings.
  • Performance Improvement: The APB solver (using MDDs for AMO-PB constraints) significantly outperforms other approaches on MRCPSP and RCPSP/t benchmarks, solving more instances to optimality within the timeout.
  • New Optimality Certifications: The authors certified the optimality of 6 new instances and improved upper bounds for 2 instances for the MMLIB50 dataset for RCPSP. For RCPSP/t, they certified optimality or infeasibility for 5090 instances and improved upper bounds for 1763 instances.

Limitations and Future Work

  • AMO Constraint Enforcement: The paper notes that the AMO constraints within AMO-products are assumed to hold and must be enforced either implicitly by other constraints or explicitly. The SAT encoding itself does not enforce these AMO relations.
  • Generalizability to other constraint types: While the paper focuses on PB constraints, future work could explore applying similar MDD-based compression techniques to other types of constraints.
  • Further exploration of implicit AMO relations: Identifying and exploiting implicit AMO relations in a wider range of problems could lead to further performance gains.
  • Integration with other SMT theories: The current work focuses on SAT encodings derived from MDDs. Exploring tighter integration with other SMT theories could be beneficial.

Summary updated

BibTeX
@inproceedings{bofill2017compact,
  author = {Miquel Bofill and Jordi Coll and Josep Suy and Mateu Villaret},
  title = {{Compact MDDs for Pseudo-Boolean Constraints with At-Most-One Relations in Resource-Constrained Scheduling Problems}},
  booktitle = {International Joint Conference on Artificial Intelligence},
  year = {2017},
  doi = {10.24963/ijcai.2017/78},
}
Figure