Programación en enteros
Un problema de programación en enteros es un programa de optimización o factibilidad matemática en el cual algunas o todas las variables tienen que ser enteras.
En muchos escenarios el término se refiere a programación lineal en enteros (PLE), en el cual la función objetivo y las restricciones (aparte de las restricciones enteras) son lineales.
Note que similar a los programas lineales, los PLEs que no están en forma estándar pueden ser convertidos a forma estándar eliminando las desigualdades e introduciendo variables artificiales (
) y reemplazando las variables que no están restringidas en signo con la diferencia de dos variables restringidas en signo La imagen a la derecha muestra el siguiente problema.
Los puntos enteros factibles se muestran en rojo, y las líneas rojas discontinuas delimitan la región convexa, la cual es el poliedro más pequeño que contiene todos esos puntos.
Las soluciones óptimas del problema entero son los puntos
Note que si la solución de la relajación es redondeada al entero más cercano, ésta no es factible para el PLE.
La programación lineal en enteros mixta (PLEM) involucra problemas en los cuales algunas de las variables,
La programación lineal cero-uno involucra problemas en los cuales las variables son restringidas a los valores 0 o 1.
variables binarias: Un gran número de problemas pueden ser formulados como PLEs.
Esto incluye: Puesto que la programación lineal en enteros está en NP (las soluciones pueden ser verificadas en tiempo polinomial) y existen problemas NP-completos que pueden ser polinomialmente reducidos a los PLEs, entonces, la programación lineal en enteros es NP-completo.
Existen dos razones principales para usar variables enteras cuando se modelan problemas como programas lineales: Estas consideraciones ocurren frecuentemente en la práctica y por consiguiente la programación lineal en enteros puede ser usada en muchas áreas de aplicación, algunas de las cuales son brevemente descritas a continuación.
La PLEM tiene muchas aplicaciones en la producción industrial, incluyendo modelado trabajo-tienda.
Un objetivo posible es maximizar la producción total, sin exceder los recursos disponibles.
Por ejemplo, un problema puede implicar asignar autobuses o metros a rutas individuales para que un horario sea cumplido, y también equiparlos con chóferes.
Aquí las variables de decisión binarias indican dónde un autobús o metro es asignado a una ruta y dónde un chófer es asignado a un tren o metro en particular.
En muchos casos, las capacidades están restringidas a cantidades enteras.
Usualmente existen, dependiendo de la tecnología usada, restricciones adicionales que pueden ser modeladas como desigualdades lineales con variables enteras o binarias.
[4] Este problema puede ser formulado como un programa lineal en enteros en el cual las variables binarias indican donde una frecuencia es asignada a una antena.
Consecuentemente, la solución retornada por el algoritmo símplex se garantiza que es entera.
no es totalmente unimodular, existen una variedad de algoritmos que pueden ser usados para resolver los programas lineales en enteros exactamente.
Una clase de estos algoritmos son los métodos de planos cortantes los cuales funcionan resolviendo la relajación de PL y entonces añadir restricciones lineales que lleve la solución a ser entera sin excluir algún punto entero factible.
Una ventaja es que los algoritmos pueden ser tempranamente terminados y siempre y cuando al menos una solución entera ha sido encontrada, una factible, aunque no necesariamente óptima, ésta puede ser retornada.
Finalmente, los métodos de ramificación y acotación pueden ser usados para retornar múltiples soluciones óptimas.
Puesto que la programación lineal en enteros es NP-completo, muchas instancias de problemas son intratables, por lo que métodos heurísticos deben ser usados en su lugar.
Por ejemplo, búsqueda tabú puede ser usada para buscar soluciones de PLEs.
[6] Para usar búsqueda tabú para resolver PLEs, los movimientos pueden ser definidos como incrementar o decrementar una variable entera de una solución factible, mientras que todas las demás variables enteras se mantienen constantes.
Finalmente, memoria de término largo puede guiar la búsqueda hacia los valores enteros que no han sido previamente intentados.
Otros métodos heurísticos que pueden ser usados para resolver PLEs incluye Existen también una variedad de otras heurísticas de problemas específicos, tales como heurísitica k-opt para el TSP.
Note que una desventaja de los métodos heurísticos es que si fallan en encontrar una solución, no puede ser determinado donde es porque no hay solución factible, o donde el algoritmo simplemente no pudo encontrar una solución.
