[Parte c - Método de Benders] Por qué se puede estancar la búsqueda?

[Parte c - Método de Benders] Por qué se puede estancar la búsqueda?

de Federico Matonte Martinez -
Número de respuestas: 4

Buenas noches. Con Luciana decidimos separar el problema en un Problema Maestro (PM) de Contratación (que aborda cuantos con empleados contratar cada mes) y cuanto de sus tiempos de trabajo dedican a cada producto, y un Sub Problema (SP) de producción (que incluye también la selección de almacenamiento o retraso del cumplimiento de la demanda), omitimos la formulación por si esto no está permitido. 
Hemos probado con varias soluciones iniciales de mejor y peor calidad pero con cualquiera de ellas luego de 2 a 5 iteraciones se estanca y no avanza, teniendo un costo total por arriba del millón (lo que supera con creces el óptimo, cercano a los 600K que encontramos para la parte b).

Es válida esta separación? 

Tomamos como criterio para esta separación la cercanía conceptual de las variables, para  que juntas definan problemas conceptualmente correcto y que el subproblema sea acota. Hay otro criterio que podamos considerar? 

Entendemos que más allá de la solución inicial, si planteásemos bien el método, deberíamos de llegar al óptimo. Esto es correcto? 

No hemos intentado invertir la selección del PM y el SP, porque en las pruebas que realizamos el problema de Contratación nos resulta no acotado. 
Muchas gracias y saludos.

En respuesta a Federico Matonte Martinez

Re: [Parte c - Método de Benders] Por qué se puede estancar la búsqueda?

de Luciana Vidal Jaureguy -
Buenas!
Queríamos comentar que logramos que itere una mayor cantidad de veces, y si bien conseguimos un resultado próximo al óptimo no es el mismo costo: tenemos una diferencia de 4200 aproximadamente.

Probamos a correr más iteraciones, pero no logramos que el costo mejore. Puede ser causa de que hayamos separado mal el PM y SP? O no importa cómo se divida y con qué sol se inice, se debería llegar al óptimo?

Hay posibilidad de tener una charla? Porque no sabemos bien qué deberíamos fixear de nuestra solución para llegar al resultado óptimo, dado que chequeamos nuestro método contra el ejercicio trnloc01p (fuimos por la solución primal) y parecería q estamos ok.

Gracias!
Saludos,
Luciana.
En respuesta a Federico Matonte Martinez

Re: [Parte c - Método de Benders] Por qué se puede estancar la búsqueda?

de Víctor Albornoz -

Estimados Alumnos: mis saludos a la distancia y disculpas por no atender sus inquietudes y las de otros de sus compañeros de curso.

Mis nuevas obligaciones y clases de hoy y todo mañana sábado me complican hacerlo en lo más inmediato.

El domingo les contesto y desde ya sepan que he ampliado el plazo de entrega de la tarea en una semana.

Atte., Prof. Víctor M. Albornoz

En respuesta a Víctor Albornoz

Re: [Parte c - Método de Benders] Por qué se puede estancar la búsqueda?

de Federico Matonte Martinez -
No hay problema Víctor, por suerte pudimos seguir adelante y logramos completar la tarea.
Aun así, nos interesa las respuestas a las dudas teóricas planteadas.
Desde ya muchas gracias.
En respuesta a Federico Matonte Martinez

Re: [Parte c - Método de Benders] Por qué se puede estancar la búsqueda?

de Víctor Albornoz -
Estimada Luciana, Estimado Federico: mis saludos para ustedes. Qué bueno que pudieron sacar adelante su tarea.

Algunos comentarios adicionales que pueden ser útiles para todos sus compañeros son los siguientes:

i) La descomposición propuesta en el contexto del método de Benders debe ser tal que el Subproblema siempre debe tener solución óptima cualquiera sea el valor obtenido para las variables originales que definen el Problema Maestro. De no ser así, ello se puede tratar en el método pero creo no haber discutido ese aspecto en clases (se requiere agregar otras restricciones/cortes en el maestro).

ii) Si lo anterior se cumple, puede haber varias formas de descomponer el problema igualmente y ello determina la rapidez de convergencia del método. Lo anterior en el entendido que la estructura del Subproblema puede ser explotada en general para resolverlo muy eficientemente (con un algoritmo ad-hoc por ejemplo) o que pueda separarse a su vez en varios subproblemas más pequeños en lugar de uno solo.

iii) Es muy importante entender igualmente que el Subproblema resultante sea un modelo lineal en variable continua (o uno convexo más generalmente) para alcanzar la solución óptima del problema original. Si el Subproblema tiene variables enteras llegarán a la solución óptima de un modelo similar al original. Más precisamente al que tiene por restricciones las que involucran a las variables originales que dejaron en el maestro y la envoltura convexa de las restricciones asociadas a las que dejaron en el Subproblema. Como este último conjunto no se conoce, si alguien ya implementó tal descomposición, sugiero resolver el Subprblema en variable continua (omitiendo la integralidad) y comparar el valor óptimo alcanzado con la del problema original resuelto directamente y relajando esas mismas variables enteras del Subproblema en el modelo original y esos dos valores si deben coincidir.

iv) Si en la implementación del método de Benders uno parte por proponer una solución factible en las variables originales que quedaron en el maestro (como en el ejemplo de localización visto en clases), ello puede determinar la cantidad de iteraciones que termina haciendo pero alcanzará la solución óptima de todos modos cuidando lo señalado en mis comentarios anteriores

Atte., Prof. Víctor M. Albornoz