Generative Branching for Mixed-Integer Linear Programming

Ruobing Wang; Xin Li; Yangchuan Wang; Zijian Zhang; Mingzhong Wang

doi:10.1609/aaai.v40i17.38450

Generative Branching for Mixed-Integer Linear Programming

Ruobing Wang
, Xin Li^*
, Yangchuan Wang
, Zijian Zhang
, Mingzhong Wang

^*此作品的通讯作者

Beijing Institute of Technology
Jilin University
University of the Sunshine Coast

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

摘要

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.

源语言	英语
主期刊名	Proceedings of the AAAI Conference on Artificial Intelligence
编辑	Sven Koenig, Chad Jenkins, Matthew E. Taylor
出版商	Association for the Advancement of Artificial Intelligence
页	14352-14360
页数	9
版本	17
ISBN（印刷版）	9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067, 9781577359067
DOI	https://doi.org/10.1609/aaai.v40i17.38450
出版状态	已出版 - 2026
活动	40th AAAI Conference on Artificial Intelligence, AAAI 2026 - Singapore, 新加坡期限: 20 1月 2026 → 27 1月 2026

出版系列

姓名	Proceedings of the AAAI Conference on Artificial Intelligence
编号	17
卷	40
ISSN（印刷版）	2159-5399
ISSN（电子版）	2374-3468

会议

会议	40th AAAI Conference on Artificial Intelligence, AAAI 2026
国家/地区	新加坡
市	Singapore
时期	20/01/26 → 27/01/26

访问文件

10.1609/aaai.v40i17.38450

其它文件与链接

链接到 Scopus 的出版物

引用此

Wang, R., Li, X., Wang, Y., Zhang, Z., & Wang, M. (2026). Generative Branching for Mixed-Integer Linear Programming. 在 S. Koenig, C. Jenkins, & M. E. Taylor (编辑), Proceedings of the AAAI Conference on Artificial Intelligence (17 编辑, 页码 14352-14360). (Proceedings of the AAAI Conference on Artificial Intelligence; 卷 40, 号码 17). Association for the Advancement of Artificial Intelligence. https://doi.org/10.1609/aaai.v40i17.38450

Wang, Ruobing ; Li, Xin ; Wang, Yangchuan 等. / Generative Branching for Mixed-Integer Linear Programming. Proceedings of the AAAI Conference on Artificial Intelligence. 编辑 / Sven Koenig ; Chad Jenkins ; Matthew E. Taylor. 17. 编辑 Association for the Advancement of Artificial Intelligence, 2026. 页码 14352-14360 (Proceedings of the AAAI Conference on Artificial Intelligence; 17).

@inproceedings{de44671861a740878bffeffbe1058b06,

title = "Generative Branching for Mixed-Integer Linear Programming",

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.",

author = "Ruobing Wang and Xin Li and Yangchuan Wang and Zijian Zhang and Mingzhong Wang",

note = "Publisher Copyright: {\textcopyright} 2026, Association for the Advancement of Artificial Intelligence (www.aaai.org). All rights reserved.; 40th AAAI Conference on Artificial Intelligence, AAAI 2026 ; Conference date: 20-01-2026 Through 27-01-2026",

year = "2026",

doi = "10.1609/aaai.v40i17.38450",

language = "English",

isbn = "9781577359067",

series = "Proceedings of the AAAI Conference on Artificial Intelligence",

publisher = "Association for the Advancement of Artificial Intelligence",

number = "17",

pages = "14352--14360",

editor = "Sven Koenig and Chad Jenkins and Taylor, \{Matthew E.\}",

booktitle = "Proceedings of the AAAI Conference on Artificial Intelligence",

edition = "17",

}

Wang, R, Li, X, Wang, Y, Zhang, Z & Wang, M 2026, Generative Branching for Mixed-Integer Linear Programming. 在 S Koenig, C Jenkins & ME Taylor (编辑), Proceedings of the AAAI Conference on Artificial Intelligence. 17 编辑, Proceedings of the AAAI Conference on Artificial Intelligence, 号码 17, 卷 40, Association for the Advancement of Artificial Intelligence, 页码 14352-14360, 40th AAAI Conference on Artificial Intelligence, AAAI 2026, Singapore, 新加坡, 20/01/26. https://doi.org/10.1609/aaai.v40i17.38450

Generative Branching for Mixed-Integer Linear Programming. / Wang, Ruobing; Li, Xin; Wang, Yangchuan 等.
Proceedings of the AAAI Conference on Artificial Intelligence. 编辑 / Sven Koenig; Chad Jenkins; Matthew E. Taylor. 17. 编辑 Association for the Advancement of Artificial Intelligence, 2026. 页码 14352-14360 (Proceedings of the AAAI Conference on Artificial Intelligence; 卷 40, 号码 17).

科研成果: 书/报告/会议事项章节 › 会议稿件 › 同行评审

TY - GEN

T1 - Generative Branching for Mixed-Integer Linear Programming

AU - Wang, Ruobing

AU - Li, Xin

AU - Wang, Yangchuan

AU - Zhang, Zijian

AU - Wang, Mingzhong

PY - 2026

Y1 - 2026

N2 - 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.

AB - 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.

UR - https://www.scopus.com/pages/publications/105034608293

U2 - 10.1609/aaai.v40i17.38450

DO - 10.1609/aaai.v40i17.38450

M3 - Conference contribution

AN - SCOPUS:105034608293

SN - 9781577359067

T3 - Proceedings of the AAAI Conference on Artificial Intelligence

SP - 14352

EP - 14360

BT - Proceedings of the AAAI Conference on Artificial Intelligence

A2 - Koenig, Sven

A2 - Jenkins, Chad

A2 - Taylor, Matthew E.

PB - Association for the Advancement of Artificial Intelligence

T2 - 40th AAAI Conference on Artificial Intelligence, AAAI 2026

Y2 - 20 January 2026 through 27 January 2026

ER -

Wang R, Li X, Wang Y, Zhang Z, Wang M. Generative Branching for Mixed-Integer Linear Programming. 在 Koenig S, Jenkins C, Taylor ME, 编辑, Proceedings of the AAAI Conference on Artificial Intelligence. 17 编辑 Association for the Advancement of Artificial Intelligence. 2026. 页码 14352-14360. (Proceedings of the AAAI Conference on Artificial Intelligence; 17). doi: 10.1609/aaai.v40i17.38450

Generative Branching for Mixed-Integer Linear Programming

摘要

出版系列

会议

访问文件

其它文件与链接

学术指纹

引用此