Primera mejora conseguida

La primera mejora es la que actualiza el valor de U , según los costes derivados de servicio a todos los clientes desde todas las plantas.

Para problemas pequeños funciona. Pero, no está claro que la mejora esté bien, por que en problemas pequeños no se tiene que actualizar el valor de u.

Estoy probando para problemas del orden de 100 plantas y 1000 clientes. En estos casos si que es necesario actualizar u, por que hacemos más de una iteración, y debemos penalizar cada vez más los costes.

 

Y ahora que?

Hoy he dedicado la mañana a hacer trazas para saber donde falla. Pero no encuentro donde.

Esta tarde me tocará más de lo mismo.

Intentaré aplicar la otra mejora por otro lado sola, a ver si por ese lado sale.

El caso es que tengo que estar a punto de conseguirlo, asi que ya veremos.

Más esta tarde...

Nuevos resultados

Después de los examenes, vuelta al PFC.

La semana pasada no saque resultados muy buenos para la nueva mejora a aplicar.

Esta mejora esta basada en hacer más pequeños los subproblemas que tienen que llegar a resolver el problema concreto.

Esta mejora se realiza eliminando las X que sabemos que su multiplicador c >= 0.

 

Otra de las mejoras que debemos aplicar es la actualización de U. Previamente hay que odenar los costes y localizar donde irá situado uj0. Si hay que actualizas uj0, hacerlo con el valor cj que corresponda, y así sucesivamente, en orden creciente. El vector U irá tomando valores cada vez más altos para penalizar los costes.

 

De momento vamos a aplicar la primera mejora y ver los resultados obtenidos.

 

 

Óptimo muy cercano

Ya que acabamos la primera parte de este proyecto ,(ver que alcance tiene CPLEX resolviendo problemas CFL), ahora toca ponerse a optimizar.

En esta pimera parte hemos comprobado como CPLEX resuelve todos los problemas de la bateria de problemas OR-Library, alojada en

http://people.brunel.ac.uk/~mastjjb/jeb/info.html (2009)

Estos datos están analizados en el paper J.E. Beasley  "An algorithm for solving large capacitated warehouse location problems" European Journal of Operational Research 33(1988) 314-325.

He realizado un artículo para presentar en Marzo, por que finalizaba la beca. Hemos entregado los resultados de todas las pruebas, junto con una ubicación del problema, su formulación, las herramientas y el equipo utilizado, y las técnicas que utiliza cada herramienta para resolver cada una de las instancias.

En la segunda parte veremos la relajación semi-Lagrangiana. Esta relajación hace que el problema sea más fácil de resolver que el problema primal o principal. Con esta técnica partimos el problema primal en subproblemas más pequeños, y por tanto más fáciles de solucionar.

Para hacer el problema relajado:

1- Resolver la RL del problema primal.

          De aquí obtenemos un vector de varialbes duales que nos dará el valor del vector U0. Este vector contendrá la penalización que le damos al problema para que tienda a resolverse completamente.

2- Resolver el problema relajado de CFL con relajacion semi-Lagrangiana.

          Los valores de las plantas(y) sólo pueden ser enteros.Esta restricción es importante.

          Necesitamos:

                   - Actulalizar el valor de U

                            Con la actualización hacemos que cada vez se resuelva un problema relajado, acercandonos a la  solución del problema primal.

                   - Criterio de parada

                             Necesitamos este criterio de parada para saber cuando hemos llegado al óptimo.

 

 

 

 

 

Modificar entrada de datos

La unica entrada de datos posible seria de todos con igual número de columnas. Y ahora lo que estamos haciendo es partiendolo en dos.

Así se hace muy costoso el obtener ficheros válidos para nuestra entrada de datos.

Es necesario modificarlo. Deberiamos poder poner un número de columnas que fuera igual al número de localizaciones y lo demás a 0.

 

Paso para leer datos del fichero y asignarlos bien

Si el número de localizaciones es impar no sale el ejercicio por que el paso tiene una división entre 2.

Esto tengo que contemplarlo, es decir, tengo que arreglarlo con un if comprobando si el número es par o impar, mediante el módulo.

 

IntVars

Parece que IntVars no esta funcionando por que si resolvemos sin Cplex con la llamada a linprog, obtenemos resultados que no son en ningun caso enteros, sino todos lineales.

En cambio, cuando hacemos la llamada a linprog desde Cplex, pone todos los valores de las x a enteros, 0 ó 1, y las y a continuos.

Realmente, debería ser al revés, es decir, para los valores de las x que fueran valores continuos, y el valor de la y deberia ser entero.

 

 

Nos centramos en resolver Rardin con mipSolve

Ya he conseguido obtener un resultado para el ejemplo de Rardin.

Lo resuelve con la llamada a mipSolve y despues con tomRun.

El resultado obtenido es el mismo que teniamos para Linprog, ya que mipSolve resuelve ejemplos de tipo mixed-integer linear programming, es decir, resolución para problemas mixtos entero-lineales.

Gracias a IntVars tenemos que el resultado es el correcto, teniendo en cuenta que los ultimos 8 valores de el vector x son realmente los valores de y, que deben ser enteros. El resto de x, es decir, los 112 elementos primeros pueden ser valores entre 0 y 1.

Haciendo algunas pruebas nos damos cuenta que si eliminamos el valor de IntVars, conseguimos el mismo resultado.

Eso es raro, muy raro, ya que parece que esta poniendo los resultados buenos sin necesidad de decirle si queremos que sean enteras o lineales.

 

 

Llamada a mipSolve

Dos lineas de investigación para probar el funcionamiento de mipSolve

- Resolver Rardin con llamadas mipSolve

       Es necesario hacer cambios en la matrices que se le pasan al problema ya que en mipSolve no existe un matriz que sea Aeq

       También tenemos que añadir las variables restantes que antes no teniamos y ahora si.

- Resolver el cap 41 con menos datos.

     Reducir el problema a número de clientes 10 y de localizaciones a 5, en principio.

 

Procedimientos por falta de tiempo

Como es muy díficil que terminemos el trabajo para el dia 1 de Marzo, César y yo hemos acordado que adelantaremos lo máximo posible hasta Marzo, y lo que quede del proyecto lo seguiremos haciendo de cara a entregalo como PFC.

Asi pues, voy a realizar 10h semanales en el aula del Dept II, para poder consultar mis dudas a César cuando las tengas. Así estamos más cerca uno del otro.

Y por otro lado, cuando tenga huecos en casa, también iré adelantando trabajo. Así lograre antes de fin de año haber avanzado algo en el proyecto.

 

Duda

Tengo dudas de como hacer esto:

 

Sum desde i=1 to m de x_ij >=1.

Por que no se si debe ser con  blkdiag de unos, es decir, una matriz que en su diagonal tenga matrices de unos, y lo demás cero. O directamente toda la matriz tiene que ser de ceros.

A ver si mañana me resuelve la duda César.

Mañana tenemos la reunión a las 9 de la mañana.

Startup.m

He vuelto a repasar el problema y creo que el fallo esta en la matriz A y b. Voy a volver  a repasarlo ahora.

No he conseguido aún hacer que Matlab ejecute startup.m al comienzo siempre, para que no tenga que llamarlo yo siempre desde mi codigo. Aún no tengo la solución pero creo que estoy a punto de conseguirlo.

Queda repasar otra vez el problema a ver si soy capaz de encontrar el fallo.

Editando:

Sólo puedo hacer que el .dll no se comprobado cada vez que se lanza startup pero no puedo ejecutarlo cada vez que se abre Matlab.

 

Avances semana

Entre ayer y hoy he avanzado poco.

A ver si mañana o en la reunión con  César.

Manejo de IntVars

Esto es sencillo.

IntVars es un  vector que identificará las variables que le pasamos a una llamada, para saber si son enteras o continuas. También acepta valores binarios.

Se usa de la siguiente manera.

Si el vector esta vacío, se entiende que no hay variables enteras.

Si el vector tiene n elementos y estos tienen valores 0 o 1, se entiende como que los valores a 1 identifican la posición de la salida en la que se encuentra un número entero o binario. Si es 0, es una variable continua.

Si el vector contiene valores mayores que 1 (>1), se considera que son las posiciones de los variables de tipo entero o binario.

Como se queda el problema cap41

El problema tendra en cuenta sólo las restricciones de satisfacción de demanda y de capacidad. Ambas quedaran con símbolo de desigualdad.(Demanda - >= y Capacidad - <=)

No tendremos en cuenta, de momento, la restricción x_ij <= y_i, pero si para obtener una optimización, ya que añadir restricciones al problema ayuda a CPlex a una resolución más rápida.

 

IntVars

Tal y como yo pensaba la clave esta en IntVars.

Este vector define que variables de nuestro programa son enteras o binarias. Por tanto, tenemos que las y_i tienen que ser binarias, ya que solo pueden tomar valor de 0 o 1. Es decir, 0 , esta cerrada la localización, y 1 , está abierta la localización.

Para las x_ij, deben estar entre 0 y 1, pero no tienen que ser binarias, ni enteras. La definición de los límites se contempla en x_U y x_L .

 

Sin internet en toda la semana.

Esta semana no he podido publicar avances por que internet no me funciona.

Hoy hago un resumen de todo un poco.

Desesperación....

Llevo toda la semana con lo mismo, y no salgo de este agujero.

Aportes de cosas nuevas:

Con IntVars podemos poner las varialbes que con enteras o binarias.

Puede que la solución este en las variables slacks. Que son aquellas que se añaden a una restricción para cambiar la desigualdad de la ecuación. Requieren que se convierta de una desigualdad a una igualdad en la que una comibnación lineal de variables es <= a una costante dada.Como es una restricción aumentada los valores no pueden ser negativos.

El problema que tengo creo que esta en que el paso de parámetros a la llamada no es el válido, ya que he probado con otros test de ejemplo que trae el tomlab y todos los resuelve con el mismo resultado, siendo que unos los resuelve con Simplex y yo los cambié a Cplex.

Creo que la cuestión está en sabe como poner la matrices de A y b, junto con las de Aeq y beq, que eran necesarias para Linprog y Bintprog.

Haciendo pruebas:

-Si quitamos Aeq y beq, sigue saliendo 0.

-Si quitamos A y b sigue saliendo 0.

-Si igualamos b_L a b_U, teniendo en cuenta que b_U = [b;beq], nos da como resultado que no es fatible. Además se salen 6 variables de rango.

 

Leyendo la documentación del manual deTOMLAB/CPLEX, no encuentro nada para solucionarlo.

También me he leido el Manual de TOMLAB, de donde he sacado ejemplos para hacer pruebas.

También he buscado cosas por Internet pero no logro encontrar nada.

Y en un intento desesperado de ayuda he mandado un email a Marcus , mi amigo de TOMLAB.

Mañana será otro día.

Reunión con César. A ver si me hecha un cable.

 

Mañana otra reunión

No entiendo por que no funciona.

Las llamadas se hacen bien, y el algoritmo sabemos que esta bien por que cuando ejecuto Linprog o Bintprog funciona perfectamente.

No lo entiendo.

A ver si mañana me hecha una mano César.

 

Avences de la reunión

Estos avances son de la reunión celebrada el dia 3 de octubre. No pude publicar antes por que realmente me iba mal internet.

- Ya el problema del Rardin con Bintprog y Linprog. Tanto en Matlab como en Cplex, pero siempre con las sentencias adecuadas.

Una vez que el Cplex esta activo, lo que hace es ejecutar Bintprog o Linprog bajo su propio software. Con esto lo que obtenemos es que el tiempo que tardaba en Bintprog se reduzca en mucho. Antes necesitaba casi 40 minutos. Ahora en un par de segundos ya lo tienes.