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 2019 2018 2017 2016 2015 2014 2013 2012 2011 2010 2009 2008 2007 2006 2005 2004 2003 2002 2001 2000 1999 1998 1997 1996