Relajación Lagrangeana para el problema de particionamiento en datos geográficos
|
 |
|
Post a Comment
|
|
|
|
|
CONTRIBUTORS:
|
|
|
CONFERENCE NAME:
|
|
|
CONF. LOCATION:
|
San José, Costa Rica
|
|
CONFERENCE YEAR:
|
2012
|
|
PUB TYPE:
|
Conference Presentation
|
|
SUBJECT(S):
|
Operations Research, Lagrangean Relaxation, Geographic Partitioning
|
|
DISCIPLINE:
|
Mathematics
|
|
HTTP:
|
http://www.cimpa.ucr.ac.cr/simmac/SIMMAC.pdf
|
|
LANGUAGE:
|
Spanish
|
|
PUB ID:
|
103-505-232
(Last edited on
2012/08/09 10:28:27 GMT-6)
|
|
SPONSOR(S):
|
|
|
ABSTRACT:
Entre los algoritmos de agrupamiento de mayor utilidad en la agregación territorial, destacan los algoritmos de particionamiento, que buscan encontrar un conjunto de representantes de los datos a clasificar cuando se conoce el número de clases a priori. En este trabajo hemos escogido dos métodos de particionamiento bien conocidos en la literatura: p-mediana y PAM (Particionamiento Alrededor de los Medoides). Estos algoritmos se han utilizado para agrupar datos espaciales denominados Áreas Geoestadísticas Básicas (AGEBS). Se ha comprobado la eficiencia de los métodos para agrupar 469 AGEBS con diferentes valores para el número de clases, demostrando su capacidad para obtener una solución óptima con un esfuerzo computacional razonable. Por otra parte, se realizan pruebas para una instancia con 5087 AGEBS con diferentes valores para el número de clases. Dado que se asume elevada complejidad computacional para esta cantidad de datos, se utilizó para este propósito un algoritmo de particionamiento con un hibrido de recocido simulado y búsqueda por entorno variable. Para su resolución se ejecutan una serie de pruebas experimentales donde se registran los resultados logrados. Finalmente se estiman las cotas inferiores para el problema que nos ocupa mediante un esquema de relajación Lagrangeana donde se dualizan las restricciones de asignación obteniendo mejores resultados que con él método heurístico implementado. Asimismo, en cada iteración del algoritmo de optimización sub-gradiente, utilizado para resolver el dual Lagrangeano, se usa un procedimiento para obtener cotas superiores del problema.
De acuerdo con los resultados obtenidos para esta instancia, se observa que se pueden obtener soluciones factibles de muy buena calidad con un esfuerzo computacional razonable.
|
|
|
|
STATISTICS
|
|
Click on # to view
|
|
Citations
|
|
0
|
|
References
|
|
0
|
|
Comments
|
|
0
|
|
Quality
|
|
0/0.00
|
|
Interest
|
|
0/0.00
|
|
View(er)s
|
|
1/76
|
|
|
|
|
|
|
| Prev |
Next |
|