3 présentations

• 
  08h30 - 08h52

  Nonserial decision diagrams

  • John Hooker, prés., Carnegie Mellon University

  We investigate properties of nonserial decision diagrams, which might also be described as and-or decision diagrams (DDs). They are inspired by nonserial dynamic programming but benefit from the reduction and relaxation possibilities of DDs. We generalize traditional uniqueness theorems for reduced DDs to nonserial weighted and unweighted DDs. We also explore the effectiveness of nonserial DDs to reduce the DD size when variable coupling is limited, for example on set packing problems.

• 
  08h52 - 09h14

  Solving Combinatorial Optimization Problems with the Decision Diagram-Based Solver CODD

  • Willem-Jan van Hoeve, prés., Carnegie Mellon University
  • Laurent Michel, University of Connecticut

  We present CODD, a system for solving combinatorial optimization problems using decision diagram technology. Problems are represented as state-based dynamic programming models using the CODD specification language. The model is used to automatically compile relaxed and restricted decision diagrams that are embedded inside a branch-and-bound search process. We show how the models can be enhanced with user-defined state functions, e.g., to compute a local bound. We demonstrate the functionality of CODD on a variety of combinatorial optimization problems and compare its performance to other state-based solvers as well as integer programming and constraint programming solvers. CODD provides competitive results on these domains and can outperform the other solvers, sometimes by orders of magnitude.

• 
  09h14 - 09h36

  Exploiting Transition Dominance in Domain-Independent Dynamic Programming

  • Allen Z. Zhong, Monash University
  • Ryo Kuroiwa, National Institute of Informatics, Japan
  • Jimmy H.M. Lee, The Chinese University of Hong Kong
  • Peter J. Stuckey, Monash University
  • J. Christopher Beck, prés., University of Toronto

  Domain-independent dynamic programming (DIDP) is a recently proposed model-based paradigm that extends dynamic programming (DP) and has demonstrated promising performance in addressing various combinatorial optimization problems. This framework allows users to define DP models based on a state transition system. In this paper, we define the concept of transition dominance within DIDP where one transition can always lead to better solutions than another, and thus the search can avoid the dominated one. To efficiently implement the pruning effects of transition dominance, we further introduce state functions for caching values and avoiding redundant computations. Additionally, we explore how different viewpoints in DP models impact the modeling of transition dominance. We experimentally evaluate DP models across various problem classes using state space search algorithms within the DIDP framework. The results confirm that combining transition dominance with state functions significantly improve the performance for search algorithms compared to baselines.