Improving the Filtering of Branch-and-Bound MDD Solver

Gillard, Xavier;Coppé, Vianney;Schaus, Pierre;Cire, André Augusto
(2021) Integration of Constraint Programming, Artificial Intelligence, and Operations Research : Lecture Notes in Computer Science — ISBN: [978-3-030-78229-0], p. 231-247, published

Files

paper_38.pdf
  • Open Access
  • Adobe PDF
  • 510.84 KB
Download

Details

Authors
  • Gillard, Xavierorcid-logoUCLouvain
    Author
  • Coppé, Vianneyorcid-logoUCLouvain
    Collaborator
  • Schaus, Pierreorcid-logoUCLouvain
    Scientific Director/Editor
  • Cire, André Augustoorcid-logoUToronto
    Collaborator
Abstract
This paper presents and evaluates two pruning techniques to reinforce the efficiency of constraint optimization solvers based on multi-valued decision-diagrams (MDD). It adopts the branch-and-bound framework proposed by Bergman et al. in 2016 to solve dynamic programs to optimality. In particular, our paper presents and evaluates the effectiveness of the local-bound (LocB) and rough upper-bound pruning (RUB). LocB is a new and effective rule that leverages the approximate MDD structure to avoid the exploration of non-interesting nodes. RUB is a rule to reduce the search space during the development of bounded-width-MDDs. The experimental study we conducted on the Maximum Independent Set Problem (MISP), Maximum Cut Problem (MCP), Maximum 2 Satisfiability (MAX2SAT) and the Traveling Salesman Problem with Time Windows (TSPTW) shows evidence indicating that rough-upper-bound and local-bound pruning have a high impact on optimization solvers based on branch-and-bound with MDDs. In particular, it shows that RUB delivers excellent results but requires some effort when defining the model. Also, it shows that LocB provides a significant improvement automatically; without necessitating any user-supplied information. Finally, it also shows that rough-upper-bound and local-bound pruning are not mutually exclusive, and their combined benefit supersedes the individual benefit of using each technique.
Affiliations

Citations

  • APA
  • Chicago
  • FWB

Gillard, X. (2021). Improving the Filtering of Branch-and-Bound MDD Solver. In Peter J Stuckey (ed.), Integration of Constraint Programming, Artificial Intelligence, and Operations Research : Lecture Notes in Computer Science (p. p. 231-247). Springer. https://doi.org/10.1007/978-3-030-78230-6_15