Extended formulations in combinatorial optimization

This survey is concerned with the size of formulations for combinatorial optimization problems. Natural formulations often have a number of constraints that is exponential in the size of the data needed to describe the problem. Here we are particularly inter-ested in situations where the addition of a polynomial number of extra variables allows a formulation with a polynomial number of constraints