Groupe d’études et de recherche en analyse des décisions

Learning a classification of mixed-integer quadratic programming problems

Giulia Zarpellon Polytechnique Montréal, Canada

Within state-of-the-art optimization solvers such as IBM-CPLEX the ability to solve both convex and nonconvex Mixed-Integer Quadratic Programming (MIQP) problems to proven optimality goes back few years, but still presents unclear aspects. We are interested in understanding whether for solving an MIQP problem it is favorable to linearize its quadratic part or not. Our approach employs Machine Learning techniques to learn a classifier that predicts, for a given MIQP instance, the most suitable resolution method within IBM-CPLEX's algorithmic framework. We aim as well at gaining methodological insights about the instances' features leading this discrimination. Together with a new generated dataset, we examine part of CPLEX internal testbed and discuss different learning scenarios to integrate learning and optimization processes. By defining novel measures, we interpret learning results and evaluate the quality of the tested classifiers from the optimization point of view.

(Joint work with Pierre Bonami and Andrea Lodi)

Du café et des biscuits seront offerts au début du séminaire.
Bienvenue à tous!