2433. A Clustering-based Variable Ordering Framework for Relaxed Decision Diagrams
Invited abstract in session TA-12: AI for Optimization Modeling, stream Artificial Intelligence, Machine Learning and Optimization.
Thursday, 8:45-10:15Room: H10
Authors (first author is the speaker)
| 1. | Mohsen Nafar
|
| Brandenburg University of Technology | |
| 2. | Hamed Azami Zenouzagh
|
| Computer Science, Gran Sasso Science Institute | |
| 3. | Michael Römer
|
| Decision Analytics Group, Bielefeld University | |
| 4. | Lin Xie
|
| Chair of Information Systemes and Business Analytics, Brandenburg University of Technolgy |
Abstract
High-quality primal and dual bounds are critical for devising efficient exact solution approaches for Discrete Optimization (DO) problems. Decision Diagrams (DDs) provide strong and generic mechanisms for providing such bounds. This paper focuses on so-called relaxed DDs which, by merging nodes, over-approximate the solution space of DO problems and provide dual bounds the quality of which hinges upon the ordering of the variables in the DD compilation and on the selection of the nodes to merge. We present a novel clustering-based variable ordering framework for relaxed decision diagrams. In a set of computational experiments on instances of the Maximum Weighted Independent Set Problem (MWISP), we show that using this framework for compiling relaxed DDs within a DD-based branch-and-bound algorithm substantially reduces its solution time.
Keywords
- Combinatorial Optimization
- Dynamic Programming
- Machine Learning
Status: accepted
Back to the list of papers