A. Jiménez-Cordero, J. M. Morales González, S. Pineda Morente
Mixed Integer Linear Programs (MILP) are well known to be NP-hard problems. Although pure optimization-based methods, such as constraint generation (CG), guarantee to provide an optimal solution if enough time is given, their use in online applications is still a great challenge. To alleviate it, some machine learning (ML) tools 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 solutions.
By linking mathematical optimization and ML, this talk proposes an approach that speeds up the traditional CG method, preserving feasibility and optimality guarantees. Particularly, we warm-start the CG algorithm with an invariant constraint set. This way, the computational burden to solve online each MILP problem is significantly diminished. The performance of the proposed approach is quantified through synthetic and real-life MILP applications.
Keywords: Mixed integer linear programming, machine learning, constraint generation, warm-start, feasibility and optimality guarantees
Scheduled
GT04 Multivariate Analysis and Classification V. Mathematical Optimization and Data Science
June 8, 2022 12:40 PM
Cloister room
