Programación entera

Un problema de programación entera es un programa de optimización o viabilidad matemática en el que algunas o todas las variables están restringidas a ser números 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 programación lineal entera 0-1, en el que las incógnitas son binarias y sólo se deben satisfacer las restricciones, es uno de los 21 problemas NP-completos de Karp.

Si algunas variables de decisión no son discretas, el problema se conoce como problema de programación entera mixta.

Formulario canónico y estándar para ILP

En la programación lineal entero, el forma canónica es distinto del formulario estándar. Así se expresa un programa lineal entero en forma canónica (nota que es el x{displaystyle mathbf {x} vector que debe decidirse:

maximizarcTxsujeto aAx≤ ≤ b,x≥ ≥ 0,yx▪ ▪ Zn,{displaystyle {begin{aligned} {text{maximize} {mathbf {c} ^{mathrm {T}mathbf {x}\\\\fnMicrosoft {f}}} {m}mcccccH0} Amathbf {x} leq mathbf {b}\\c}c}mthbf {x} geq mathbf {0}\\\cccccccH0} {cH0}cc}ccH0}ccH0} {Z} {fn} {fn}}}

y un ILP en forma estándar se expresa como

maximizarcTxsujeto aAx+s=b,s≥ ≥ 0,x≥ ≥ 0,yx▪ ▪ Zn,{displaystyle {begin{aligned} {text{maximize} {mathbf {c} ^{mathrm {T}mathbf {x}\\\\fnMicrosoft {f}}} {m}mccccHFF}c\ccH0}}} Amathbf {x} +mathbf {s} =mathbf {b}\mathbf {s}gqmathbf {0}\\\\cHbf {x} geqmathbf {0}\\\cH00} {ccHFF} {x} in mathbb {Z} {fn} {fn}}}

Donde c▪ ▪ Rn,b▪ ▪ Rm{displaystyle mathbf {c} in mathbb {R} ^{n},mathbf {b} in mathbb {R} ^{m} son vectores y A▪ ▪ Rm× × n{displaystyle Ain mathbb {R} {mtimes n} es una matriz. Como con programas lineales, ILPs no en forma estándar se puede convertir a forma estándar eliminando desigualdades, introduciendo variables de escamas (s{displaystyle mathbf {s}) y la sustitución de variables que no están sujetas a signos por la diferencia de dos variables configuradas por signos.

Ejemplo

El gráfico de la derecha muestra el siguiente problema.

maxSí.− − x+Sí.≤ ≤ 13x+2Sí.≤ ≤ 122x+3Sí.≤ ≤ 12x,Sí.≥ ≥ 0x,Sí.▪ ▪ Z{displaystyle {begin{aligned}max >{text{} }y\-x+y reducidaleq 13x+2y reducidaleq 122x+3y limitleq 12xx,y limitegeq 0x,y limitein mathbb {Z} end{aligned}}

Los puntos enteros factibles se muestran en rojo, y las líneas rojas dashed indican su casco convex, que es el poliedro convexo más pequeño que contiene todos estos puntos. Las líneas azules junto con los ejes coordenados definen el poliedro de la relajación LP, que es dada por las desigualdades sin la limitación de la integralidad. El objetivo de la optimización es mover la línea negra desgarrada hasta arriba mientras todavía toca el poliedro. Las soluciones óptimas del problema entero son los puntos ()1,2){displaystyle (1,2)} y ()2,2){displaystyle (2,2)} que ambos tienen un valor objetivo de 2. El óptimo único de la relajación es ()1.8,2.8){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

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

Vamos G=()V,E){displaystyle G=(V,E)} ser un gráfico no dirigido. Define un programa lineal como sigue:

min.. v▪ ▪ VSí.vSí.v+Sí.u≥ ≥ 1О О uv▪ ▪ ESí.v≥ ≥ 0О О v▪ ▪ VSí.v▪ ▪ ZО О v▪ ▪ V{displaystyle {begin{aligned}min sum _{vin Y... 1 golpeforall uvin Ey_{v} limitgeq 0 V\y_{v}in mathbb {Z} ' }

Dado que el límite de limitaciones Sí.v{displaystyle y_{v} a 0 o 1, cualquier solución factible al programa entero es un subconjunto de vértices. La primera limitació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. Adicionalmente dado una cubierta de vértice C, Sí.v{displaystyle y_{v} se puede configurar a 1 para cualquier v▪ ▪ C{displaystyle vin C} y a 0 para cualquier v∉C{displaystyle vnot in C} así nos da una solución factible al programa entero. Así podemos concluir que si minimizamos la suma de Sí.v{displaystyle y_{v} También hemos encontrado la cubierta mínima de vértice.

Variantes

Programación lineal de entero mixto ()MILP) implica problemas en los que sólo algunas de las variables, xi{displaystyle x_{i}}, se limitan a ser enteros, mientras que otras variables se permiten ser no-integers.

Programación lineal Zero-one (o programación binaria) implica problemas en los que las variables se restringen a ser 0 o 1. Cualquier variable de entero atado se puede expresar como una combinación de variables binarias. Por ejemplo, dada una variable entero, 0≤ ≤ x≤ ≤ U{displaystyle 0leq xleq U}, la variable se puede expresar utilizando ⌊ ⌊ log2⁡ ⁡ U⌋ ⌋ +1{displaystyle lfloor log ¿Qué? +1} variables binarias:

x=x1+2x2+4x3+⋯ ⋯ +2⌊ ⌊ log2⁡ ⁡ U⌋ ⌋ x⌊ ⌊ log2⁡ ⁡ U⌋ ⌋ +1.{displaystyle x=x_{1}+2x_{2}+4x_{3}+cdots +2^{lfloor log ¿Qué? }x_{lfloor log -Urfloor +1}

Aplicaciones

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

1. Las variables del entero representan cantidades que sólo pueden ser enteros. Por ejemplo, no es posible construir 3.7 coches.
2. Las variables del entero representan decisiones (por ejemplo, si incluir un borde en un gráfico) y por lo tanto sólo debe 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 utilizar en muchas áreas de aplicaciones, algunas de las cuales se describen brevemente a continuación.

Planificación de la producción

La programación de enteros mixtos tiene muchas aplicaciones en producciones industriales, incluido el modelado de talleres. Un ejemplo importante ocurre en la planificación de la producción agrícola, que implica determinar el rendimiento de la 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 se puede expresar en términos de un programa lineal, pero las variables deben limitarse a ser enteras.

Programación

Estos problemas involucran la programación de servicios y vehículos en las redes de transporte. Un problema puede ser, por ejemplo, asignar autobuses o metros a rutas individuales para que se pueda cumplir un horario, y también 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 entera, en el que todas las variables de decisión son números enteros. Puede asumir los valores como cero o uno.

Partición territorial

El problema de partición territorial o distritación consiste en dividir una región geográfica en distritos para planificar algunas operaciones considerando diferentes criterios o limitaciones. Algunos requisitos para este problema son: contigüidad, compacidad, equilibrio o equidad, respeto de las fronteras naturales y homogeneidad socioeconómica. Algunas aplicaciones para este tipo de problema incluyen: distritación política, distritación escolar, distritación de servicios de salud y distritación de gestión de residuos.

Redes de telecomunicaciones

El objetivo de estos problemas es diseñar una red de líneas a instalar de manera que se cumpla un conjunto predefinido de requisitos de comunicación y el costo total de la red sea mínimo. 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 restringidas a ser cantidades enteras. Generalmente existen, dependiendo de la tecnología utilizada, restricciones adicionales que pueden modelarse como desigualdades lineales con variables enteras o binarias.

Redes móviles

La tarea de planificación de frecuencias en las redes móviles GSM implica distribuir las frecuencias disponibles entre las antenas para que los usuarios puedan recibir servicio y se minimice la interferencia entre las antenas. Este problema se puede formular como un programa lineal entero en el que variables binarias indican si una frecuencia está asignada a una antena.

Otras aplicaciones

• Flujo de efectivo correspondiente
• Optimización del sistema energético
• Orientación UAV

Algoritmos

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 esta solución no sólo puede no ser óptima, sino que incluso puede no ser factible; es decir, puede violar alguna restricción.

Usando la unimodularidad total

Mientras que en general la solución a la relajación del LP no se garantiza que sea integral, si el ILP tiene la forma maxcTx{displaystyle max mathbf {c} {mathrm}mathbf {x} tales que Ax=b{displaystyle Amathbf {x} =mathbf {b} Donde A{displaystyle A} y b{displaystyle mathbf {b} tienen todas las entradas y A{displaystyle A} es totalmente unimodular, entonces cada solución viable básica es integral. En consecuencia, la solución devuelta por el algoritmo simplex está garantizada a ser integral. Para demostrar que cada solución viable básica es integral, x{displaystyle mathbf {x} ser una solución viable básica arbitraria. Desde x{displaystyle mathbf {x} es factible, sabemos que Ax=b{displaystyle Amathbf {x} =mathbf {b}. Vamos x0=[xn1,xn2,⋯ ⋯ ,xnj]{displaystyle mathbf {x} ¿Qué? ser los elementos correspondientes a las columnas de base para la solución básica x{displaystyle mathbf {x}. Por definición de una base, hay una submatrix cuadrado B{displaystyle B} de A{displaystyle A} con columnas linealmente independientes tal que Bx0=b{displaystyle Bmathbf {x}=Mathbf {b}.

Desde las columnas de B{displaystyle B} son linealmente independientes y B{displaystyle B} es cuadrado, B{displaystyle B} es no lineal, y, por consiguiente, por supuesto, B{displaystyle B} es unimodular y así Det()B)=± ± 1{displaystyle det(B)=pm 1}. También, desde B{displaystyle B} es no lineal, es invertible y por lo tanto x0=B− − 1b{displaystyle mathbf {x} ¿Qué?. Por definición, B− − 1=BadjDet()B)=± ± Badj{displaystyle B^{-1}={frac}=pm B^{mathrm {adj}. Aquí. Badj{displaystyle B^{mathrm {adj} denota el adjugado de B{displaystyle B} y es integral porque B{displaystyle B} es integral. Por lo tanto,

⇒ ⇒ B− − 1=± ± Badjes integral.⇒ ⇒ x0=B− − 1bes integral.⇒ ⇒ Cada solución viable básica es integral.{displaystyle {begin{aligned} Derecho B^{-1}=pm Es integral. Rightarrow mathbf {x} Es integral. Rightarrow {text{Cada solución viable básica es integral.}end{aligned}}

A{displaystyle A}

Algoritmos exactos

Cuando la matriz A{displaystyle A} no es totalmente unimodular, hay una variedad de algoritmos que se pueden utilizar para resolver programas lineales enteros exactamente. Una clase de algoritmos están cortando métodos de plano que funcionan resolviendo la relajación del LP y luego añadiendo restricciones lineales que impulsan la solución hacia ser entero sin excluir ningún punto integer factible.

Otra clase de algoritmos son las variantes del método de rama y enlace. Por ejemplo, el método de rama y corte que combina los métodos de rama, unión y plano de corte. Los algoritmos de bifurcación y enlace tienen una serie de ventajas sobre los algoritmos que sólo utilizan planos de corte. Una ventaja es que los algoritmos se pueden terminar anticipadamente 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 qué tan lejos de la optimización está la solución devuelta. Finalmente, los métodos de ramificación y vinculación se pueden utilizar para devolver múltiples soluciones óptimas.

Algoritmos exactos para un pequeño número de variables

Suppose A{displaystyle A} es un m-por-n integer matriz y b{displaystyle mathbf {b} es un m- por un vector entero. Nos centramos en el problema de viabilidad, que es decidir si existe n-por-1 vector x{displaystyle mathbf {x} satisfacción Ax≤ ≤ b{displaystyle Amathbf {x} leq mathbf {b}.

Vamos V ser el valor absoluto máximo de los coeficientes en A{displaystyle A} y b{displaystyle mathbf {b}. Si n (el número de variables) es una constante fija, entonces el problema de viabilidad se puede resolver en el tiempo polinomio en m y registro V. Esto es trivial para el caso n=1. El caso n=2 fue resuelto en 1981 por Herbert Scarf. El caso general fue resuelto en 1983 por Hendrik Lenstra, combinando ideas de László Lovász y Peter van Emde Boas. El teorema de Doignon afirma que un programa entero es factible cuando cada subconjunto de 2n{displaystyle 2^{n} restricciones es factible; un método que combina este resultado con algoritmos para problemas de tipo LP se puede utilizar para resolver programas enteros en el tiempo que es lineal en m{displaystyle m} y fija-parametro traccionable (pero posiblemente doblemente exponencial) en n{displaystyle n}, sin dependencia V{displaystyle V}.

En el caso especial de 0-1 ILP, el algoritmo de Lenstra equivale a enumeración completa: el número de soluciones posibles se fija (2ⁿ), y comprobar la viabilidad de cada solución se puede hacer en el tiempo poli(m, log V). En el caso general, donde cada variable puede ser un entero arbitrario, la enumeración completa es imposible. Aquí, el algoritmo de Lenstra utiliza ideas de Geometría de números. Transforma el problema original en uno equivalente con la propiedad siguiente: ya sea la existencia de una solución x{displaystyle mathbf {x} es obvio, o el valor de xn{displaystyle x_{n} (n-la variable) pertenece a un intervalo cuya longitud está ligada por una función n. En este último caso, el problema se reduce a un número limitado de problemas de menor dimensión. La complejidad de funcionamiento del algoritmo ha mejorado en varios pasos:

• El algoritmo original de Lenstra tenía tiempo de ejecución 2O()n3)⋅ ⋅ ()m⋅ ⋅ log⁡ ⁡ V)O()1){displaystyle 2^{O(n^{3}}cdot (mcdot log V)^{O(1)}.
• Kannan presentó un algoritmo mejorado con tiempo de ejecución nO()n)⋅ ⋅ ()m⋅ ⋅ log⁡ ⁡ V)O()1){displaystyle n^{O(n)}cdot (mcdot log V)^{O(1)}.
• Frank y Tardos presentaron un algoritmo mejorado con tiempo de ejecución n2.5n⋅ ⋅ 2O()n)⋅ ⋅ ()m⋅ ⋅ log⁡ ⁡ V)O()1){displaystyle n^{2.5n}cdot 2^{O(n)}cdot (mcdot log V)^{O(1)}.

• Dadush presentó un algoritmo mejorado con tiempo de ejecución nn⋅ ⋅ 2O()n)⋅ ⋅ ()m⋅ ⋅ log⁡ ⁡ V)O()1){displaystyle n^{n}cdot 2^{O(n)}cdot (mcdot log V)^{O(1)}.

• Reis y Rothvoss presentaron un algoritmo mejorado con tiempo de ejecución ()log⁡ ⁡ n)O()n)⋅ ⋅ ()m⋅ ⋅ log⁡ ⁡ V)O()1){displaystyle (log n)^{O(n)}cdot (mcdot log V)^{O(1)}.

Métodos heurísticos

Dado que la programación lineal entera es NP-difícil, muchos casos de problemas son intratables y, por lo tanto, se deben utilizar métodos heurísticos en su lugar. Por ejemplo, la búsqueda tabú se puede utilizar para buscar soluciones a los ILP. Para utilizar la búsqueda tabú para resolver ILP, los movimientos se pueden definir como incrementar o disminuir una variable restringida por enteros de una solución factible mientras se mantienen constantes todas las demás variables restringidas por enteros. Luego se resuelven las variables no restringidas. La memoria a corto plazo puede consistir en soluciones probadas previamente, mientras que la memoria a mediano plazo puede consistir en valores de variables enteras restringidas que han resultado en valores objetivos altos (asumiendo 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 han probado previamente.

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

• Hill escalando
• Aniquilamiento simulado
• Optimización de búsqueda reactiva
• Optimización de la colonia de hormigas
• Redes neuronales Hopfield

También existe una variedad de otras heurísticas específicas del problema, como la heurística k-opt para el problema del viajante. 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, normalmente es imposible cuantificar qué tan cerca de la solución óptima devuelta por estos métodos está.

Programación entera dispersa

A menudo es el caso de que la matriz A{displaystyle A} que define el programa entero es escasa. En particular, esto ocurre cuando la matriz tiene una estructura de bloques, que es el caso en muchas aplicaciones. La espacidad de la matriz se puede medir de la siguiente manera. El Gráfico de A{displaystyle A} tiene vértices correspondientes a columnas de A{displaystyle A}, y dos columnas forman un borde si A{displaystyle A} tiene una fila donde ambas columnas tienen entradas no cero. Equivalentemente, los vértices corresponden a variables, y dos variables forman un borde si comparten una desigualdad. El Medida de sparsity d{displaystyle d} de A{displaystyle A} es el mínimo entre la profundidad del árbol del gráfico A{displaystyle A} y la profundidad del árbol del gráfico de la transposición A{displaystyle A}. Vamos a{displaystyle a} ser el medida numérica de A{displaystyle A} definido como el valor absoluto máximo de cualquier entrada A{displaystyle A}. Vamos n{displaystyle n} sea el número de variables del programa entero. Luego se mostró en 2018 que la programación de enteros se puede resolver en el tiempo fuertemente polinomio y fijo-parametro trajable parametrizado por a{displaystyle a} y d{displaystyle d}. Es decir, para alguna función computable f{displaystyle f} y algo constante k{displaystyle k}, programación entero se puede resolver en el tiempo f()a,d)nk{displaystyle f(a,d)n^{k}. En particular, el tiempo es independiente del lado derecho b{displaystyle b} y función objetiva c{displaystyle c}. Además, en contraste con el resultado clásico de Lenstra, donde el número n{displaystyle n} de variables es un parámetro, aquí el número n{displaystyle n} de variables es una parte variable de la entrada.