Next generation extended formulations

• Applicant: Professor Dr. Stefan Weltge
• Subject Area: Mathematics
• Term: from 2020 to 2024
• Project identifier: Deutsche Forschungsgemeinschaft (DFG) - Project number 451026932

Extended formulations describe a technique to formulate mathematical problems in discrete optimization in a very compact way. Such descriptions are necessary when dealing with modern software tools to solve such problems efficiently. The underlying theory was greatly developed in recent years, which led to several exciting results at the interface of discrete optimization and theoretical computer science. These developments have changed our understanding of formulating mathematical optimization problems, and produced new powerful tools as well as connections to other areas.The goal of this project is to push the field to a second phase in which we tackle intriguing open questions from different perspectives, develop new applications of the concept itself, and exploit recent connections to other areas such as circuit complexity and topology. While most results of the first phase were still concerned with purely linear extended formulations, we also aim to extend existing theory to the more general setting of mixed-integer formulations whose practical relevance is even higher.

• DFG Programme: Research Grants