  Mixed Integer Linear Programs (MILP) are well known to be NP-hard
(Non-deterministic Polynomial-time hard) problems in general. Even though pure
optimization-based methods, such as constraint generation, are guaranteed to
provide an optimal solution if enough time is given, their use in online
applications remains a great challenge due to their usual excessive time
requirements. To alleviate their computational burden, some machine learning
techniques (ML) have been proposed in the literature, using the information
provided by previously solved MILP instances. Unfortunately, these techniques
report a non-negligible percentage of infeasible or suboptimal instances.
  By linking mathematical optimization and machine learning, this paper
proposes a novel approach that speeds up the traditional constraint generation
method, preserving feasibility and optimality guarantees. In particular, we
first identify offline the so-called invariant constraint set of past MILP
instances. We then train (also offline) a machine learning method to learn an
invariant constraint set as a function of the problem parameters of each
instance. Next, we predict online an invariant constraint set of the new unseen
MILP application and use it to initialize the constraint generation method.
This warm-started strategy significantly reduces the number of iterations to
reach optimality, and therefore, the computational burden to solve online each
MILP problem is significantly reduced. Very importantly, all the feasibility
and optimality theoretical guarantees of the traditional constraint generation
method are inherited by our proposed methodology. The computational performance
of the proposed approach is quantified through synthetic and real-life MILP
applications.
