Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2022
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866913199200141312 |
|---|---|
| author | Coppé, Vianney Gillard, Xavier Schaus, Pierre |
| author_facet | Coppé, Vianney Gillard, Xavier Schaus, Pierre |
| contents | The branch-and-bound algorithm based on decision diagrams introduced by Bergman et al. in 2016 is a framework for solving discrete optimization problems with a dynamic programming formulation. It works by compiling a series of bounded-width decision diagrams that can provide lower and upper bounds for any given subproblem. Eventually, every part of the search space will be either explored or pruned by the algorithm, thus proving optimality. This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. These thresholds are based on dominance relations between partial solutions previously found and on the pruning inequalities of the filtering techniques introduced by Gillard et al. in 2021. Computational experiments show that the pruning brought by this caching mechanism allows significantly reducing the number of nodes expanded by the algorithm. This results in more benchmark instances of difficult optimization problems being solved in less time while using narrower decision diagrams. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2211_13118 |
| institution | arXiv |
| publishDate | 2022 |
| record_format | arxiv |
| spellingShingle | Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection Coppé, Vianney Gillard, Xavier Schaus, Pierre Data Structures and Algorithms Artificial Intelligence Discrete Mathematics Optimization and Control 90C39, 90C27, 90C57 I.2.8; G.2.1 The branch-and-bound algorithm based on decision diagrams introduced by Bergman et al. in 2016 is a framework for solving discrete optimization problems with a dynamic programming formulation. It works by compiling a series of bounded-width decision diagrams that can provide lower and upper bounds for any given subproblem. Eventually, every part of the search space will be either explored or pruned by the algorithm, thus proving optimality. This paper presents new ingredients to speed up the search by exploiting the structure of dynamic programming models. The key idea is to prevent the repeated expansion of nodes corresponding to the same dynamic programming states by querying expansion thresholds cached throughout the search. These thresholds are based on dominance relations between partial solutions previously found and on the pruning inequalities of the filtering techniques introduced by Gillard et al. in 2021. Computational experiments show that the pruning brought by this caching mechanism allows significantly reducing the number of nodes expanded by the algorithm. This results in more benchmark instances of difficult optimization problems being solved in less time while using narrower decision diagrams. |
| title | Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection |
| topic | Data Structures and Algorithms Artificial Intelligence Discrete Mathematics Optimization and Control 90C39, 90C27, 90C57 I.2.8; G.2.1 |
| url | https://arxiv.org/abs/2211.13118 |