Para el método de ramificación y corte, es esencial conocer muchas facetas de los politopos generados por el problema. Sin embargo, actualmente es uno de los problemas más difíciles calcular todas las facetas de dichos politopos a medida que crecen rápidamente.
Para un problema de optimización arbitrario, el politopo utilizado por los métodos de ramificación y corte o también por métodos de plano de corte es el casco convexo de todos los vértices factibles. Un vértice es una asignación de todas las variables del modelo. Como ejemplo (muy simple): si uno maximizara st y entonces los vértices , y son vértices factibles. viola la desigualdad y, por lo tanto, no es factible. El problema de optimización (combinatoria) sería elegir entre los vértices factibles. (En este caso, obviamentees lo óptimo). El casco convexo de estos vértices es el triángulo con exactamente estos tres vértices. Las facetas de este politopo simple son , y . Tenga en cuenta que la descripción a través de las facetas es más precisa que el modelo. En la mayoría de los problemas difíciles, como el TSP, el número de facetas supera el número de desigualdades del modelo en varios órdenes de magnitud.
Teniendo en cuenta el problema del vendedor ambulante, para qué número de nodos se conoce completamente el politopo y cuántas facetas hay. si no está completo, ¿cuáles son los límites inferiores en el número de facetas?
Estoy particularmente interesado en la denominada formulación del camino hamiltoniano del TSP:
Si tiene información sobre los politopos de otras formulaciones del TSP, siéntase libre de compartirla también.
Respuestas:
Para límites asintóticos, Fiorini, Massar, Pokutta, Tiwari y de Wolf mostraron recientemente límites inferiores exponenciales en el número de facetas de cualquier politopo que se proyecta al politopo TSP (el politopo TSP, que es el casco convexo de soluciones TSP factibles). Esto es más fuerte de lo que pides e implica que incluso agregar variables adicionales no hará que el politopo TSP sea representable de manera eficiente.
Su artículo es un seguimiento del clásico de 1988 de Yannakakis, quien mostró el mismo resultado pero solo para politopos que satisfacen una cierta condición de simetría.
fuente
Hay una biblioteca llamada SMAPO (abreviatura de biblioteca de descripciones lineales de pequeñas instancias de problemas de POlytopes en optimización combinatoria) para muchos politopos incluyendo TVP simétrico y TSP gráfico.
Para el STSP, esta es la lista de la cantidad de facetas para politopos pequeños
fuente