Seção de Software: o uso de software de modelagem AIMMS na solução de problemas
de programação matemática
Seção de Software
O uso de software de modelagem AIMMS na solução de problemas de programação
matemática
Aníbal Alberto Vilcapoma IgnácioI; Virgílio José Martins Ferreira FilhoII, *
IPrograma de Engenharia de Produção / COPPE Universidade Federal de Rio de
Janeiro Rio de Janeiro RJ avilcap@pep.ufrj.br_
IIPrograma de Engenharia de Produção / COPPE e Departamento de Engenharia
Industrial Universidade Federal de Rio de Janeiro Rio de Janeiro RJ
virgilio@ufrj.br
1. Introdução
A pesquisa operacional, nos últimos tempos, tem desenvolvido uma grande
variedade de modelos e algoritmos de otimização para a resolução de problemas
em diversas áreas como: logística, telecomunicações, produção, finanças etc..
As ferramentas de apoio à decisão se fundamentam fortemente nas técnicas de
otimização, entretanto, sua aplicação prática pode acarretar diversas
dificuldades na fase de modelagem e no gerenciamento eficiente dos sistemas
computacionais, o que muitas vezes inviabiliza o seu acesso por parte de
diversas empresas e entidades governamentais. Segundo Geoffring (1987) e Matura
et al. (2004), os modelos matemáticos de otimização têm duas formas gerais de
uso. Na primeira, o modelo é usado ao nível estratégico, implicando em uma
resolução do problema usada a intervalos de tempo consideravelmente longos, o
que é intrínseco em uma decisão estratégica. Na segunda, o modelo atende a uma
necessidade ao nível táctico-operacional, os modelos de solução são usados
periodicamente e neste nível de decisão, nem sempre há necessidade de
profissionais especializados em Pesquisa Operacional. O desenvolvimento das
ferramentas, para cada um dos dois tipos, é obviamente distinto. Para atender a
estas demandas, existem, atualmente, diversos sistemas de modelagem que
facilitam o processo de implementação e solução dos modelos utilizando
linguagem algébrica, os sistemas de Suporte Analítico à Decisão.
Normalmente, o sistema de suporte analítico à decisão é um sistema interativo
que enfatiza técnicas computacionais avançadas que, muitas vezes são
transparentes para os usuários, oferecendo amplas facilidades de análise dos
problemas por sua visibilidade externa. As aplicações típicas desse tipo de
ferramenta são:
• Representação de uma realidade complexa;
• Organização e uso de grande volume de dados multidimensionais,
inter-relacionados, baseados em informações próprias do problema e de
diversos parâmetros associados à solução do mesmo;
• Utilização de técnicas avançadas de ferramentas de otimização e de
manipulações aritméticas para se encontrar uma solução;
• Através das técnicas analíticas ou dos experimentos computacionais
pode-se avaliar as conseqüências de diversas soluções, sob diferentes
cenários;
• Emprego de técnicas de visualização avançadas que fornecem uma
percepção da solução e/ou da complexidade do problema;
• Possibilidade de mudanças se houver maior compreensão de uma
realidade mutável ou percepções melhoradas.
Em geral é necessário muito conhecimento para se usar um sistema de apoio à
decisão, dominando-se a linguagem de modelagem e os parâmetros que controlam
diferentes aspectos do solver. As pessoas experientes em Pesquisa Operacional
compreendem bem os modelos e conseguem com facilidade realizar modificações e
detectar erros. No entanto, a delegação dessas tarefas para usuários finais é
muito complicada, já que são tarefas que requerem grande especialização.
Os sistemas de suporte analítico à decisão mais conhecidos são AIMMS, AMPL,
GAMS, LINGO, MPL, OPL Studio. O Quadro_1 a seguir apresenta os endereços de
Internet onde podem ser obtidas informações mais detalhadas sobre cada um
deles.
O Quadro_2 apresenta uma comparação destes principais sistemas com respeito a
suas funcionalidades, considerando tanto características da modelagem, quanto
da interface com o usuário e outros sistemas.
Neste artigo são apresentadas as características funcionais do AIMMS (Advanced
Integrated Multidimensional Modeling Software). Segundo Bisschop (2002), o
AIMMS é uma ferramenta que inclui as duas formas gerais de uso dos modelos
matemáticos, já que permite construí-los ao nível estratégico e ao nível tático
operacional, através de ferramentas de apoio à decisão iterativa para a solução
dos problemas. É também apresentado um exemplo que exibe uma importante
característica iterativa do Solver e da linguagem AIMMS, que pode ser usada,
por exemplo, para se explorar relaxações Lagrangeanas em problemas de forte
complexidade computacional.
Uma versão de teste (try version), que pode ser usada durante 30 dias, pode ser
obtida na página eletrônica do AIMMS. Esta versão suporta até cerca de 1200
variáveis.
2. AIMMS
O AIMMS Advanced Integrated Multidimensional Modeling Software oferece um
ambiente de desenvolvimento, no qual pessoas experientes em modelagem podem
criar aplicações funcionais, prontas para serem usadas por pessoas mais leigas
ou usuários finais. Como um ambiente de desenvolvimento de apoio analítico à
decisão, o AIMMS possibilita uma combinação de características de métodos
matemáticos e de ferramentas de desenvolvimento, tais como: o explorador de
modelos num ambiente gráfico para se construir e manter aplicações de modelagem
complexa; os métodos de solução exata; os procedimentos que permitem interagir
com as linguagens C, C++, Fortran e ferramentas de interface com as bases de
dados através de ODBC/OLE DB (ver na Figura_1).
O sistema AIMMS proporciona ambiente adequado para:
• Modelar problemas de otimização;
• Criar uma interface de usuário final ajustada às necessidades do
usuário;
• Fornecer um ambiente de execução em tempo real para os que tomam as
decisões.
O sistema AIMMS oferece uma notação de índice que possibilita capturar a
complexidade de problemas reais. Além disso, permite expressar muitos cálculos
complexos de uma maneira compacta, sem a preocupação com o gerenciamento da
memória ou considerações de estocagem de dados. Uma das principais
características do AIMMS é sua capacidade de especificar e resolver modelos de
otimização com restrições lineares e não lineares. Usando-se a mesma notação
compacta disponível para declarações de procedimentos, as restrições simbólicas
podem ser formuladas de modo simples e conciso. Com apenas uma simples
declaração, um modelo de otimização pode ser transferido para o solver e
resolvido por ferramentas, tais como CPLEX, XA, CONOPT e XPRESS.
2.1 Características de Linguagem
O AIMMS apresenta uma linguagem de programação que permite interagir com o
usuário na modelagem e na construção de procedimentos que antecedem e/ou
interagem na execução de um modelo matemático.
As características mais importantes dessa linguagem são:
• Conjunto de funções matemáticas, estatísticas e financeiras;
• Capacidade de expressar modelos baseados no tempo, através do uso
de calendários e horizontes de tempo, inclusive suporte para
intervalos de tempo dinâmico com agregação e desagregação
automáticas;
• Capacidade de associar unidades de medida com identificadores de
modelo, assegurando assim a consistência das unidades dentro das
expressões;
• Suporte de modelagem para problemas mistos;
• Suporte de módulos, para facilitar o melhor desenvolvimento de um
modelo AIMMS por múltiplos usuários. Os módulos são basicamente
seções do modelo com um espaço de nome separado, prevenindo assim a
ocorrência de colisão de nomes quando um ou mais módulos são
importados em um modelo AIMMS;
• Os arquivos são salvos automaticamente a intervalos fixos de tempo,
o que permite se retornar a versões anteriores com muita facilidade;
• Suporte de chamadas de funções e procedimentos externos que não
estão implementados na linguagem AIMMS.
2.2 Interface do Usuário
O AIMMS dispõe de um ambiente de desenvolvimento integrado com todas as
facilidades de um ambiente gráfico apresentado pelas ferramentas do Windows.
Construtor Integrado GUI (Graphical User Interface)
O AIMMS oferece uma ferramenta integrada para a construção de uma interface
gráfica personalizada (GUI) para o usuário, em uma aplicação de apoio à
decisão. A tela final do usuário pode ser criada de modo simples, clicando-se e
arrastando-se, tanto objetos gráficos comuns como também tabelas, gráficos e
curvas, todos associados aos identificadores multidimensionais no modelo do
usuário. Outros objetos incluem gráficos Gantt para se visualizar no tempo, o
fluxo de atividades.
Ferramentas GUI
Ferramenta_Administrativa_de_GUI:
A interfase do usuário final é um aspecto importante na construção de diversos
aplicativos. Esta ferramenta permite organizar todas as telas existentes em uma
aplicação AIMMS, onde se pode ter aplicações em estrutura de árvore e o
relacionamento das páginas definindo uma estrutura hierárquica, como páginas-
pai, páginas-filho, próxima página ou página anterior. Esta ferramenta permite
uma maneira fácil de navegar por todas as páginas de um determinado aplicativo
como também adicionar outras, apagá-las ou modificá-las, respeitando-se uma
política estrita de permissão.
Administrador_de_Modelos_de_Página:
Os modelos (template) das páginas são usados para se especificar propriedades
de objetos. Usando-se esta ferramenta se pode criar e administrar grande número
de objetos (páginas) com características similares, como por exemplo esquema de
cores, criação de áreas para títulos, ícones ou logotipos. Os templates podem
ser organizados em estruturas hierárquicas, podendo ser administrados por esta
ferramenta.
Construtor_de_Menu:
O editor de menus é uma das ferramentas que permite se construir e se manter
menus personalizados como menu de barras (menubars, toolbars e popup).
Quaisquer templates ou pages podem ser embutidos em um menu personalizado com
estruturas hierárquicas.
2.3 Manipulação dos Dados
As facilidades de gerenciamento de dados do AIMMS estão concentradas em
conceitos de Cases e Conjuntos de Dados. Os Cases são um conjunto de dados
associados com os identificadores dos modelos matemáticos e o Conjunto de Dados
corresponde a um conjunto de informações relacionadas a uma categoria como
demanda, suprimento, etc. Uma associação de Conjunto de Dados pode formar um
Case ou cada Conjunto de Dados pode ser compartilhado por mais de um Case,
permitindo análises com critérios condicionais (if ... then) que podem ser
realizadas através de um grande número de Cases e serem executadas em batch.
O AIMMS fornece um conjunto de ferramentas de conexão para se incorporar dados
no sistema de apoio à decisão, através do ODBC e do OLE DB. Procedimentos
simplificados ajudam ao usuário relacionar as colunas da base de dados com os
diversos identificadores multidimensionais do modelo. Uma vez estabelecido o
relacionamento acima, as instruções de escrita e de leitura podem ser
realizadas na base de dados.
2.4 Resolução de Modelos Matemáticos
Um modelo matemático consiste de um conjunto de variáveis a serem determinadas;
uma coleção de restrições que devem ser satisfeitas; e uma função objetivo para
ser otimizada. A meta desse modelo é encontrar uma solução, com o auxílio de um
solver, tal que a função objetivo assuma um valor ótimo (mínimo ou máximo).
Dependendo de diferentes tipos de características das variáveis e restrições,
um programa matemático em AIMMS pode ser classificado, de acordo com as
seguintes condições:
• Se a função objetivo e todas as restrições contiverem somente
expressões lineares (em termos de variáveis) e se todas as variáveis
puderem assumir valores contínuos dentro de sua série, então o
programa é linear.
• Se alguma variável em um programa linear puder assumir somente
valores inteiros, então o programa é inteiro linear misto.
• Se o objetivo for uma função quadrática em termos de variáveis,
enquanto as restrições forem lineares, então o programa é quadrático.
• Se o objetivo não for nem linear nem quadrático ou se algumas das
restrições contiverem expressões não lineares, o programa é não
linear.
O AIMMS chama automaticamente o solver apropriado para encontrar uma solução
ótima.
Declaração e Atributos do MODELO MATEMÁTICO
No AIMMS, um modelo matemático é definido dentro de um conjunto de atributos
previamente definidos. O atributo DIRECTIONS permite escolher entre maximizar e
minimizar a função objetivo. O tributo VARIAVEL define o conjunto ou um
subconjunto de variáveis que fazem parte do modelo a ser executado. Através do
atributo OBJETIVE, é definida a variável como a função objetivo do Modelo. Seu
valor pode ser uma referência para uma variável já definida ou para uma
expressão em função das variáveis. Se não se especificar uma função objetivo, o
modelo matemático é resolvido para se encontrar uma solução viável. O atributo
DIRECTION, quando usado em conjunto com uma função objetivo, serve para indicar
se o solver deve minimizar ou maximizar essa função. Com o atributo VARIABLES
se pode especificar qual o conjunto de variáveis que deve ser incluído em um
programa matemático. Este deve ser um conjunto pré-definido a partir de todas
as variáveis do sistema (AllVariables) ou um subconjunto deste. O conjunto
AllVariables é pré-definido pelo AIMMS e contem os nomes de todas as variáveis
declaradas no modelo e seu conteúdo não pode ser modificado, na fase de
compilação. Se o atributo VARIABLES for designado como um subconjunto do
conjunto AllVariables, o AIMMS tratará todas as variáveis de fora do conjunto
como se elas fossem parâmetros. O atributo NONVAR de uma variável em um
programa matemático permite alterar o estado individual de uma variável, sem
levar em consideração as classes de variáveis.
Existem alguns casos nos quais uma "variável" toma um valor fixo dentro de um
modelo matemático. Nesse caso o AIMMS define uma restrição de igualdade
associada ao valor fixo da variável. Tanto as variáveis quanto as restrições
estão pré-definidas no conjunto AllVariables e AllConstraints, respectivamente.
Pode-se acrescentar uma variável definida ao conjunto de variáveis e de
restrições de um programa matemático, independentemente, nas seguintes
condições:
• Se houver omissão de uma variável definida em um conjunto de
variáveis de um dado modelo matemático, todas as ocorrências da
variável serão fixadas a seu valor corrente.
• Se houver omissão de uma variável definida em um conjunto de
restrições de um dado modelo matemático, a restrição definida não
será gerada.
Com o atributo CONSTRAINTS pode-se especificar quais restrições fazem parte do
programa matemático. Seus valores devem ser o conjunto All-Constraints (todas
as restrições definidas no sistema) ou um subconjunto deste. Esse conjunto
contém os nomes de todas as restrições declaradas e os nomes de todas as
variáveis que tiverem um atributo de declaração. Seu conteúdo é calculado no
tempo de compilação e não pode ser alterado no tempo de execução. A definição
do conjunto de restrições segue as seguintes condições:
• Se for feita especificação do conjunto All-Constraints, o AIMMS
gerará restrições individuais para todas as restrições e variáveis
declaradas com uma definição.
• Se houver especificação de um subconjunto do All-Constraints, o
AIMMS somente gerará restrições individuais para as restrições
declaradas e para as variáveis definidas nesse subconjunto.
• Se o programa matemático tiver um objetivo que seja uma variável
definida, sua definição será acrescentada ao conjunto de restrições
geradas durante a geração.
Álgebra_do_Modelo:
Alterando-se o conteúdo dos conjuntos de identificadores que entraram nos
atributos VARIABLES e CONSTRAINTS de um programa matemático, pode-se produzir
uma forma simples de álgebra do modelo. Melhor dizendo, pode-se investigar os
efeitos da adição ou remoção de restrições e/ou variáveis a partir de uma
interface gráfica proporcionada pelo AIMMS.
Com o atributo TYPE de um modelo matemático pode se definir um tipo de solução
adotada. Quando o tipo especificado não é compatível com o programa gerado, o
AIMMS retornará uma mensagem de erro.
Tipos_Disponíveis:
Os solvers disponíveis pelo AIMMS são descritos no Quadro_3. Quando o tipo rmip
é especificado, todas as variáveis inteiras são tratadas como contínuas dentro
de seus limites. O tipo rmip é uma versão global do atributo RELAX associado
com variáveis individuais. Os tipos ls e nls só podem ser selecionados na
ausência do atributo OBJECTIVE.
Pode-se usar o atributo CONVENTION para se especificar a convenção da unidade
que se quer usar para a escala das variáveis e restrições de um programa
matemático.
Com o atributo VIOLATION PENALTY se pode instruir o AIMMS a adicionar
automaticamente termos artificiais às restrições para ajudar a resolver e/ou
localizar inviabilidades em um programa.
O seguinte exemplo ilustra um modelo típico:
Neste exemplo define-se um modelo linear TransportModel que é construído a
partir de todas as restrições e variáveis, definidas no sistema. A variável
TransportCost define a função objetivo a ser minimizada.
O AIMMS é dotado de funções de acompanhamento que permitem avaliar algumas
características do modelo, que podem ser utilizados para:
• Conseguir informações gerais sobre o programa matemático gerado;
• Obter informação sobre o processo de solução;
• Determinar quando e como ativar um procedimento callback.
As funções mais utilizadas no Solver são:
Objective favor da função objetivo corrente;
LinearObjective valor da solução objetivo relaxada corrente;
ProgramStatus estado corrente do modelo;
SolverStatus estado corrente do solver;
Iterations Current número de iterações;
NumberOfConstraints número de restrições individuais;
NumberOfVariables número de variáveis individuais;
NumberOfNonzeros números de não-zeros;
NumberOfInfeasibilities número final de soluções (Solver) das
inviabilidades.
Após a execução dos Solver, o AIMMS fornece o controle do sistema para o
usuário. Este processo é chamado de Callback. O AIMMS também proporciona um
conjunto de funções para acompanhar este processo. Os exemplos mais comuns são:
CallbackProcedure nome do procedimento Callback;
User CallbackIterations retorno ao callback apos certo número de
iterações;
CallbackStatusChange nome do procedimento callback chamado depois
de uma mudança de estado;
CallbackNewIncumbent nome do procedimento callback chamado para
todo novo valor encarregado;
CallbackReturnStatus retorno ao estado do callback SolverCalls.
3. Exemplo de Aplicação
Com o objetivo de apresentar as características básicas do AIMMS, considera-se
o problema de localização de concentradores apresentado por Ferreira Fo. &
Galvão (1998). Dado um conjunto de localizações possíveis para os
concentradores, determinar o número e o lugar onde os concentradores deverão
ser utilizados e quais usuários deverão ser alocados a cada um deles sem violar
a capacidade dos concentradores minimizando o custo total. A formulação é
apresentada a seguir.
Minimizar
Sujeito_a
O primeiro componente da função objetivo representa os custos de comunicação, o
segundo componente captura custos fixos de instalação. A primeira restrição
assegura que cada usuário deve ser conectado a, exatamente, um concentrador. A
segunda restrição assegura que os usuários só podem ser alocados a
concentradores com capacidades adequadas. A terceira restrição assegura que os
nós sejam alocados somente a locais onde existam concentradores. E a última
restrição expressa a natureza binária das variáveis de decisão
Este modelo matemático pode com muita facilidade ser modelado no AIMMS, através
da ferramenta "model explorer". Para se definir o modelo, primeiramente deve-se
definir os índices (set) a serem usados, como por exemplo o conjunto de índices
I e J que são chamados terminais e concentradores, respectivamente. Na
declaração de índices também podem ser definidos outros índices como o
tableVersion que identifica os conjunto de instâncias a serem consideradas. Uma
vez definidos esses índices, pode-se definir, através do Select Type of
Identifier, as variáveis, constantes, restrições em sua representação algébrica
como mostrado na Figura_2.
A restrição 2 do modelo (Figura_3) é definida, usando-se sua representação
algébrica para permitir a separação entre os dados e a construção do modelo.
Os parâmetros de entrada do modelo (c(i,j), a(i,j), v(j)) podem estar
associados a uma base de dados, para a qual devem ser definidos os apropriados
ODBCs. Para esse exemplo considera-se uma base de dados no Microsoft Access que
é mapeada para o parâmetro de custos como visto na Figura_4. O ODBC usado é
definido como BD_PLC e sua ligação com a base de dados é obtida pela associação
de Custo_alocação_R com os parâmetros c(i,j), através do mapeamento das colunas
da tabela Custo_alocação, com os índices i, j e o valor c.
Na definição do modelo matemático, considera-se uma variável como função
objetivo, uma direção (maximizar ou minimizar) e um subconjunto de variáveis e
restrições. No exemplo, foram consideradas todas as variáveis e todo o conjunto
de restrições, sendo o tipo de método de solução definido como MIP (ver Figura
5).
Para se resolver o modelo, deve-se definir a linha de comando Solve PLC, no
procedimento "MainExecution", como pode ser visto na Figura_6.
Em muitas ocasiões, existe o interesse em encontrar limites inferiores e
superiores para um determinado problema, ou devido à complexidade do problema
ou porque esses limites constituem passos intermediários na ferramenta de
solução. O AIMMS fornece um conjunto de facilidades para se lidar com estes
tipos de situação. O AIMMS, por incorporar uma linguagem de programação,
permite se implementar heurísticas de solução, utilizando-se os métodos de
solução exatos, fornecidos pelo solver. A seguir, é apresentada uma heurística
de subgradiente para se encontrar limites superiores para um modelo de
relaxação Lagrangeana para o problema apresentado.
Ferreira Fo. & Galvão (1998) sugerem que a relaxação da restrição (1) é a
mais adequada para o problema. Considerando-se esta restrição, define-se uma
nova função objetivo, como apresentado na Figura_7, onde Alf(i) são os
multiplicadores de Lagrange.
Para se estabelecer o espaço viável para o problema Lagrangeano, um subconjunto
de Restrições e de variáveis é definido. Como foi relaxada a restrição 1, o
conjunto de restrições válidas é composto pelas restrições 2 e 3 (ver Figura
8).
Uma vez definidos a função objetivo, o conjunto de restrições e o conjunto de
variáveis, pode ser definido com facilidade o modelo relaxado, como mostrado na
Figura_9.
Com a definição deste modelo, pode ser construída facilmente, a heurística de
subgradiente mostrada no procedimento da Figura_10. Os subproblemas resultantes
da decomposição do problema Lagrangeano, podem ser resolvidos pelo solver do
AIMMS, iterativamente. Esta grande facilidade permite se explorar diversas
relaxações, considerando-se as diversas alternativas associadas a cada uma das
restrições do modelo, sem a preocupação, no início, com a construção do método
de solução associado a cada subproblema gerado. É importante ressaltar que
métodos de solução desenvolvidos através da análise de cada subproblema podem
ser muito mais eficientes, no que diz respeito a tempo computacional, do que o
solver do AIMMS. Porém, na fase exploratória do modelo, a alternativa de
solução do solver torna-se uma ferramenta muito importante.
O AIMMS por ser uma linguagem de programação permite a construção de qualquer
procedimento ou função que se faça necessário para se desenvolver uma
heurística de solução para problemas complexos. A facilidade que o AIMMS
oferece no uso do solver em um modelo matemático, através de uma instrução
dentro da linguagem, abre muitos horizontes em termos de desenvolvimento de
novas heurísticas que também podem fazer uso de procedimentos já prontos em C,
C++, e FORTRAN.
4. Conclusões
Os sistemas de suporte analítico à decisão permitem melhorar a tomada de
decisões, através do uso de modelos matemáticos que permitem o uso das
ferramentas da Pesquisa Operacional. O AIMMS fornece ferramentas para se
desenvolver e se construir sistemas de apoio à decisão, desde procedimentos que
ajudam na modelagem, até aplicativos com interface amigável para usuários
finais. No que diz respeito ao desenvolvimento do sistema, o AIMMS fornece
recursos para a modelagem de problemas, para a manipulação de dados, para a
criação de cenários e para a resolução de formas exatas de modelos matemáticos,
tudo isso através de uma linguagem que utiliza como instrução o Solver, que
permite também a construção de heurísticas de solução para problemas
computacionalmente caros. No que diz respeito à criação de um sistema de apoio
à decisão, o AIMMS fornece todo um conjunto de interfaces gráficas que
possibilita, ao usuário final, uma melhor visualização do problema de forma
abrangente.
