Academic Journal
Strengthening Relaxed Decision Diagrams for Maximum Independent Set Problem: Novel Variable Ordering and Merge Heuristics
| العنوان: | Strengthening Relaxed Decision Diagrams for Maximum Independent Set Problem: Novel Variable Ordering and Merge Heuristics |
|---|---|
| المؤلفون: | Nafar, Mohsen, Römer, Michael |
| المساهمون: | Mohsen Nafar and Michael Römer |
| بيانات النشر: | Schloss Dagstuhl – Leibniz-Zentrum für Informatik |
| سنة النشر: | 2024 |
| المجموعة: | DROPS - Dagstuhl Research Online Publication Server (Schloss Dagstuhl - Leibniz Center for Informatics ) |
| مصطلحات موضوعية: | Decision Diagram, Dynamic Programming, Maximum Independent Set Problem, Dual Bound |
| الوصف: | Finding high-quality bounds is key to devising efficient exact solution approaches for Discrete Optimization (DO) problems. To this end, Decision Diagrams (DDs) provide strong and generic bounding mechanisms. 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. Addressing the Maximum Independent Set Problem, we present a novel dynamic variable ordering strategy relying on induced subgraphs of the original graph, and a new tie-based merge heuristic. In a set of computational experiments, we show that our strategies yield much stronger bounds than the standard state-of-the-art approaches. Furthermore, implementing our heuristics in a DD-based branch-and-bound, we reduce the solution times by around 33 % on average and by more than 50 % on hard instances. |
| نوع الوثيقة: | article in journal/newspaper conference object |
| وصف الملف: | application/pdf |
| اللغة: | English |
| Relation: | Is Part Of LIPIcs, Volume 307, 30th International Conference on Principles and Practice of Constraint Programming (CP 2024); https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.21 |
| DOI: | 10.4230/LIPIcs.CP.2024.21 |
| الاتاحة: | https://doi.org/10.4230/LIPIcs.CP.2024.21 https://nbn-resolving.org/urn:nbn:de:0030-drops-207069 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.CP.2024.21 |
| Rights: | https://creativecommons.org/licenses/by/4.0/legalcode |
| رقم الانضمام: | edsbas.F58E05CC |
| قاعدة البيانات: | BASE |
| DOI: | 10.4230/LIPIcs.CP.2024.21 |
|---|