Generando interesantes problemas de optimización combinatoria

9

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.200U(0 0,1)μ 100σ4 4

Así que probé el siguiente enfoque: después de generar la matriz U(0 0,1) , realice una caminata aleatoria larga alrededor del gráfico y aleatoriamente (Bernoulli con pags=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 μ alrededor de 2 y σ 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?

Alejandro Piad
fuente
3
¿Buscar bibliotecas de puntos de referencia de TSP, como se estudió en OR (por ejemplo, buscar trabajos en TSP por Applegate et al., Por ejemplo, aquí )?
Neal Young
2
Existe el TSPLIB con muchas instancias.
adrianN
Gracias, verifiqué el enlace y es útil, pero mi pregunta es sobre la generación de instancias no porque quiera resolver una instancia específica, sino porque busco una idea de lo que hace buenos problemas combinatorios, una idea que luego puede extenderse a Otros problemas además de TSP.
Alejandro Piad
publicación relacionada: cstheory.stackexchange.com/questions/739/…
Neal Young
1
@Alejandro, El problema de la camarilla oculta podría ser un ejemplo de lo que estás buscando. Además, puede buscar investigaciones sobre qué instancias aleatorias de satisfacción se consideran difíciles.
Neal Young

Respuestas:

6

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 0,1)U(0 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.

DW
fuente
Me gusta mucho este enfoque, de hecho, está muy cerca de lo que estaba tratando de idear, y parece bastante adaptable a diferentes problemas. Mi motivación inicial fue hacer problemas de prueba para los estudiantes, por lo que, aunque entiendo los problemas de las palabras reales, me sirve para esta situación bastante artificial (tratar de calificar los algoritmos de los estudiantes). En cualquier caso, trataré de adaptarlo también a mis necesidades de investigación, pero eso necesitará una mirada más cercana, como usted dice, para determinar si las instancias creadas de esta manera son lo suficientemente representativas. Muchas gracias, obtuviste mi +1 y mi aceptación.
Alejandro Piad
3

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.

vzn
fuente
1
Me gusta el enfoque de conversión, aunque no proporciona más enlaces específicamente relacionados con TSP, pero de todos modos gracias por la idea, lo exploraré más a fondo. Tienes mi +1.
Alejandro Piad
1
@alejandro thx ok heres un enlace sobre eso. vea, por ejemplo, comenzando en la diapositiva 28 aquí [¡clase de pregrado!], CMSC 451: SAT, coloración, Hamiltonian Cycle, TSP Diapositivas Por: Carl Kingsford . convertir SAT → ciclo hamiltoniano (TSP). puede haber enfoques de conversión más eficientes (menos gastos generales) o con otros aspectos personalizados en la literatura si eso es lo que se desea. espero escuchar más sobre su trabajo, tal vez responda aquí o en mi blog si lo desea
vzn
1
Revisé el pdf, de muy alto nivel pero lo suficientemente comprensible. Aunque por el momento obtuve lo que necesito con la respuesta @DW, su enfoque me parece muy interesante. Tendré que intentarlo por mi cuenta. Había visto la reducción anteriormente (en un curso de pregrado de complejidad) pero no había pensado en una implementación real específicamente para crear instancias difíciles. Tengo un interés a largo plazo en la optimización y la metaheurística, y una de mis áreas de interés es crear problemas interesantes de referencia. Por cierto, acabo de revisar su blog, ¡seguro que volveremos!
Alejandro Piad