The computational effort required to solve a linear optimization problem very often depends on the number of facets of the corresponding polytope. However, in many situations, this polytope can be expressed as the projection of a higher-dimensional polytope, leading to a so-called extended formulation for the original problem, which can then be solved more efficiently.
We are interested in computationally identifying such extended formulations, and in particular in finding one with the smallest possible number of facets. That minimum number of facets is called the extension complexity of the polytope.
This quantity is closely related to the concept of nonnegative rank, which is the minimum number of nonnegative rank-one matrices whose sum is equal to a given matrix. More precisely, the extension complexity of a polytope is equal to the nonnegative rank of the slack matrix computed from this polytope, and the decomposition of this slack matrix into rank-one terms provides an explicit description of the extended formulation.
Unfortunately, computing the nonnegative rank is NP-hard in general. In this talk, we will present recent progress in computing bounds on this quantity. First, we will survey existing lower bounds on this quantity, including one that only depends on the geometry of the polytope. Then, we will show how local optimization algorithms can be used as heuristics to provide good upper bounds on the extension complexity, and report on their efficiency on a set of concrete polytopes.
Current 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996
