MILP-FBGen: LP/MILP Instance Generation with Feasibility/Boundedness

Yahong Zhang, Chenchen Fan, Donghui Chen, Congrui Li, Wenli Ouyang, Mingda Zhu, Junchi Yan
Proceedings of the 41st International Conference on Machine Learning, PMLR 235:58881-58896, 2024.

Abstract

Machine learning (ML) has been actively adopted in Linear Programming (LP) and Mixed-Integer Linear Programming (MILP), whose potential is hindered by instance scarcity. Current synthetic instance generation methods often fall short in closely mirroring the distribution of original datasets or ensuring the feasibility and boundedness of the generated data — a critical requirement for obtaining reliable supervised labels in model training. In this paper, we present a diffusion-based LP/MILP instance generative framework called MILP-FBGen. It strikes a balance between structural similarity and novelty while maintaining feasibility/boundedness via a meticulously designed structure-preserving generation module and a feasibility/boundedness-constrained sampling module. Our method shows superiority on two fronts: 1) preservation of key properties (hardness, feasibility, and boundedness) of LP/MILP instances, and 2) enhanced performance on downstream tasks. Extensive studies show two-fold superiority that our method ensures higher distributional similarity and 100% feasibility in both easy and hard datasets, surpassing current state-of-the-art techniques.

Cite this Paper

BibTeX
@InProceedings{pmlr-v235-zhang24p, title = {{MILP}-{FBG}en: {LP}/{MILP} Instance Generation with {F}easibility/{B}oundedness}, author = {Zhang, Yahong and Fan, Chenchen and Chen, Donghui and Li, Congrui and Ouyang, Wenli and Zhu, Mingda and Yan, Junchi}, booktitle = {Proceedings of the 41st International Conference on Machine Learning}, pages = {58881--58896}, year = {2024}, editor = {Salakhutdinov, Ruslan and Kolter, Zico and Heller, Katherine and Weller, Adrian and Oliver, Nuria and Scarlett, Jonathan and Berkenkamp, Felix}, volume = {235}, series = {Proceedings of Machine Learning Research}, month = {21--27 Jul}, publisher = {PMLR}, pdf = {https://raw.githubusercontent.com/mlresearch/v235/main/assets/zhang24p/zhang24p.pdf}, url = {https://proceedings.mlr.press/v235/zhang24p.html}, abstract = {Machine learning (ML) has been actively adopted in Linear Programming (LP) and Mixed-Integer Linear Programming (MILP), whose potential is hindered by instance scarcity. Current synthetic instance generation methods often fall short in closely mirroring the distribution of original datasets or ensuring the feasibility and boundedness of the generated data — a critical requirement for obtaining reliable supervised labels in model training. In this paper, we present a diffusion-based LP/MILP instance generative framework called MILP-FBGen. It strikes a balance between structural similarity and novelty while maintaining feasibility/boundedness via a meticulously designed structure-preserving generation module and a feasibility/boundedness-constrained sampling module. Our method shows superiority on two fronts: 1) preservation of key properties (hardness, feasibility, and boundedness) of LP/MILP instances, and 2) enhanced performance on downstream tasks. Extensive studies show two-fold superiority that our method ensures higher distributional similarity and 100% feasibility in both easy and hard datasets, surpassing current state-of-the-art techniques.} }
Endnote
%0 Conference Paper %T MILP-FBGen: LP/MILP Instance Generation with Feasibility/Boundedness %A Yahong Zhang %A Chenchen Fan %A Donghui Chen %A Congrui Li %A Wenli Ouyang %A Mingda Zhu %A Junchi Yan %B Proceedings of the 41st International Conference on Machine Learning %C Proceedings of Machine Learning Research %D 2024 %E Ruslan Salakhutdinov %E Zico Kolter %E Katherine Heller %E Adrian Weller %E Nuria Oliver %E Jonathan Scarlett %E Felix Berkenkamp %F pmlr-v235-zhang24p %I PMLR %P 58881--58896 %U https://proceedings.mlr.press/v235/zhang24p.html %V 235 %X Machine learning (ML) has been actively adopted in Linear Programming (LP) and Mixed-Integer Linear Programming (MILP), whose potential is hindered by instance scarcity. Current synthetic instance generation methods often fall short in closely mirroring the distribution of original datasets or ensuring the feasibility and boundedness of the generated data — a critical requirement for obtaining reliable supervised labels in model training. In this paper, we present a diffusion-based LP/MILP instance generative framework called MILP-FBGen. It strikes a balance between structural similarity and novelty while maintaining feasibility/boundedness via a meticulously designed structure-preserving generation module and a feasibility/boundedness-constrained sampling module. Our method shows superiority on two fronts: 1) preservation of key properties (hardness, feasibility, and boundedness) of LP/MILP instances, and 2) enhanced performance on downstream tasks. Extensive studies show two-fold superiority that our method ensures higher distributional similarity and 100% feasibility in both easy and hard datasets, surpassing current state-of-the-art techniques.
APA
Zhang, Y., Fan, C., Chen, D., Li, C., Ouyang, W., Zhu, M. & Yan, J.. (2024). MILP-FBGen: LP/MILP Instance Generation with Feasibility/Boundedness. Proceedings of the 41st International Conference on Machine Learning, in Proceedings of Machine Learning Research 235:58881-58896 Available from https://proceedings.mlr.press/v235/zhang24p.html.

Related Material