Improving the filtering of Branch-And-Bound MDD solver (extended)

2021-04-24 · Xavier Gillard, Vianney Coppé, Pierre Schaus, André Augusto Cire

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.

📄 PDF Abstract BibTeX arXiv:2104.11951

Code (1)

xgillard/ddo 공식 구현

Methods 이 논문이 사용한 방법론

Pruning 설명 없음

Branched Signature Kernel Solvers for ODEs with rough Single-Trajectory signals

2026-05-25 · Munawar Ali, Qi Feng, Charlie Pyle, George Xu arxiv

We develop a branched signature kernel solver for linear and nonlinear ordinary differential equations driven by a \emph{single observed trajectory} of a possibly rough forcing signal -- a setting that arises naturally i…

Learning to Search in Branch and Bound Algorithms

2014-12-01 · NeurIPS 2014 12 · He He, Hal Daume III, Jason M. Eisner

Branch-and-bound is a widely used method in combinatorial optimization, including mixed integer programming, structured prediction and MAP inference. While most work has been focused on developing problem-specific techni…

Combinatorial Optimization Imitation Learning Structured Prediction

Learning to Branch in Combinatorial Optimization with Graph Pointer Networks

2023-07-04 · Rui Wang, Zhiming Zhou, Tao Zhang, Ling Wang 외

Branch-and-bound is a typical way to solve combinatorial optimization problems. This paper proposes a graph pointer network model for learning the variable selection policy in the branch-and-bound. We extract the graph f…

Combinatorial Optimization Graph Neural Network Variable Selection

Machine Learning Augmented Branch and Bound for Mixed Integer Linear Programming

2024-02-08 · Lara Scavuzzo, Karen Aardal, Andrea Lodi, Neil Yorke-Smith

Mixed Integer Linear Programming (MILP) is a pillar of mathematical optimization that offers a powerful modeling language for a wide range of applications. During the past decades, enormous algorithmic progress has been …

TreeDQN: Learning to minimize Branch-and-Bound tree

2023-06-09 · Dmitry Sorokin, Alexander Kostin

Combinatorial optimization problems require an exhaustive search to find the optimal solution. A convenient approach to solving combinatorial optimization tasks in the form of Mixed Integer Linear Programs is Branch-and-…

Combinatorial Optimization reinforcement-learning Reinforcement Learning Variable Selection