domingo, 21 de junio de 2015

Algunas perspectivas sobre la solución de problemas de programación entera (V)

Aunque toda esta simplificación no es usual, con frecuencia los problemas de programación entera que surgen en la práctica tiene alguna estructura especial que se puede aprovechar para simplificarlos. A veces se pueden resolver con éxito versiones muy largas de estos problemas. Cada vez son más importantes los algortimos de propósitos especiales que están elaborados específicamente para explotar ciertos tipos de estructuras especiales en programación entera.

Entonces, los dos factores determinantes de la dificultad computacional de un problema de PE son 1) el número de variables enteras y 2) la estructura del problema. Esta situación es opuesta a la de programación lineal, en donde el número de restricciones funcionales es mucho más importante que el número de variables. En programación entera, el número de restricciones tiene alguna importancia (en especial, si se van a resolver las solturas de PL), pero es estrictamente secundario para los otros dos factores. De hecho, existen casos en los que aumentar el número de restricciones disminuye el tiempo de cálculo ya que se reduce el número de soluciones factibles. En los problemas de PEM es el número de variables enteras y no el número total de variables el que es importante, pues las variables continuas casi no tienen efecto sobre el esfuerzo computacional.

No hay comentarios.:

Publicar un comentario