Jesús M. Jorge Santiso, jjorge@ull.es

Jonay Rodríguez Báez, jrbaez@ull.es

Grupo de optimización y minería de datos

Departamento de Estadística, Investigación Operativa y Computación

Escuela Técnica Superior de Ingeniería Informática

Universidad de La Laguna

Introducción

Especificación del lenguaje MOPL

Integración en Sistema Map

Líneas de trabajo futuro

Se ha diseñado y desarrollado una extensióndel lenguaje algebraico OPL que incluyaademás de sus funcionalidades principales, lacapacidad de tratar con múltiples objetivos deforma simultánea y/o de representar modelosde optimización sobre la región eficiente deun problema de optimización multiobjetivo.

Esta extensión se ha denominado MOPL(Multiobjective Optimization ProgrammingLanguage) y ha sido integrada en una suite deoptimización de desarrollo propio (SistemaMAP).

Existen múltiples lenguajes para el tratamientode modelos de optimización:

◦ Lenguajes de programación general (C, C++, Java,…).Entrada o salida de datos personalizada. Entornosaltamente especializados, de difícil mantenimiento.

◦ Lenguajes o entornos de cálculo numérico (hojas decálculo, MATLAB, …). Poseen graves inconvenientes altrabajar con modelos con grandes volúmenes dedatos.

◦ Lenguajes algebraicos de modelado (GAMS, AMPS,OPL, …). Permiten una manejo sencillo de complejosmodelos de optimización y una separación natural delos esquemas de los problemas y los datos asociados.

Lenguaje algebraico de modelo cuyas característicasprincipales son:

◦ Permite una formulación sencilla de modelos grandes ycomplejos.

◦ Separa de manera natural los datos de la estructura delmodelo.

◦ La formulación del problema es independiente del tamaño delmismo.

◦ Permite la realización de cambios en el modelo de manerasencilla y segura, lo que facilita el refinamiento continuo enla formulación del problema.

◦ Resulta muy fácil implantar la formulación de cualquiertipo de problemas de programación lineal, no lineal, flujosen redes, etc.

OPL no permite trabajar con problemas conmúltiples funciones a optimizar (MOP, porsus siglas Multiobjective ProgrammingProblem ).

VMAX

. :

Cx

s a

Ax b

l x u

OPL no permite optimizar una función linealsobre una determinada región EP.

EP ⇔ Conjunto de soluciones eficientes del problema MOP

max

. :

t

P

v x

s a

x E

Las extensiones más relevantesimplementadas sobre OPL para manejareste tipo de problemas consisten en:

◦ Permitir especificar varias funciones objetivo, en lugar desólo una, en la sección de declaración de objetivos delmodelo.

◦ Permitir especificar modelos cuya región factible vengadada a través de un MOP.

El cuerpo básico de un problema en formatoMOPL estará especificado por:

◦ Declaración de constantes y parámetros.

◦ Declaración de variables de decisión.

◦ Declaración de varias funciones objetivo.

◦ Declaración de varias restricciones.

MOPL soporta los siguientes tipos de datos básicos:◦ Enteros: int.◦ Enteros no negativos: int+.◦ Números en punto flotante: float.◦ Números en punto flotante no negativos: float+.◦ Booleano: boolean (sólo para las variables de decisión).

Se permite declarar y asignar constantes,parámetros y variables de decisión con cualquierade los tipos básicos disponibles.

int i = 2;float pi = 3.14;int j = i^4;float size = j * pi;int smallpi = floor(pi);

Rangos◦ Permiten asignar un nombre a un intervalo cuya cota

inferior y superior.int limit = 4;

range Range1 = 1.. limit ; // Rango desde 1 hasta 4

range Range2 = limit -1.. limit *3; // Rango desde 3 hasta 12

Arrays◦ Vectores

int a[1..4] = [10, 20, 30, 40]; // Asignación explicita de datos

◦ Matricesint b[Range1][1..3] = ...; // Asignación externa de datos

Son los datos de salida del modelo queespecifican su solución.

Se declaran haciendo uso de la palabrareservada dvar e indicando su tipo.

Pueden ser de diversos tipos básicos e inclusoarrays.

dvar boolean IndUse[Range1][Range2];

dvar float Coord in -10..30;

dvar int x1;

dvar int+ price[Range3];

MOPL permite hacer uso de estructuras de control,lo que clarifica la esquematización de los modelosy facilita su modificación en el futuro.

Estructuras soportadas:◦ ForAll. Establece un bucle en el que se asignan a sus

variables argumento cada uno de los valores de un conjuntodado.

◦ Sum. Permite especificar una serie de sumas.

Es posible hacer uso de iteradores dependientes:

forall (i in 1..20)

forall (j in i..i*30)

Se permite la declaración de varias funcionesobjetivo con diferentes sentidos (maximizar ominimizar).

Las restricciones se construyen a partir deconstantes, variables y operaciones aritméticasdentro de un bloque subject to delimitado porllaves.

Es posible hacer uso de estructuras de control,simplificando notablemente el número delíneas a implementar.

Se soportan dos modos distintos de inicialización dedatos:

Inicialización explícita o directa. Al declarar las variables yase les asigna un valor dentro del propio fichero delmodelo.

int a[1..3] = [3,6,8];float p = 3.5;

Inicialización externa. Los valores de lasconstantes/parámetros se especifican en un fichero dedatos externo. Éste estará especificado dentro de unproyecto MOPL, definido mediante un fichero XML, queincluirá además el fichero con el esquema del modelo autilizar.

int a[1..3] = …; //Declaración en el fichero del modelo

a = [3,6,8]; //Asignación de valores en el fichero de datos externo

2max

2

x y

x y

. . :

cos( 2( 2))

sin( 2( 2)) 1

0,..., 2

s a

x j CTE

y j CTE

j CTE

0

0

0 1

x

y

z

0

0

0 1

x

y

z

. . :

cos( 2( 2))

sin( 2( 2)) 1

0,..., 2

s a

x j CTE

y j CTE

j CTE

2max

2

x y

x y

int n= 3;int k = 2;int CTE = 4;

range Nrange = 1..n;range Krange = 1..k;

float C[Krange][Nrange] = [[-0.5, 1,0] , [1, -0.5,0]];dvar float+ x[Nrange]; //x1=x, x2=y, x3=z

maximizeForall (i in Krange)

Sum (j in Nrange) C[i][j] * x[j];

Subject to{

forall (j in 1..CTE-1)x[1] * cos((((j-1)*pi)/(2* (CTE-2)))) + x[2] * sin ((((j-1)*pi)/(2* (CTE-2)))) <= 1;x[3] <= 1;

} *Armand & Malivert (1991)

sum(i in Krange) x[i][i] = A;sum(i in Krange) x[i][k-i +1] = A;int k = 4;

int n = k^2;int A = ((k^2+1)*k)/2;int B = k^2 -1;

range Nrange = 1..sqrt(n);range Krange = 1..k;range LimitDvar = 1..n;range RangeApha = 1..(k^2)-1;

dvar int+ x[Nrange][Nrange] in LimitDvar;dvar boolean alpha[RangeAlpha][RangeAlpha] ;dvar boolean beta[RangeAlpha][RangeAlpha];

Subject to{

forall (i in Krange)sum (j in Krange) x[i][j] = A;

forall (j in Krange)sum (i in Krange) x[i][j] = A;

forall (j in Krange)sum (i in Krange) x[i][((i + j -2) % k) + 1] = A;

forall (i in Krange)sum (j in Krange) x[((i +j -2) % k) + ] [(k- j)+1 ]=A;

Diagonal principal e inversa

Suma de todos los cuadrados con k

elementos contiguos

forall(i in 1..(k^2-1))forall(j in 0..i-1){x[(i/k) + 1][(i % k)+1] - x[(j/k) + 1][(j % k) + 1] +

k^2 * alpha[i][j+1] <= B;

x[(j/k) + 1][(j % k) + 1] -x[(i/k) + 1][(i % k)+1] + k^2 * beta[i][j+1]<= B;

alpha[i][j+1] + beta[i][j+1] = 1;}

}

forall (i in 1..k-sqrt(k) + 1)forall (j in 1..k-sqrt(k) + 1)

sum(m in i..i + sqrt(k) - 1)sum(p in j..j + sqrt(k) - 1)

x[m][p] = A;

Todas las variables distintas

Suma por filas y por columnas

Resolutor vectorial de fácilmanejo.

Gran cantidad de técnicas yalgoritmos para analizar yresolver diversos tipos deproblemas.

Generación y resolución deproblemas en batería.

Exportación de problemas aformato LP, MPS y XML.

Visor de soluciones yrepresentación gráfica de lasmismas.

Visualizar y gestionar los ficheros de datos y modelosincluidos en los proyectos MOPL.

Mostrar el contenido del modelo MOPL seleccionado,indicando el número y nombre de clases incluidas en losmodelos MOPL.

Editor deproblemas

Librería de algoritmos

multiobjetivo

Motor de programación lineal escalar

Integrado en la interfaz del resolutor y como herramienta independiente.

Importación y exportación de soluciones en XML.

Posibilidad de representar gráficamente las soluciones en dos o tres dimensiones.

Visualización de diferenteslienzos en múltiplespestañas.

Control de movimiento yzoom de las figuras entiempo real.

Personalización de lasfiguras (ocultación, cambiode propiedades, etc.).

Importación y exportaciónde las características de loslienzos en formato XML.

Posibilidad de realizar proyecciones de lasolución sobre las variables que desee elusuario.

Capacidad de mezclar diferentes lienzos y unir diferentessoluciones de un mismo problema en un único lienzo y así podervisualizar conjuntamente los elementos notables de dichoproblema.

Cargar datos de modelos MOPL a través de conexiones a bases de datos.

Desarrollo de una herramienta de diseño de experimentos computacionales.

Creación de un portal que permita resolver de forma online problemas de programación multiobjetivo.

Grupo de optimización y minería de datos