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