Generando interesantes problemas de optimización combinatoria

Estoy impartiendo un curso sobre metaheurística y necesito generar instancias interesantes de problemas combinatorios clásicos para el término proyecto. Centrémonos en TSP. Estamos abordando gráficos de dimensión y mayores. Por supuesto, intenté generar un gráfico con una matriz de costos con valores tomados de una aleatoria , y descubrí que (como se esperaba) el histograma para el costo de la ruta (dibujado al muestrear muchas rutas aleatorias) tiene una distribución normal muy estrecha ( es pero es alrededor de ). Esto significa, en mi opinión, que el problema es muy fácil, ya que la mayoría de las rutas aleatorias estarán por debajo del promedio, y la ruta de costo mínimo está muy cerca de una ruta aleatoria.$200$$U(0,1)$$\mu$$~100$$\sigma$$4$

Así que probé el siguiente enfoque: después de generar la matriz $U(0,1)$ , realice una caminata aleatoria larga alrededor del gráfico y aleatoriamente (Bernoulli con $p=0.5$ ) duplique o reduzca a la mitad el valor del borde. Esto tiende a reducir todos los valores, llegando finalmente a cero, pero si sigo el número correcto de pasos, puedo obtener una distribución con $\mu$ alrededor de $2$ y $\sigma$ alrededor de $1$ .

Mi pregunta es, primero, ¿es esta incluso una buena definición para un problema interesante ? Idealmente, me gustaría una instancia que sea altamente multimodal (para las funciones de vecindario más comunes), y que tenga muy pocas rutas cerca del valor mínimo, de modo que la mayoría de las soluciones aleatorias estén muy lejos de lo óptimo. La segunda pregunta es, dada esta descripción, ¿cómo puedo generar instancias con tales características?

Un enfoque general para generar instancias más difíciles es el siguiente:

• Comience con una instancia de problema aleatorio.
• Incruste una "puerta trasera oculta": elija aleatoriamente una buena solución (una que probablemente sea mucho mejor que cualquier solución que ya exista) y modifique la instancia del problema para incorporarla por la fuerza en la instancia del problema.

Por ejemplo, para TSP, podría hacer algo como lo siguiente. Genere una instancia de problema aleatoria eligiendo una matriz de costos aleatoria . Luego, ajuste la instancia del problema para ocultar una solución mucho mejor: seleccione aleatoriamente un recorrido que visite cada vértice exactamente una vez y reduzca los pesos de borde en ese recorrido (por ejemplo, generarlo aleatoriamente desde donde ; reducir el peso existente; o modificar el borde existente con alguna probabilidad fija). Este procedimiento de ajuste asegura que la solución óptima será, con alta probabilidad, ese recorrido especial que seleccionó. Si tiene suerte y selecciona una inserción razonable, tampoco será tan fácil reconocer dónde escondió la solución especial.$U(0,1)$$U(0,c)$$c<1$

Este enfoque se deriva de ideas generales en criptografía, donde queremos crear problemas unidireccionales de trampillas: donde el problema es difícil de resolver sin el conocimiento de la trampilla secreta, pero con el conocimiento de la trampilla secreta, el problema se vuelve muy fácil. Ha habido muchos intentos de integrar trampillas secretas en una variedad de problemas difíciles (mientras se conserva la dureza del problema incluso después de que se haya agregado la trampilla), con diversos grados de éxito. Pero este enfoque general parece que podría funcionar, para sus propósitos.

Las instancias de problemas resultantes pueden ser difíciles , pero ¿serán interesantes desde una perspectiva práctica? No lo sé. Me gana Me parecen bastante artificiales, pero ¿qué sé?

Si su objetivo principal es seleccionar instancias problemáticas que sean prácticamente relevantes y representativas de las aplicaciones de TSP en el mundo real, mi sugerencia sería adoptar un enfoque totalmente diferente. En su lugar, comience examinando las aplicaciones de TSP en el mundo real, luego busque instancias representativas de esos problemas y conviértalas en su instancia de problema TSP correspondiente, de modo que esté trabajando con instancias de problemas derivadas de un problema del mundo real.

Un enfoque que a menudo le brinda un alto control sobre la naturaleza de las soluciones es la conversión de un problema completo de NP a otro. ahora define "interesante" en su pregunta de manera estadística, pero otro enfoque ordenado es utilizar problemas clásicos del campo. mi favorito es factoring / SAT. es trivial encontrar números "suaves" con muchos factores o números primos con solo dos "factores" (uno y el primo). cree la instancia de SAT para resolver la factorización, y las soluciones son los factores (en realidad, permutaciones de factores, pero también que no es difícil contar con anticipación).

Según este enfoque, existe una definición natural de "interesante": instancias duras que no se pueden resolver en tiempo P. y se garantiza que este enfoque producirá instancias difíciles para factorizar números no uniformes, de lo contrario resolvería una pregunta abierta en teoría de complejidad, es decir, la dureza de la factorización .

entonces, posiblemente convierta a su problema, en este caso TSP. para completar esta respuesta, sería bueno tener una conversión directa de SAT a TSP, creo que están ahí, pero no estoy familiarizado con ellos. sin embargo, aquí hay algunas referencias sobre factoring-to-SAT en esta pregunta: reducir el problema de factorización de enteros a un problema NP completo

Si no le gusta la factorización, podría ser preferible crear las instancias en SAT primero por una variedad de razones. puede comenzar con instancias SAT aleatorias ajustadas para centrarse en el punto de transición fácil-difícil-fácil, etc. o podría trabajar desde instancias difíciles de DIMACS , generadas por la comunidad. o crear otros "programas" lógicos en SAT.