Decision Diagram-Based Branch-and-Bound with Caching for Dominance and Suboptimality Detection

Vianney Coppé (), Xavier Gillard () and Pierre Schaus ()
Additional contact information
Vianney Coppé: UCLouvain, 1348 Louvain-la-Neuve, Belgium
Xavier Gillard: UCLouvain, 1348 Louvain-la-Neuve, Belgium
Pierre Schaus: UCLouvain, 1348 Louvain-la-Neuve, Belgium

INFORMS Journal on Computing, 2024, vol. 36, issue 6, 1522-1542

Abstract: The branch-and-bound algorithm based on decision diagrams 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 pruning inequalities given by rough upper bounds and local bounds — two additional filtering techniques recently introduced. Computational experiments show that the pruning brought by this caching mechanism allows for 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.

Keywords: discrete optimization; decision diagrams; branch-and-bound; caching (search for similar items in EconPapers)
Date: 2024
References: View references in EconPapers View complete reference list from CitEc
Citations:

Downloads: (external link)
http://dx.doi.org/10.1287/ijoc.2022.0340 (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:inm:orijoc:v:36:y:2024:i:6:p:1522-1542

Access Statistics for this article

More articles in INFORMS Journal on Computing from INFORMS Contact information at EDIRC.
Bibliographic data for series maintained by Chris Asher ().