DIG-MILP: a Deep Instance Generator for Mixed-Integer Linear Programming
  with Feasibility Guarantee
Haoyu Wang Jialin Liu Xiaohan Chen Xinshang Wang Pan Li Wotao Yin
Mixed-integer linear programming (MILP) stands as a notable NP-hard problem
pivotal to numerous crucial industrial applications. The development of
effective algorithms, the tuning of solvers, and the training of machine
learning models for MILP resolution all hinge on access to extensive, diverse,
and representative data. Yet compared to the abundant naturally occurring data
in image and text realms, MILP is markedly data deficient, underscoring the
vital role of synthetic MILP generation. We present DIG-MILP, a deep generative
framework based on variational auto-encoder (VAE), adept at extracting
deep-level structural features from highly limited MILP data and producing
instances that closely mirror the target data. Notably, by leveraging the MILP
duality, DIG-MILP guarantees a correct and complete generation space as well as
ensures the boundedness and feasibility of the generated instances. Our
empirical study highlights the novelty and quality of the instances generated
by DIG-MILP through two distinct downstream tasks: (S1) Data sharing, where
solver solution times correlate highly positive between original and
DIG-MILP-generated instances, allowing data sharing for solver tuning without
publishing the original data; (S2) Data Augmentation, wherein the
DIG-MILP-generated instances bolster the generalization performance of machine
learning models tasked with resolving MILP problems.