### François Glineur (Université Catholique de Louvain)

#### Computing lower and upper bounds on the extension complexity of polytopes

*Joint work with Julien Dewez (UCL) and Nicolas Gillis and Arnaud Vandaele (University of Mons).*

*Wednesday 20 May 2015 at 15.00, JCMB 6206*

##### Abstract

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.

### Seminars by year

*Current*
*2016*
*2015*
*2014*
*2013*
*2012*
*2011*
*2010*
*2009*
*2008*
*2007*
*2006*
*2005*
*2004*
*2003*
*2002*
*2001*
*2000*
*1999*
*1998*
*1997*
*1996*