Optimização Discreta

Licenciatura em Matemática 
2º semestre - 2001/02


Faculdade de Ciências e Tecnologia
Universidade de Coimbra

Docente:

João Soares Email:jsoares@mat.uc.pt
Gabinete 6.4 do Dep. Matemática Tel. 239 791 154
Horário de Atendimento: 
Terças das 17.00 às 18.00 (Gabinete 6.4@DM)		  

Sumários das aulas teóricas

Fevereiro: 

DIA AULA SUMÁRIO
19  1 Informações sobre a disciplina. Formulação de problemas de programação inteira: problema da Afectação, problema da Mochila 0-1, problema da Cobertura, problema do Caixeiro Viajante Não Simétrico.
21 2 Formulação de problemas de programação inteira mista: restrições disjunctivas, problema da Localização de Armazéns sem restrições de capacidade, custos fixos. Formulação ideal. Comparar formulações. Revisão de conceitos de Programação Linear.
26 3 Formulação da união de dois polítopos.
Obtenção de limites primais: algoritmos guloso para o problema da mochila e de pesquisa local para o problema da localização de armazens.
Obtenção de limites duais: relaxação linear, relaxação combinatória.
28 4 Obtenção de limites duais para o valor óptimo de um problema inteiro: dualidade lagrangeana e dualidade.
Exercícios do capítulo 2 do livro adoptado: 1.

Março: 

DIA AULA SUMÁRIO
5 5 Matrizes Totalmente Unimodulares: definição e propriedades. Aplicações da Unimodularidade Total a problemas definidos em grafos orientados: fluxo de custo mínimo, caminho mais curto entre dois vértices, fluxo máximo entre dois vértices.
7 6 Exercícios do capítulo 3 do livro adoptado: 2, 3.
12 7 O algoritmo guloso para o problema da árvore geradora de peso máximo num grafo não orientado.
Exercícios do capítulo 3 do livro adoptado: 8.
14 8 O algoritmo guloso para optimização submodular.
19 9 Introdução ao estudo de matroides.
Caracterização algébrica de árvores e florestas de grafos não orientados.
21 10 Não houve aula por motivo do seminário do Professor Bona da Universidade de Chicago. Tempo lectivo será diluído em três aulas teórico-práticas seguintes (dos dias 2, 9 e 23).
26   Férias da Páscoa
28   Férias da Páscoa

Abril: 

DIA AULA SUMÁRIO
2 11 Conjunto de restrições Totalmente Dual Integral (TDI): definição e propriedades.
4 12 Conceitos e aplicações de Combinatória Poliedral: independência afim, invólucro afim, dimensão, faces e facetas (parte 1).
9 13 Conceitos e aplicações de Combinatória Poliedral: independência afim, invólucro afim, dimensão, faces e facetas (parte 2).
11 14 Emparelhamentos de máxima cardinalidade.
Algoritmo para determinar o emparelhamento de máxima cardinalidade num grafo bipartido não orientado. 
16 15 Aula substituída pelo seminário alargado do Professor Ismael Farias do CORE "Branch-and-cut para optimização combinatória sem o uso de variaveis binárias auxiliares" do dia 17 de Abril.
18 16 Aula substituída pelo seminário alargado do Professor Ismael Farias do CORE "Branch-and-cut para optimização combinatória sem o uso de variaveis binárias auxiliares" do dia 17 de Abril.
23 17 Redução do problema de determinar o emparelhamento de peso méximo a um problema de afectação.
O Método Hungaro para o emparelhamento de peso máximo.
25   Feriado
30 18 Redução do problema do Carteiro Chinês num grafo não orientado ao problema de determinar o emparelhamento perfeito de menor peso num grafo completo (exercício 4 do capítulo 4 do livro adoptado).

Maio: 

DIA AULA SUMÁRIO
2 19 O problema de loteamento (do inglês, lot-sizing) sem restrições de capacidade: definição do problema, resolução via programação dinâmica, complexidade computacional.
7   Tolerância de ponto
9 20 O problema da mochila 0-1 (do inglês, 0-1 knapsack): resolução via programação dinâmica, complexidade computacional.
Exercícios do capítulo 5 do livro adoptado: 10.
14 21 Exercícios do capítulo 5 do livro adoptado: 7.
O método de enumeração exaustiva (do inglês, Branch-and-Bound): motivação e aplicação a um exemplo.
16 22 O método de enumeração exaustiva (do inglês, Branch-and-Bound): regras práticas para ramificação e selecção do subproblema seguinte. Pré-processamento.
21 23 Desigualdades válidas para Programação Inteira: Introdução; o algoritmo de Gomory e alguns exemplos de aplicação.
23 24 Desigualdades válidas para Programação Inteira Mista: as desigualdades válidas da classe Mixed Integer Rounding.
O algoritmo de Gomory para Programação Inteira Mista.
Exercícios do capítulo 8 do livro adoptado: 4, 8.
29 25 Exercícios do capítulo 8 do livro adoptado: 9, 11.
30   Feriado

Junho: 

DIA AULA SUMÁRIO
4  26 Apresentação dos trabalhos.

última actualização em 20 de Julho de 2002