Proyecto del curso de Diseño de Algoritmos II de la Universidad Simón Bolívar.

• Cristian Medina 10-10445
• Manuel Pacheco 10-10524

El proyecto es un estudio del resultado de la aplicación de metaheurísticas de búsqueda local, trayectoria y poblacionales para la resolución del problema MDP descrito en optsicom.es a través de la implementación de las metaheurísticas en el lenguaje C++.

Se utilizan instancias de los sets SOM-b, GKD-c, MDG-b y MDG-c, clasificados por nosotroms como problemas small, medium and large. Estos se encuentran comprimidos en la carpeta testcases y pueden ser descomprimidos usando make extract-cases, y eliminados usando make clean-cases.

Para obtener el proyecto, puede utilizarse la interfaz de GitHub o bajo el comando

git clone https://github.com/ShadowManu/CI5652_MDP.git

El proyecto utiliza el buildsystem cmake bajo un wrapper make. Una vez obtenido, el proyecto puede construirse con make build o simplemente make

El ejecutable resultante estará ubicado en la misma carpeta con el nombre mdp.

El programa espera 4 argumentos:

• Nombre de archivo
• Estrategia de solución inicial
• Metaheurística a utilizar
• Random seed (opcional)

Ejemplo:

./mdp GKD-c_1_n500_m50.txt random localsearch 3467981

El programa da 3 resultados en orden:

• Solución inicial
• Solución final
• Tiempo de ejecución

Alternativamente, el proyecto posee un script en Ruby donde se pueden correr carpetas de archivos con un número de corridas deseado.

./ruby runner.rb ./testcases/small greedy localsearch 15