The p-median on disconnected graphs
 
 
Description:  The <i>p</i>-median problem is a well-known NP-hard combinatorial optimization problem that seeks for the location of p facilities on the vertices (customers) of a graph G to minimize the sum of transportation costs for satisfying the demands of the customers from the facilities.

In many real applications graph <i>G</i> is disconnected. That is the case of p-median problem defined over split administrative regions or regions geographically apart (e.g. archipelagos), and the case of problems coming from industry such as the optimal diversity management problem (ODMP).

In this talk I will show how to solve the p-median problem working on each connected component of <i>G</i> separately. This is special relevant when dealing with huge graphs, which is usually the case of the instances of ODMP (e.g. for the production of wire harness for the automotive industry).

Joint work with Agostinho Agra and Cristina Requejo

Date:  2016-11-09
Start Time:   14:30
Speaker:  Jorge Orestes Cerdeira (Univ. Nova de Lisboa)
Institution:  Faculdade de Ciências e Tecnologia, Universidade NOVA de Lisboa
Research Groups: -Numerical Analysis and Optimization
See more:   <Main>  
 
© Centre for Mathematics, University of Coimbra, funded by
Science and Technology Foundation
Powered by: rdOnWeb v1.4 | technical support