LISTA DE PROBLEMAS

El problema del vendedor ambulante de cuello de botella ( TSP de cuello de botella ) es un problema de optimización discreta o combinatoria . El problema es encontrar el ciclo hamiltoniano en un gráfico ponderado que minimice el peso del borde más pesado del ciclo. ^[1] Primero fue formulado por Gilmore y Gomory (1964) con algunas restricciones adicionales, y en su generalidad completa por Garfinkel y Gilbert (1978) . 

Complejidad [ editar ]

Se sabe que el problema es NP-hard . La versión del problema de decisión de esto, "para una longitud dada x, ¿hay un ciclo hamiltoniano en un gráfico G sin un borde más largo que x ?", Es NP-completo . La completitud NP sigue inmediatamente a una reducción del problema de encontrar un ciclo hamiltoniano. ^[4]

Algoritmos [ editar ]

Otra reducción, desde el TSP de cuello de botella al TSP habitual (donde el objetivo es minimizar la suma de las longitudes de borde), permite que cualquier algoritmo para el TSP habitual también se use para resolver el TSP de cuello de botella. Si los pesos de borde del TSP de cuello de botella se reemplazan por cualquier otro número que tenga el mismo orden relativo, entonces la solución de cuello de botella permanece sin cambios. Si, además, cada número en la secuencia excede la suma de todos los números más pequeños, entonces la solución de cuello de botella también será igual a la solución habitual de TSP. Por ejemplo, dicho resultado puede lograrse restableciendo cada peso a n ⁱ donde n es el número de vértices en el gráfico e ies el rango del peso original del borde en la secuencia ordenada de pesos. Por ejemplo, después de esta transformación, el algoritmo Held-Karp podría usarse para resolver el cuello de botella TSP en el tiempo O ( n ² 2 ⁿ ) . ^[1]

Alternativamente, el problema puede resolverse realizando una búsqueda binaria o una búsqueda secuencial para la x más pequeña, de modo que la subgrafía de los bordes de peso como máximo x tenga un ciclo hamiltoniano. Este método conduce a soluciones cuyo tiempo de ejecución es solo un factor logarítmico mayor que el tiempo para encontrar un ciclo hamiltoniano. ^[1]

Variaciones [ editar ]

En un TSP de cuello de botella asimétrico , hay casos en los que el peso del nodo A a B es diferente del peso de B a A (por ejemplo, el tiempo de viaje entre dos ciudades con un atasco en una dirección).

El TSP de cuello de botella euclidiano , o TSP de cuello de botella plano, es el TSP de cuello de botella con la distancia que es la distancia euclidiana ordinaria . El problema sigue siendo NP-duro. Sin embargo, muchas heurísticas funcionan mejor para él que para otras funciones de distancia.

El problema del vendedor ambulante de dispersión máxima es otra variación del problema del vendedor ambulante en el que el objetivo es encontrar un ciclo hamiltoniano que maximice la longitud mínima del borde en lugar de minimizar la longitud máxima. Sus aplicaciones incluyen el análisis de imágenes médicas y la programación de pasos de metalurgia en la fabricación de aeronaves para evitar la acumulación de calor de pasos cercanos tanto en el tiempo como en el espacio. Se puede traducir a una instancia del problema del cuello de botella TSP al negar todas las longitudes de borde (o, para mantener los resultados positivos, restarlos a todos de una constante lo suficientemente grande). Sin embargo, aunque esta transformación conserva la solución óptima, no conserva la calidad de las aproximaciones a esa solución. ^[1]

Algoritmo de aproximación métrica [ editar ]

Si el gráfico es un espacio métrico, entonces hay un algoritmo de aproximación eficiente que encuentra un ciclo hamiltoniano con un peso máximo en el borde que no es más del doble del óptimo. Este resultado sigue el teorema de Fleischner , que el cuadrado de un gráfico conectado a 2 vértices siempre contiene un ciclo hamiltoniano. Es fácil encontrar un valor de umbral θ , el valor más pequeño de manera que los bordes de peso θ formen un gráfico de 2 conectados. Entonces θ proporciona un límite inferior válido en el peso del cuello de botella TSP, porque el cuello de botella TSP es en sí mismo un gráfico de 2 conexiones y necesariamente contiene un borde de peso al menos θ. Sin embargo, el cuadrado del subgrafo de bordes de peso como máximo θ es hamiltoniano. Por la desigualdad del triángulo para espacios métricos, su ciclo hamiltoniano tiene bordes de peso como máximo 2 θ . ^[5] [6]

Esta relación de aproximación es la mejor posible. Para, cualquier gráfico no ponderado se puede transformar en un espacio métrico estableciendo sus pesos de borde en 1 y estableciendo la distancia entre todos los pares de vértices no adyacentes en 2 . Se podría utilizar una aproximación con una relación mejor que 2 en este espacio métrico para determinar si el gráfico original contiene un ciclo hamiltoniano, un problema de NP completo. ^[6]

Sin el supuesto de que la entrada es un espacio métrico, no es posible una relación de aproximación finita.

Un problema de programación de enteros es un programa de optimización matemática o de factibilidad en el que algunas o todas las variables están restringidas a ser enteros . En muchos entornos, el término se refiere a la programación lineal entera (ILP), en la que la función objetivo y las restricciones (distintas de las restricciones enteras) son lineales .

La programación entera es NP-completa . En particular, el caso especial de la programación lineal de enteros 0-1, en el que las incógnitas son binarias, y solo se deben cumplir las restricciones, es uno de los 21 problemas completos de NP de Karp .

Si algunas variables de decisión no son discretas, el problema se conoce como un problema de programación de enteros mixtos . 

Forma canónica y estándar para ILP [ editar ]

Un programa lineal entero en forma canónica se expresa como: ^[2]

{\ displaystyle {\ begin {alineado} & {\ text {maximizar}} && \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x} \\ & {\ text {sujeto a}} && A \ mathbf {x} \ leq \ mathbf {b}, \\ &&& \ mathbf {x} \ geq \ mathbf {0}, \\ & {\ text {and}} && \ mathbf {x} \ in \ mathbb {Z} ^ {n}, \ end {alineado}}}

y un ILP en forma estándar se expresa como

{\ displaystyle {\ begin {alineado} & {\ text {maximizar}} && \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x} \\ & {\ text {sujeto a}} && A \ mathbf {x} + \ mathbf {s} = \ mathbf {b}, \\ &&& \ mathbf {s} \ geq \ mathbf {0}, \\ &&& \ mathbf {x} \ geq \ mathbf {0}, \\ & {\ text {and}} && \ mathbf {x} \ in \ mathbb {Z} ^ {n}, \ end {alineado}}}

dónde $${\ displaystyle \ mathbf {c}, \ mathbf {b}} son vectores y $${\ displaystyle A}es una matriz, donde todas las entradas son enteros. Al igual que con los programas lineales, los ILP que no están en forma estándar se pueden convertir a forma estándar eliminando desigualdades e introduciendo variables de holgura ($${\ displaystyle \ mathbf {s}}) y la sustitución de variables que no tienen restricción de signos con la diferencia de dos variables con restricción de signos

Ejemplo [ editar ]

Politopo IP con relajación LP

El diagrama de la derecha muestra el siguiente problema.

{\ displaystyle {\ begin {alineado} \ max & {\ text {}} y \\ - x + y & \ leq 1 \\ 3x + 2y & \ leq 12 \\ 2x + 3y & \ leq 12 \\ x, y & \ geq 0 \\ x, y & \ in \ mathbb {Z} \ end {alineado}}}

Los puntos enteros factibles se muestran en rojo, y las líneas discontinuas rojas indican su casco convexo, que es el poliedro convexo más pequeño que contiene todos estos puntos. Las líneas azules junto con los ejes de coordenadas definen el poliedro de la relajación LP, que está dada por las desigualdades sin la restricción de integralidad. El objetivo de la optimización es mover la línea punteada negra hacia arriba sin dejar de tocar el poliedro. Las soluciones óptimas del problema entero son los puntos.$${\ displaystyle (1,2)} y $${\ displaystyle (2,2)} que tienen un valor objetivo de 2. El óptimo único de la relajación es $${\ displaystyle (1.8,2.8)}con valor objetivo de 2.8. Si la solución de la relajación se redondea a los enteros más cercanos, no es factible para el ILP.

Prueba de dureza NP [ editar ]

La siguiente es una reducción de la cobertura mínima de vértice a la programación entera que servirá como prueba de la dureza NP.

Dejar $${\ displaystyle G = (V, E)}ser un gráfico no dirigido Defina un programa lineal de la siguiente manera:

{\ displaystyle {\ begin {alineado} \ min \ sum _ {v \ in V} y_ {v} \\ y_ {v} + y_ {u} & \ geq 1 && \ forall uv \ in E \\ y_ {v } & \ geq 0 && \ forall v \ in V \\ y_ {v} & \ in \ mathbb {Z} && \ forall v \ in V \ end {alineado}}}

Dado que las limitaciones limitan $${\ displaystyle y_ {v}}a 0 o 1, cualquier solución factible para el programa entero es un subconjunto de vértices. La primera restricción implica que al menos un punto final de cada borde está incluido en este subconjunto. Por lo tanto, la solución describe una cubierta de vértice. Además, dada alguna cubierta de vértice C$${\ displaystyle y_ {v}} se puede establecer en 1 para cualquier $${\ displaystyle v \ en C} y a 0 para cualquier $${\ displaystyle v \ not \ en C}dándonos así una solución factible para el programa entero. Así podemos concluir que si minimizamos la suma de$${\ displaystyle y_ {v}}También hemos encontrado la cobertura mínima de vértice. ^[3]

Variantes [ editar ]

La programación lineal de enteros mixtos ( MILP ) implica problemas en los que solo algunas de las variables,$${\ displaystyle x_ {i}}, están restringidos a ser enteros, mientras que otras variables pueden ser no enteras.

La programación lineal cero uno implica problemas en los que las variables están restringidas a 0 o 1. Cualquier variable entera limitada puede expresarse como una combinación de variables binarias. ^[4] Por ejemplo, dada una variable entera,$${\ displaystyle 0 \ leq x \ leq U}, la variable se puede expresar usando $${\ displaystyle \ lfloor \ log _ {2} U \ rfloor +1} variables binarias:

$${\ displaystyle x = x_ {1} + 2x_ {2} + 4x_ {3} + \ cdots +2 ^ {\ lfloor \ log _ {2} U \ rfloor} x _ {\ lfloor \ log _ {2} U \ rfloor +1}.}

Aplicaciones [ editar ]

Hay dos razones principales para usar variables enteras al modelar problemas como un programa lineal:

1. Las variables enteras representan cantidades que solo pueden ser enteras. Por ejemplo, no es posible construir 3.7 autos.
2. Las variables enteras representan decisiones (por ejemplo, si se debe incluir una arista en un gráfico ) y, por lo tanto, solo deben tomar el valor 0 o 1.

Estas consideraciones ocurren con frecuencia en la práctica y, por lo tanto, la programación lineal entera se puede usar en muchas áreas de aplicaciones, algunas de las cuales se describen brevemente a continuación.

Planificación de producción [ editar ]

La programación de enteros mixtos tiene muchas aplicaciones en la producción industrial, incluido el modelado en taller. Un ejemplo importante que ocurre en la planificación de la producción agrícola implica determinar el rendimiento de producción de varios cultivos que pueden compartir recursos (por ejemplo, tierra, mano de obra, capital, semillas, fertilizantes, etc.). Un posible objetivo es maximizar la producción total, sin exceder los recursos disponibles. En algunos casos, esto puede expresarse en términos de un programa lineal, pero las variables deben limitarse a ser enteras.

Programación [ editar ]

Estos problemas involucran el servicio y la programación del vehículo en las redes de transporte. Por ejemplo, un problema puede implicar asignar autobuses o subterráneos a rutas individuales para que se pueda cumplir un horario, y también para equiparlos con conductores. Aquí las variables de decisión binarias indican si un autobús o metro está asignado a una ruta y si un conductor está asignado a un tren o metro en particular. La técnica de programación cero-uno se ha aplicado con éxito para resolver un problema de selección de proyectos en el que los proyectos son mutuamente excluyentes y / o tecnológicamente interdependientes. Se utiliza en un caso especial de programación de enteros, en el que todas las variables de decisión son enteros. Puede asumir los valores como cero o uno.

Redes de telecomunicaciones [ editar ]

El objetivo de estos problemas es diseñar una red de líneas para instalar de modo que se cumpla un conjunto predefinido de requisitos de comunicación y el costo total de la red sea mínimo. ^[5] Esto requiere optimizar tanto la topología de la red como la configuración de las capacidades de las distintas líneas. En muchos casos, las capacidades están limitadas a ser cantidades enteras. Por lo general, existen, según la tecnología utilizada, restricciones adicionales que pueden modelarse como desigualdades lineales con enteros o variables binarias.

Redes celulares [ editar ]

La tarea de planificación de frecuencia en redes móviles GSM implica la distribución de frecuencias disponibles a través de las antenas para que los usuarios puedan ser atendidos y se minimice la interferencia entre las antenas. ^[6] Este problema puede formularse como un programa lineal entero en el que las variables binarias indican si una frecuencia está asignada a una antena.

Algoritmos [ editar ]

La forma ingenua de resolver un ILP es simplemente eliminar la restricción de que x es un número entero, resolver el LP correspondiente (llamado relajación LP del ILP) y luego redondear las entradas de la solución a la relajación LP. Pero, no solo esta solución puede no ser óptima, sino que incluso puede no ser factible; es decir, puede violar alguna restricción.

Usando la unimodularidad total [ editar ]

Si bien, en general, no se garantizará que la solución para la relajación LP sea integral, si el ILP tiene la forma $${\ displaystyle \ max \ mathbf {c} ^ {\ mathrm {T}} \ mathbf {x}} tal que $${\ displaystyle A \ mathbf {x} = \ mathbf {b}} dónde $${\ displaystyle A} y $${\ displaystyle \ mathbf {b}} tener todas las entradas enteras y $${\ displaystyle A}es totalmente imimodular , entonces cada solución factible básica es integral. En consecuencia, se garantiza que la solución devuelta por el algoritmo simplex es integral. Para demostrar que cada solución factible básica es integral, dejemos que$${\ displaystyle \ mathbf {x}}Ser una solución factible básica arbitraria. Ya que$${\ displaystyle \ mathbf {x}} es factible, sabemos que $${\ displaystyle A \ mathbf {x} = \ mathbf {b}}. Dejar$${\ displaystyle \ mathbf {x} _ {0} = [x_ {n_ {1}}, x_ {n_ {2}}, \ cdots, x_ {n_ {j}}]} ser los elementos correspondientes a las columnas base para la solución básica $${\ displaystyle \ mathbf {x}}. Por definición de una base, hay alguna submatriz cuadrada$${\ displaystyle B} de $${\ displaystyle A} con columnas linealmente independientes de modo que $${\ displaystyle B \ mathbf {x} _ {0} = \ mathbf {b}}.

Desde las columnas de $${\ displaystyle B} son linealmente independientes y $${\ displaystyle B} es cuadrado $${\ displaystyle B} es no singular y, por lo tanto, por suposición, $${\ displaystyle B}es unimodular y por eso$${\ displaystyle \ det (B) = \ pm 1}. Además, desde$${\ displaystyle B} es no singular, es invertible y por lo tanto $${\ displaystyle \ mathbf {x} _ {0} = B ^ {- 1} \ mathbf {b}}. Por definición,$${\ displaystyle B ^ {- 1} = {\ frac {B ^ {adj}} {\ det (B)}} = \ pm B ^ {adj}}. aquí$${\ displaystyle B ^ {adj}}denota el adjunto de$${\ displaystyle B} y es integral porque $${\ displaystyle B}es integral Por lo tanto,

{\ displaystyle {\ begin {alineado} & \ Rightarrow B ^ {- 1} = \ pm B ^ {adj} {\ text {es integral.}} \\ & \ Rightarrow x_ {0} = B ^ {- 1 } b {\ text {es integral.}} \\ & \ Rightarrow {\ text {Toda solución factible básica es integral.}} \ end {alineado}}}

Por lo tanto, si la matriz $${\ displaystyle A} de un ILP es totalmente unimodular, en lugar de usar un algoritmo ILP, el método simplex puede usarse para resolver la relajación LP y la solución será entera.

Algoritmos exactos [ editar ]

Cuando la matriz $${\ displaystyle A}no es totalmente unimodular, hay una variedad de algoritmos que pueden usarse para resolver programas lineales enteros exactamente. Una clase de algoritmos son los métodos de plano de corte que funcionan resolviendo la relajación de LP y luego agregando restricciones lineales que conducen a la solución a ser entera sin excluir ningún punto entero factible.

Otra clase de algoritmos son las variantes de la rama y el método enlazado . Por ejemplo, el método de ramificación y corte que combina los métodos de ramificación y encuadernación y plano de corte. Los algoritmos de ramificación y unión tienen una serie de ventajas sobre los algoritmos que solo usan planos de corte. Una ventaja es que los algoritmos pueden terminarse antes de tiempo y siempre que se haya encontrado al menos una solución integral, se puede devolver una solución factible, aunque no necesariamente óptima. Además, las soluciones de las relajaciones de LP se pueden utilizar para proporcionar una estimación del peor de los casos de cuán lejos de la óptima es la solución devuelta. Finalmente, los métodos de ramificación y enlace pueden usarse para devolver múltiples soluciones óptimas.

Lenstra en 1983 demostró que, cuando el número de variables es fijo, el problema de programación de enteros de factibilidad puede resolverse en tiempo polinómico. ^[7]

Métodos heurísticos [ editar ]

Como la programación lineal entera es NP-hard , muchas instancias de problemas son intratables y, por lo tanto, deben usarse métodos heurísticos. Por ejemplo, la búsqueda tabú se puede utilizar para buscar soluciones a los ILP. ^[8] Para usar la búsqueda tabú para resolver los ILP, los movimientos se pueden definir como aumentar o disminuir una variable restringida entera de una solución factible mientras se mantienen constantes todas las demás variables restringidas enteras. Las variables no restringidas se resuelven para. La memoria a corto plazo puede consistir en soluciones previamente probadas, mientras que la memoria a mediano plazo puede consistir en valores para las variables limitadas de enteros que han resultado en valores objetivos altos (suponiendo que el ILP es un problema de maximización). Finalmente, la memoria a largo plazo puede guiar la búsqueda hacia valores enteros que no se hayan probado previamente.

Otros métodos heurísticos que se pueden aplicar a ILP incluyen

• Montañismo
• Recocido simulado
• Optimización de búsqueda reactiva
• Optimización de colonias de hormigas
• Redes neuronales Hopfield

También hay una variedad de otras heurísticas específicas del problema, como la heurística k-opt para el problema del vendedor ambulante. Una desventaja de los métodos heurísticos es que si no logran encontrar una solución, no se puede determinar si es porque no hay una solución factible o si el algoritmo simplemente no pudo encontrarla. Además, generalmente es imposible cuantificar cuán cerca de óptima es una solución devuelta por estos métodos.