Programação por Propagação de Restrições

Programação por Propagação de Restrições: Teoria e Aplicações

Monografia apresentada como parte constituinte da disciplina MAC0499 - Trabalho de Formatura Supervisionado.

Instituto de Matemática e Estatística - Universidade de São Paulo.

Aluno: Igor Ribeiro Sucupira.

Supervisor: Prof. Dr. Flávio Soares Corrêa da Silva.

Modalidade de trabalho: Iniciação Científica.

Primeira Parte: Aspectos Técnicos

1. Introdução

A programação de restrições (constraint programming) - conforme apresentada em [3] e [4] - é uma tecnologia de programação cuja principal característica é permitir ao programador uma dedicação total à modelagem, tornando oculto o processo de efetiva resolução dos problemas apresentados. Como conseqüência, a programação de restrições tem a capacidade de reduzir o esforço de programação e tornar mais natural a programação modular. Essas qualidades, apoiadas em uma forte fundamentação teórica e aliadas à eficiência dos sistemas existentes para a prática da programação de restrições, têm resultado num grande sucesso dessa tecnologia, tornando-a escolha freqüente para o tratamento de diversas classes de problemas. Exemplos desses problemas ([7]) são:

O problema de manter corretas as relações entre os objetos de uma interface gráfica, após interações do usuário através dessa interface. Por exemplo, em uma aplicação para planejamento de decoração, deseja-se que, caso uma cadeira seja movida dentro de um quarto, não seja possível colocá-la em uma posição onde já há outro móvel. Também é importante, em diversas aplicações, manter a consistência entre os dados armazenados e as representações gráficas desses dados. Ainda, é comum a necessidade de manter a consistência entre diversas visualizações dos mesmos dados.

Problemas complexos de Otimização Combinatória. Neste caso, além da simplificação da modelagem e do bom desempenho devido à propagação de restrições (conceito que será exposto mais adiante), a programação de restrições tem a oferecer uma grande facilidade no controle das técnicas de busca. Os sucessos mais comuns têm ocorrido nas áreas de planejamento, escalonamento e roteamento.

Modelar um problema para ser resolvido em um sistema de programação de restrições consiste em especificar um conjunto de variáveis, o domínio de cada uma delas e um conjunto de restrições adicionais, estabelecendo relações entre variáveis ou restringindo individualmente cada domínio. Um sistema para programação de restrições deve, portanto, ter embutido um mecanismo que o permita resolver os problemas modelados pelo usuário. As formulações teóricas mais comuns para a implementação de tal mecanismo são descritas detalhadamente em [4], que servirá de base para a apresentação sucinta a seguir.

A forma mais básica de implementar um mecanismo de resolução é o algoritmo de busca "gerar-e-testar", que consiste em, de acordo com alguma ordem sistemática, gerar todas as possíveis valorações para as variáveis, fazendo a verificação de viabilidade sempre que uma valoração completa é gerada. Devido à grande ineficiência da técnica "gerar-e-testar", é mais comum a implementação do algoritmo de backtracking, que gera as valorações incrementalmente, verificando a viabilidade de cada valoração parcial, de acordo com as restrições que envolvem as variáveis já instanciadas. Embora, na grande maioria dos casos, o algoritmo de backtracking seja muito mais eficiente que a técnica de "gerar-e-testar", ambos consomem tempo exponencial e normalmente são aceitáveis apenas no tratamento de problemas de pequeno porte.

Outra idéia bastante conhecida para a resolução de problemas de satisfação de restrições é a utilização das técnicas de consistência, ou seja, da remoção de valores inconsistentes - de acordo com as restrições - dos domínios das variáveis. Qualquer problema de satisfação de restrições pode ser representado como um grafo de restrições, em que cada vértice representa uma variável e cada aresta representa uma restrição. Mesmo que o problema não seja binário, ou seja, mesmo que existam restrições envolvendo mais de duas variáveis, existirá um problema binário equivalente ([8]) e, portanto, um grafo de restrições para esse problema. Como conseqüência, as técnicas de consistência mais utilizadas são baseadas no grafo de restrições. Na Figura 1.1, vemos um exemplo de grafo de restrições, para um problema com duas variáveis (A Є {1,2,3} e B Є {0,3,5}), uma restrição binária (A > B) e duas restrições unárias (A < 2 e B > 0).

A forma mais simples de consistência, chamada consistência por nó, é obtida removendo-se valores do domínio de cada variável individualmente, de acordo com suas restrições unárias.

A forma de consistência mais utilizada é a consistência por aresta, que é obtida removendo-se dos domínios das variáveis os valores inconsistentes com as restrições binárias, considerando-se cada par de variáveis individualmente.

Existem algoritmos que implementam outras formas mais fortes de consistência (por exemplo: a consistência por caminho), mas tais algoritmos são pouco utilizados, devido ao grande consumo de tempo e/ou de memória.

A maior parte das técnicas de consistência (em especial, as técnicas mais eficientes e mais utilizadas) são incompletas, ou seja, não eliminam, em geral, a necessidade de busca (o pequeno problema ilustrado na Figura 1.1 seria uma exceção óbvia, uma vez que, após a aplicação das restrições unárias, um algoritmo para obtenção de consistência por aresta seria capaz de indicar que o problema não tem solução).

Assim, os mais bem-sucedidos mecanismos completos de resolução baseiam-se em propagação de restrições: a utilização de um algoritmo "gerar-e-testar" aliado a técnicas eficientes de verificação de consistências. Como aplicações comuns das técnicas de obtenção de consistência, podem-se citar:

	Forward checking: quando uma variável A é instanciada, aplica-se a consistência por arestas entre A e todas as variáveis ainda não instanciadas que estejam envolvidas em restrições binárias com A.
	Full look ahead: quando uma variável A é instanciada, aplica-se a consistência por arestas da mesma forma utilizada pela técnica de forward checking. Adicionalmente, aplica-se a consistência por arestas entre todos os pares de variáveis não instanciadas que possam ser afetadas indiretamente pela valoração de A.

Para que um sistema para programação de restrições seja completo, do ponto de vista prático, não basta que ele tenha a capacidade de, dado um problema P, realizar a busca por uma solução qualquer ou por todas as soluções de P. Em uma imensidão de aplicações práticas - os chamados problemas de otimização -, é necessário buscar uma solução que minimize determinada função de custos, ou seja, deseja-se a "melhor" solução, de acordo com a avaliação determinada pelo usuário. É claro que a busca por todas as soluções, do ponto de vista de funcionalidade, seria suficiente para a determinação da solução ótima. Porém, essa implementação seria extremamente ineficiente, se comparada, por exemplo, à técnica genérica mais popular para otimização com satisfação de restrições: os algoritmos branch and bound.

Para a implementação um algoritmo branch and bound, é necessária a existência de:

	Uma função de custos, para que as soluções possam ser comparadas.
	Uma função heurística h que, dada uma valoração parcial das variáveis, ou seja, um nó não terminal da árvore de busca, calcule um limite inferior para o custo da melhor solução que pode ser encontrada na sub-árvore correspondente.
	Uma variável C que armazene o custo da melhor solução encontrada até o momento. Essa variável terá valor infinito no momento de início da busca.

Compondo-se esse ambiente, é possível realizar a busca pela solução ótima tendo-se em mente que, sempre que ocorre a geração de um nó X da árvore de busca e tal nó não satisfaz a condição h(X) < C, não é necessário explorar a sub-árvore de raiz X.

2. Objetivos

Como visto, a programação por propagação de restrições mostra-se bastante promissora para a construção de programas eficientes e elegantes. Porém, o domínio da fundamentação teórica e das técnicas de programação necessárias à utilização plena do potencial dos sistemas baseados em propagação de restrições é ainda uma tarefa nada trivial. Normalmente, conhecer os recursos disponíveis em um sistema para programação de restrições é o suficiente para modelar problemas corretamente, mas não para a obtenção de resultados eficientes. Com essa motivação, o objetivo deste trabalho é a compreensão teórica do paradigma de programação por propagação de restrições e a obtenção de desenvoltura na utilização de um sistema que ofereça suporte à programação por propagação de restrições.

Para o desenvolvimento prático, foi escolhido o sistema Mozart-Oz ([9]), que é fruto de um projeto internacional europeu em desenvolvimento há mais de dez anos. Esse sistema implementa a linguagem Oz, que dá suporte, em um conjunto coerente, a diversos paradigmas: programação de restrições, orientação a objetos, concorrência, programação funcional etc.

Para a aplicação das técnicas estudadas, foram selecionados dois problemas a serem tratados no ambiente Mozart-Oz:

Distribuição de horários para o Departamento de Ciência da Computação: o objetivo é a construção de grades horárias de aulas que satisfaçam as restrições naturais, além de restrições impostas pelo usuário, buscando a otimização. As restrições a serem implementadas, assim como a função de custos, serão definidas com base nas necessidades do Departamento de Ciência da Computação do Instituto de Matemática e Estatística da Universidade de São Paulo.

Escalonamento e roteamento de helicópteros para distribuição de pessoal: recentemente, o Dr. Flávio Soares Corrêa da Silva participou de um projeto de transferência de tecnologia, contratado pela Petrobrás, com o objetivo de otimizar o escalonamento e roteamento de helicópteros para a distribuição de pessoal nas plataformas de exploração de petróleo offshore da Petrobrás. No presente trabalho, pretende-se que aquele sistema seja reimplementado, para que seja efetuada uma análise comparativa das possibilidades do paradigma de programação por propagação de restrições, perante um sistema escrito em Prolog, por programadores experientes, e meticulosamente depurado visando a otimizar seu desempenho computacional.

3. Metodologia

A tese [2] - em particular o capítulo 3 - é um excelente ponto de partida para uma boa compreensão do ambiente oferecido pelo Mozart para a programação por propagação de restrições.

Para uma fundamentação teórica e prática que permita a programação no ambiente Mozart-Oz, um ponto de partida natural é o tutorial da linguagem ("Language Tutorial"), disponível com o sistema. Como auxílio nesse assunto, os tutoriais "Application Programming" e "Open Programming" são de razoável importância.

Para a obtenção da capacidade de utilizar com desenvoltura a programação por propagação de restrições no ambiente Mozart-Oz, o tutorial "Finite Domain Constraint Programming" é de suma importância.

Complementando o material já citado, uma grande parcela dos manuais de referência, também disponíveis com o sistema Mozart-Oz, são essenciais, para consulta freqüente.

Para especificar formalmente o primeiro problema tratado neste trabalho, foi essencial a consulta ao Prof. Dr. Flávio Soares Corrêa da Silva e, indiretamente, ao Prof. Dr. José Coelho de Pina Júnior, para a determinação de restrições e de uma função de custos que pudessem ser úteis ao Departamento de Ciência da Computação.

Para a implementação do primeiro problema, foi de grande ajuda o artigo [6] e algo instrutiva a leitura do núcleo do código-fonte do programa de demonstração "College Timetabling", disponível com o sistema Mozart-Oz.

A especificação formal do segundo problema teve como base as informações fornecidas pelo Prof. Dr. Flávio Soares Corrêa da Silva. Contrariando a idéia inicial, optou-se pelo tratamento de um problema mais abstrato e, portanto, mais genérico, o que certamente será mais instrutivo para o aluno.

4. Atividades Realizadas e Resultados Obtidos

A primeira fundamentação teórica obtida, descrita resumidamente a seguir, refere-se à programação de restrições na linguagem Oz.

Os domínios finitos são subconjuntos do conjunto de inteiros {0, 1, 2, ..., sup}, onde sup é definido na implementação da linguagem. As restrições em domínios finitos são fórmulas da lógica de predicados, como:

X = 67; X Є 17#809; X \= Y; X² - Y² < Z²; X₁, ..., X₁₀ são distintas duas a duas.

Nesses exemplos, X, Y, Z, X₁, ..., X₁₀ representam variáveis, o operador # constrói um intervalo de inteiros e o operador \= representa a desigualdade.

As estruturas centrais da arquitetura de propagação de restrições da linguagem Oz são os espaços de computação (Figura 4.1). Cada espaço de computação é composto por um conjunto de propagadores ligados a um repositório de restrições.

Um repositório de restrições contém variáveis com seus respectivos domínios, enquanto cada propagador está associado a uma restrição. Assim, um propagador para uma restrição C é uma entidade computacional concorrente que tem a função de assegurar a consistência dos domínios das variáveis que ocorrem em C, de acordo com essa restrição. Cada mecanismo de propagação oferecido pela linguagem Oz pode empregar uma técnica de consistência diferente.

É comum existirem diversas opções de propagadores para o mesmo tipo de restrição, permitindo ao usuário decidir quão forte - e, por conseqüência, custosa - deve ser a técnica de consistência adotada. Por exemplo: {FD.distinctD [A B C]} cria um propagador que assegura a consistência por arestas para a restrição de que A, B e C devem ser distintas, duas a duas; substituindo FD.distinctD por FD.distinct ou FD.distinctB, o propagador criado tentaria assegurar a mesma restrição, utilizando técnicas mais eficientes - embora mais fracas.

Diz-se que um espaço de computação E atingiu a estabilidade (Figura 4.2) quando ocorre uma situação em que todos os propagadores de E já impuseram todas as restrições que podiam ao estado atual do repositório de restrições. Quando um propagador já impôs todas as restrições que podia ao estado atual e certamente não alterará qualquer estado futuro do repositório, este propagador é removido (Figura 4.2-c).

Em uma busca por soluções, na linguagem Oz, a ramificação (criação das sub-árvores de um nó de decisão) é implementada através da criação de cópias do espaço de computação corrente, adicionando-se propagadores a cada uma das cópias. Por exemplo: se, em um nó de decisão E, faz-se a escolha pela ramificação da busca nos casos X = 3 e X \= 3, são criadas duas cópias - E1 e E2 - do espaço E, acrescentando-se a E1 um propagador para X = 3 e a E2 um propagador para X \= 3. E1 e E2 serão, na árvore de busca, as raízes das sub-árvores de E. No contexto do ambiente Mozart-Oz, a operação de ramificação é mais comumente chamada de distribuição.

Conforme observado em [3], uma busca baseada na cópia de estados tem a vantagem de ser eficiente em relação a outros mecanismos (como recomputação e trailing), mas pode representar um consumo de memória inadmissível, nos casos em que a árvore de busca tem uma profundidade muito grande. Devido a essa dificuldade, o mecanismo de busca da linguagem Oz pode ser parametrizado pelo usuário com uma distância de recomputação. Uma distância de recomputação D indica que as cópias de estados devem ser feitas a cada D níveis da árvore de busca, utilizando-se a recomputação nos demais casos. Ainda em [3], é demonstrado que, se fosse utilizada a estratégia de trailing - registro das mudanças ocorridas entre os níveis -, ainda seria necessário um consumo de memória muito grande, para árvores muito profundas.

Completando o mecanismo de resolução, a estratégia branch and bound é implementada da seguinte maneira: quando é encontrada uma solução S com maior qualidade - segundo critérios quaisquer, definidos pelo usuário - que a melhor solução já encontrada, são criados propagadores, em todos os espaços ainda não explorados da árvore de busca, para a restrição de que a solução deve ser melhor que S. Assim, a última solução encontrada será garantidamente a solução ótima.

Ainda no que diz respeito à fundamentação teórica e prática obtida, pode-se destacar como um resultado expressivo a obtenção de desenvoltura na construção de programas para uma linguagem multi-paradigma bem organizada, o que envolve a fixação e a integração de todos os conceitos mais importantes de linguagens de programação. Nesse contexto, o resultado compatível com os objetivos do projeto é o conhecimento, adquirido pelo aluno, das técnicas mais importantes para a construção, em um sistema prático eficiente (Mozart-Oz), de programas que explorem satisfatoriamente o paradigma de programação por propagação de restrições.

A partir de informações obtidas principalmente junto ao Prof. Dr. Flávio S. C. da Silva, foi construída uma especificação para o primeiro problema prático deste trabalho, objetivando a construção de um programa que, ao mesmo tempo, fosse genérico e levasse em consideração as necessidades do Departamento de Ciência da Computação do IME-USP.

A especificação a ser utilizada pelo usuário não será abordada neste texto e está definida no manual do usuário, disponível juntamente com o código-fonte e com a documentação - cujo objetivo é explicitar o funcionamento do programa aos leitores com conhecimentos básicos na linguagem Oz -, no seguinte arquivo:

horarios.zip

A resolução efetiva do problema é feita com base em um conjunto de dados obtidos a partir de uma transformação dos dados de entrada do usuário. Mesmo após essa transformação, o formato dos dados ainda leva em consideração a facilidade de manipulação pelo programa. Assim, o que será apresentado aqui é o formato de entrada dos dados para um problema hipotético equivalente:

N: o número de dias em que devem estar compreendidas as aulas. Por exemplo: se a grade horária deve compreender os dias de segunda-feira a quinta-feira, tem-se N = 4. Esses dias serão numerados em seqüência, a partir de 1.

As aulas do problema. Cada aula é composta por:

Um número, que identifica univocamente a aula.

Duração, em unidades de 5 minutos.

A lista de horários em que a aula pode começar. Cada horário é um número que representa a quantidade de unidades de 5 minutos decorridas desde o início do dia 1. Observe que há 288 unidades em um dia.

Os números das aulas que não podem ser dadas em intervalos que coincidam com esta aula. Esse tipo de restrição será chamado, informalmente, de restrição de exclusão mútua.

As turmas, ou seja, os oferecimentos de disciplinas. Cada turma é composta por:

Os números das aulas desta turma.

A distância mínima, em dias, que deve haver entre quaisquer duas aulas desta turma.

Idem, para a distância máxima.

Um valor booleano indicando se as aulas desta turma devem ser dadas em horários diferentes, módulo 288. Se esse valor for true, não será possível, por exemplo, ter uma aula começando no horário 96 (8h do dia 1) e outra começando no horário 672 (8h do dia 3).

As preferências, cada uma composta por:

Peso: um número natural estritamente menor que 6.

Os números das aulas envolvidas nesta preferência.

A lista de intervalos de horários com os quais as aulas desta preferência não podem coincidir.

As restrições que devem ser asseguradas são:

	Os domínios iniciais para os horários das aulas.
	As restrições de exclusão mútua.
	As restrições de distância em dias.
	As restrições de desigualdade de horários módulo 288.

Diz-se que uma preferência P foi satisfeita se nenhuma das aulas envolvidas na preferência é dada em um intervalo que coincida com algum dos intervalos definidos em P.

Assim, o valor a ser minimizado é a soma dos pesos das preferências não satisfeitas.

Esse problema é extremamente complexo, o que pode ser ilustrado pelo fato de que o problema da k-coloração dos vértices de um grafo - que, conforme [1], é NP-completo - pode ser reduzido em tempo polinomial para um caso muito particular do problema tratado neste trabalho:

Dados um grafo não-dirigido G = (V, E) e um inteiro positivo k, o problema da k-coloração pode ser resolvido da seguinte maneira:

Defina N = teto(k / 288).

Para cada vértice v_i, defina uma aula A_i tal que:

A_i tem duração 1.

Os horários possíveis para o início de A_i são 0, 1, 2, 3, ..., k-1.

Para toda aula A_j, i ≠ j, A_i tem exclusão mútua com A_j se e somente se existe uma aresta (v_i, v_j).

Defina o conjunto de aulas como A = {A₁, ..., A_|V|}.

Para cada aula A_i que pertence a A, defina uma turma T_i.

Defina o conjunto de Turmas T = {T₁, ..., T_|V|}.

Defina o conjunto de preferências P = {}.

Se existe solução para a instância (N, A, T, P) do problema dos horários, então existe k-coloração dos vértices de G. Caso contrário, não existe.

Devido à grande complexidade desse primeiro problema, não faria sentido desenvolver um algoritmo cujo único objetivo fosse encontrar a solução ótima. Portanto, foi adotada uma abordagem flexível, baseada em uma simplificação do conceito teórico de algoritmo anytime. Um algoritmo anytime, conforme definição em [5], possui as seguintes características:

	Sua execução pode ser interrompida e posteriormente retomada, sem sobrecarga considerável.
	Sua execução pode ser terminada a qualquer momento, resultando em uma solução para o problema.
	A qualidade das soluções fornecidas cresce em função do tempo de execução, de maneira bem comportada.

O algoritmo de fato implementado segue um conjunto mais simples de regras:

	Toda solução encontrada fica imediatamente disponível em um arquivo que contém o conjunto das soluções encontradas durante a execução.
	A execução pode ser terminada a qualquer momento.
	A qualidade das soluções encontradas cresce em função do tempo de execução.

Os principais fatores determinantes para a escolha desse algoritmo foram:

	A busca é completa.
	O usuário tem total poder para decidir qual é o tempo máximo aceitável para a execução do programa. Além disso, pode utilizar seus próprios critérios para verificar, a qualquer momento, se as soluções já encontradas são suficientemente boas.
	Podem ser utilizadas heurísticas para antecipar o aparecimento de soluções boas, pois a escolha de um algoritmo anytime não impede a utilização de outras técnicas.

O formato em que o programa implementado recebe os dados de entrada envolve diversas informações aparentemente adicionais, mas que têm como único objetivo facilitar a utilização prática. Dessas informações, é necessário destacar, para que fiquem claros os processos de resolução e de experimentação, os fatos:

	Cada turma possui um professor. Com essa informação, o programa pode garantir automaticamente a exclusão mútua entre aulas dadas pelo mesmo professor.
	Podem ser especificados conjuntos de turmas, que informalmente serão chamados grupos de exclusão mútua. Todas as aulas de uma turma que pertence a um grupo G possuem exclusão mútua com as aulas de todas as outras turmas de G.

O usuário do programa deve escolher uma das seguintes abordagens para a resolução do problema:

Maximizar o esforço realizado pelo algoritmo para antecipar o aparecimento da solução ótima.

Maximizar o esforço realizado pelo algoritmo para antecipar o aparecimento da primeira solução. Esta forma de execução possui duas outras conseqüências importantes, em relação à abordagem 1:

O número total de soluções encontradas tende a aumentar.

O tempo decorrido até o aparecimento da solução ótima tende a aumentar.

O processo de resolução implementado tem a seguinte estrutura geral:

Tentativa de divisão do problema em casos independentes, através da verificação da existência de professores independentes. Por professor independente, entenda-se um professor cujas aulas não possuem exclusão mútua com nenhuma aula de outro professor.

Cada problema é resolvido da seguinte maneira:

Criação de propagadores para todas as restrições especificadas.

(Este passo só é realizado pela abordagem 1)
Distribuição nas preferências, estando cada ramificação associada a uma preferência P, dividindo a busca entre os casos em que P é satisfeita e os casos restantes. Assim, se a seqüência de preferências do problema é, por exemplo, {P₁, P₂, P₃}, o conjunto de preferências satisfeitas pode ser {P₁, P₂, P₃}, {P₁, P₂}, {P₁, P₃}, {P₁}, {P₂, P₃}, {P₂}, {P₃} ou {}. Essa é justamente a ordem em que será realizada a busca. O estabelecimento dessa ordem é uma tentativa de fazer com que as soluções de baixo custo sejam encontradas rapidamente.

Distribuição - necessária - nos horários das aulas. Em cada nó, a variável escolhida para receber valor será aquela que estiver mais restrita, ou seja, cujo domínio tiver tamanho mínimo. Para escolher o primeiro valor a ser atribuído à variável escolhida, escolhe-se o valor menos restritivo - ou seja: que cause o menor impacto possível nos domínios das demais variáveis -, segundo um critério heurístico - maiores detalhes na documentação do programa. Escolher o valor de fato menos restritivo seria uma operação muito custosa, se considerarmos que tal operação deve ser realizada a cada ponto de decisão da árvore de busca.

Alguns detalhes de implementação, focados no desempenho, merecem ser destacados:

	(Este tópico se refere apenas à abordagem 1) Antes da resolução do problema, é feita uma estimativa, para cada preferência P - veja maiores detalhes dessa estimativa na documentação do programa - do grau de dificuldade da tarefa de se satisfazer P. Através da observação dessas estimativas, podem-se organizar as preferências, em ordem crescente de complexidade. Essa ordenação tem um impacto gigantesco na eficiência do programa, pois afeta a distribuição nas preferências. A título de exemplo, verifique o caso em que a seqüência de preferências é {P₁, P₂, P₃, P₄} e o conjunto de preferências satisfeitas na solução ótima é {P₃, P₄}. Nesse caso, existem 16 valorações possíveis para o conjunto de preferências satisfeitas. Fazendo-se a distribuição com a ordem dada, o conjunto {P₃, P₄} seria a 13º valoração explorada na busca. Utilizando-se uma boa estimativa, que permita a reordenação das preferências como, por exemplo, {P₃, P₄, P₁, P₂}, o conjunto {P₃, P₄} seria a 4º valoração explorada.
	Suponha uma relação de equivalência, entre aulas de uma mesma turma, tal que duas aulas são equivalentes se e somente se possuem a mesma duração e o mesmo conjunto de horários possíveis. Assim, para cada classe de equivalência C, podem-se criar restrições artificiais que imponham uma ordem qualquer dentro de C. Por exemplo: se o conjunto de aulas de determinada turma é {A₁, A₂, A₃, A₄} e as classes de equivalência são {A₁, A₃} e {A₂, A₄}, podem ser criadas restrições para que A₁ seja dada antes de A₃ e A₂ seja dada antes de A₄. A criação desse tipo de restrição - operação tecnicamente chamada de eliminação de simetrias - tem a capacidade de diminuir o tamanho da árvore de busca, mas, nesta aplicação específica, o ganho de eficiência não é marcante.
	Também é feita, para cada aula A, uma estimativa - veja maiores detalhes na documentação - da influência de A na dificuldade de se encontrar uma grade horária. As aulas são postas em ordem decrescente de complexidade, de forma que, em cada nó de decisão, seja escolhida, dentre as variáveis com domínio de tamanho mínimo, a aula de maior complexidade. Essa ordenação tem grande impacto na eficiência, uma vez que é comum haver, em um ponto de decisão, mais de uma variável com domínio de tamanho mínimo.

Como visto, a busca por uma solução qualquer para o primeiro problema deste trabalho constitui um problema NP-completo. Portanto, não seria possível, utilizando-se as técnicas conhecidas, implementar um algoritmo que pudesse oferecer garantias de sempre encontrar uma solução em tempo polinomial. De fato, em muitos casos, o programa implementado pode ter um desempenho muito ruim. Enumerar todos esses casos, prevendo todas as possíveis formas dos dados de entrada, não é uma tarefa viável. Portanto, fez-se necessária uma análise experimental focada no Departamento de Ciência da Computação do IME-USP.

Observe, ainda, que uma análise de caso médio - bastante complicada, devido aos diversos métodos heurísticos utilizados pelo programa - não substituiria a análise experimental, uma vez que seria demasiado genérica, se for levado em conta o fato de que a aplicação deve estar voltada para um Departamento específico.

Todos os experimentos realizados lidam com variações de um exemplo baseado na grade horária do primeiro semestre do ano de 2003. Mais especificamente, todas as entradas construídas possuem o seguinte porte:

	Existem 38 turmas, com 2 aulas cada.
	Para cada turma T, o intervalo mínimo entre cada par de aulas de T é de pelo menos 2 dias.
	O número total de professores (16) não é grande, evitando assim uma simplificação excessiva - em casos com muitos professores, há maiores chances de que o problema possa ser dividido em casos simples, independentes entre si.
	Existem 3 grupos de exclusão mútua, com 5 turmas cada.
	Existem 11 preferências.
	O problema é solúvel.

As 11 variações sobre esse exemplo foram realizadas através das preferências. Todos os dados de exemplo, assim como os resultados obtidos*, estão disponíveis com o programa.

Algumas observações sobre os resultados:

Abordagem 1:

	Em 8 casos, o desempenho foi excelente - o programa terminou em poucos segundos. Em quase todos esses casos, a primeira solução encontrada era a solução ótima.
	Em 3 casos, esta abordagem mostrou-se inviável - mesmo após uma espera de 5 horas, não houve resultados.

Abordagem 2:

	Em 5 casos, o programa terminou em poucos minutos.
	Em 1 caso, o programa terminou em 4 horas.
	Em 5 casos, a primeira solução foi encontrada em menos de 1 segundo**, mas, mesmo após uma espera de 5 horas, o programa não terminou.

As seguintes características, aparentemente, diminuem o consumo de tempo do programa:

	Preferências heterogêneas, ou seja, que abrangem dias diferentes.
	Preferências cujos dias excluídos se concentram no começo da semana***.
	Preferências excessivamente restritivas ou pouco restritivas.

* Os experimentos foram realizados em um computador equipado com processador de 1,8 GHz e com 512 MB de memória RAM.

** É natural que a busca pela primeira solução seja semelhante em todos os casos, uma vez que os dados de exemplo possuem diferenças apenas no que diz respeito às preferências.

*** Excluir os últimos dias da semana resultaria em desempenho semelhante.

O segundo problema abordado neste trabalho ainda está em fase de estudos para implementação. Com isso - e para evitar estender excessivamente o escopo desta monografia -, apresentar-se-á somente a especificação determinada para o problema:

Dados*:

Dois números naturais: n > 0 e k > 0.

Dois conjuntos de pontos de um mesmo plano: P, com n elementos, e G (o conjunto de garagens), com k elementos.

Um conjunto de veículos, cada um com as seguintes características:

Posição inicial (uma garagem).

Capacidade do tanque de combustível.

Número de assentos destinados a passageiros.

Capacidade de carga: limite superior para a soma dos pesos dos passageiros com o peso da carga não humana (incluindo o peso do combustível, que é relevante).

Tipo**.

Peso inicial***.

Dois números racionais positivos: a e b.

Um conjunto de requisições, sendo cada uma composta por:

Um peso: número natural representando o custo do não atendimento da requisição.

Uma origem o e um destino d, sendo o e d elementos de G ou de P.

Um conjunto de objetos a serem transportados entre o e d. É dado o peso de cada objeto.

A quantidade de pessoas a serem transportadas entre o e d.

* Todos os parâmetros numéricos utilizados no problema são adimensionais.

** Um veículo pode ser de dois tipos:

Veículo que, ao fim de um passeio, deve estar em sua posição inicial (a garagem de onde partiu).
Veículo que, ao fim de um passeio, deve estar em uma garagem qualquer de G.

*** Inicialmente, não há qualquer tipo de carga nos veículos. Em particular, os tanques de combustível estão vazios.

Tem-se:

	O peso de x unidades de combustível é P(x) = a ּ x.
	O consumo instantâneo de combustível (unidades de volume por unidade de distância) de um veículo com peso total y é C(y) = b ּ y.
	Partindo-se das duas fórmulas acima, é possível determinar (Figura 4.3) o consumo de combustível de um veículo no percurso de uma distância d.

O objetivo é determinar, para cada veículo:

	A quantidade de combustível que o tanque do veículo deve receber inicialmente.
	O passeio (possivelmente vazio) que o veículo deve fazer e as requisições que serão atendidas durante o passeio.

A função de custos é definida como c(s) = u + p, onde s é uma solução, u é o consumo total de combustível em s e p é a soma dos pesos das requisições não atendidas por s. Informalmente, com essa função de custos está sendo feita a suposição de que, dada uma requisição R, o peso de R representa o custo, em unidades de combustível, do não atendimento de R.

5. Conclusão

A compreensão profunda de um sistema que ofereça suporte à programação de restrições envolve uma dedicação que transcende o esforço necessário para o aprendizado de uma linguagem de programação, uma vez que circunscreve o domínio teórico e prático de mecanismos de resolução. Mesmo após atingida essa compreensão, o tratamento eficiente de problemas complexos de Otimização Combinatória não deixa de ser uma tarefa bastante árdua. Porém, as ferramentas oferecidas pela programação de restrições têm a capacidade de amenizar essa tarefa, em especial pela automatização do gerenciamento das principais estruturas de dados envolvidas na busca de soluções e pela agilização do processo de experimentação de diferentes técnicas.

Apoio

O presente trabalho foi realizado com o apoio do Conselho Nacional de Desenvolvimento Científico e Tecnológico - CNPq -, através do Programa Institucional de Bolsas de Iniciação Científica - PIBIC.

Referências

[1]: GAREY, M., JOHNSON, D. Computers and Intractability: A Guide to the Theory of NP-completeness. San Francisco: W. H. Freeman, 1979.

[2]: MÜLLER, T. Constraint Propagation in Mozart. Saarbrücken: 2001. PhD thesis, Universität der Saarlandes.

[3]: SCHULTE, C. Programming Constraint Services. Saarbrücken: 2000. PhD thesis, Universität der Saarlandes.

[4]: BARTÁK, R. Constraint Programming: In Pursuit of the Holy Grail. In: Proceedings of WDS99 (invited lecture). Prague: 1999.

[5]: DEAN, T., BODDY, M. An Analysis of Time-Dependent Planning. In: Proceedings of the Seventh National Conference on AI (AAAI-88).

[6]: HENZ, M, WÜRTZ, J. Using Oz for College Timetabling. In: BURKE, E, ROSS, P. (editors). The Practice and Theory of Automated Time Tabling: The Selected Proceedings of the 1st International Conference on the Practice and Theory of Automated Time Tabling. Edinburgh: 1995. p. 162-177.

[7]: WALLACE, M. Survey: Practical Applications of Constraint Programming. Constraints Journal, v. 1, nº 1, 1996.

[8]: BARTÁK, R. On-line Guide to Constraint Programming. Prague: 1998. (http://kti.mff.cuni.cz/~bartak/constraints)

[9]: The Mozart Programming System. (http://mozart-oz.org)

Segunda Parte: Relações entre o Curso de Graduação e a Iniciação Científica

1. Desafios e Frustrações

O grande desafio deste trabalho foi escolher a abordagem a ser utilizada para o tratamento do primeiro problema prático - o problema da construção de grades horárias para o Departamento de Ciência da Computação do IME-USP. O primeiro programa desenvolvido tratava o problema de maneira óbvia e explorava mal o paradigma de programação por propagação de restrições, o que resultava em um enorme consumo de tempo, mesmo no tratamento de instâncias de tamanho reduzido. Lidar com esse desafio exigiu uma compreensão melhor do problema - especialmente do fato de que, em uma versão mais simples, ele constitui um problema NP-completo -, um aprofundamento teórico e prático no sistema Mozart-Oz, uma breve pesquisa sobre técnicas comuns utilizadas no ataque a problemas complexos, além de, naturalmente, raciocínio e criatividade.

A complexidade desse primeiro problema prático teve como conseqüência o atraso no tratamento do segundo problema, o que, embora não tenha sido uma surpresa, foi de certo uma frustração, pois inviabilizou a total inclusão neste trabalho dos resultados da Iniciação Científica.

Uma frustração menor está relacionada a um dos passos da resolução do primeiro problema: o programa desenvolvido apenas encontra o que chamamos de professores independentes, mas poderia encontrar todos os conjuntos independentes minimais de professores - problema equivalente à determinação dos componentes conexos de um grafo. O programa deixou de ganhar esse aprimoramento, pois se fez necessário evitar uma redução ainda maior do tempo disponível para o tratamento do segundo problema.

2. Disciplinas Mais Relevantes

Naturalmente, este trabalho não poderia ter sido desenvolvido sem os conhecimentos básicos obtidos nas seguintes disciplinas: Introdução à Computação, Princípios de Desenvolvimento de Algoritmos e Estruturas de Dados.

As disciplinas de Cálculo - exceto Cálculo Diferencial e Integral III - foram importantes já na especificação formal do segundo problema prático.

A disciplina mais importante no apoio à compreensão do paradigma de programação por propagação de restrições - objetivo principal deste trabalho - foi, sem dúvida, Conceitos Fundamentais de Linguagens de Programação, que torna muito menos intrincado o estudo de uma linguagem multi-paradigma, como o Oz.

O aumento da eficiência do programa implementado seria uma tarefa mais árdua se não contasse com as técnicas apresentadas pela disciplina Introdução à Inteligência Artificial.

3. Interação Com o Orientador

A relação aluno-orientador foi bastante serena - o que, devido às personalidades de ambos, não poderia ser diferente. O orientador deu bastante liberdade ao aluno - atitude importante em qualquer trabalho de pesquisa científica -, não deixando, por outro lado, de lhe dar apoio nos momentos em que isso se fez necessário.

4. Aplicações Práticas de Conceitos Estudados Durante o Curso

Como o programa implementado sofreu diversas alterações, foi possível observar os ganhos de desempenho resultantes da utilização de técnicas clássicas de Inteligência Artificial em um problema complexo de Otimização Combinatória. A grosso modo, pode-se dizer que o programa surgiu como um algoritmo de backtracking - pois explorava mal os recursos de propagação de restrições do Mozart-Oz -, evoluiu para a utilização efetiva de técnicas de consistência e ganhou diversas outras pequenas alterações - como a estratégia de escolha do valor menos restritivo, ao ser instanciada uma variável.

No entanto, mais interessante foi, ao entrar em contato com a linguagem Oz, perceber que me limitar ao paradigma imperativo - mesmo com o auxílio da orientação a objetos - seria uma extrema subutilização do sistema Mozart-Oz. Com isso, ficou claro o poder da visão global oferecida pela disciplina Conceitos Fundamentais de Linguagens de Programação. Porém, minha dificuldade inicial também explicita o fato de que essa visão global está ausente em praticamente todas as disciplinas do curso.

5. Como Aprimorar os Conhecimentos

Dentre as diversas maneiras possíveis de tornar mais ampla e profunda a investigação sobre Programação de Restrições, podem-se destacar:

	A experimentação com outros ambientes de programação que dêem suporte à Programação de Restrições.
	Um estudo ainda mais abrangente do Mozart-Oz - no que diz respeito à Programação de Restrições -, através dos diversos tutoriais disponíveis com o sistema.
	Uma incursão pela área de Otimização Combinatória, conhecendo-se os problemas mais famosos, assim como as abordagens mais comuns utilizadas no tratamento de problemas complexos - algoritmos de aproximação, algoritmos probabilísticos, métodos heurísticos etc. Com essa base, seria mais simples verificar em quais casos a Programação de Restrições pode agilizar o desenvolvimento sem ter como ônus uma perda de eficiência.

	O número total de soluções encontradas tende a aumentar.
	O tempo decorrido até o aparecimento da solução ótima tende a aumentar.