La optimización lineal de números enteros (OLNE) (o programación de números lineales enteros (MILP) o programación de enteros (IP) o Programación lineal de enteros (ILP)) es un campo de las matemáticas y de la informática teórica en el que consideramos problemas de optimización de un determinado formulario. Estos problemas se describen mediante una función de costo y restricciones lineales, y mediante variables enteras.
La restricción de integralidad sobre las variables, que diferencia el OLNE de la optimización lineal clásica, es necesaria para modelar ciertos problemas, en particular problemas algorítmicos. Pero esta restricción adicional hace que el problema sea más complejo y requiere técnicas especiales.
Un problema de optimización es un problema matemático en el que, dado un conjunto de variables y las restricciones sobre esas variables, uno debe encontrar una asignación que maximice (o minimice) una determinada función de costo. Hablamos de un problema lineal cuando las restricciones y la función de costo son combinaciones lineales de las variables y el problema son números enteros si estas variables solo pueden tomar valores en el conjunto de números enteros.
La restricción que obliga a las variables a tomar valores enteros se llama restricción de completitud. Cuando borramos esta restricción, hablamos de un problema de relajación relajado o continuo , y luego estamos tratando con un problema de optimización lineal . La relación entre lo óptimo en la versión relajada y en la versión completa a menudo se denomina brecha de integralidad .
Un problema OLNE se puede plantear en dos formas clásicas: la forma canónica y la forma estándar. La forma canónica de una maximización es:
,y la forma estándar es:
donde son vectores y es una matriz con valores enteros.
Damos un ejemplo del problema OLNE, ilustrado por la imagen de al lado.
Hay dos variables, por lo que las soluciones son pares de números enteros. Los puntos rojos son los pares que verifican las restricciones y las líneas punteadas rojas muestran la envolvente convexa de estos puntos. Las soluciones óptimas a este problema son (1,2) y (2,2).
Las líneas azules y el eje x delimitan los pares de reales que satisfacen todas las restricciones excepto la restricción de completitud. Lo óptimo es mejor en esta versión relajada.
Muchos problemas algorítmicos y de investigación de operaciones pueden traducirse en un problema OLNE. Por ejemplo, el problema de la cobertura por conjuntos es el siguiente. Dado un conjunto A , decimos que un elemento e está cubierto por A si e pertenece a A ; para un conjunto U y una familia S de subconjuntos de U , el problema consiste en cubrir todos los elementos U con la subfamilia más pequeña posible de S. Este problema se traduce naturalmente en la siguiente forma:
minimizar: | (Minimizar el número de subconjuntos) | ||
tal que : | (Todos los artículos están cubiertos) | ||
. | (Cada subconjunto está en la portada o no) |
En el sentido de la teoría de la complejidad , la optimización lineal entera se considera difícil porque es un problema NP-difícil . Esta complejidad se deduce fácilmente de la dificultad NP del problema de cobertura del conjunto . Una de las consecuencias prácticas es que, para problemas grandes, el tiempo de cálculo puede ser muy grande.
Sin embargo, la complejidad es polinomial cuando el número de variables es fijo, como mostró Lenstra en 1983.
Cuando las restricciones toman la forma de una matriz totalmente unimodular y entera, es posible una resolución de tiempo polinomial porque las soluciones del problema relajado son enteras.
Si el número de variables es fijo, entonces el problema también es polinomio.
Entre los métodos clásicos de resolución, cabe mencionar el método de los planos secantes (en particular utilizando secciones de Gomory) y el principio de separación y evaluación ( ramificación y cota ). Desde la década de 1990, la inclusión de secciones de Gomory ha acelerado enormemente el algoritmo de separación y evaluación. Esto dio origen a una nueva clase de algoritmos llamados rama y corte .
La teoría de algoritmos de aproximación a menudo usa una formulación OLNE de problemas y trata de limitar la brecha de integralidad para obtener una solución aproximada en tiempo polinomial .
Este tipo de optimización se utiliza ampliamente en la investigación de operaciones . También se ha convertido en un enfoque clásico en bioinformática .