MINOA: Mixed-Integer Non-Linear Optimisation: Algorithms and Applications

MINOA is funded under the  H2020-MSCA-ITN program 

Abstract
Building upon the achievements of the Marie-Curie ITN Mixed-Integer Non-Linear Optimization (MINO) (2012 – 2016), the goal of the Mixed-Integer Non-Linear Optimisation Applications (MINOA) proposal is to train the next generation of highly qualified researchers and managers in applied mathematics, operations research and computer science that are able to face the modern imperative challenges of European and international relevance in areas such as energy, logistics, engineering, natural sciences, and data analytics. Twelve Early-Stage Researchers (ESRs) will be trained through an innovative training programme based on individual research projects motivated by these applications that due to their high complexity will stimulate new developments in the field. The mathematical challenges can neither be met by using a single optimisation method alone, nor isolated by single academic partners. Instead, MINOA aims at building bridges between different mathematical methodologies and at creating novel and effective algorithmic enhancements. As special challenges, the ESRs will work on dynamic aspects and optimisation in real time, optimisation under uncertainty, multilevel optimization and non-commutativity in quantum computing. The ESRs will devise new effective algorithms and computer implementations. They will validate their methods for the applications with respect to metrics that they will define. All ESRs will derive recommendations, both for optimised MINO applications and for the effectiveness of the novel methodologies. These ESRs belong to a new generation of highly-skilled researchers that will strengthen Europe’e human capital base in R&I in the fast growing field of mathematical optimisation. The ESR projects will be pursued in joint supervision between experienced practitioners from leading European industries and leading optimisation experts, covering a wide range of scientific fields (from mathematics to quantum computing and real-world applications).

MINOA@IASI subproject:

Exact methods for non-linear optimisation problems on graphs

Objectives: The goal is to advance the state-of-the-art in the solutions of graph problems related to cliques, cycles, and cuts optimisation with nonlinear functions. One such problem is the max-cut problem that is equivalent to the general Quadratic Unconstrained Binary Optimisation (QUBO). These problems have recently received a renewed great attention as they are the typical target of computing devises based on quantum techniques. State-of-the-art algorithms able to provide solutions with certified qualities also for very large sparse instances are based on low-rank reformulations of semidefinite relaxations. On the other hand, separation procedures have been proposed that make it possible to exploit the linear relaxations to possibly obtain exact optima. The research will focus on combining these techniques to improve the solution times of the existing algorithms and to extend their scope to problems (e.g., Max-Sat), where the objective function is a polynomial of degree greater than two. Another case is the optimisation of a nonlinear function over cycles. This is a generalization of the separation problem of cycle inequalities for max-cut. The contribution to the objective function will depend on the membership of an edge to a cycle and to a particular subset of the cycle. This problem arises in the distribution of power energy to solve the optimal transmission switching (OTS) problem. A subproblem of OTS is Unit Commitment (UC) that is usually disregarded or considered as a separate problem. The connections between the two problems will also be taken into account. In particular, UC is a Mixed-Integer Nonlinear Problem with convex function and semicontinuous variables. Improvements in the solution of this class of problems will be investigated to obtain global advances. Other graph optimisation problems are related to clique optimisation, in particular the identification of subcliques partitioning the graph and defining clusters. This has application in the study of Big Data graphs and in data protection.
Expected Results: Theoretical results about non-linear optimisation problems on graphs with convex as well as non-convex functions, applications in power energy, data science, statistical physics, quantum computing.
Planned secondment(s): Siemens, CNRS
Supervisors: Claudio Gentile (CNR-IASI), Giovanni Rinaldi (CNR-IASI)
Mentor: Paolo Ventura (CNR-IASI), Claudia D’Ambrosio (CNRS-LIX)
Associated Partner: Sapienza University Rome, PhD Program ABRO