Skip to yearly menu bar Skip to main content


Poster

ACM-MILP: Adaptive Constraint Modification via Grouping and Selection for Hardness-Preserving MILP Instance Generation

Ziao Guo · Yang Li · Chang Liu · Wenli Ouyang · Junchi Yan


Abstract:

With the evolution of Mixed-integer linear programming (MILP) research, the significance of data has become increasingly pronounced. High-quality data is instrumental in enhancing the training of ML-based solvers and the development of classic solvers, yet the limited availability of real-world data urges the need for MILP instance generation methods. Existing MILP generation approaches primarily rely on iterating the random single-constraint modifications to augment new instances, which overlooks the inherent problem structure with constraint interrelations, leading to compromised quality and solvability of the generated instances. To this end, we propose ACM-MILP, a framework for MILP instance generation, to achieve adaptive constraint modification and constraint interrelation modeling. ACM-MILP employs an adaptive constraint selection mechanism based on probability estimation within the latent space to preserve instance characteristics. Meanwhile, it detects and groups strongly related constraints through community detection, enabling collective modifications that account for constraint dependencies. Experimental results demonstrate significant improvements in problem-solving hardness similarity under our framework. Additionally, in the downstream task, we showcase the efficacy of ACM-MILP-generated instances in hyperparameter tuning.

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