Compact MDDs for Pseudo-Boolean Constraints with At-Most-One Relations in
Resource-Constrained Scheduling Problems
Abstract
Pseudo-Boolean (PB) constraints are usually encoded into Boolean clauses using compact Binary
Decision Diagram (BDD) representations. Although these constraints appear in many problems,
they are particularly useful for representing resource constraints in scheduling problems. Sometimes, the Boolean variables in the PB constraints
have implicit at-most-one relations. In this work
we introduce a way to take advantage of these implicit relations to obtain a compact Multi-Decision
Diagram (MDD) representation for those PB constraints. We provide empirical evidence of the
usefulness of this technique for some ResourceConstrained Project Scheduling Problem (RCPSP)
variants, namely the Multi-Mode RCPSP (MRCPSP) and the RCPSP with Time-Dependent Resource Capacities and Requests (RCPSP/t). The
size reduction of the representation of the PB constraints lets us decrease the number of Boolean
variables in the encodings by one order of magnitude. We close/certify the optimum of many instances of these problems