El problema de quemar grafos es un problema de optimización combinatoria NP-duro que ayuda a cuantificar cuán vulnerable es un grafo a la contagio. Este documento presenta tres formulaciones matemáticas del problema: un programa lineal entero (ILP) y dos problemas de satisfacción de restricciones (CSP1 y CSP2). Gracias al software de optimización listo para usar, estas formulaciones pueden resolverse de manera óptima en grafos arbitrarios; esto es relevante porque los únicos algoritmos diseñados hasta la fecha para este problema son algoritmos de aproximación y heurísticas, que no garantizan encontrar soluciones óptimas. Comparamos empíricamente las formulaciones propuestas utilizando grafos aleatorios y software de optimización listo para usar. Los resultados muestran que CSP1 y CSP2 tienden a alcanzar soluciones óptimas en menos tiempo que el ILP. Por lo tanto, las ejecutamos en algunos grafos de referencia de un orden de hasta 5908. Se mejoraron las soluciones previamente conocidas para algunos de estos grafos. Sacamos algunas observaciones empíricas de los resultados experimentales. Por ejemplo, encontramos la tendencia: cuanto mayor es la solución óptima del grafo, más difícil es encontrarla. Finalmente, el conjunto resultante de soluciones óptimas podría ser útil como un conjunto de datos de referencia para la evaluación del rendimiento de algoritmos no exactos.