Background
Many real-life problems can be formulated and solved with Mixed Integer Linear Programming (MILP), a powerful mathematical tool to describe the goal and the constraints of a problem through linear inequalities. A problem can be formulated with many alternative MILP models, some of which are more efficient than others in providing the optimal solution. The goal of this project is to develop techniques that analyze a MILP model and automatically transform it into an equivalent model that from a computational point of view is easier to solve, if possible. This project will build upon the expertise of researchers from DTU Management Engineering as well as a research teams in Germany and France that are working towards the same goal. MOSEK, a Danish company that is one of the leading providers of solvers for mathematical optimization problems, will also be part of the project. In the long term MOSEK will explore the possibilities to embed the research outcomes of this project in their products.
Research problem and questions
In general, application of Lagrangian decomposition to a specific MILP requires expert knowledge and the decomposition often has to be implemented from scratch. This makes it infeasible for use in commercial solvers, which could otherwise benefit from it. AutoDec will therefore specifically address the following:
- Given a MILP, how can one automatically detect whether Lagrangian decomposition will be beneficial?
- How can the specifications of how to apply Lagrangian decomposition to said MILP be generated automatically?
Method
First we want to build our knowledge about Lagrangian decomposition; by looking in the literature, what problems has the method been applied to so far and what were the results; and by applying the method to problems it has not yet been applied to. To answer the two research questions we will implement a number of different techniques, machine learning, hypergraph partitioning, and more. Quantitative analysis will be used to test the performance of these on a number of problems.
Expected Results
An implementation of an algorithm which given a MILP will determine whether to use Lagrangian decomposition and if so, how. If successful, this algorithm would allow non-experts to apply Lagrangian decomposition to some problem and could also be used by experts, who wants to know whether Langragian decomposition could work well for some problem before they implement a more specialized version of the method. Eventually, the algorithm could be added to a commercial solver, to allow the solver to use Lagrangian decomposition where it could be beneficial.