Sergio García Quilles (University of Edinburgh)

Solving large p-median models using a radius formulation
Wednesday 20 November 2013 at 15.30, JCMB 6206

Abstract

One of the most classical problems in Discrete Location is the p-median problem. It consists in, given a finite set of points, decide where to locate a fixed number p of facilities (the medians) and how to allocate the non-median points to the median nodes in such a way that total cost (usually distance) be minimum. It is a problem with many applications: clustering, emergency services, image processing, political districting, etc. However, it is difficult to solve large instances in an efficient way due to the fact that the classical formulation has a quadratic number of variables and constraints. Recently, it has been developed an alternative formulation called radius formulation that allows to solve much larger instances very efficiently. This formulation and the algorithm used to solve it will be detailed in the first part of the talk. In the second part, it will be shown that a similar idea can be used to solve a problem of clustering with feature selection, problem that can be seen as "double p-median" problem.

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