Linear extended formulations: packing, covering, and restricted SoS

The performance of state-of-the-art solvers in optimization is very sensi-tive to the way a problem is formulated. Even for instances of small size,formulations that have too many constraints or that are weak can enormouslyincrease the computational e -ort needed to obtain an optimal, or even a fea-sible, solution. Developing techniques to obtain strong formulations that usefew constraints has therefore been a main research goal in optimization. Thischallenge has intensi?ed in the last years, as new technologies allowed thecollection and storage of a much larger quantity of data, which propelled thedevelopment of optimization problems that are more complex and larger insize.Extended Formulations have emerged as a fundamental paradigm to ob-tain competitive formulations. The main idea of this approach lies in the factthat a formulation can often be represented more succinctly as the projectionof a convex set lying in a higher dimensional space. This leads to a reductionin the number of constraints needed to describe the formulation, which inrelevant cases can go from exponential to polynomial in the dimension of theproblem.The goal of this proposal is to provide new fundamental results for con-structing and improving linear extended formulations, and use those resultsto computationally solve integer optimization problems arising for instancein resource allocation, production planning, and scheduling.We will achieve this by developing and using tools from di -erent areas oftheoretical and applied mathematics, like polyhedral combinatorics, commu-nication protocols, and algebraic geometry. E -ectiveness of our techniqueswill be tested on notoriously hard optimization problems.