EURO 2024 Copenhagen
Abstract Submission

EURO-Online login

4289. Using Clustering to Strengthen Decision Diagram Bounds for Discrete Optimization

Invited abstract in session TC-3: Optimization and Machine Learning: Methodological Advances, stream Data Science Meets Optimization.

Tuesday, 12:30-14:00
Room: 1005 (building: 202)

Authors (first author is the speaker)

1. Michael Römer
Decision Analytics Group, Bielefeld University
2. Mohsen Nafar
Bielefeld University

Abstract

Offering a generic approach to obtaining both upper and lower bounds, decision diagrams (DDs) are becoming an increasingly important tool for solving discrete optimization problems. In particular, they provide a powerful alternative to other well-known generic bounding mechanisms such as the LP relaxation. A standard approach to employ DDs for discrete optimization is to formulate the problem as a Dynamic Program and to compile a DD top-down in a layer-by-layer fashion. To limit the size of the resulting DD and to obtain bounds, one typically imposes a maximum width for each layer which is then enforced by either merging nodes (resulting in a relaxed DD providing a dual bound) or by dropping nodes (resulting in a restricted DD providing a primal bound). The quality of the DD bounds obtained from this top-down compilation heavily depends on the heuristics used for the selection of the nodes to merge or drop. While it is sometimes possible to engineer problem-specific heuristics for this, a generic approach relies on sorting the layer’s nodes based on objective function information. In this talk, we propose a generic and problem-agnostic approach that relies on clustering nodes based on the state information. In a set of experiments with different knapsack and scheduling problems, we show that our approach outperforms the classical generic approach, and often achieves drastically better bounds both with respect to the size of the DD and the time used for compiling the DDs.

Keywords

Status: accepted

Back to the list of papers