How many integer variables do we need?; Prof. Dr. Stefan Weltge (TU München)

ABSTRACT: The number of integer variables in a mixed-integer linear program is regarded as an important measure for its algorithmic complexity. However, very little is known about what can be expressed by a compact mixed-integer program with few integer variables. For instance, how many integer variables are needed to formulate classic problems such as MATCHING or TSP as a polynomial-size mixed-integer program? I will talk about recent joint work with Alfonso Cevallos and Rico Zenklusen (ETH Zurich), in which we provide almost tight answers to such questions for a variety of classic combinatorial optimization problems. In this work, we developed a framework for lifting existing inapproximability results for extended formulations to the setting of mixed-integer extended formulations. Our results build upon a new decomposition technique that, for any convex set C, allows for approximating any mixed-integer description of C by the intersection of C with the union of a small number of affine subspaces.