Logo image
Back
Generative Branching for Mixed-Integer Linear Programming
Conference paper   Peer reviewed

Generative Branching for Mixed-Integer Linear Programming

Ruobing Wang, Xin Li, Yangchuan Wang, Zijian Zhang and Mingzhong Wang
Proceedings of the AAAI Conference on Artificial Intelligence, Vol.40(17), pp.14352-14360
AAAI Press
2026
DOI: https://doi.org/10.1609/aaai.v40i17.38450
url
https://doi.org/10.1609/aaai.v40i17.38450View
Published Version Open

Abstract

Branch-and-bound (B&B) is a fundamental algorithmic framework for solving Mixed-Integer Linear Programming (MILP) problems, where branching decisions critically affect solver efficiency. Recent learning-based methods apply imitation learning to select branching variables, but their deterministic predictions limit exploration and generalization. In this paper, we propose a novel framework that formulates branching variable selection as a conditional generative process, exploring deep-level decision features. Our approach leverages diffusion models to enable diverse and exploratory branching score generation, while consistency modeling distills this process into efficient one-step inference conditioned on the B&B state. This mode allows our method to achieve both high-quality and fast branching decisions, significantly improving the overall performance of branch-and-bound solvers. Extensive experiments on challenging cross-scale and cross-category benchmarks demonstrate that our framework consistently outperforms state-of-the-art imitation learning baselines, delivering substantial improvements in solution quality, computational efficiency, and inference speed.

Details

Metrics

1 Record Views
Logo image