MAC0325 (2021)
Otimização Combinatória

MAC0325 é disciplina obrigatória nos módulos Algoritmos e Otimização da trilha de Teoria da Computação do BCC (Bacharelado em Ciência da Computação).

A Otimização Combinatória (também conhecida como Otimização Discreta) procura as melhores combinações em um conjuntos finito de objetos. Em geral, isso implica em procurar a melhor combinação dos valores inteiros de certas variáveis.

Ementa oficial

Ementa oficial (conforme catálogo de graduação do IME e catálogo de graduação da USP):

OBJETIVOS: Ensinar técnicas para o tratamento de problemas de otimização combinatória, em especial aqueles que podem ser formulados como problemas em grafos.

PROGRAMA: O escopo da otimização combinatória e programação inteira. Modelagem de vários problemas usando variáveis 0/1. O problema do transporte. Especialização do método simplex para redes. Aplicações: teorema de Hall, teorema de König, teorema de Dilworth. O problema do transporte capacitado: o método primal-dual. Algoritmos para fluxos máximos em redes. Fluxos de custo mínimo e circulações viáveis: o método out-of-kilter. Estudo aprofundado de poliedros de alguns problemas não-unimodulares bem resolvidos (emparelhamentos, branchings, etc.).

Não vamos seguir essa ementa à risca pois ela está um pouco desatualizada.

Requisitos

Os alunos de MAC0325 devem ter conhecimentos prévios de Programação Linear, Grafos e Análise de Algoritmos.

Os requisitos oficiais são MAC0121 (Algoritmos e Estruturas de Dados I) ou MAC0315 (Otimização Linear). (A rigor, deveria ser MAC0121 e MAC0315.) Há dois pré-requisitos extra-oficiais: MAC0328 (Algoritmos em Grafos) e MAC0338 (Análise de Algoritmos).

Horário, sala, professor

As aulas serão dadas à distância, online, numa sala do Zoom. Para discussões, perguntas, avisos, mensagens, e entrega de exercícios, usaremos o site e-Disciplinas da USP (um derivado do Moodle).

Horário das aulas: terças-feiras às 8:00 e quintas-feiras às 10:00. A primeira aula acontecerá na terça-feira, 17/8/2021. (Veja o calendário escolar USP para 2021.) As aulas serão dadas por Paulo Feofiloff. Não temos monitor.

Livros e material didático

Principais referências:

[CCPS] W.J. Cook, W.H. Cunningham, W.R. Pulleyblank and A. Schrijver, Combinatorial Optimization, Wiley, 1998. [Leitura online a partir do IP da USP.]
[PF] P. Feofiloff, Otimização Combinatória, IME-USP. Esse material está sendo constantemente modificado!

Referências adicionais:

[Sch17] A. Schrijver, A Course in Combinatorial Optimization, notas de aula, 2017.
[BM08] J. A. Bondy, U. S. R. Murty, Graph Theory, Springer, 2008.
[PS] C.H. Papadimitriou and K. Steiglitz, Combinatorial Optimization: Algorithms and Complexity, Prentice-Hall, 1982.
[Sch03] A. Schrijver, Combinatorial Optimization: Polyhedra and Efficiency (volumes A, B, C), Springer, 2003. [Leitura online a partir do IP da USP]
[AMO] R.K. Ahuja, T.L. Magnanti and J.B. Orlin, Network Flows: Theory, Algorithms and Applications, Prentice-Hall, 1993.
P. Feofiloff, Algoritmos para Grafos (via Sedgewick), IME-USP.
P. Feofiloff, Algoritmos de Programação Linear, IME-USP.
P. Feofiloff, Análise de Algoritmos, IME-USP.
P. Feofiloff, Minicurso de Análise de Algoritmos, IME-USP.
Série de vídeos Essence of Linear Algebra do 3blue1bown.
Online Linear and Integer Optimization Solver (by Gerard Sierksma and Yori Zwols): online-optimizer.appspot.com/

Critério de avaliação

Teremos uma prova e várias tarefas ao longo do semestre. A nota final será composta por 40% da nota da prova e 60% da média das tarefas. Entretanto, se a nota da prova ficar abaixo de 5 ou a média das tarefas ficar abaixo de 5, a nota final será a menor das duas.

Calendário de aulas e provas

Aula 1: 2021-08-17 (terça 8:00): Apresentação. Regras do jogo. Esclarecimento de dúvidas.; Enquete e questionário preliminares.; Minhas notas de aula.; Tarefa A, para 19/8, quinta, até as 8:00.
Aula 2: 2021-08-19 (quinta 10:00): Problema do caminho mínimo com custos arbitrários.; Potencial viável.; Algoritmo de Ford.; Algoritmo de Ford–Bellman; Tarefa B, para 26/8, quinta, até as 8:00.
Aula 3: 2021-08-24 (terça 8:00): Algoritmo de Ford-Bellman para caminhos mínimos sob custos arbitrários.; Algoritmo para DAGs, algoritmo de Dijkstra, e de busca em largura.; Programa linear para potencial viável máximo.
Aula 4: 2021-08-26 (quinta 10:00): O poliedro dos potenciais viáveis. Vetores extremos.; Dualidade em programação linear.; Programa linear para caminhos mínimos.; O poliedro dos caminhos mínimos. Vetores extremos.; Tarefa C, para 31/8, terça, até as 8:00.; Tarefa D, para 2/9, quinta, até as 8:00.
Aula 5: 2021-08-31 (terça 8:00): O problema do fluxo máximo.
Aula 6: 2021-09-02 (quinta 10:00): Discussão da Tarefa D.; Tarefa E, para 9/9, quinta, até 8:00.
Feriado (Independência): 2021-09-07 (terça)
Aula 7: 2021-09-09 (quinta 10:00): Teorema do fluxo máximo e corte mínimo.; Algoritmo de Ford-Fulkerson.; Aperfeiçoamento de Edmonds-Karp.; Programa linear para fluxo máximo e corte mínimo.; Tarefa F, para 14/9, terça, até 8:00.
Aula 8: 2021-09-14 (terça 8:00): Programa linear para fluxo máximo e corte mínimo.; Aplicação de fluxo máximo: emparelhamento bipartido máximo.; Tarefa G, para 16/9, quinta, até 8:00.
Aula 9: 2021-09-16 (quinta 10:00): Aplicação de fluxo máximo: o problema do transporte.; Aplicação de fluxo máximo: teorema de Gale.; Tarefa H, para 21/9, terça, até 8:00.
Aula 10: 2021-09-21 (terça 8:00): Aplicação de fluxo máximo: teorema de Gale.; Tarefa I, para 23/9, terça, até 8:00.
Aula 11: 2021-09-23 (quinta 10:00): Aplicação de fluxo máximo: teorema de Gale.; Laboratório de exercícios.; Tarefa J, para 28/9, terça, até 8:00.
Aula 12: 2021-09-28 (terça 8:00): Fluxo viável de custo mínimo.; Tarefa K, para 1/10, sexta, até 20:00.
Aula 13: 2021-09-30 (quinta 10:00): Fluxo viável de custo mínimo.; Algoritmo dos ciclos de aumento.; Tarefa L, para 5/10, terça, até 8:00.
Aula 14: 2021-10-05 (terça 8:00): Exercícios sobre fluxo viável de custo mínimo.; Tarefa M, para 7/10, quinta, até 8:00.
Aula 15: 2021-10-07 (quinta 10:00): Corte global mínimo em grafo não-dirigido.; Tarefa N, para 13/10, quarta, até 8:00.
Feriado (Padroeira do Brasil): 2021-10-12 (terça)
Aula 16: 2021-10-14 (quinta 10:00): Corte global mínimo em grafo não-dirigido.; Tarefa O, para 19/10, terça, até 8:00.
Aula 17: 2021-10-19 (terça 8:00): Algoritmo de Gomory--Hu.; Tarefa P, para 21/10, quinta, até 8:00.
Aula 18: 2021-10-21 (quinta 10:00): Emparelhamentos máximos.; Teorema de Tutte-Berge.; Tarefa Q, para 26/10, terça, até 8:00.
Aula 19: 2021-10-26 (terça 8:00): Emparelhamentos máximos.; Emparelhamentos perfeitos.; Teorema de Tutte.; Tarefa R, para 28/10, quinta, até 8:00.
Aula 20: 2021-10-28 (quinta 10:00): Algoritmo para emparelhamento perfeito em grafo bipartido.; Tarefa S, para 4/11, quinta, até 8:00.
Feriado (Finados): 2021-11-02 (terça 8:00)
Aula 21: 2021-11-04 (quinta 10:00): Algoritmo para emparelhamento perfeito em grafo arbitrário.; Tarefa T, para 9/11, terça, até 8:00.
Aula 22: 2021-11-09 (terça 8:00): Algoritmo para emparelhamento máximo.; Tarefa U, para 11/11, quinta, até 8:00.
Aula 23: 2021-11-11 (quinta 10:00): Emparelhamento perfeito de custo mínimo em grafos bipartidos.; Tarefa V, para 23/11, terça, até 7:00.
Break (Proclamação da República): 16/11 (terça)
Break (Proclamação da República): 18/11 (quinta)
Aula 24: 2021-11-23 (terça 8:00): Emparelhamento perfeito de custo mínimo.; Algoritmo Húngaro para emparelhamento perfeito de custo mínimo em grafos bipartidos.; Tarefa W, para 25/11, quinta, até 7:00.
Aula 25: 2021-11-25 (quinta 10:00): Algoritmo do emparelhamento perfeito de custo mínimo.; Tarefa Z, para 30/11, terça, até 7:00.
Aula 26: 2021-11-30 (terça 8:00): Algoritmo do emparelhamento perfeito de custo mínimo em grafos arbitrários.; Tarefa ZA, para 2/12, quinta, até 7:00.
Aula 27: 2021-12-02 (quinta 10:00): Poliedro dos emparelhamentos perfeitos.; Tarefa ZB, para 7/12, terça, até 7:00.
Aula 28: 2021-12-07 (terça 8:00): Poliedros, politopos, e vértices.; Poliedro dos emparelhamentos perfeitos.; Tarefa ZC, para 10/12, sexta, até 7:00.
Aula 29: 2021-12-09 (quinta 10:00): Laboratório de exercícios.
Prova: 14/12 (terça 8:00): A prova será realizada online, via e-disciplinas.; Começo da prova: 8h de 14/12.; Duração máxima da prova: 8 horas.; Fim da prova: 7h de 17/12, sexta-feira.
2021-12-16 (quinta 10:00): Não haverá aula mas o professor poderá ser consultado pelo Zoom:

MAC0325 (2021) Otimização Combinatória