En la intersección de la algoritmia y la modelización
Un problema de un millón de dólares: ¿encontrar una solución es tan fácil como verificarla? Escrito en la forma « P = NP ?», este problema por ahora sigue sin resolver. Así, demostrar que un horario cumple las restricciones impuestas es fácil, pero ¿encontrar uno que sirva? Si hay que enumerarlos uno por uno para probarlos, corremos el riesgo de pasar un tiempo más largo que la edad del sol, mientras que nos gustaría tener la solución en cinco minutos o en veinticuatro horas. Primero se busca identificar los problemas que sabemos resolver rápidamente. Para los demás, se utilizarán si es posible búsquedas arborescentes inteligentes, algoritmos exactos eficientes de tipo recorrido combinatorio, o métodos aproximados (metaheurísticas).
Todos los artículos de este dossier
Programación lineal con números enteros | Tangente
Para resolver problemas de optimización, puede ser necesario plantearlos mediante modelos matemáticos. La programación lineal con números enteros permite hacerlo utilizando únicamente polinomios de primer grado cuyas variables deben tomar valores enteros.
¿P es igual a NP?
La cuestión mantiene en vilo a la comunidad científica desde hace ya más de cuarenta años. Forma parte de los «problemas del milenio», una lista de siete grandes enigmas matemáticos planteados por el Instituto Clay de Matemáticas en 2000. Aclaremos la cuestión.
Metaheurísticas: optimización aproximada | Tangente
Problemas NP-difíciles, explosión combinatoria, modelos con millones de variables y un número exponencial de inecuaciones… ¿Qué hacer cuando ningún método de optimización funciona? ¿Qué método utilizar cuando se quiere obtener rápidamente una solución a un problema?
Recorridos combinatorios: caminos más cortos | Tangente
Cuando decidimos el camino sobre la marcha, debemos elegir, como en un laberinto, entre varias vías. Y la pregunta vuelve a plantearse en cada nueva bifurcación, lo que provoca una explosión combinatoria de los caminos posibles. ¿Cómo sortear esta explosión?
Búsqueda en árbol
Optimizar el uso de un telescopio para saber qué parte del cielo observar es fundamental. Un desafío así, que puede reducirse a un problema de coloración, exige pruebas que ni siquiera un ordenador moderno tiene tiempo de realizar de manera exhaustiva.