Programación entera

Un problema de programación entera es una optimización matemática o un problema de satisfacibilidad en el que algunas o todas las variables deben ser números enteros [1] . A menudo, el término se refiere a la programación lineal entera (ILP), en la que la función objetivo y las restricciones (excepto el requisito de número entero) son lineales .

La programación entera es un problema NP-difícil . Un caso especial, la programación lineal entera 0-1, en la que las variables toman los valores 0 o 1, es uno de los 21 problemas NP-completos de Karp .

Tipos canónicos y estándar de CLP

El problema de la programación lineal entera en forma canónica se expresa como [2]

maximizar	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
bajo condiciones	$A\mathbf {x} \leq \mathbf {b}$
	$\mathbf {x} \geq \mathbf {0}$
y	${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n))$ ,

y en forma estándar

maximizar	$\mathbf {c} ^{\mathrm {T} }\mathbf {x}$
bajo condiciones	$A\mathbf {x} +\mathbf {s} =\mathbf {b}$
	$\mathbf {s} \geq \mathbf {0}$
y	${\displaystyle \mathbf {x} \in \mathbb {Z} ^{n))$

donde son vectores y es una matriz cuyos elementos son enteros. Tenga en cuenta que, como en el caso de la programación lineal, un problema ILP que no está en forma estándar se puede reducir a la forma estándar eliminando las desigualdades introduciendo variables adicionales y artificiales y reemplazando las variables que no están sujetas a la restricción de no negatividad por dos variables $\mathbf {c} ,\mathbf {b}$ $A$

Ejemplo

La figura de la derecha muestra la siguiente tarea.

{\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 válidos se muestran en rojo y las líneas de puntos rojas muestran el casco convexo de estos puntos, que es el polígono más pequeño que contiene todos estos puntos. Las líneas azules, junto con los ejes de coordenadas, definen el polígono de atenuación lineal, que viene dado por desigualdades sin el requisito de número entero. El objetivo de optimización es mover la línea punteada negra para que esté lo más alto posible, pero que toque el polígono. Las soluciones óptimas al problema de los enteros son los puntos y , en los que la función objetivo toma el valor 2. La única solución al problema debilitado (lineal) es el punto , donde la función objetivo toma el valor 2,8. Tenga en cuenta que si redondeamos la solución de un problema de programación lineal al entero más cercano, la solución no será válida para el ILP. ${\ estilo de visualización (1,2)}$ ${\ estilo de visualización (2,2)}$ ${\ estilo de visualización (1.8, 2.8)}$

Prueba de dureza NP

El siguiente argumento es una reducción del problema de minimización de la cobertura de vértices a un problema de programación entera, que prueba la dureza NP.

Sea un grafo no dirigido. Definimos un problema de programación lineal de la siguiente manera: $G=(V,E)$

{\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 el requisito de que tomen los valores 0 o 1, cualquier solución factible para la programación entera es un subconjunto de vértices. La primera restricción implica que al menos un extremo de cada borde está incluido en el subconjunto. Por lo tanto, la solución da una cobertura de vértice. Además, dada una cubierta de vértice C, podemos asignar un valor de 1 para cualquiera y 0 para cualquier , lo que nos da una solución válida al problema de programación entera. De esto podemos concluir que al minimizar la suma , también obtenemos la cobertura mínima de vértice [3] . $y_{v}$ $y_{v}$ ${\ estilo de visualización v \ en C}$ ${\ estilo de visualización v \ no \ en C}$ $y_{v}$

Opciones

En la programación lineal entera mixta (MILP), solo algunas de las variables deben ser enteras, mientras que el resto de las variables pueden no ser enteras. $x_{yo}$

En la programación booleana, las variables deben tomar los valores 0 o 1. Tenga en cuenta que cualquier variable entera acotada se puede expresar como una combinación de variables booleanas [4] . Por ejemplo, si hay una variable entera , se puede expresar en términos de variables booleanas: ${\ estilo de visualización 0 \ leq x \ leq U}$ $\lpiso \log _{2}U\rpiso +1$

x=x_{1}+2x_{2}+4x_{3}+\ldots +2^{\lpiso \log _{2}U\rpiso}x_{\lpiso \log _{2}U\ rpiso +1}.

Aplicaciones

Hay dos razones principales para usar variables enteras al modelar problemas de programación lineal:

Las variables enteras representan cantidades que solo pueden ser números enteros. Por ejemplo, no es posible construir 3,7 coches.
Las variables enteras representan decisiones que toman los valores 0 o 1.

Estas convenciones son comunes en la práctica y, por lo tanto, la programación lineal entera se puede usar en muchas áreas, algunas de las cuales se analizan brevemente a continuación.

Planificación de la producción

La programación de enteros mixtos tiene muchas aplicaciones en la fabricación, incluidas las simulaciones de programación. Un ejemplo ocurre en la planificación de la producción en la agricultura para determinar la producción de productos que pueden tener recursos comunes (como tierra, mano de obra, costos, semillas, fertilizantes, etc.). Un posible objetivo de optimización podría ser maximizar los ingresos sin ir más allá de los límites de los recursos disponibles. En algunos casos, el problema se puede expresar como un problema de programación lineal, pero las variables deben ser números enteros.

Planificación

En estas tareas es necesario asegurar el mantenimiento y programación de la red de transporte. Por ejemplo, la tarea puede ser organizar autobuses o trenes a lo largo de las rutas para cumplir con el horario, así como proporcionar conductores para el material rodante. Aquí, las variables booleanas (es decir, que toman el valor 0 o 1) determinan si se asigna un autobús o un tren a una ruta, y si se asigna un conductor a un autobús/tren en particular.

Redes de datos

El propósito de esta tarea es construir una red de datos para proporcionar requisitos predefinidos por el costo mínimo [5] . Esta tarea requiere la optimización tanto de la topología de la red como del ancho de banda de los elementos de la red. En muchos casos, el rendimiento se expresa en cantidades discretas, lo que da como resultado variables enteras. Por lo general, se aplican otras restricciones específicas de la tecnología, que se pueden modelar como variables enteras o booleanas.

Redes celulares

La tarea de planificación de frecuencias en redes móviles GSM requiere la distribución de frecuencias permitidas entre antenas para asegurar la comunicación y minimizar la interferencia entre antenas [6] . Este problema se puede formular como un problema de programación lineal en el que las variables booleanas reflejan si se asigna una frecuencia particular a una antena particular.

Algoritmos

La forma ingenua de resolver el problema ILP es simplemente ignorar la restricción de enteros en las variables x , resolver el problema LP correspondiente (que se denomina relajación lineal de las restricciones del problema ILP) y luego redondear los componentes de la solución del problema resultante. Sin embargo, la solución resultante puede no solo no ser óptima, sino incluso inaceptable, es decir, es posible que se violen algunas restricciones.

Uso de unimodularidad completa

Aunque, en el caso general, la integralidad de la solución del problema debilitado no está garantizada, si el ILP tiene la forma bajo las condiciones , donde y tiene como elementos números enteros y es completamente unimodular , entonces cualquier solución factible básica será entera. Por lo tanto, la solución dada por el método símplex seguramente será un número entero [7] . Para mostrar que cualquier solución básica de tal problema es un número entero, sea una solución admisible arbitraria. Como es admisible, sabemos que . Sean los elementos correspondientes a las columnas básicas de la solución básica . Por definición de una base, existe alguna submatriz cuadrada de una matriz con columnas linealmente independientes tales que . $\max \mathbf {c} ^{\mathrm {T} }\mathbf {x}$ $A\mathbf {x} =\mathbf {b}$ $A,\mathbf {b}$ ${\ matemáticas {c}}$ $A$ $\mathbf{x}$ $\mathbf{x}$ $A\mathbf {x} =\mathbf {b}$ $\mathbf {x}_{0}=[x_{n_{1}},x_{n_{2}},\cdots,x_{n_{j}}]$ $\mathbf{x}$ $B$ $A$ $B\mathbf {x} _{0}=\mathbf {b}$

Dado que las columnas son linealmente independientes y la matriz es cuadrada, la matriz es no singular, y por lo tanto, bajo el supuesto de que es unimodular , . Como no es singular, la matriz es invertible, y por lo tanto . Por definición, . Aquí significa la matriz de unión para y es entero porque es entero. De este modo, $B$ $B$ $B$ $B$ ${\ estilo de visualización \ det (B) = \ pm 1}$ $B$ $\mathbf {x} _{0}=B^{-1}\mathbf {b}$ $B^{-1}={\frac {B^{adj}}{\det(B)))=\pm B^{adj}$ ${\ Displaystyle B ^ {adj}}$ $B$ $B$

{\ Displaystyle \ Rightarrow B^{-1}=\pm B^{adj})

entero

{\ estilo de visualización \ flecha derecha x_ {0} = B ^ {-1} b}

entero

\Flecha correcta

Cualquier solución básica admisible es entera.

Así, si la matriz ILP es completamente unimodular, en lugar de resolver el problema ILP, se puede utilizar una relajación lineal del problema, lo que dará una solución entera. $A$

Algoritmos exactos

Si la matriz no es completamente unimodular, existen una serie de algoritmos que resuelven exactamente el problema de la programación lineal entera. Una de las clases de tales algoritmos son los métodos de plano de corte (métodos de Gomori), que funcionan resolviendo un problema lineal debilitado con la posterior adición de restricciones lineales que cortan la solución no entera del problema sin cortar las soluciones factibles enteras. $A$

Otra clase de algoritmos son las variantes del método branch andbound . Por ejemplo, el método branch-and-cut , que combina el método branch-and-bound con métodos de plano de corte. Los métodos de bifurcación y límite tienen una serie de ventajas sobre los algoritmos que solo usan planos de recorte. Una de las ventajas es que el algoritmo puede terminar antes de tiempo, tan pronto como se encuentre al menos una solución entera válida, aunque no la óptima. Además, la resolución de un problema lineal relajado se puede utilizar para estimar qué tan lejos está del óptimo. Finalmente, los métodos de bifurcación y acotación se pueden usar para obtener múltiples soluciones óptimas.

Lenstra en 1983 mostró [8] que en el caso de un número fijo de variables, una solución factible a un problema de programación entera se puede encontrar en tiempo polinomial.

Métodos heurísticos

Debido a que los problemas de programación lineal entera son NP-difíciles , muchos problemas son difíciles de resolver, por lo que se aplican métodos heurísticos. Por ejemplo, se puede utilizar una búsqueda tabú [9] . Para usar la búsqueda tabú para resolver el problema ILP, un paso de algoritmo se puede definir como incrementar o disminuir una variable entera mientras se dejan las otras variables enteras sin cambios. Luego se encuentra una solución para las variables en las que no se impone la restricción de número entero. La memoria a corto plazo se puede utilizar para almacenar intentos anteriores, mientras que la memoria a más largo plazo puede consistir en valores de variables enteras para las que se obtienen valores de función objetivo más grandes (asumiendo un problema de maximización). Finalmente, la memoria a largo plazo se puede usar para buscar valores enteros que aún no se han probado.

Otras heurísticas que se pueden aplicar para resolver el ILP

Escalar una superficie convexa
Algoritmo de recocido simulado
Optimización pasiva de motores de búsqueda
Algoritmo de hormiga
Red neuronal Hopfield

También hay otras heurísticas específicas de la tarea, como la heurística k-opt para el problema del viajante de comercio. Tenga en cuenta que la desventaja de los métodos heurísticos es que, en caso de que no se encuentre una solución, el método no determina si esto sucedió debido a la falta de una solución válida o porque el algoritmo no pudo encontrarla. Además, normalmente es imposible determinar qué tan cerca de la solución óptima se obtiene con este método.

Notas

↑ Karmanov, 1986 , pág. 11-12.
↑ Papadimitriou, Steiglitz, 1998 .
↑ Erikson .
↑ Williams, HP Lógica y programación entera (indefinida) . - 2009. - V. 130. - (Serie Internacional en Investigación de Operaciones y Ciencias de la Administración). - ISBN 978-0-387-92280-5 .
↑ Borndörfer, R.; Grötschel, M. Diseño de redes de telecomunicaciones mediante programación entera (2012). (indefinido)
↑ Sharma, Planificación de frecuencia de Deepak (2010). (indefinido)
↑ Entonces, por ejemplo, el problema del transporte se puede considerar como un problema de programación lineal y el método de los potenciales para resolver este problema es, de hecho, un método símplex. La solución básica del método simplex corresponde al árbol en el método potencial, y la matriz correspondiente siempre tiene un determinante de 1. Así, con datos iniciales enteros, la solución del problema de transporte por el método simplex (o el método potencial, que es equivalente) siempre obtendrá una solución entera.
↑ Lenstra, 1983 .
↑ Glover, 1989 , pág. 4–32.

Literatura

CH Papadimitriou, K. Steiglitz. Optimización combinatoria: algoritmos y complejidad. - Mineola, Nueva York: Dover, 1998. - ISBN 0486402584 .
Erickson, J. Reducción de programación entera (2015). Archivado desde el original el 18 de mayo de 2015. (indefinido)
HP Williams. Programación lógica y entera. - 2009. - V. 130. - (Serie Internacional en Investigación de Operaciones y Ciencias de la Administración). - ISBN 978-0-387-92280-5 .
HW Lenstra. Programación entera con un número fijo de variables // Matemáticas de la investigación de operaciones. - 1983. - noviembre ( vol. 8 , número 8 ).
F. Glover. Búsqueda tabú-Parte II // ORSA Revista de informática. - 1989. - Vol. 1 , número. 3 . - S. 4-32 . -doi : 10.1287/ ijoc.2.1.4 .

Lectura para leer más

Karmanov VG Programación matemática. — M .: Nauka , 1986. — 288 p.
Programación de enteros Balinski ML : métodos, usos, cálculos // Ciencias de la gestión. - 1965. - Vol. 12, nº3. - Pág. 253-313. -doi : 10.1287/ mnsc.12.3.253 .
George L. Nemhauser, Laurence A. Wolsey. Optimización entera y combinatoria. - Wiley, 1988. - ISBN 978-0-471-82819-8 .
Alejandro Schrijver. Teoría de la programación lineal y entera. - John Wiley and Sons, 1998. - ISBN 978-0-471-98232-6 .
Laurence A. Wolsey. Programación entera. - Wiley, 1998. - ISBN 978-0-471-28366-9 .
Dimitris Bertsimas, Robert Weismantel. Optimización sobre enteros. - Ideas dinámicas, 2005. - ISBN 978-0-9759146-2-5 .
John K. Karlof. Programación entera: teoría y práctica. - CRC Press, 2006. - ISBN 978-0-8493-1914-3 .
H.Paul Williams. Programación Lógica y Entera. - Springer, 2009. - ISBN 978-0-387-92279-9 .
50 años de programación entera 1958-2008: desde los primeros años hasta el estado del arte / Michael Jünger, Thomas M. Liebling, Denis Naddef, George Nemhauser, William R. Pulleyblank, Gerhard Reinelt, Giovanni Rinaldi, Laurence A Wolsey. - Springer, 2009. - ISBN 978-3-540-68274-5 .
Der-San Chen, Robert G. Batson, Yu Dang. Programación Entera Aplicada: Modelado y Solución. - John Wiley and Sons, 2010. - ISBN 978-0-470-37306-4 .

Enlaces

Métodos de optimización
unidimensional	método de la sección áurea Dicotomía método de parábola búsqueda de cuadrícula Método de búsqueda de bloque uniforme método fibonacci búsqueda ternaria método Piyavsky Método Strongin
orden cero	método de Gauss Método Nelder-Mead Método Hook-Jeeves método de Rosenbrock metodo powell
Primer orden	descenso de gradiente método Zeutendijk Descenso coordinado método de gradiente conjugado Métodos Cuasi-Newtonianos Algoritmo de Levenberg-Marquardt
segundo orden	método de newton Método de Newton-Raphson Algoritmo de Broyden-Fletcher-Goldfarb-Shanno (BFGS)
estocástico	Método de Montecarlo recocido simulado Algoritmos evolutivos evolución diferencial Algoritmo de hormiga método de enjambre de partículas Algoritmo de colonia de abejas Método de paseo aleatorio
Métodos de programación lineal	método símplex algoritmo de gomori método elipsoide método potencial
Métodos de programación no lineal	Programación cuadrática secuencial