### Jordi Castro (Universitat Politécnica de Catalunya, Barcelona)

#### IPMs for huge MILPs? A successful approach for capacitated multiperiod facility location

*Joint work with S. Nasini and F. Saldanha-da-Gama.*

*Wednesday 18 November 2015 at 15.00, JCMB 5326*

##### Abstract

The capacitated facility location problem is a well-known MILP, which has
been efficiently solved, among others, by cutting-plane procedures. In
this work we focus on a multiperiod variant of this problem. The cutting
plane approach requires the solution of a convex non-differentiable
function Q(y), y being the binary variables. This function Q(y) is lower
approximated by cutting planes, which are obtained by solving a linear
optimization subproblem for each time period. For huge instances, the
bottleneck is the efficient solution of those subproblems. Fortunately,
the block-angular structure of the subproblems allows their efficient
solution by the specialized interior-point method implemented in the
solver BlockIP.

This approach allowed the solution of huge instances of up to three time
periods, 200 locations and one million customers, resulting in MILPs of
600 binary and 600 million continuous variables. Those MILP instances
were optimally solved by the cutting-plane-interior-point approach in
less than one hour of CPU, while state-of-the-art solvers (i.e., CPLEX)
were unable to solve them by exhausting the 144 Gigabytes of available
memory.

### 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*