Solver para problemas Room Capacitated Examination Timetabling Problem basado en Simulated Annealing

Nota: se aplicaron las correcciones al algoritmo según lo retroalimentado en Presentación de Avance 1.

• Se implementa Simulated Annealing bajo el concepto diseñado
• Se implementa el movimiento bajo el concepto diseñado
• Se corrige validación de salas según el supuesto de particularidad sala-examen según lo detectado.
• Se conservó la función de evaluación original dado que se adapta de mejor forma al objetivo principal (minimización de bloques ocupados)

Instrucciones de compilación

Para compilar de forma automática utilice el comando make en su consola, dentro del directorio donde se encuentra el código fuente.

Para limpiar los archivos de compilación utilice el comando make clean en el directorio donde se encuentra el código fuente.

Para compilar manualmente utilice:

g++ main.cpp -o test -Wall

Instrucciones de ejecución

El programa recibe múltiples flags, estas corresponden a:

-s: Seed a utilizar, numero entero simple que se utilizará como semilla en la ejecución

-m: Número entero de cantidad de iteraciones máxima que debe realizar el algoritmo, una vez que se llegue a esa cantidad de iteraciones, el algoritmo finaliza y exporta resultados, se recomienda usar 650 para replicar las pruebas realizadas

-e: Número entero de cantidad de iteraciones que define cada cuanto se aplicará el enfriamiento al algoritmo, una cantidad menor implica reduccion de temperatura de forma mas frecuente, cantidad mayor mantiene la misma temperatura por períodos alargados. Se recomienda usar 8 o 16 para replicar las pruebas realizadas

-t: Double, decimal que indica la temperatura inicial que se desea utilizar en la ejecucion, se recomienda utilizar 100 para replicar las pruebas realizadas

-a: Double, decimal entre 0 y 1 que indica la reducción de temperatura que se desea aplicar en el esquema de enfriamiento T*Alpha, números más cercanos a 1 implican reducción más paulatina, números más cercanos a 0 implican reducción drástica. Se recomienda entre 0.8 a 0.99

-f: String de ruta al archivo de instancias que se desea ocupar, procurar que sea accesible por el programa. Se recomienda utilizar la carpeta "Instancias" incluida en el proyecto

-d: flag opcional que permite activar el modo debug o verbose, imprime toda la información acerca de la ejecución del algoritmo que se haya configurado en el archivo main.cpp. NO RECOMENDADA DADO QUE DIFICULTA LA LECTURA DE LOS DATOS DE SALIDA O SEGUIR EL FLUJO DEL ALGORITMO, UTILIZAR SOLO EN CASO DE QUE MODIFIQUE EL CODIGO Y DESEE PROBAR NUEVAS FUNCIONALIDADES O MODIFICACIONES

Para ejecutar con outputs normales:

./test -s seed_a_usar -m max_iteraciones -e iteraciones_enfriamiento -t temp -a alpha -f ruta_archivo

Ejemplo: ./test -s 28633115 -m 100 -e 8 -t 100 -a 0.8 -f Instancias/i1.in

(seed 28633115, 100 iteraciones maximas, aplicar enfriamiento cada 8 iteraciones, 100 grados de temperatura inicial, 0.8 como ponderacion Alpha, usar archivo de instancia 1)

Para ejecutar con outputs para revisión de comportamiento:

./test -s seed_a_usar -m max_iteraciones -e iteraciones_enfriamiento -t temp -a alpha -f ruta_archivo -d

Ejemplo: ./test -s 28633115 -m 100 -e 8 -t 100 -a 0.8 -f Instancias/i1.in -d

Se incluye un archivo bash que permite ejecutar el set de pruebas utilizado en los experimentos, el cual fija las iteraciones maximas en 650, utiliza las 5 seeds detalladas en el artículo, utiliza la temperatura recomendada a 100 grados y ejecuta el set de pruebas usando el conjunto de Alpha 0.8 y 0.99 y el conjunto de iteraciones de enfriamiento 8 y 16.

Para ejecutar el set de pruebas utilice:

bash ./tests.sh ruta_instancia

Ejemplo: bash ./tests.sh Instancias/i7.in