Skip to yearly menu bar Skip to main content


Poster

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

Yahong Zhang · Chenchen Fan · Donghui Chen · Congrui Li · Wenli Ouyang · Mingda Zhu · Junchi Yan


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 and maintains feasibility/boundedness via a meticulously designed structure-preserving generation module and a feasibility/boundedness-constraint sampling module. We further propose an end-to-end task-oriented training scheme. 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 empirical studies show that it outperforms SOTA instance generation models.

Live content is unavailable. Log in and register to view live content