CORAL Seminar: Quentin Louveaux, Université de Liège, Belgium

Title: Using machine learning to improve branching decisions and possible parallelization in the branch-and-bound algorithm

Info about event


Monday 30 October 2017,  at 14:30 - 15:30


Fuglesangs Allé 4, 8210 Aarhus V, building 2621(B), room 122


Marcel Turkensteen

Presenter: Quentin Louveaux, Université de Liège, Belgium 

Title: Using machine learning to improve branching decisions and possible parallelization in the branch-and-bound algorithm (Joint work with Alejandro Marcos Alvarez and Louis Wehenkel)

Abstract: In this work, we show connections that exist between machine learning and mathematical optimization. Broadly speaking, mathematical optimization consists in minimizing or maximizing a function by assigning appropriate values to its input variables while satisfying a set of inequalities and equalities. Machine learning however is a discipline that studies algorithms that can learn from data and subsequently use the acquired knowledge in one way or another. Machine learning is nowadays very widely used in applications where a lot of data is available, and where decisions using the available data have to be made either repeatedly, quickly, or very accurately.
    Although these fields are usually studied separately, there exist clear relationships between them. The clearest relationship is unidirectional: (continuous) optimization is very often used as a tool to solve machine learning problems. As such, optimization is seen as a component of machine learning approaches. On the contrary, the other relationship, the one in the opposite direction, is too rarely acknowledged and leveraged. In this work, we explicitly study the latter link by using machine learning techniques as a component of optimization algorithms.
    To explain why machine learning can be used to improve optimization algorithms, we can observe that most optimization algorithms have, at some point, to take decisions during the course of the solution procedure. These decisions may be theoretically justified, but may be arbitrary as well. More specifically, we consider the branch-and-bound algorithm, which is a standard algorithm to solve mixed-integer optimization problems. With respect to the algorithm, we consider two important decisions that need to be taken, sometimes arbitrarily: the branching variable decision and a possible initial splitting into subproblems. We show how we can use machine learning in order to handle these issues.

Organizer: Marcel Turkensteen, CORAL