Edmar Hell Kampke Novas Estratégias para Obtenção de Limitantes Inferiores para o Problema de Tabela-Horário de Universidades Vitória - ES 2020 Edmar Hell Kampke Novas Estratégias para Obtenção de Limitantes Inferiores para o Problema de Tabela-Horário de Universidades Tese de Doutorado apresentada ao Programa de Pós-Graduação em Informática (PPGI) da UFES como parte dos requisitos para ob- tenção do Grau de Doutor em Ciência da Computação. Universidade Federal do Espírito Santo - UFES Centro Tecnológico Programa de Pós-Graduação em Informática Orientador: Prof. Dr. Geraldo Regis Mauri Coorientadora: Profa. Dra. Maria Claudia Silva Boeres Vitória - ES 2020 Ficha catalográfica disponibilizada pelo Sistema Integrado de Bibliotecas - SIBI/UFES e elaborada pelo autor K15n Kampke, Edmar Hell, 1982- KamNovas Estratégias para Obtenção de Limitantes Inferiores para o Problema de Tabela-Horário de Universidades / Edmar Hell Kampke. - 2020. Kam112 f. : il. KamOrientador: Geraldo Regis Mauri. KamCoorientadora: Maria Claudia Silva Boeres. KamTese (Doutorado em Informática) - Universidade Federal do Espírito Santo, Centro Tecnológico. Kam1. Otimização Combinatória. 2. Modelos Matemáticos. 3. Teoria dos Grafos. 4. Programação Linear. 5. Universidades e Faculdades. I. Mauri, Geraldo Regis. II. Boeres, Maria Claudia Silva. III. Universidade Federal do Espírito Santo. Centro Tecnológico. IV. Título. CDU: 004 Edmar Hell Kampke Novas Estratégias para Obtenção de Limitantes Inferiores para o Problema de Tabela-Horário de Universidades Tese de Doutorado apresentada ao Programa de Pós-Graduação em Informática (PPGI) da UFES como parte dos requisitos para ob- tenção do Grau de Doutor em Ciência da Computação. Trabalho Aprovado. Vitória - ES, 07 de Agosto de 2020. Prof. Dr. Geraldo Regis Mauri Orientador Profa. Dra. Maria Claudia Silva Boeres Coorientadora Prof. Dr. André Renato Sales Amaral Universidade Federal do Espírito Santo (UFES) Profa. Dra. Lucia Catabriga Universidade Federal do Espírito Santo (UFES) Prof. Dr. Luciano Lessa Lorenzoni Instituto Federal de Educação, Ciência e Tecnologia do Espírito Santo (IFES) Prof. Dr. Haroldo Gambini Santos Universidade Federal de Ouro Preto (UFOP) Vitória - ES 2020 Aos meus pais, Helmar e Ilza. Agradecimentos Agradeço a Deus, por guiar os meus passos e renovar minhas forças a cada dia. Agradeço aos meus pais, Helmar e Ilza, pelo amor e apoio incondicional. Obrigado pelas lições de vida e fé que me tornaram uma pessoa forte e persistente. Aos meus irmãos, Vera e Edgar, e demais familiares e amigos, pelo carinho, apoio e tantos momentos de alegria. Agradeço ao meu orientador, Professor Geraldo, pelo conhecimento compartilhado, pela atenção, por confiar em mim e pelas várias oportunidades que me fizeram crescer na vida acadêmica. Agredeço à minha coorientadora, Professora Maria Claudia, e também a Professora Maria Cristina, por acreditarem em mim e terem me dado essa oportunidade. Faltam palavras para descrever o meu agradecimento pelo incentivo, paciência e compreensão que sempre demonstraram por mim. Vocês sempre serão um grande exemplo para mim. Aos Membros da Banca Examinadora pela participação na defesa deste trabalho e pelas valiosas contribuições. Aos demais professores, colaboradores e colegas do Programa de Pós-Graduação em Informática (PPGI) da Universidade Federal do Espírito Santo (UFES), que sempre estiveram dispostos a ajudar. Em especial, agradeço aos colegas do Labotim, que muito me ajudaram no desenvolvimento deste trabalho. Entre eles destaco a colega Erika pela parceria nos anos iniciais do doutorado e o colega André pelo apoio na análise estatística. Ao Departamento de Computação (DCOMP) do Centro de Ciências Exatas, Natu- rais e da Saúde (CCENS) da UFES, pelo apoio prestado na realização deste trabalho. Aos colegas que me acompanharam nessa jornada e estiveram comigo nas muitas viagens. Um agradecimento especial à Professora Juliana, amiga e companheira de estudo e trabalho. A todos que contribuíram, direta ou indiretamente, para conclusão dessa etapa da minha vida. Cheguei até aqui porque tive a oportunidade de conhecer, conviver e aprender com pessoas muito especiais. Muito obrigado! “Pensava que nós seguíamos caminhos já feitos, mas parece que não os há. O nosso ir faz o caminho." (C. S. Lewis) Resumo O Problema de Tabela-Horário de Universidades (PTHU) é um dos mais pesquisados dentre os problemas de Otimização Combinatória (OC). Este problema consiste em alocar uma sequência de aulas nas salas disponíveis para um período de tempo predeterminado (tabela-horário) considerando necessidades de alunos, professores e satisfazendo algumas restrições. Várias formulações para o PTHU podem ser encontradas na literatura pois as necessidades que devem ser atendidas na construção da tabela-horário variam para cada instituição. Neste trabalho é considerado o PTHU baseado na formulação de currículos de cursos (CB-CTT) proposta na segunda edição do campeonato internacional de tabela- horário (ITC-2007). Até o momento, diversos métodos baseados em Programação Linear Inteira (PLI) foram propostos na literatura para obter valores de limitantes inferiores desse problema de minimização. Neste trabalho são apresentadas novas estratégias baseadas no princípio dividir para conquistar com o intuito de obter valores de limitantes inferiores. As estratégias apresentadas usam a biblioteca METIS para particionar o problema original em subproblemas que são resolvidos com o otimizador CPLEX. Experimentos computacio- nais foram executados nas instâncias de referência usadas no ITC-2007 e os resultados foram comparados com os melhores limitantes inferiores encontrados na literatura. Esses resultados mostram que as estratégias propostas são capazes de melhorar o valor do melhor limitante inferior atualmente conhecido em duas das 21 instâncias e provar a otimalidade em outras 15 instâncias. Palavras-chaves: Tabela-Horário de Universidades. Limitantes Inferiores. Particiona- mento. Relaxações. Abstract The University Timetabling Problem (UTP) is one of the most researched topics in the field of combinatorial optimization. This problem consists of allocating a set of lectures to available rooms and periods (timetable) considering students and teachers requests and constraints. Several mathematical formulations for the UTP can be found in the literature once specificities of this problem can vary for each institution. The formulation considered in this work is based on courses curricula of an university, proposed in the second International Timetabling Competition (ITC-2007). So far, several methods based on integer linear programming have been proposed in the literature to obtain lower bounds for this minimization problem. Here, new strategies based on the divide and conquer principle are presented in order to obtain lower bounds for the problem. In this way, the original problem is partitioned with METIS library into sub-problems, each one solved by CPLEX solver. Computational experiments were performed on the ITC-2007 benchmark instances and the results were compared to the best lower bounds found in the literature. These results show the strategies proposed are able to improve the best known lower bounds for two of 21 instances tested and prove the optimality for another 15 instances. Keywords: University Timetabling. Lower Bounds. Partitioning. Relaxations. Lista de figuras Figura 1 – Arquivo de exemplo - Instância Toy. . . . . . . . . . . . . . . . . . . . 38 Figura 2 – Arquivo de resposta - Instância Toy. . . . . . . . . . . . . . . . . . . . 39 Figura 3 – Grafo GU da instância Toy. . . . . . . . . . . . . . . . . . . . . . . . . 62 Figura 4 – Grafo GC da instância Toy. . . . . . . . . . . . . . . . . . . . . . . . . 63 Figura 5 – Grafo GU da instância Toy particionado em 2 subproblemas (k = 2). . 67 Figura 6 – Grafo GC da instância Toy particionado em 2 subproblemas (k = 2). . 69 Figura 7 – Grafo GC da instância Toy − Arestas tracejadas representam o currículo Cur1. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69 Figura 8 – Grafo GC da instância Toy − Vértice tracejado representa as variáveis de cópia da disciplina TecCos. . . . . . . . . . . . . . . . . . . . . . . . 72 Figura 9 – Fluxograma dos métodos propostos. . . . . . . . . . . . . . . . . . . . 73 Lista de tabelas Tabela 1 – Comparação de limitantes inferiores obtidos pelos modelos matemáticos propostos por Burke et al. (2010) e Lach e Lübbecke (2012). . . . . . . 79 Tabela 2 – Comparação de limitantes inferiores obtidos pelo método C-partition com método proposto por Hao e Benlic (2011). . . . . . . . . . . . . . 80 Tabela 3 – Número de subproblemas γ que obteve o melhor valor de limitante inferior e o valor máximo de k (δ). . . . . . . . . . . . . . . . . . . . . 83 Tabela 4 – Limitantes inferiores obtidos pelos métodos propostos na Etapa 1. . . . 85 Tabela 5 – Limitantes inferiores obtidos pelos métodos propostos na Etapa 2. . . . 88 Tabela 6 – Comparação de limitantes inferiores obtidos pelo método C-partition-org com outros métodos (14 instâncias). . . . . . . . . . . . . . . . . . . . 91 Tabela 7 – Comparação de limitantes inferiores obtidos pelo método C-partition-org com outros métodos (21 instâncias). . . . . . . . . . . . . . . . . . . . 92 Tabela 8 – Resumo das principais contribuições do método C-partition-org e demais trabalhos da literatura. . . . . . . . . . . . . . . . . . . . . . . . . . . . 93 Tabela 9 – Resultados do primeiro Teste de Nemenyi. . . . . . . . . . . . . . . . . 98 Tabela 10 – Resultados do segundo Teste de Nemenyi. . . . . . . . . . . . . . . . . 99 Tabela 11 – Análise comparativa de tempo do método C-partition-org com outros trabalhos da literatura. . . . . . . . . . . . . . . . . . . . . . . . . . . . 100 Lista de abreviaturas e siglas API Application Programming Interface CB-CTT Curriculum-Based Course Timetabling GRASP Greedy Randomized Adaptive Search Procedure ITC International Timetabling Competition OC Otimização Combinatória PLI Programação Linear Inteira PTHE Problema de Tabela-Horário de Escolas PTHU Problema de Tabela-Horário de Universidades RFt Restrições Fortes RFc Restrições Fracas Lista de símbolos B Conjunto binário {0, 1} Z Conjunto de números inteiros C Conjunto de disciplinas U Conjunto de currículos D Conjunto de dias P Conjunto de períodos R Conjunto de salas T Conjunto de professores Cu Conjunto de disciplinas que pertencem ao currículo u ∈ U Ct Conjunto de disciplinas lecionadas pelo professor t ∈ T Pd Conjunto de períodos do dia d ∈ D Uc Conjunto de currículos no qual a disciplina c ∈ C pertence dp Dia do período p ∈ P lctc Quantidade de aulas da disciplina c ∈ C mldc Número mínimo de dias de aula da disciplina c ∈ C stc Quantidade de alunos matriculados na disciplina c ∈ C capr Capacidade da sala r ∈ R N Subconjunto de C × P em que (c, p) representa a disponibilidade da disciplina c ser lecionada no período p N Subconjunto de C × P em que (c, p) representa a indisponibilidade da disciplina c ser lecionada no período p Nc Conjunto de períodos que a disciplina c ∈ C não possui indisponibilidade Np Conjunto de disciplinas que não possuem indisponibilidade no período p ∈ P Ψ Conjunto de todas as diferentes capacidades de sala C≥ψ Conjunto de disciplinas que a quantidade de alunos matriculados é maior que ψ ∈ Ψ R≥ψ Conjunto de salas que possuem capacidade maior que ψ ∈ Ψ WRC Penalidade da restrição fraca S1 (capacidade de sala) WMD Penalidade da restrição fraca S2 (número mínimo de dias de aula) WCC Penalidade da restrição fraca S3 (aulas isoladas) WRS Penalidade da restrição fraca S4 (estabilidade de sala) Sumário 1 INTRODUÇÃO . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.1 Motivação . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 1.2 Objetivos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.2.1 Objetivos gerais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 29 1.2.2 Objetivos específicos . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.3 Principais contribuições . . . . . . . . . . . . . . . . . . . . . . . . . . 30 1.4 Publicações . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31 1.5 Organização do trabalho . . . . . . . . . . . . . . . . . . . . . . . . . 32 2 DESCRIÇÃO DO PROBLEMA . . . . . . . . . . . . . . . . . . . . . 35 3 TRABALHOS CORRELATOS . . . . . . . . . . . . . . . . . . . . . 41 3.1 Modelos matemáticos e limitantes . . . . . . . . . . . . . . . . . . . . 42 3.1.1 Modelo compacto de Burke et al. (2010) e limitantes inferiores . . . . . . . 43 3.1.2 Branch-and-cut de Burke et al. (2012) . . . . . . . . . . . . . . . . . . . . 46 3.1.3 Modelo de duas fases de Lach e Lübbecke (2012) . . . . . . . . . . . . . . 47 3.1.4 Abordagem dividir para conquistar de Hao e Benlic (2011) . . . . . . . . . 49 3.1.5 Geração de colunas de Cacchiani et al. (2013) . . . . . . . . . . . . . . . . 51 3.1.6 Codificações SAT de Achá e Nieuwenhuis (2014) . . . . . . . . . . . . . . 52 3.1.7 Novas abordagens de Bagger et al. (2019) . . . . . . . . . . . . . . . . . . 52 3.1.8 Observações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.2 Métodos heurísticos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.1 Vencedores do ITC-2007 . . . . . . . . . . . . . . . . . . . . . . . . . . . 56 3.2.2 Métodos heurísticos posteriores ao ITC-2007 . . . . . . . . . . . . . . . . 57 3.2.3 Observações finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 59 4 METODOLOGIA . . . . . . . . . . . . . . . . . . . . . . . . . . . . 61 4.1 Representação do PTHU usando grafos . . . . . . . . . . . . . . . . . 62 4.1.1 Grafo GU . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62 4.1.2 Grafo GC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.2 METIS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 4.3 Métodos sem variáveis de cópia . . . . . . . . . . . . . . . . . . . . . 65 4.3.1 U-partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 65 4.3.2 C-partition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.4 Métodos com variáveis de cópia . . . . . . . . . . . . . . . . . . . . . 69 4.5 Fluxograma dos métodos propostos . . . . . . . . . . . . . . . . . . . 72 5 EXPERIMENTOS E RESULTADOS . . . . . . . . . . . . . . . . . . 75 5.1 O conjunto de instâncias comp01-comp21 (CB-CTT/ITC-2007) . . 75 5.2 Detalhes de implementação e aplicação dos métodos propostos . . 76 5.3 Experimentos computacionais e análise dos resultados . . . . . . . . 77 5.3.1 Análise dos resultados obtidos . . . . . . . . . . . . . . . . . . . . . . . . 84 5.3.2 Análise comparativa com resultados da literatura . . . . . . . . . . . . . . 89 6 CONCLUSÕES E TRABALHOS FUTUROS . . . . . . . . . . . . . 103 REFERÊNCIAS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 107 25 1 Introdução Os problemas de Otimização Combinatória (OC) estão presentes em diversas atividades cotidianas e são comuns em diversas áreas, como exemplo, na criação de rotas de veículos para entrega de encomendas, no planejamento das tarefas a serem executadas por uma indústria e na elaboração de horários escolares. Esses problemas podem ser representados como a minimização ou maximização de uma função matemática, também denominada função objetivo. As variáveis da função objetivo são denominadas de variáveis de decisão e devem ser estritamente inteiras, além de obedecer a certas restrições. Dessa forma, um problema de OC pode ser matematicamente definido como (GOLDBARG; LUNA, 2005): Minimizar (Maximizar) f(X) sujeito a gj(X) {6,=,>} bj ∀ j ∈ {1, 2, . . . ,m} (1.1) xLi 6 xi 6 xUi ∀ i ∈ {1, 2, . . . , n} (1.2) xi ∈ Z ∀ i ∈ {1, 2, . . . , n} (1.3) sendo X = (x1,x2,. . . ,xn) o vetor das n variáveis de decisão, f(X) a função objetivo, gj(X) a j-ésima restrição, podendo esta ser uma desigualdade ou uma igualdade, e bj que é denominado de termo independente da j-ésima restrição. O número de restrições de desigualdade ou igualdade é m. Os limites das variáveis de decisão são determinados através das expressões (1.2), em que xLi é o limite inferior e xUi é o limite superior da i-ésima variável de decisão. Por fim, o conjunto de restrições (1.3) garante que as variáveis de decisão assumam apenas valores inteiros. Segundo Wolsey (1998), se a função objetivo e as restrições de um problema de OC forem lineares, então ele é considerado como um problema de Programação Linear Inteira (PLI). De forma geral, um problema de PLI, com dimensões reais, possui muitas variáveis de decisão. Por isso, a quantidade de combinações para esses valores é muito grande, e encontrar a melhor combinação de valores que atenda as restrições do problema e de forma rápida é uma tarefa árdua. Os problemas de escalonamento (scheduling) estão entre os mais pesquisados dentre os problemas de OC (BABAEI; KARIMPOUR; HADIDI, 2015), e tratam da alocação de 26 Capítulo 1. Introdução recursos em determinados horários. Os problemas de tabela-horário são um subconjunto importante dos problemas de scheduling, cujas aplicações são variadas, como exemplo, na elaboração das escalas de trabalho de funcionários (DELLA CROCE; SALASSA, 2014), no agendamento de partidas para campeonatos esportivos (RIBEIRO; URRUTIA, 2012) e na elaboração de horários escolares (SANTOS; OCHI; SOUZA, 2005). No caso específico da tabela-horário educacional, o problema consiste em alocar um conjunto de aulas em um número pré-determinado de dias e horários, satisfazendo restrições pessoais (professores e alunos), do espaço físico disponível e da instituição. A solução manual deste tipo de problema não é uma tarefa simples, já que é difícil contemplar todos os anseios das partes envolvidas. Além disso, as escolas (universidades) precisam resolver o problema anualmente (semestralmente). Dessa maneira, atenção especial tem sido dada a solução automática de tabela- horário. Começando com o trabalho de Gotlieb (1962), o problema de tabela-horário educacional recebeu grande destaque na área de OC, tendo sido publicados diversos trabalhos desde então, como mostrado nas pesquisas de Schaerf (1999), Lewis (2008), Babaei, Karimpour e Hadidi (2015) e Bettinelli et al. (2015). 1.1 Motivação Na literatura, diversas formulações para o problema de tabela-horário educacional são apresentadas, já que as restrições variam de acordo com a instituição envolvida. No entanto, todas as formulações podem ser classificadas em uma das três categorias (SCHAERF, 1999): • Tabela-horário de Escola - Programação semanal de aulas para as turmas da escola, de tal forma que professores não lecionem aulas para duas turmas ao mesmo tempo e que turmas não assistam mais de uma aula no mesmo horário. • Tabela-horário de Universidade - Programação semanal das aulas das disciplinas universitárias sem sobreposição de aulas que tenham alunos em comum. • Tabela-horário de Exames - Programação para aplicação dos exames das disci- plinas, sem sobreposição de exames das disciplinas que tenham alunos em comum e procurando alocar os exames dos alunos em dias com o maior intervalo possível. Segundo Schaerf (1999), o Problema de Tabela-Horário de Universidades (PTHU) geralmente tem mais restrições que o Problema de Tabela-Horário de Escolas (PTHE), pois no PTHE as turmas são conjuntos disjuntos de alunos, enquanto que no PTHU um aluno pode estar matriculado em mais de uma disciplina, ou seja, nesse caso é considerada a restrição que as disciplinas com alunos em comum não podem ter aulas alocadas no 1.1. Motivação 27 mesmo horário. Além disso, no PTHU normalmente as salas e suas capacidades também são consideradas, enquanto no PTHE são normalmente desconsideradas, pois na maioria dos casos se assume que cada turma terá suas aulas em uma única sala, que por sua vez possui capacidade adequada para a quantidade de alunos da turma. Schaerf (1999) afirma também que o PTHU está entre os mais difíceis da área de OC. O PTHU pode ser classificado NP-completo para a maioria das formulações, uma vez que o problema de coloração de grafos pode ser reduzido em tempo polinomial ao PTHU (SCHAERF, 1999; LEWIS, 2008). Assim, a solução exata só pode ser garantida em tempo computacional viável para instâncias bem pequenas, que não correspondem às instâncias reais da maioria das universidades. Contudo, mesmo com tempo ilimitado, em alguns casos não é possível encontrar uma solução que atenda todas as restrições consideradas na formulação do PTHU. Por isso, o conjunto de restrições é particionado normalmente em dois grupos: Restrições Fortes (RFt) e Restrições Fracas (RFc). O conjunto RFt é composto por aquelas restrições que não podem ser violadas. Elas restringem o conjunto de soluções para impedir situações irreais, como exemplo, alunos assistindo mais de uma aula no mesmo horário ou uma sala sendo alocada para mais de uma aula no mesmo horário. Se uma tabela-horário não viola nenhuma restrição forte ela é dita ser uma solução viável do PTHU. Já o conjunto RFc é composto por aquelas restrições que não interferem na via- bilidade da solução, mas refletem certas preferências das instituições. É desejável, por exemplo, que um grupo de alunos não tenha aulas isoladas durante o dia e que aulas da mesma disciplina sejam lecionadas na mesma sala. As restrições fracas podem possuir pesos diferentes para refletir sua importância na qualidade da solução do PTHU. Dessa forma, o objetivo do PTHU é encontrar uma tabela-horário viável e que minimize a quantidade de violações das restrições do conjunto RFc, sendo assim um problema de minimização. Levando em consideração que existem diferentes formulações para o PTHU, já que as restrições consideradas variam entre as universidades, uma dificuldade adicional surge ao comparar a qualidade dos resultados obtidos pelos métodos propostos para cada formulação. Com o intuito de estabelecer uma definição precisa do problema, além de apresentar um conjunto de instâncias para serem usadas como benchmark e incentivar a comunidade acadêmica a estudar os problemas de tabela-horário, a European Metaheuristics Network (http://www.metaheuristics.net), financiada pela conferência internacional sobre teoria e prática de tabela-horário - PATAT (http://www.patatconference.org), organiza campeona- tos internacionais de tabela-horário (International Timetabling Competition-ITC ). Esses 28 Capítulo 1. Introdução campeonatos permitem a comparação de performance entre diferentes métodos de solução, já que a formulação e o conjunto de instâncias é igual para todos os competidores. Em 2002 foi realizada a primeira edição do ITC (ITC-2002) com o objetivo de atrair pesquisadores. O ITC-2002 abordou o PTHU que considera a matrícula de alunos em disciplinas, sendo que cada disciplina é representada por uma única aula (evento) e possui um conjunto de requisitos (exigências) para sua realização. Cada disciplina deve ser alocada em uma sala com capacidade superior ao número de alunos matriculados e que atenda todas as exigências da disciplina. Após o sucesso do ITC-2002, a segunda edição foi realizada em 2007 (ITC-2007). A inovação do ITC-2007 foi distinguir o problema de tabela-horário em três formu- lações distintas, cada uma delas com seu próprio conjunto de instâncias. Essas formulações correspondem ao problema de tabela-horário de exames, ao PTHU considerando a solicita- ção de matrícula dos estudantes (Post Enrolment based Course Timetabling, PE-CTT) e ao PTHU considerando os currículos dos cursos (Curriculum-Based Course Timetabling, CB-CTT). Além disso, os organizadores do ITC-2007 disponibilizaram dois programas, denominados benchmark e validator. O programa benchmark analisa as configurações do computador com o objetivo de informar o tempo limite de execução do algoritmo, sendo que essa quantidade de tempo é equivalente ao tempo limite de execução do algoritmo nos computadores do campeonato. Já o programa validator faz a validação dos resultados obtidos, permitindo assim que os competidores verificassem alguma incongruência nos seus algoritmos. O website da competição (http://www.cs.qub.ac.uk/itc2007) apresenta outras informações sobre o ITC-2007. Por fim, em 2011 foi realizada a terceira edição (ITC-2011), abordando pela primeira vez o problema de tabela-horário de escolas de ensino médio. O objetivo dessa competição foi permitir que pesquisadores experimentem suas técnicas em um conjunto de instâncias extraídas de escolas reais que representam bem o problema que é enfrentado na prática. Durante o desenvolvimento dessa pesquisa foi lançada a quarta edição da competição (ITC-2019). Essa edição também aborda o PTHU, porém como a previsão de término da competição é o mês de agosto de 2020, neste trabalho o problema abordado foi o PTHU da formulação CB-CTT do ITC-2007. A formulação CB-CTT foi escolhida dentre as três formulações do ITC-2007 por ser a que mais se aproxima da realidade das universidades brasileiras. É importante ressaltar que uma grande contribuição do ITC-2007 é a disponi- bilização de um conjunto de instâncias usadas no campeonato. No caso da formulação CB-CTT, o ITC-2007 disponibilizou 21 instâncias reais da Universidade de Udine, Itália, de diferentes tamanhos, para serem usadas como benchmark. Essas instâncias foram divididas em três grupos de sete instâncias cada, sendo que as instâncias do primeiro grupo foram 1.2. Objetivos 29 disponibilizadas no primeiro dia da competição. Duas semanas antes do fim da competição, as instâncias do segundo grupo foram disponibilizadas para os competidores. O último grupo de instâncias só foi disponibilizado após o término da competição, pois foram usadas para classificar os melhores competidores. Diante disso, pode-se resumir que o ITC-2007 contribuiu de várias formas com a comunidade acadêmica que pesquisa problemas de tabela-horário, mas principalmente com a definição das formulações e a disponibilização das instâncias. Isso pode ser comprovado com vários trabalhos na literatura que propõem métodos de solução para a formulação CB-CTT (BETTINELLI et al., 2015), mesmo após o término da competição. Dentre os métodos de solução, os mais comuns são os métodos heurísticos, como Simulated Annealing (BELLIO et al., 2016), Greedy Randomized Adaptive Search Procedure (GRASP) (KAMPKE et al., 2015) e Busca Tabu (LÜ; HAO, 2010). Além de métodos de solução, alguns trabalhos na literatura apresentam modelos matemáticos e métodos para encontrar limitantes inferiores para o PTHU da formulação CB-CTT. A importância desses métodos está no fato de permitir a avaliação da qualidade das soluções obtidas e até mesmo provar a otimalidade delas. Assim, considerando que as instâncias e a formulação CB-CTT do ITC-2007 são amplamente conhecidas, e que mesmo 13 anos após o término do campeonato a otimilidade das melhores soluções para algumas instâncias ainda não foi provada, surge portanto a motivação para o desenvolvimento deste trabalho. Por fim, uma outra motivação para o desenvolvimento deste trabalho está no fato que até o momento não foi encontrado na literatura algum método que use a abordagem dividir para conquistar com a biblioteca METIS para encontrar limitantes inferiores para a formulação CB-CTT, sendo que em outros problemas essa combinação encontrou limitantes de qualidade e de forma rápida (RIBEIRO; LORENA, 2008; MAURI; LORENA, 2012; MAURI, 2019). 1.2 Objetivos Esta seção é dividida em objetivos gerais (Subseção 1.2.1) e específicos (Subse- ção 1.2.2). 1.2.1 Objetivos gerais Propor e analisar novas estatégias para obtenção de limitantes inferiores para a formulação CB-CTT do PTHU proposto no ITC-2007. 30 Capítulo 1. Introdução 1.2.2 Objetivos específicos 1. Identificar e compreender modelos matemáticos para serem usados na obtenção de limitantes inferiores da formulação CB-CTT do PTHU; 2. Detectar relaxações nos modelos matemáticos que forneçam valores de limitantes inferiores de qualidade com baixo tempo computacional; 3. Definir maneiras de dividir o problema original, relaxando restrições, em subproble- mas independentes; 4. Implementar métodos que dividem o problema original em subproblemas e os resolver com um método de programação matemática; 5. Identificar meios de tornar as relaxações mais fortes, ou seja, modelar as restrições de forma a ficarem mais próximas das originais e obter melhores valores de limitantes inferiores; 6. Comparar os resultados experimentais dos valores de limitantes inferiores obtidos e a quantidade de tempo usada para obter esses valores, em relação ao que é encontrado atualmente na literatura. 1.3 Principais contribuições As principais contribuições desta tese estão relacionadas com a apresentação de quatro novos métodos, baseados na abordagem de programação dividir para conquistar. Esses métodos usam a biblioteca METIS para particionar (dividir) o problema original em problemas menores, relaxando assim algumas restrições. Dessa forma, encontram valores de limitantes inferiores para o PTHU abordado. Além da apresentação dos métodos, uma outra contribuição está relacionada com o tempo necessário para se encontrar os resultados, já que foi possível encontrar resultados 45,19% mais rápido do que outras abordagens da literatura, como as codificações SAT de Achá e Nieuwenhuis (2014). Em relação aos valores de limitantes inferiores obtidos pelos métodos, foi possível observar que os resultados foram, em média, melhores que a maioria dos trabalhos da literatura que também apresentam valores de limitantes inferiores para o PTHU da formulação CB-CTT. Além disso, em duas instâncias o valor do melhor limitante inferior encontrado até então foi atualizado. Por fim, um dos métodos apresentados nesta tese encontrou o valor ótimo em 15 das 21 instâncias, sendo que o trabalho disponível na literatura que provou a otimalidade para o maior número de instâncias encontrou o valor ótimo em 13 instâncias. 1.4. Publicações 31 1.4 Publicações Os seguintes artigos e resumos foram publicados durante o desenvolvimento deste trabalho: • Trabalhos completos publicados em anais de congressos - CARVALHO, A. S.; MARIANO, G. P.; KAMPKE, E. H.; MAURI, G. R. Simulated Annealing Aplicado ao Problema de Programação de Horários do CCA-UFES. In: Blucher Marine Engineering Proceedings - XVIII SPOLM - Rio de Janeiro, RJ. CASNAV, 2015. v. 2, n. 1, p. 341-352. - SEGATTO, E. A.; BOERES, M. C. S.; RANGEL, M. C.; KAMPKE, E. H. Um Algoritmo GRASP com Cadeia de Kempe Aplicado ao Problema de Tabela- horário para Universidades. In: Anais do XLVII SBPO - Simpósio Brasileiro de Pesquisa Operacional - Porto de Galinhas, PE. SOBRAPO, 2015. p. 2643-2654. - KAMPKE, E. H.; ROCHA, W. S.; BOERES, M. C. S.; RANGEL, M. C. A grasp algorithm with path relinking for the university courses timetabling problem. In: Proceeding Series of the Brazilian Society of Computational and Applied Mathematics - CMAC-SE 2015 - Vitória, ES. SBMAC, 2015. v. 3, n. 2, p. 1081–1087. - MOREIRA, L. V.; MONTEIRO, R. C.; KAMPKE, E. H.; MAURI, G. R. Meta-heurística GRASP para o Problema de Tabela-horário de Disciplinas do Departamento de Computação do CCA-UFES. In: Anais do XLVIII SBPO - Simpósio Brasileiro de Pesquisa Operacional - Vitória, ES. SOBRAPO, 2016. p. 2171-2182. - KAMPKE, E. H.; SEGATTO, E. A.; BOERES, M. C. S.; RANGEL, M. C.; MAURI, G. R. Neighborhood analysis on the university timetabling problem. In: GERVASI, O. et al. (Ed.). Lecture Notes in Computer Science - Computational Science and Its Applications – ICCSA 2017 - Trieste, Italy. Cham: Springer International Publishing, 2017. p. 148–164. - MONTEIRO, R. C.; KAMPKE, E. H.; BISSOLI, D. C.; MAURI, G. R. Algo- ritmo Híbrido Iterated Local Search e Simulated Annealing para o Problema de Tabela-Horário de Universidades. In: Anais do XLIX SBPO - Simpósio Brasileiro de Pesquisa Operacional - Blumenau, SC. SOBRAPO, 2017. p. 1-12. - KAMPKE, E. H.; SCHEIDEGER, L. M.; MAURI, G. R.; BOERES, M. C. S. A network flow based construction for a grasp+sa algorithm to solve the university timetabling problem. In: MISRA, S. et al. (Ed.). Lecture Notes in Computer Science - Computational Science and Its Applications – ICCSA 2019 32 Capítulo 1. Introdução - Saint Petersburg, Russia. Cham: Springer International Publishing, 2019. p. 215–231. • Resumos expandidos publicados em anais de congressos - CARVALHO, A. S.; MARIANO, G. P.; KAMPKE, E. H.; MAURI, G. R. Simulated Annealing e Hill Climbing Aplicado ao Problema de Programação de Horários do CCA-UFES. In: Proceeding Series of the Brazilian Society of Computational and Applied Mathematics - CMAC-SE 2015 - Vitória, ES. SBMAC, 2015. v. 3, n. 2, p. 1201–1202. - MONTEIRO, R. C.; KAMPKE, E. H. Heurísticas de Construção no Problema de Tabela-Hórario de Universidades. In: Anais do XXXVII congresso da sociedade brasileira de computação (CSBC)- 2o Encontro de Teoria da Computação (ETC) - São Paulo, SP. SBC, 2017. v. 1, n. 1, p. 158-161. • Resumos publicados em anais de congressos - CARVALHO, A. S.; MARIANO, G. P.; KAMPKE, E. H.; MAURI, G. R. Simu- lated Annealing e Adaptive Large Neighborhood Search aplicado ao problema de programação de horários do CCA-UFES. In: Anais do XLVII SBPO - Simpósio Brasileiro de Pesquisa Operacional - Porto de Galinhas, PE. SOBRAPO, 2015. p. 3539-3539. - SEGATTO, E. A.; BOERES, M. C. S.; RANGEL, M. C.; KAMPKE, E. H. Algoritmos GRASP e VNS para o Problema de Tabela-Horário para Universida- des. In: Anais do XLVIII SBPO - Simpósio Brasileiro de Pesquisa Operacional - Vitória, ES. SOBRAPO, 2016. p. 3361-3361. 1.5 Organização do trabalho Este trabalho está organizado em 6 capítulos, sendo este o primeiro. No Capítulo 2, o PTHU da formulação CB-CTT proposta no ITC-2007 é descrito em detalhes. As restrições fortes e fracas são apresentadas juntamente com a função objetivo. Nesse capítulo, arquivos texto de uma instância e sua solução são apresentados como exemplo. O Capítulo 3 apresenta vários trabalhos que também abordam o PTHU da formula- ção CB-CTT. Aqueles que discorrem sobre modelos matemáticos e métodos para obtenção de limitantes inferiores, e que foram usados como referência nesse trabalho, são descritos e apresentados detalhadamente. Outros trabalhos, que propõem métodos heurísticos de solução do problema, ou seja, para obtenção de limitantes superiores (solução viável), também são apresentados. 1.5. Organização do trabalho 33 Os métodos U-partition, C-partition, C-partition-null e C-partition-org para ob- tenção de limitantes inferiores para o PTHU abordado são descritos detalhadamente no Capítulo 4. Neste capítulo também são apresentadas previamente a definição dos grafos GU , usado no método U-partition, e GC , usado nos métodos C-partition, C-partition-null e C-partition-org, e a biblioteca METIS, usada para particionar os grafos. Ao final, um flu- xograma dos métodos U-partition, C-partition, C-partition-null e C-partition-org também é exibido. O Capítulo 5 apresenta os experimentos computacionais, como eles foram avaliados, bem como os resultados obtidos e suas análises. Comparações com resultados da literatura, a fim de avaliar a qualidade dos limitantes inferiores encontrados, também são realizadas. Por último, no Capítulo 6 são apresentadas as conclusões do trabalho e sugestões de trabalhos futuros. 35 2 Descrição do problema O PTHU pode ser definido como a tarefa de alocar as aulas de um conjunto de disciplinas em um número limitado de horários e salas, de acordo com as restrições definidas pela formulação (LEWIS, 2008). Neste trabalho o foco é o PTHU da formulação CB-CTT proposta no ITC-2007, ou seja, o PTHU baseado em currículos de cursos, sendo que um currículo é definido como um conjunto de disciplinas que tem alunos em comum. Portanto, o PTHU da formulação CB-CTT consiste na alocação de aulas para várias disciplinas em um horário semanal, considerando um número de salas e de períodos de aulas, em que conflitos entre as disciplinas são determinados de acordo com o currículo, e não pela solicitação de matrícula realizada pelos alunos. A formulação CB-CTT do ITC-2007 é descrita em detalhes por Gaspero, McCollum e Schaerf (2007). As instâncias utilizadas na competição são baseadas em casos reais da Universidade de Udine, Itália. Resumidamente, cada instância é composta pelos seguintes conjuntos de informa- ções: • Dias, Períodos e Horários: Cada dia possui um número fixo de horários de aula, que é o mesmo para todos os dias. Um período é um par composto por um dia e um horário. O número total de períodos disponíveis para alocação é obtido pela multiplicação do número de dias pelo número de horários em um dia. • Disciplinas e Professores: Cada disciplina possui um número fixo de aulas que devem ser alocadas em períodos distintos, um professor que a leciona e o número de alunos que a assistem. Para cada disciplina há uma quantidade mínima de dias distintos em que suas aulas devem ser alocadas. • Salas: Cada sala possui uma capacidade definida pelo número de assentos disponíveis. • Currículos: Consiste em um conjunto de disciplinas que possuem alunos em comum. • Indisponibilidades: Períodos em que uma determinada disciplina não pode ser lecionada. A partir dessas informações são definidas as restrições fortes e fracas do PTHU da formulação CB-CTT. É importante lembrar que as restrições fortes devem ser sempre respeitadas. Qualquer violação de uma restrição forte gera uma tabela-horário inviável, que na prática não pode ser utilizada. Por outro lado, as restrições fracas devem ser satisfeitas o máximo possível e, quanto menos violações, melhor é a tabela-horário. A formulação 36 Capítulo 2. Descrição do problema CB-CTT do ITC-2007 define oito restrições no total, sendo quatro restrições fortes e quatro restrições fracas. As restrições são descritas a seguir: • Restrições Fortes: – H1-Aulas: Todas as aulas de uma disciplina devem ser alocadas, e em períodos diferentes. Uma violação ocorre se uma aula não é alocada, ou se duas aulas da mesma disciplina são alocadas no mesmo período. – H2-Ocupação de Sala: Duas aulas não podem ser alocadas em uma mesma sala e no mesmo período. Cada aula extra em uma mesma sala e no mesmo período conta como uma violação. – H3-Conflitos: Aulas de disciplinas de um mesmo currículo, ou ministradas pelo mesmo professor devem ser alocadas em períodos diferentes. Duas aulas conflitantes no mesmo período representa uma violação. – H4-Indisponibilidade: Se o professor de uma disciplina não está disponível para lecioná-la em determinado período, nenhuma aula dessa disciplina pode ser alocada nesse período. Cada aula alocada em um período não disponível para a disciplina conta como uma violação. • Restrições Fracas: – S1-Capacidade de Sala: Para cada disciplina, o número de alunos que está matriculado na disciplina deve ser menor ou igual ao número de assentos disponíveis em todas as salas que ocorrem aulas dessa disciplina. Cada aluno acima da capacidade conta como uma violação. – S2-Número Mínimo de Dias de Aula: As aulas de uma disciplina devem ser espalhadas em um número mínimo de dias. Cada dia abaixo do número mínimo de dias conta como uma violação. – S3-Aulas Isoladas: Aulas de disciplinas de um mesmo currículo devem ser adjacentes uma à outra. Para cada currículo, uma violação é contada quando há uma aula não adjacente à nenhuma outra aula do mesmo currículo no mesmo dia. – S4-Estabilidade de Sala: Todas as aulas de uma disciplina devem acontecer na mesma sala. Cada sala distinta usada para aulas dessa disciplina, além da primeira, contam como uma violação. A qualidade de uma solução viável, ou seja, uma solução que não viola nenhuma restrição forte (H1-H4), depende da quantidade de violações das restrições fracas (S1-S4), sendo que cada restrição fraca possui um peso associado. 37 Portanto, o objetivo do PTHU da formulação CB-CTT é encontrar uma tabela- horário viável que minimiza a soma ponderada das violações das restrições fracas. Consi- derando Ω o conjunto de todas as soluções viáveis, para cada χ ∈ Ω, o valor da função objetivo f é definido por: f(χ) = 4∑ i=1 αi · βi(χ) sendo que (α1,α2,α3,α4) = (1,5,2,1) representa os pesos atribuídos, respectivamente, a cada uma das restrições fracas S1-S4. Os valores dos pesos foram definidos pelos organizadores do ITC-2007 (GASPERO; MCCOLLUM; SCHAERF, 2007). βi(χ) representa o número total de violações de cada restrição fraca i na solução viável χ ∈ Ω. Assim, pode-se dizer então, que formalmente o objetivo do PTHU da formulação CB-CTT é encontrar uma solução viável χ∗ ∈ Ω, de tal forma, que para todo χ ∈ Ω, f(χ∗) ≤ f(χ). A partir disso, o ITC-2007 definiu um conjunto de 21 instâncias reais (comp01- comp21), de diferentes tamanhos, para permitir a comparação de diferentes métodos de solução do PTHU da formulação CB-CTT. Esse conjunto foi proposto por Gaspero, McCollum e Schaerf (2007) e está disponível para download no website da competição (http://www.cs.qub.ac.uk/itc2007). Gaspero, McCollum e Schaerf (2007) também apresentam informações importantes sobre cada instância, como o número de disciplinas (30-131), o número de salas (5-20), o número de currículos (13-150) e também o número total de aulas a serem alocadas (138-434). Apesar dessas informações ajudarem a medir a dificuldade para obter uma solução viável em uma instância, os autores também apresentam outras medidas, que relacionam essas informações e proporcionam assim uma análise mais precisa sobre o tamanho de uma instância e a respectiva dificuldade para obter uma solução viável. Dentre essas medidas destaca-se a média de conflitos entre aulas e a média da quantidade de aulas por currículo por dia. O padrão do arquivo, definido pelo ITC-2007, que representa uma instância da formulação CB-CTT, é ilustrado na Figura 1, fornecido pela própria organização do campeonato. O arquivo pode ser dividido em cinco partes: cabeçalho, disciplinas, salas, currí- culos e indisponibilidades. O cabeçalho é composto por sete linhas, cada uma contendo, respectivamente, o nome da instância, o número de disciplinas, salas, dias, períodos por dia, currículos e indisponibilidades. Na parte das disciplinas, cada linha contém o nome de uma disciplina, nome do professor que a leciona, quantidade de aulas na semana, número mínimo de dias semanais de aula e quantidade de alunos. A terceira parte apresenta informações a 38 Capítulo 2. Descrição do problema Name: Toy Courses: 4 Rooms: 3 Days: 5 Periods_per_day: 4 Curricula: 2 Constraints: 8 COURSES: SceCosC Ocra 3 3 30 ArcTec Indaco 4 2 42 TecCos Rosa 3 4 40 GeoTec Scarlatti 3 4 18 ROOMS: rA 32 rB 50 rC 40 CURRICULA: Cur1 3 SceCosC ArcTec TecCos Cur2 2 TecCos GeoTec UNAVAILABILITY_CONSTRAINTS: TecCos 2 0 TecCos 2 1 TecCos 3 2 TecCos 3 3 ArcTec 4 0 ArcTec 4 1 ArcTec 4 2 ArcTec 4 3 END. Figura 1 – Arquivo de exemplo - Instância Toy. respeito das salas. Cada linha representa uma sala e possui o seu nome seguido de sua capacidade (número de assentos). As informações sobre os currículos compõem a penúltima parte. Cada currículo é representado por uma linha contendo o seu nome, o número de disciplinas presentes nele seguido dos nomes de cada disciplina. Por último, são listadas as indisponibilidades das disciplinas, uma por linha, contendo o nome da disciplina, o dia e horário em que a disciplina não pode ser lecionada. Dessa forma, na Figura 1 a primeira linha dessa última parte indica que a disciplina TecCos não poderá ter aula alocada no primeiro horário (horário 0 ) do terceiro dia (dia 2 ). A Figura 2 mostra um exemplo de um arquivo de resposta, ou seja, contendo uma 39 possível solução da instância Toy que foi apresentada na Figura 1. O arquivo deve conter, para cada aula alocada, uma linha contendo o nome da disciplina, o nome da sala, o dia e o horário do dia em que está alocada. Por exemplo, a primeira linha do arquivo apresentado na Figura 2 representa que uma aula da disciplina GeoTec foi alocada na sala rA no segundo horário (horário 1 ) do segundo dia (dia 1 ). GeoTec rA 1 1 GeoTec rA 2 3 ArcTec rB 2 1 ArcTec rB 1 1 GeoTec rA 0 0 TecCos rB 2 2 ArcTec rB 1 3 SceCosC rB 0 0 ArcTec rB 3 0 SceCosC rB 1 2 TecCos rB 0 1 TecCos rB 1 0 SceCosC rB 3 1 Figura 2 – Arquivo de resposta - Instância Toy. 41 3 Trabalhos Correlatos O PTHU tem sido amplamente estudado pela comunidade acadêmica devido a sua importância teórica e prática. É possível encontrar diversos trabalhos na literatura com diferentes abordagens para o problema. No entanto, essas abordagens tem recaído basicamente em dois grupos: métodos de programação matemática e métodos heurísticos (BETTINELLI et al., 2015). Os métodos de programação matemática tem como principal objetivo encontrar a solução ótima do PTHU a partir de um modelo matemático. Esses métodos também são denominados exatos (BAZARAA; JARVIS; SHERALI, 2009). Devido à complexidade do PTHU, grande parte dos métodos exatos precisa de uma grande quantidade de tempo para encontrar a solução ótima. Assim, alguns desses métodos relaxam (ignoram) algumas restrições para encontrar uma solução do problema mais rapidamente (MAURI, 2008). O valor da solução obtida nesses casos representa um limitante inferior (superior) do problema de minimização (maximização). No caso da formulação CB-CTT do PTHU, por ser um problema de minimização, o valor de um limitante inferior (Lower Bound - LB), para uma instância, indica que uma solução viável daquela instância não possui valor de função objetivo menor que LB (GOLDBARG; LUNA, 2005). Em contrapartida, o objetivo dos métodos heurísticos é encontrar uma solução viável e de qualidade para o PTHU de forma eficiente, ou seja, com pouco tempo computacional. Nos métodos heurísticos não é possível assegurar que a solução encontrada é a ótima (MAURI, 2008). No caso da formulação CB-CTT do PTHU, por ser um problema de minimização, o valor da função objetivo de uma solução viável, obtida por um método heurístico, representa um limitante superior (Upper Bound - UB). Dessa maneira, quanto menor for a distância entre LB e UB, melhor será a qualidade da solução obtida pelo método heurístico. Se os valores forem iguais, isso representa que a otimalidade foi provada, ou seja, que a solução obtida pelo método heurístico é a ótima (GOLDBARG; LUNA, 2005). Neste capítulo é apresentada apenas uma parte dos trabalhos que abordam o PTHU, em especial aqueles que abordam a formulação CB-CTT do ITC-2007. Assim, a Seção 3.1 é dedicada a trabalhos que apresentam modelos matemáticos e métodos para obtenção de limitantes inferiores, principalmente os trabalhos cujos resultados são usados como referência. Já a Seção 3.2 apresenta trabalhos que propõem métodos heurísticos de solução para o problema. É importante destacar que neste trabalho são citados alguns conceitos da Teoria dos Grafos. Todos esses conceitos podem ser encontrados em Diestel (2016). A seguir são 42 Capítulo 3. Trabalhos Correlatos apresentadas apenas as definições dos principais conceitos citados neste trabalho. Definição 1 (Grafo Bipartido): O grafo G = (V,A) é denominado bipartido se o conjunto de vértices V pode ser particionado em dois subconjuntos X e Y , de tal forma que V = X ∪ Y , X ∩ Y = ∅ e para toda aresta {a, b} ∈ A, a ∈ X e b ∈ Y . Definição 2 (Acoplamento): Um subconjunto de arestas M do grafo G = (V,A), M ⊆ A, representa um acoplamento em G, se, e somente se, existe o subconjunto X de vértices, X ⊆ V , de forma que todo vértice em X é incidente a uma, e apenas uma, aresta de M . Definição 3 (Acoplamento completo em um grafo bipartido): Um acoplamento M do grafo bipartido G = (X ∪ Y,A) é denominado completo se todos os vértices de X, considerando |X| ≤ |Y |, sejam incidentes a todas as arestas de M . Definição 4 (Acoplamento Maximal): Considerando M um acoplamento no grafo G = (V,A), M é maximal se não existe aresta a ∈ A, a 6∈ M , tal que M + {a} também seja um acoplamento. Definição 5 (Grafo Conexo): O grafo G = (V,A) é denominado conexo se todo par de vértices a ∈ V e b ∈ V são conectados por um caminho em G. Definição 6 (Componente Conexa): Seja G = (V,A) um grafo não vazio. Um subgrafo é maximal com respeito à conexidade se não existe outro subgrafo em G no qual ele esteja contido e que seja conexo. Definição 7 (Clique): Um clique no grafo G = (V,A) é um conjunto V’ de vértices, tal que V ′ ⊆ V , V ′ 6= ∅, e para todo par v′i e v′j de vértices distintos em V’ tem se {v′i, v′j} ∈ A. 3.1 Modelos matemáticos e limitantes Existem diversos trabalhos na literatura que apresentam modelos matemáticos para a formulação CB-CTT. Em alguns deles são apresentados métodos para obtenção de limitantes inferiores. Nesta seção são apresentados apenas os dois principais modelos matemáticos para a formulação CB-CTT. A escolha desses modelos ocorreu pelo fato dos demais modelos propostos, que não são apresentados neste trabalho, serem baseados nesses dois. Os valores de limitantes inferiores obtidos com base nesses modelos matemáticos ajudam a avaliar a qualidade de soluções de métodos heurísticos. No caso de problemas muito complexos, ou seja, de difícil solução por métodos exatos, como o PTHU, a im- 3.1. Modelos matemáticos e limitantes 43 portância de encontrar bons valores de limitantes, e até mesmo provar a otimalidade de algumas instâncias, é ainda maior. Os primeiros trabalhos que abordam métodos de programação matemática, para o PTHU da formulação CB-CTT, apresentam modelos matemáticos com muitas variáveis e restrições (BURKE et al., 2010), além de métodos exatos clássicos como Branch-and-cut (BURKE et al., 2012). Posteriormente, novos modelos, com menos variáveis e restrições, são apresentados (LACH; LÜBBECKE, 2012). Métodos que relaxam restrições e dividem o problema também são apresentados na literatura (HAO; BENLIC, 2011). Alguns trabalhos mais recentes usam abordagens pouco conhecidas até então, como exemplo a representação do problema com dois modelos matemáticos que são conectados por uma rede de fluxo (BAGGER et al., 2019). A seguir são apresentados em ordem cronológica alguns trabalhos na literatura que propõem modelos matemáticos e métodos de obtenção de limitantes inferiores para a formulação CB-CTT do PTHU. Nesses trabalhos são apresentados os resultados obtidos quando o método proposto em cada um deles foi executado no conjunto de instâncias do ITC-2007. A escolha desses trabalhos levou em consideração a contribuição de cada um deles, seja provando a otimalidade de algumas instâncias ou melhorando os valores de limitantes inferiores conhecidos até então. 3.1.1 Modelo compacto de Burke et al. (2010) e limitantes inferiores No trabalho de Burke et al. (2010) é apresentado um modelo matemático para a formulação CB-CTT do ITC-2007. O modelo apresentado é denominado Monolítico pois representa na íntegra a formulação CB-CTT, sendo portanto usado para obtenção de limitantes inferiores e superiores para o problema. O modelo Monolítico representa um modelo de PLI, podendo assim ser resolvido por um método de programação matemática para obtenção da solução ótima do problema. Neste modelo, cinco conjuntos de variáveis de decisão são definidos: • xp,r,c ∈ B é igual a 1 se a disciplina c ∈ C possuir uma aula alocada no período p ∈ P e na sala r ∈ R e 0 caso contrário; • vd,c ∈ B é igual a 1 se a disciplina c ∈ C possuir pelo menos uma aula alocada no dia d ∈ D e 0 caso contrário; • qc ∈ Z representa a diferença entre o número mínimo de dias de aula da disciplina c ∈ C (mldc) e o número de dias distintos que a disciplina c possui aulas alocadas, caso a diferença seja positiva e 0 caso contrário; • zu,p ∈ B é igual a 1 se há uma aula isolada do currículo u ∈ U alocada no período p ∈ P e 0 caso contrário; 44 Capítulo 3. Trabalhos Correlatos • yr,c ∈ B é igual a 1 se há pelo menos uma aula da disciplina c ∈ C alocada na sala r ∈ R e 0 caso contrário. O modelo Monolítico proposto por Burke et al. (2010) é apresentado a seguir: min WRC ∑ r∈R ∑ p∈P ∑ c∈C stc>capr xp,r,c(stc − capr) +WMD ∑ c∈C qc +WCC ∑ u∈U ∑ p∈P zu,p +WRS ∑ c∈C (( ∑ r∈R yr,c)− 1) sujeito a ∑ p∈P ∑ r∈R xp,r,c = lctc ∀c ∈ C (3.1) ∑ c∈C xp,r,c 6 1 ∀p ∈ P, r ∈ R (3.2) ∑ r∈R xp,r,c 6 1 ∀p ∈ P, c ∈ C (3.3) ∑ r∈R ∑ c∈Ct xp,r,c 6 1 ∀p ∈ P, t ∈ T (3.4) ∑ r∈R ∑ c∈Cu xp,r,c 6 1 ∀p ∈ P, u ∈ U (3.5) ∑ r∈R xp,r,c = 0 ∀(c, p) ∈ N (3.6) ∑ r∈R xp,r,c 6 vdp,c ∀c ∈ C, p ∈ P (3.7) ∑ r∈R ∑ p∈Pd xp,r,c > vd,c ∀c ∈ C, d ∈ D (3.8) ∑ d∈D vd,c > mldc − qc ∀c ∈ C (3.9) ∑ c∈Cu ∑ r∈R (xp,r,c − xp−1,r,c − xp+1,r,c) 6 zu,p ∀u ∈ U, p ∈ P (3.10) xp,r,c 6 yr,c ∀p ∈ P, r ∈ R, c ∈ C (3.11)∑ p∈P xp,r,c > yr,c ∀r ∈ R, c ∈ C (3.12) xp,r,c ∈ B ∀p ∈ p, r ∈ R, c ∈ C (3.13) vd,c ∈ B ∀d ∈ D, c ∈ C (3.14) qc ∈ Z ∀c ∈ C (3.15) zu,p ∈ B ∀u ∈ U, p ∈ P (3.16) yr,c ∈ B ∀r ∈ R, c ∈ C (3.17) A função objetivo visa minimizar a violação das restrições fracas, uma vez que as restrições fortes são modeladas nos conjuntos de restrições (3.1)−(3.6), e garantem que todas as aulas da disciplina c ∈ C sejam alocadas (3.1), que não exista mais de 3.1. Modelos matemáticos e limitantes 45 uma aula alocada na mesma sala e no mesmo período (3.2), que uma disciplina tenha no máximo uma aula alocada por período (3.3), que disciplinas lecionadas pelo mesmo professor (3.4) ou do mesmo currículo (3.5) não sejam alocadas no mesmo período, e por fim, que uma disciplina não tenha uma das suas aulas alocadas em um período que possui indisponibilidade (3.6). Os conjuntos de restrições (3.7)−(3.12) são usados para representar as restrições fracas. Dessa forma, (3.7) e (3.8) garantem que as variáveis vd,c assumem valores iguais a 1 se, e somente se, a disciplina c ∈ C possuir uma aula alocada no dia d ∈ D. Os valores das variáveis qc são definidos a partir dos valores das variáveis vd,c e isso é garantido em (3.9). O conjunto de restrições (3.10) modela a restrição fraca S3 (aulas isoladas), mas vale destacar que caso o período p ∈ P seja o primeiro ou último do dia d ∈ D, então as variáveis xp−1,r,c e xp+1,r,c, respectivamente, terão valor 0, uma vez que não existem. A restrição fraca S4 (estabilidade de sala) é modelada pelos conjuntos de restrições (3.11) e (3.12). Por último, os conjuntos de restrições (3.13)−(3.17) definem o domínio das variáveis de decisão. Burke et al. (2010) apresentam os resultados da execução do modelo Monolítico pelo otimizador CPLEX (IBM ILOG, 2017) com o tempo de execução limitado em 31200 segundos (40 × 780), sendo 780 segundos o valor calculado pelo programa benchmark no computador usado para os experimentos computacionais. O programa benchmark, disponibilizado pela organização do ITC-2007, analisa as configurações do computador com o objetivo de informar a quantidade de tempo que seria equivalente ao dos computadores do campeonato. O valor do multiplicador 40 foi definido pelos autores sem apresentar uma justificativa para essa escolha. A maior parte dos demais trabalhos apresentados nesta seção também usam esse critério para definir o tempo limite dos seus métodos. Dessa forma, Burke et al. (2010) encontraram, no tempo estipulado (31200 se- gundos), valores de limitantes inferiores e superiores para as 14 instâncias do problema disponibilizadas pela organização do ITC-2007 até aquele momento. Em apenas uma instância os valores de limitantes (inferior e superior) foram iguais, ou seja, foi possível provar a otimalidade apenas dessa instância. Nesse mesmo trabalho, Burke et al. (2010) propõem a alteração do modelo Mo- nolítico de duas maneiras diferentes, através de relaxações, derivando assim os modelos simplificados Surface1 e Surface2. Esses novos modelos são denominados assim pois, diferentemente do modelo Monolítico, encontram apenas valores de limitantes inferiores. O modelo Surface1 ignora as penalidades das violações das restrições S1 (capacidade de sala) e S4 (estabilidade de sala), ou seja, WRC = 0 e WRS = 0, além de adicionar restrições adicionais para limitar o número de salas usadas em cada período. Essas relaxações foram definidas dessa maneira pois assim o número de variáveis e restrições nesse novo modelo é muito menor do que no modelo Monolítico. Já no modelo Surface2 a 46 Capítulo 3. Trabalhos Correlatos idéia é usar o conceito de multi-salas, ou seja, considerar que todas as |R| salas possuem a capacidade igual à capacidade da maior sala disponível inicialmente. Posteriormente, foi considerada a existência de duas multi-salas, sendo que em uma multi-sala foram agrupadas as salas com capacidade maior que um limite e na outra multi-sala, as demais. Em ambos os casos, as quatro penalidades da função objetivo são consideradas e o número de variáveis e restrições permanece menor que no modelo Monolítico. Os resultados apresentados por Burke et al. (2010) para 14 instâncias mostram que o modelo Surface2, também com tempo de execução limitado em 31200 segundos, apresentou, em média, melhores valores de limitantes inferiores do que os modelos Monolítico e Surface1, tendo provado a otimalidade de 6 instâncias, enquanto o Monolítico e Surface1 provaram a otimalidade de 1 e 4 instâncias, respectivamente. 3.1.2 Branch-and-cut de Burke et al. (2012) No trabalho de Burke et al. (2012) é proposto um algoritmo branch-and-cut para o problema. Inicialmente os autores sugerem uma relaxação no modelo Monolítico, mais precisamente no conjunto de restrições (3.10), que modelam a restrição fraca S3 (aulas isoladas). Esse conjunto de restrições foi escolhido para ser relaxado pois o número de restrições, bem como a sua dificuldade, está diretamente relacionado ao número de currículos e a quantidade de disciplinas que cada um deles possui, sendo portanto um conjunto de restrições que dificulta a alocação das aulas. Ao novo modelo, denominado Monolítico Relaxado, é adicionado um conjunto de restrições. Esse conjunto de restrições representa um corte (GOLDBARG; LUNA, 2005). No trabalho de Burke et al. (2012) esse corte no modelo Monolítico Relaxado foi denominado Tipo 1. Um segundo corte (Tipo 2 ) também é proposto e possui três conjuntos de restrições a serem adicionadas. Os valores de limitantes inferiores obtidos pelo algoritmo branch-and-cut, proposto por Burke et al. (2012) e aplicado ao modelo Monolítico Relaxado com os dois tipos de corte, foi pior do que os resultados obtidos pelos modelos Monolítico, Surface1 e Surface2 (BURKE et al., 2010). Os autores também apresentam os resultados obtidos ao resolverem o modelo Surface1 com a adição de um dos três conjuntos de restrições propostas no corte Tipo 2. Esses resultados são, em média, melhores que os resultados do branch-and-cut aplicado ao modelo Monolítico Relaxado com os dois tipos de corte, porém também são piores do que os valores obtidos pelos modelos Monolítico, Surface1 e Surface2 (BURKE et al., 2010). Apesar dos resultados apresentados por Burke et al. (2012) terem sido, em média, piores que os apresentados por Burke et al. (2010), em três instâncias o melhor valor de limitante inferior, conhecido até aquele momento, foi atualizado. 3.1. Modelos matemáticos e limitantes 47 3.1.3 Modelo de duas fases de Lach e Lübbecke (2012) Lach e Lübbecke (2012) também propuseram um modelo matemático de PLI para resolver a formulação CB-CTT. O trabalho que apresenta o modelo proposto foi publicado em 2012, mas teve sua primeira versão disponibilizada online em 2010. O modelo de Lach e Lübbecke (2012) possui menos variáveis e restrições que o Monolítico proposto por Burke et al. (2010). Além disso, é decomposto em dois modelos menores de PLI, cada um representando uma fase da resolução do problema. Na primeira fase as aulas das disciplinas são alocadas em um período de tempo sem levar em consideração as salas. Existe apenas um conjunto de restrições que limita o número de aulas alocadas em cada período p ∈ P à quantidade de salas disponíveis |R|. Com esse conjunto de restrições é possível calcular a quantidade de violações da restrição fraca S1 (capacidade de sala). Dessa forma, na primeira fase, além da restrição fraca S1, a resolução do modelo também tem por objetivo minimizar as restrições fracas S2 (número mínimo de dias de aula) e S3 (aulas isoladas). Na segunda fase, com a solução obtida na resolução da primeira fase, ou seja, de acordo com a quantidade de violações da restrição fraca S1 (capacidade de sala), as aulas são então alocadas nas salas, considerando o objetivo de minimizar a restrição fraca S4 (estabilidade de sala). No modelo de PLI da primeira fase, além dos conjuntos de variáveis vd,c, qc e zu,p já definidas anteriormente, também são usados outros três conjuntos: • xp,c ∈ B é igual a 1 se a disciplina c ∈ C possuir uma aula alocada no período p ∈ P e 0 caso contrário; • ωp,ψ,c ∈ B é igual a 1 se a disciplina c ∈ C possuir uma aula alocada no período p ∈ P em uma sala com capacidade menor que ψ ∈ Ψ e 0 caso contrário; • ϕu,p ∈ B é igual a 1 se há uma aula isolada do currículo u ∈ U alocada no período p ∈ P e 0 caso contrário; É necessário destacar que as variáveis xp,c e ωp,ψ,c só são consideradas no modelo se a disciplina c ∈ C não possuir indisponibilidade no período p ∈ P , ou seja, se (c, p) /∈ N . Além disso, a variável ωp,ψ,c também só é considerada se a quantidade de alunos matriculados na disciplina c ∈ C for maior ou igual a ψ (stc ≥ ψ). O modelo matemático de PLI da primeira fase proposto por Lach e Lübbecke (2012) é apresentado a seguir: min WRC ∑ ψ∈Ψ ∑ p∈P ∑ c∈C≥ψ , c∈Np ωp,ψ,c · θp,ψ,c +WMD ∑ c∈C qc +WCC ∑ u∈U ∑ p∈P zu,p 48 Capítulo 3. Trabalhos Correlatos sujeito a ∑ p∈Nc xp,c = lctc ∀c ∈ C (3.18) ∑ c∈Np xp,c 6 |R| ∀p ∈ P (3.19) xp,c > ωp,ψ,c ∀ψ ∈ Ψ, c ∈ C≥ψ, (c, p) ∈ N (3.20)∑ c∈C≥ψ , c∈Np (xp,c − ωp,ψ,c) 6 |R≥ψ| ∀p ∈ P, ψ ∈ Ψ (3.21) ∑ p∈Pd, p∈Nc xp,c > vd,c ∀d ∈ D, c ∈ C (3.22) ∑ d∈D vd,c > mldc − qc ∀c ∈ C (3.23) ∑ c∈Cu, c∈Np xp,c = ϕu,p ∀u ∈ U, p ∈ P (3.24) − ϕu,p−1 + ϕu,p − ϕu,p+1 6 zu,p ∀u ∈ U, p ∈ P (3.25)∑ c∈Ct, c∈Np xp,c 6 1 ∀p ∈ P, t ∈ T (3.26) xp,c ∈ B ∀(c, p) ∈ N (3.27) ωp,ψ,c ∈ B ∀ψ ∈ Ψ, c ∈ C≥ψ, (c, p) ∈ N (3.28) vd,c ∈ B ∀d ∈ D, c ∈ C (3.29) qc ∈ Z ∀c ∈ C (3.30) zu,p ∈ B ∀u ∈ U, p ∈ P (3.31) ϕu,p ∈ B ∀u ∈ U, p ∈ P (3.32) A função objetivo do modelo possui três termos, representando respectivamente a violação das restrições fracas S1, S2 e S3, uma vez que a restrição S4 é ignorada. Vale destacar que o valor de θp,ψ,c, apresentado pela primeira vez na função objetivo do modelo proposto, é definido por: θp,ψi,c = min{stc − ψi, ψi+1 − ψi} (3.33) O valor de θp,ψi,c (3.33) é definido dessa maneira para que a aula da disciplina c ∈ C lecionada no período p ∈ P , caso não possa ser alocada em uma sala com capacidade maior que o número de alunos matriculados, seja alocada preferencialmente em uma sala cuja capacidade é inferior, porém o mais próximo possível do número de alunos matriculados. O conjunto de restrições (3.18) garante que todas as aulas da disciplina c ∈ C sejam alocadas em algum período e o conjunto de restrições (3.19) assegura que no máximo |R| aulas podem ser alocadas no período p ∈ P . O correto relacionamento entre 3.1. Modelos matemáticos e limitantes 49 as variáveis de decisão xp,c e ωp,ψ,c é garantido pelos conjuntos de restrições (3.20) e (3.21). Esse correto relacionamento permite que os valores das variáveis de decisão ωp,ψ,c sejam definidos de acordo com os valores das variáveis xp,c. O valor das variáveis de decisão vd,c é definido no conjunto de restrições (3.22), sendo que essas variáveis são usadas no conjunto de restrições (3.23) para definir a penalidade qc de S2 (número mínimo de dias de aula) para cada disciplina c ∈ C. O conjunto de restrições (3.24) garante o correto relacionamento entre as variáveis de decisão xp,c e ϕu,p, e assim a penalidade zu,p de S3 (aulas isoladas) é definida no conjunto de restrições (3.25). Como as disciplinas lecionadas pelo mesmo professor não podem ter suas aulas alocadas no mesmo período, o conjunto de restrições (3.26) garante esta exigência. Por fim, os conjuntos de restrições (3.27)−(3.32) definem o domínio das variáveis de decisão. O modelo matemático de PLI da segunda fase representa a formulação padrão do problema de acoplamento completo de custo mínimo em um grafo bipartido G = (X∪Y,A) (AHUJA; MAGNANTI; ORLIN, 1993). No grafo G = (X ∪ Y,A), cada variável xp,c que, após a resolução do modelo da primeira fase tiver valor igual a 1, será representada por um vértice do conjunto X. O conjunto de vértices Y possui |P × R| vértices representando todas as combinações de salas e períodos. A aresta {µp,c,υp,r}, sendo µp,c ∈ X e υp,r ∈ Y , pertence ao conjunto A se ωp,ψ,c é igual a 1, ou se ωp,ψ,c é igual a 0 e a capacidade da sala r é maior ou igual ao número de alunos matriculados em c. Nesse modelo é adicionado um conjunto de restrições que modela a restrição fraca S4 (estabilidade de sala). Lach e Lübbecke (2012) resolveram o modelo da primeira fase no otimizador CPLEX com tempo limite de 13000 segundos (40 × 325), sendo 325 segundos o valor informado pelo programa benchmark, disponibilizado pela organização do ITC-2007, no computador usado para os experimentos computacionais. Os valores obtidos são limitantes inferiores válidos e mesmo obtendo, em média, resultados que não superam os valores obtidos na resolução do modelo Surface2 por Burke et al. (2012), a otimalidade foi provada em 4 das 14 instâncias usadas nos testes, e em outras duas o valor do limitante inferior obtido foi melhor do que o conhecido até aquele momento. 3.1.4 Abordagem dividir para conquistar de Hao e Benlic (2011) O trabalho de Lach e Lübbecke (2012), por ter sido disponibilizado online em 2010, motivou o trabalho de Hao e Benlic (2011). Nesse trabalho é proposto um método baseado na ideia de particionar o problema original em subproblemas e resolver cada um deles separadamente, seguindo assim o príncípio de dividir para conquistar. A proposta é que um subconjunto selecionado dos conjuntos de restrições (3.18)−(3.26) do modelo de PLI da primeira fase é eliminado ou relaxado, de tal forma que o problema possa ser dividido em subproblemas independentes. Cada um dos subproblemas é resolvido pelo otimizador 50 Capítulo 3. Trabalhos Correlatos COIN-OR (COIN-OR FOUNDATION, 2011) com tempo limite de 25200 segundos (7 horas) por subproblema. Os autores não detalham a motivação que os levou a definir esse tempo limite. Um limitante inferior válido para o problema original é então obtido pela soma dos valores obtidos na resolução dos subproblemas. É importante frisar que apenas o modelo da primeira fase, proposto por Lach e Lübbecke (2012), é considerado no trabalho de Hao e Benlic (2011). O método proposto por Hao e Benlic (2011) pode ser resumido em três passos: 1. Particionar o conjunto C de disciplinas. 2. Resolver cada subproblema obtido em cada classe da partição, com um otimizador. 3. Somar os valores encontrados na etapa anterior para calcular o limitante inferior do problema original. Para realizar a partição descrita no passo 1, Hao e Benlic (2011) executaram um algoritmo Iterated Tabu Search. Esse algoritmo define a partição do problema original em k (parâmetro de entrada) classes através do grafo G = (V,A), definido da seguinte maneira: o conjunto de vértices V possui um vértice para cada disciplina c ∈ C, e uma aresta {c1,c2} pertence a A se existir pelo menos um currículo u ∈ U que tenha ambas as disciplinas, ou seja, c1, c2 ∈ Cu para algum u ∈ U . Durante a execução do algoritmo Iterated Tabu Search o tamanho de cada classe (subconjunto de vértices) é limitado em (1, 2× |C|)/k. Assim, evita-se que as classes da partição tenham tamanhos muito diferentes entre si. Após a execução do algoritmo, caso os vértices c1 e c2 pertençam a diferentes classes, sendo que c1 e c2 são adjacentes entre si (c1, c2 ∈ Cu para algum u ∈ U), então todas as arestas que representam o currículo u, inclusive a aresta {c1, c2}, são removidas de G. Dessa forma, no modelo proposto por Lach e Lübbecke (2012) para a primeira fase, Hao e Benlic (2011) consideram que um subconjunto dos conjuntos de restrições (3.24) e (3.25), que correspondem às arestas eliminadas, podem ser desconsideradas no problema e assim não pertencerem a nenhum dos subproblemas. Nos conjuntos de restrições (3.19), (3.21) e (3.26), aquelas que relacionarem disciplinas de classes diferentes serão relaxadas, permitindo que o problema original possa ser dividido em subproblemas independentes. Hao e Benlic (2011) executaram o algoritmo Iterated Tabu Search variando o valor de k entre 2 e 6 para cada uma das 21 instâncias da formulação CB-CTT proposta no ITC-2007. Em todas as execuções foi encontrada uma partição do problema em menos de 600 segundos. Os resultados apresentados por Hao e Benlic (2011) são apenas do melhor valor de limitante inferior e o respectivo número de classes (k). A partir dos resultados é possível notar que o método proposto foi capaz de encontrar limitantes inferiores, em 3.1. Modelos matemáticos e limitantes 51 média, melhores que os obtidos na resolução do modelo Surface2 de Burke et al. (2012), sendo que a otimalidade de 7 das 14 instâncias iniciais foi provada, além de ter encontrado o melhor valor de limitante inferior, conhecido até aquele momento, para outras quatro instâncias. O trabalho de Hao e Benlic (2011) e os demais trabalhos descritos a seguir, nesta seção, executaram seus métodos após a divulgação, pela organização do ITC-2007, das últimas sete instâncias. Assim, esses trabalhos encontraram limitantes inferiores para todas as 21 instâncias da formulação CB-CTT. 3.1.5 Geração de colunas de Cacchiani et al. (2013) No trabalho de Cacchiani et al. (2013) foram apresentados novos e diferentes modelos matemáticos para o problema. Dentre esses modelos destaca-se o denominado por Two Weekly Schedule Types (2WST), pois ao ser resolvido pelo otimizador CPLEX apresentou resultados melhores quando comparados com os demais. No entanto, é importante destacar que o modelo 2WST considera um conjunto maior de variáveis que o modelo Monolítico de Burke et al. (2010) e o modelo de duas fases de Lach e Lübbecke (2012). O modelo 2WST é baseado no modelo Monolítico, apresentado na Seção 3.1.1, cuja função objetivo visa minimizar as violações das quatro restrições fracas (S1-S4) da formulação CB-CTT. Inicialmente, Cacchiani et al. (2013) dividiram a função objetivo do modelo Monolítico em duas partes, sendo que na primeira parte são consideradas apenas as restrições S1 (capacidade de sala) e S4 (estabilidade de sala). Já na segunda parte são consideradas as outras restrições: S2 (número mínimo de dias de aula) e S3 (aulas isoladas). Com essa divisão, dois modelos matemáticos independentes, denominados M1 e M2, foram obtidos, sendo que a resolução do modelo M1 encontra uma solução que minimiza a violação das restrições S1 e S4, enquanto que a resolução do M2 encontra uma solução que minimiza as violações das demais restrições (S2 e S3). A partir disso, o modelo 2WST foi proposto como a combinação linear de soluções dos modelos M1 e M2. Em outras palavras, o 2WST tem por objetivo minimizar a soma das soluções obtidas pelos dois modelos, com restrições que garantam que apenas uma solução, para cada um dos modelos, será considerada. Cacchiani et al. (2013) apresentam então um método para encontrar limitantes inferiores. Esse método consiste em resolver separadamente os modelos M1 e M2, pois a soma dos valores encontrados representa um limitante inferior. Para resolver o modelo M1 foi utilizado o otimizador CPLEX, enquanto o modelo M2 foi resolvido pelo método de Geração de Colunas com tempo de execução limitado em 22800 segundos (40 × 570), sendo 570 segundos o valor informado pelo programa benchmark, disponibilizado pela organização do ITC-2007, no computador usado para os experimentos computacionais. 52 Capítulo 3. Trabalhos Correlatos O método proposto por Cacchiani et al. (2013) provou a otimalidade de 6 instâncias e em outras 6 instâncias os valores obtidos foram melhores que os resultados encontrados até aquele momento, superando assim, em média, os resultados obtidos por Hao e Benlic (2011). 3.1.6 Codificações SAT de Achá e Nieuwenhuis (2014) O trabalho de Achá e Nieuwenhuis (2014) apresenta diferentes formas de codificar a formulação CB-CTT para o problema de satisfatibilidade booleana, também denominado SAT (GAREY; JOHNSON, 1979). As codificações diferem entre si pelos subconjuntos de restrições fortes e fracas consideradas e pela maneira como são definidas. Mesmo com essas diferenças, todas as codificações propostas podem encontrar limitantes inferiores e superiores ao problema, ou seja, em alguns casos a otimalidade também pode ser provada. Vale ressaltar que no problema SAT as restrições fracas também são definidas como restrições fortes, ou seja, se um otimizador para o problema SAT encontra uma solução, obrigatoriamente essa solução terá custo zero. Dentre as codificações propostas, a que apresentou os melhores limitantes inferiores foi a codificação que inicialmente desconsidera todas as restrições fracas, mas que depois vai adicionando cláusulas ao problema SAT. Essas cláusulas modelam as restrições fracas e a quantidade de cláusulas adicionadas é proporcional ao valor das penalidades. Assim, WRC cláusulas são adicionadas para levar em conta a restrição S1 (capacidade de sala), WMD para levar em conta S2 (número mínimo de dias de aula), e assim por diante. As codificações propostas foram resolvidas com um otimizador para o problema SAT, denominado Barcelogic (BOFILL et al., 2008). O tempo limite de execução foi de 105 segundos, sendo que os autores não detalham a motivação que os levou a definir esse tempo limite. Apesar da média dos limitantes inferiores encontrados por Achá e Nieuwenhuis (2014) ter sido pior do que a encontrada por Cacchiani et al. (2013), a codificação provou a otimalidade de 11 das 21 instâncias, sendo portanto o método que até aquele momento provou a otimalidade no maior número de instâncias. 3.1.7 Novas abordagens de Bagger et al. (2019) Três trabalhos (BAGGER; DESAULNIERS; DESROSIERS, 2019; BAGGER et al., 2019; BAGGER; SøRENSEN; STIDSEN, 2019) foram recentemente publicados apre- sentando novos valores de limitantes inferiores para a formulação CB-CTT do PTHU. Esses trabalhos possuem em comum o autor Niels-Christian Fink Bagger da Universidade Técnica da Dinamarca e o ano da publicação: 2019. No entanto, em cada um deles é apre- sentada uma abordagem diferente para obtenção de limitantes inferiores para a formulação 3.1. Modelos matemáticos e limitantes 53 CB-CTT do PTHU. Além disso, apesar do ano de publicação dos trabalhos ser 2019, cada um deles, Bagger, Desaulniers e Desrosiers (2019), Bagger et al. (2019) e Bagger, Sørensen e Stidsen (2019), teve uma primeira versão disponibilizada online, respectivamente, em 2016, 2017 e 2018. No trabalho disponibilizado online em 2016, Bagger, Desaulniers e Desrosiers (2019) apresentam um modelo matemático com relaxações. Nesse modelo matemático apenas as restrições fracas S2 (número mínimo de dias de aula) e S3 (aulas isoladas) são consideradas na função objetivo. Leva-se em consideração também o que os autores denominam de padrões de alocações, sendo que um padrão representa a possibilidade de alocação de aulas de uma disciplina em um subconjunto dos períodos de um dia. Um conjunto de restrições garante que apenas um padrão por disciplina e por dia é escolhido. Outro conjunto de restrições garante que no máximo |R| aulas serão alocadas em um mesmo período. O número de padrões de um dia d é 2|Pd|, ou seja, se a tabela-horário tiver, por exemplo, 4 períodos por dia, então haverá 16 padrões de alocação de aulas de cada disciplina c ∈ C no dia d. Considerando que esse valor aumenta consideravelmente o número de variáveis e restrições do modelo, os autores propõem uma etapa de pré-processamento, para reduzir o número de variáveis e restrições. Em seguida, os autores apresentam e provam algumas desigualdades que tornam a relaxação mais forte se inseridas como restrições no modelo. Considerando que o valor informado pelo programa benchmark, disponibilizado pela organização do ITC-2007, no computador usado para os experimentos computacionais foi de 208 segundos, Bagger, Desaulniers e Desrosiers (2019) resolvem o modelo com o otimizador Gurobi (GUROBI OPTIMIZATION, 2016), limitando o tempo de execução em 100 vezes o valor retornado pelo programa benchmark, ou seja, 20800 segundos (100 × 208). Os valores de limitantes inferiores obtidos provaram a otimalidade em 13 das 21 instâncias, sendo que atualmente é o método da literatura que provou a otimalidade no maior número de instâncias. Em outras 4 instâncias os valores obtidos foram melhores que os resultados encontrados anteriormente na literatura, superando assim, em média, os resultados obtidos por Cacchiani et al. (2013). No segundo trabalho, disponibilizado online em 2017, Bagger et al. (2019) apre- sentam a divisão do modelo matemático reproduzido na Seção 3.1.1 em dois modelos independentes. No primeiro modelo é considerada apenas a alocação das aulas em períodos, ou seja, desconsidera-se a existência de salas e consequentemente os conjuntos de restrições que modelam S1 (capacidade de sala) e S4 (estabilidade de sala). Em contrapartida, o segundo modelo considera apenas a alocação das aulas em salas, desconsiderando a existência de períodos e levando em conta apenas o conjunto de restrições que modelam S4 (estabilidade de sala). 54 Capítulo 3. Trabalhos Correlatos Bagger et al. (2019) afirmam que a motivação do desenvolvimento do trabalho vem de Lach e Lübbecke (2012), pois estes também dividiram o modelo matemático em dois modelos menores. No entanto, Lach e Lübbecke (2012) propõem a resolução dos dois modelos em sequência, enquanto que Bagger et al. (2019), apesar de também dividirem o modelo matemático em dois, propõem que os modelos sejam agrupados novamente em um único modelo. A conexão entre os dois modelos é feita com técnicas de formulação de fluxo, baseadas no problema de fluxo de custo mínimo em uma rede (AHUJA; MAGNANTI; ORLIN, 1993). Nessa conexão, leva-se em consideração a restrição fraca S1 (capacidade de sala). Portanto, os autores propõem a divisão do modelo proposto por Burke et al. (2010) em dois modelos independentes que depois são agrupados novamente em um único modelo através de técnicas de formulação de fluxo. O novo modelo é então resolvido com o otimizador Gurobi, cujo tempo de execução foi limitado em 8320 segundos (40 × 208), sendo 208 segundos o valor informado pelo programa benchmark, disponibilizado pela organização do ITC-2007, no computador usado para os experimentos computacionais. Apesar dos valores de limitantes inferiores obtidos, em média, serem piores que os obtidos no trabalho anterior (BAGGER; DESAULNIERS; DESROSIERS, 2019), eles foram, também em média, melhores que os valores obtidos por Lach e Lübbecke (2012), que motivaram esse trabalho, e os valores obtidos por Hao e Benlic (2011), que também foram motivados por Lach e Lübbecke (2012). A otimalidade foi provada em apenas 7 das 21 instâncias. Por fim, no terceiro trabalho, disponibilizado online em 2018, Bagger, Sørensen e Stidsen (2019) propuseram um método de Geração de Colunas aplicado ao modelo apresentado por Bagger, Desaulniers e Desrosiers (2019). O método foi resolvido com o otimizador Gurobi, cujo tempo limite de execução não foi definido. No entanto, Bagger, Sørensen e Stidsen (2019) reportam o tempo gasto pelo método em cada instância, sendo que foram necessários 87471 segundos para se obter os valores de limitantes inferiores para todas as instâncias. Os valores de limitantes inferiores obtidos com o método Geração de Colunas proposto por Bagger, Sørensen e Stidsen (2019) foi, em média, melhor que os demais resultados encontrados na literatura até o momento. No entanto, a otimalidade foi provada em apenas 7 das 21 instâncias. A partir dos resultados, é importante observar também que em outras 4 instâncias o valor de limitante inferior foi o melhor valor obtido até então, sendo que para uma dessas instâncias o resultado obtido superou em 41,71% o valor considerado o melhor até aquele momento. Dessa forma, os valores de limitantes inferiores obtidos nessas 4 instâncias foram os responsáveis para o método Geração de Colunas de Bagger, Sørensen e Stidsen (2019) ter superado, em média, os valores obtidos por Bagger, Desaulniers e Desrosiers (2019). 3.1. Modelos matemáticos e limitantes 55 3.1.8 Observações finais Nesta seção foram apresentados, de maneira resumida, diversos trabalhos da litera- tura em que são propostos modelos matemáticos para o PTHU da formulação CB-CTT. Dentre esses, destacam-se dois: o modelo Monolítico proposto por Burke et al. (2010) e o modelo de duas fases proposto por Lach e Lübbecke (2012). O Monolítico é um modelo completo, ou seja, considera todas as restrições fracas (S1-S4). No entanto, possui muitas variáveis e restrições, o que dificulta sua resolução. Em contrapartida, o modelo de duas fases de Lach e Lübbecke (2012) possui a desvantagem de não considerar todas as restrições fracas em uma única formulação, mas sua resolução é mais simples, já que apresenta menos variáveis e restrições. Os demais modelos matemáticos propostos para a formulação CB-CTT apresentam mais variáveis e restrições que o Monolítico, ou da mesma forma que o modelo de duas fases de Lach e Lübbecke (2012), também não são completos. Além dos trabalhos de Burke et al. (2010) e Lach e Lübbecke (2012), nesta seção também são apresentados outros que propõem métodos de obtenção de limitantes inferiores para o PTHU da formulação CB-CTT. A variedade de abordagens adotadas nesses trabalhos é grande, incluindo métodos clássicos como Branch-and-cut e Geração de colunas. Apesar disso, nenhuma das abordagens propostas conseguiu provar a otimalidade de todas as 21 instâncias usadas na formulação CB-CTT do ITC-2007. Em cinco dessas instâncias a otimalidade ainda não foi provada. Ao ordenar cronologicamente os trabalhos apresentados nesta seção, observa-se no entanto que cada um deles contribuiu de maneira significativa no estudo do problema, das quais destaca-se a melhora dos valores de limitantes inferiores encontrados anteriormente, provando a otimalidade em uma quantidade maior de instâncias, ou ainda, encontrando melhor valor médio de limitantes inferiores. Dessa maneira, diversos métodos para obtenção de limitantes inferiores foram apresentados nesta seção, cada um com características específicas, o que dificulta realizar uma comparação entre eles. Entretanto, grande parte desses métodos possui em comum a estratégia de diminuir a complexidade do problema original, seja dividindo o modelo matemático em subproblemas ou relaxando algumas restrições. Portanto, os trabalhos apresentados nesta seção contribuiram na compreensão das melhores estratégias a serem usadas para obtenção de limitantes inferiores para o PTHU da formulação CB-CTT. Com isso, os métodos apresentados nesta tese (Seções 4.3 e 4.4) seguem as estratégias de dividir o modelo matemático em subproblemas e também relaxar algumas restrições. 56 Capítulo 3. Trabalhos Correlatos 3.2 Métodos heurísticos Nesta seção são apresentados os principais algoritmos heurísticos propostos para a solução da formulação CB-CTT do ITC-2007. Inicialmente, na Subseção 3.2.1 são apresentados os algoritmos que se destacaram na competição, alcançando a primeira e a segunda colocação. Em seguida, na Subseção 3.2.2 são apresentados alguns trabalhos posteriores que obtiveram resultados de boa qualidade, sendo que os resultados obtidos por alguns desses algoritmos superam aqueles obtidos pelos competidores do ITC-2007. É importante observar, que na Subseção 3.2.2 são apresentados apenas uma parte dos trabalhos que propõem métodos de solução heurísticos para a formulação CB-CTT do ITC-2007. A escolha desses trabalhos foi feita entre os que apresentaram os melhores valores médios de solução viável até o momento ou que foram desenvolvidos pelo grupo de pesquisa do Laboratório de Otimização e Modelagem Computacional (Labotim) da UFES, que estuda o PTHU da formulação CB-CTT proposta no ITC-2007. 3.2.1 Vencedores do ITC-2007 O ITC-2007 se distinguiu das demais edições do campeonato por representar o PTHU em três formulações distintas, conforme apresentado na Seção 1.1. A formulação CB-CTT teve 17 competidores, sendo que todos os algoritmos enviados foram executados 10 vezes em cada uma das 14 instâncias disponibilizadas antes do prazo final de envio. Os cinco competidores que obtiveram, em média, os melhores resultados nessa primeira fase foram classificados para a fase seguinte, que consistia na execução dos respectivos algoritmos, novamente 10 vezes, em outras sete instâncias, que só foram disponibilizadas após a divulgação do resultado final da competição. Ao observar os resultados gerais da competição é possível perceber que os dois primeiros colocados tiveram, em média, resultados muito próximos, mas que se distanciam dos resultados dos demais competidores. Na primeira fase da competição, a média do primeiro colocado (MÜLLER, 2009) foi apenas 1,07% menor que a do segundo colocado (LÜ; HAO, 2010). Já na segunda fase a diferença entre eles foi de 2,45%, enquanto que a diferença entre Müller (2009) e o terceiro colocado foi de 13,61%. Além disso, Müller (2009) encontrou em 10 das 21 instâncias o melhor resultado da competição, enquanto que Lü e Hao (2010) encontrou o melhor resultado em outras 7 instâncias. Em três das quatro instâncias restantes foi registrado um empate entre os melhores resultados obtidos, ou seja, em apenas uma instância o melhor resultado da competição não foi obtido por Müller (2009) ou Lü e Hao (2010). Dessa forma, nesta seção é apresentado apenas as contribuições dos dois primeiros colocados na formulação CB-CTT proposta no ITC-2007. Müller (2009) participou do ITC-2007, na formulação CB-CTT, com um algoritmo 3.2. Métodos heurísticos 57 que possui três fases, sendo que na primeira uma solução viável é obtida usando o algoritmo Iterative Forward Search (MÜLLER, 2005), que por sua vez faz uso de Conflict-based Statistics para prevenir ciclos durante as iterações de construção da solução. Na fase seguinte, a partir da solução contruída, uma solução ótima local é obtida usando o método Hill Climbing (RUSSELL; NORVIG, 1995), que possui movimentos específicos ao problema, relacionados às restrições fracas, para obter uma solução vizinha. Por fim, o método Great Deluge (DUECK, 1993) é usado, de tal forma que um limite é colocado no valor da solução, e esse limite é iterativamente reduzido durante a busca. Nessa fase, o método Simulated Annealing (KIRKPATRICK; GELATT; VECCHI, 1983) é aplicado quando o valor limite é reduzido. O algoritmo Adaptive Tabu Search proposto por Lü e Hao (2010) é composto por duas fases: inicialização e integração (intensificação e diversificação). Na fase de inicialização um algoritmo guloso constrói uma solução viável para o problema, ou seja, a partir de uma tabela-horário vazia uma solução é construída iterativamente selecionando e alocando, em cada iteração, uma aula de uma disciplina. A escolha da aula a ser alocada é feita a partir de uma lista ordenada. A ordenação dessa lista é definida pelas disciplinas que possuem poucos períodos disponíveis e grande número de aulas ainda não alocadas. A solução construída é então submetida à fase seguinte, que congrega formas de intensificação e diversificação na busca de soluções. A intensificação é realizada pelo algoritmo Tabu Search, que gradualmente aumenta a profundidade de busca, enquanto que a diversificação é realizada com um procedimento de pertubação na melhor solução encontrada até o momento. 3.2.2 Métodos heurísticos posteriores ao ITC-2007 Após o ITC-2007 outros métodos de solução heurísticos são propostos na literatura para a formulação CB-CTT. Dentre esses trabalhos, Rocha (2013) usa os trabalhos de Müller (2009) e Lü e Hao (2010) como motivação, e implementa a meta-heurística GRASP (FEO; RESENDE, 1989) para o problema. Nesse caso, o GRASP proposto por Rocha (2013) constrói uma solução viável em cada iteração. A solução construída é submetida a uma etapa de busca local, sendo que após a busca local a estratégia de intensificação Path-Relinking (GLOVER, 1997) também é aplicada. Foram testados dois métodos na etapa de busca local: Hill Climbing e Simulated Annealing. Para obter uma solução vizinha, os métodos aplicam um dos movimentos move e swap. A escolha do movimento é feita de forma aleatória. Os resultados obtidos com Simulated Annealing foram melhores que os resultados obtidos com Hill Climbing. Em comparação com os resultados obtidos durante o ITC-2007, os resultados do GRASP de Rocha (2013) são inferiores aos resultados dos três primeiros colocados na competição, ou seja, caso tivesse participado do ITC-2007 teria ocupado a 4a colocação. 58 Capítulo 3. Trabalhos Correlatos Segatto et al. (2015) deu continuidade ao trabalho de Rocha (2013) implementando o movimento conhecido como Cadeia de Kempe (MORGENSTERN, 1989) para obter uma solução vizinha na etapa de busca local. No entanto, melhorias foram obtidas em apenas algumas instâncias e, em média, os resultados foram inferiores aos obtidos por Rocha (2013). Caso essa nova versão do algoritmo GRASP tivesse participado do ITC-2007 teria obtido a 6a colocação. Posteriormente, Segatto (2017) implementou melhorias na codificação dos seus algoritmos, deixando-os mais eficientes e consequentemente obtendo melhores resultados. Essa nova versão do GRASP, denominada GRASPK, encontrou resultados que, em média, são melhores do que os obtidos por Müller (2009). Dessa forma, caso o algoritmo GRASPK tivesse participado do ITC-2007, ao final da competição teria ocupado a primeira colocação. O trabalho de Bellio et al. (2016) também representa um marco importante dentre as propostas de métodos heurísticos de solução da formulação CB-CTT, pois apresenta uma dupla contribuição. Primeiramente os autores propuseram um efetivo e robusto método Simulated Annealing de fase única para resolver o problema. Em seguida, projetaram e aplicaram uma extensa análise baseada em princípios estatísticos para o procedimento de calibragem de parâmetros. O resultado dessa análise foi uma metodologia que permite a definição dos parâmetros a partir das características de cada instância, como exemplo: a quantidade de disciplinas, a quantidade de salas e a quantidade de currículos. Os resultados obtidos pelo algoritmo Simulated Annealing de Bellio et al. (2016) são melhores do que os resultados do algoritmo GRASPK de Segatto (2017), que por sua vez são melhores do que os apresentados por Müller (2009), vencedor do ITC-2007 na formulação CB-CTT. Kiefer, Hartl e Schnell (2017) apresentam um modelo matemático e também um algoritmo Adaptive Large Neighborhood Search para a solução da formulação CB-CTT. O algoritmo proposto apresenta diversos operadores de destruição e reconstrução de uma solução. A escolha dos operadores é feita de forma aleatória, mas de acordo com uma probabilidade definida a partir da qualidade das soluções obtidas nas iterações anteriores. A média dos resultados obtidos foi melhor que a obtida por Bellio et al. (2016), sendo este trabalho o que apresenta as melhores soluções atualmente. Por fim, o trabalho de Kampke et al. (2017) amplia a análise feita por Lü, Hao e Glover (2011) sobre os movimentos aplicados na busca local dos métodos heurísticos propostos para a formulação CB-CTT, incluindo nessa análise os movimentos propostos por Müller (2009). Posteriormente os autores propuseram um novo método de construção de uma solução inicial para a meta-heurística GRASP apresentada por Kampke et al. (2015), dessa vez propondo a utilização de uma modelagem do problema em uma rede de fluxo. Na fase de busca local é proposta a utilização do movimento Lecture Move que obteve o melhor desempenho na análise realizada anteriormente. Com isso, Kampke et al. (2019) apresentou avanços significativos nos resultados obtidos pela meta-heurística 3.2. Métodos heurísticos 59 GRASP e, apesar de não ter superado os resultados de Kiefer, Hartl e Schnell (2017), Bellio et al. (2016) e Segatto (2017), os resultados obtidos são melhores do que os apresentados por Müller (2009), vencedor do ITC-2007 na formulação CB-CTT. 3.2.3 Observações finais Nesta seção foram apresentados, de maneira resumida, os principais algoritmos heurísticos propostos para o PTHU da formulação CB-CTT. Ao apresentar esses algoritmos foi possível notar uma grande variedade de métodos, que por sua vez usam diferentes estratégias para obtenção de soluções viáveis (limitantes superiores). Assim, esses trabalhos, em especial os desenvolvidos no Labotim/UFES, contribuíram para o entendimento da dificuldade em encontrar uma solução viável em cada instância da formulação CB-CTT do ITC-2007, além de perceber características específicas dessas instâncias. Por fim, é importante destacar que a análise dos diferentes métodos de construção de uma solução inicial e as análises realizadas sobre os movimentos aplicados na busca local, também contribuíram para o entendimento do PTHU abordado. Todas essas contribuições foram importantes na proposta dos métodos apresentados nesta tese (Seções 4.3 e 4.4) e por consequência nas suas implementações. 61 4 Metodologia Em diversos trabalhos na literatura são propostos métodos para encontrar limitantes para o PTHU, conforme destaque no Capítulo 3. A importância desses métodos está no fato de permitir a avaliação da qualidade das soluções obtidas por outros métodos e até mesmo provar a otimalidade das soluções. Neste capítulo são apresentadas novas estratégias para encontrar limitantes infe- riores para a formulação CB-CTT do ITC-2007. Essas estratégias adotam o princípio de dividir para conquistar, também adotado por Hao e Benlic (2011), que particiona o problema original em problemas menores e em seguida resolve cada um deles com um otimizador. Ao particionar o problema, algumas restrições do modelo matemático são relaxadas, possibilitando encontrar valores de limitantes inferiores válidos. Assim, na Seção 4.1 são apresentadas duas formas de representar a formulação CB-CTT como um grafo G = (V,A). Na primeira forma, denominada GU , cada currículo u ∈ U é representado por um vértice de G e na outra, denominada GC , cada disciplina c ∈ C representa um vértice de G. Em GU , a aresta {u1, u2} ∈ A, se, e somente se, os currículos u1 e u2 tiverem pelo menos uma disciplina em comum, ou seja, se Cu1 ∩ Cu2 6= ∅. Já no grafo GC , a aresta {c1, c2} ∈ A, se, e somente se, as disciplinas c1 e c2 pertencerem simultaneamente a um mesmo currículo, ou seja, se Uc1 ∩ Uc2 6= ∅. A Seção 4.2 apresenta resumidamente a biblioteca METIS, proposta por Karypis e Kumar (1998), que implementa heurísticas para o particionamento de grafos. Os dois principais parâmetros dessas heurísticas são o grafo G a ser particionado e o número de classes k. Considerando que durante o particionamento de G algumas arestas serão cortadas e que essas arestas representam as restrições do modelo matemático que serão relaxadas, pode-se afirmar que o particionamento ideal para os métodos propostos nesse trabalho é aquele que minimiza o número de arestas cortadas, e consequentemente o número de restrições relaxadas. Nesse momento é importante salientar, conforme apresentado no Capítulo 3, que Hao e Benlic (2011) implementaram a heurística Busca Tabu Iterativa para particionar o grafo GC . Essa heurística também tem como objetivo encontrar um particionamento que minimiza o número de arestas cortadas. Na Seção 4.3 são apresentados os métodos U-partition e C-partition que particionam, respectivamente, os grafos GU e GC . Em outras palavras, esses métodos particionam o problema original em subproblemas e, em seguida, relaxando algumas restrições do modelo matemático, cada subproblema é resolvido pelo otimizador CPLEX. 62 Capítulo 4. Metodologia Na Seção 4.4 são apresentados os métodos C-partition-null e C-partition-org. A diferença desses métodos para o método C-partition está na forma como as restrições são relaxadas, uma vez que usam variáveis auxiliares, denominadas variáveis de cópia, para obter uma relaxação mais forte. A diferença entre os métodos C-partition-null e C-partition-org está apenas no valor dos coeficientes das variáveis de cópia nas funções objetivo dos subproblemas. Por fim, na Seção 4.5 é apresentado um fluxograma para os quatro métodos propostos. Nesse fluxograma são representadas todas as etapas executadas pelos métodos propostos nas Seções 4.3 e 4.4. 4.1 Representação do PTHU usando grafos Neste trabalho são propostas duas formas distintas para representar via grafos, o PTHU segundo a formulação CB-CTT. Nas Subseções 4.1.1 e 4.1.2 são apresentadas cada uma delas. 4.1.1 Grafo GU Considerando U = {u1, u2, . . . , un} o conjunto com n currículos e Cui o conjunto de disciplinas do currículo ui, o PTHU da formulação CB-CTT é então representado pelo grafo valorado GU = (V,A), sendo que GU consiste em um conjunto V de n vértices e um conjunto A de arestas entre esses vértices. Cada vértice ui ∈ V , i = 1, 2, . . . , n, corresponde a um currículo do conjunto U . Para cada par de currículos ui e uj em U , {ui, uj} ∈ A se Cui ∩ Cuj 6= ∅ e i 6= j. O valor (ou peso) de cada aresta {ui, uj} ∈ A é igual a |Cui ∩ Cuj |, que representa o número de disciplinas que os currículos ui e uj possuem em comum. Cur1 Cur2 1 Figura 3 – Grafo GU da instância Toy. Na Figura 3 é exibido o grafo GU da instância Toy apresentada na Figura 1. Observe que nesse caso o grafo possui dois vértices que representam os currículos Cur1 e Cur2. A aresta entre os currículos possui peso igual a 1, pois os currrículos possuem apenas a disciplina TecCos em comum. 4.2. METIS 63 4.1.2 Grafo GC Neste trabalho também é apresentada uma segunda forma de representar o problema com grafos, que é semelhante a que foi proposta por Hao e Benlic (2011). Assim, conside- rando o conjunto C = {c1, c2, . . . , cm} com m disciplinas, o grafo valorado GC = (V,A) corresponde ao conjunto V com m vértices e ao conjunto A de arestas entre esses vértices. Cada vértice ci ∈ V , i = 1, 2, . . . ,m, corresponde a uma disciplina do conjunto C. Para cada par de disciplinas ci e cj em C, {ci, cj} ∈ A se existe pelo menos um currículo u tal que u ∈ Uci e u ∈ Ucj , ou seja, Uci ∩ Ucj 6= ∅ e i 6= j. Da mesma forma que o grafo GU , mas diferentemente do que foi proposto por Hao e Benlic (2011), o grafo GC é valorado e o peso de cada aresta {ci, cj} ∈ A é igual a |Uci ∩ Ucj |, que representa a quantidade de currículos nos quais as disciplinas ci e cj pertencem simultaneamente. A partir disso, pode-se afirmar que todo par de disciplinas ci e cj, com i 6= j, que pertencem simultaneamente a um currículo u ∈ U , são adjacentes entre si, ou seja, todos os vértices que representam as disciplinas c ∈ Cu formam um clique em GC . TecCos GeoTec ArcTec SceCosC 1 1 1 1 Figura 4 – Grafo GC da instância Toy. A Figura 4 exibe o grafo GC da instância Toy. Cada disciplina da instância é representada por um vértice. As arestas {TecCos,ArcTec}, {SceCosC,ArcTec} e {TecCos, SceCosC} formam um clique de tamanho 3 que representa o currículo Cur1, enquanto que a aresta {TecCos,GeoTec} forma um clique de tamanho 2 representando o currículo Cur2. Nesse exemplo, todas as arestas possuem peso igu