Consulte las páginas 18-20 del artículo al que se hace referencia en el pie de página de la sección 2.2 que describe un estudio de IO realizado para el Rijkswaterstaat, de Holanda. Describa una lección importante aprendida con la validación del modelo en este estudio.

domingo, 19 de julio de 2015

Otras opciones con la técnica de ramificación y acotamiento (I)

Esta sección ha ilustrado la técnica de ramificación y acontamiento con la descripción de un algoritmo básico para resolver problemas  de programación entera binaria. Sin embargo, el marco general de trabajo de la técnica de ramificación y acotamiento proporciona una gran flexibilidad en cuanto al diseño de un algoritmo específico para cualquier tipo de problema dado. Se dispone de muchas opciones y la construcción de un algoritmo eficiente requiere adaptar el diseño específico para que se ajuste a la estructura particular del tipo de problema.

Cada algoritmo de ramificación y acotamiento contiene los mismos pasos básicos de ramificación, acotamiento y sondeo. La flexibilidad consiste en cómo se realizan estos pasos.

La ramificación siempre implica seleccionar un subproblema restante y dividirlo en subproblemas  más pequeños. En este caso, la flexibilidad se encuentra en las en las reglas para seleccionar y dividir. El algoritmo que se presentó elige el subproblema de creación más reciente, porque esto es muy eficiente para reoptimizar cada soltura de PL a partir  de la anterior. Elegir el subproblema con la mejor cota es la otra regla popular, ya que tiende a llegar más rápido  a mejores soluciones de apoyo y más sondeos. También se puede usar una combinación de estas dos reglas. La división casi siempre (pero no siempre) se hace seleccionando una variable de ramificación y asignándole, ya sea valores individuales (como el algoritmo), o intervalos de valores (como en el algoritmo de la siguiente sección). Algoritmos más elaborados por lo general  utilizan una regla para elegir estratégicamente una variable de ramificación que tienda a sondeos rápidos.


No hay comentarios.:

Publicar un comentario