MCZA014 -- Métodos de Otimização -- 2026.1

Expediente

• Professor: Aritanan Gruber , sala S-539.2
• Aulas:
  • DA1: Qua 08-10h (A-102.0) e Sex 10-12h (A-102.0)
  • NA1: Qua 19-21h (S-214.0) e Sex 21-23h (A-102.0)
• Atendimento: Qua 18-19h e Sex 12-13h (S-539.2), ou por agendamento
• Moodle: MO26.2
  andamento do curso, links úteis, material, avaliações, notas, mensagens, etc.

Ementa

A ementa original (antiga, lacônica e excessivamente ampla) consiste em:

Programação linear inteira. Modelos e métodos de otimização não linear. Modelos e métodos de otimização multiobjetivos.

A menos que sejam tratados de maneira superficial e informal, cada item requer um curso próprio.
Logo, precisamos de uma adaptação.

Nesta edição

Em vista do explicitado acima, nesta edição, focaremos em técnicas (teoria, métodos e modelos) de

Otimização Discreta em cenários determinísticos.

Enfoque em: formulações poliédricas/convexas, estruturas subjacentes unificantes, igualdades min-max, construções algorítmicas mais avançadas, e na complexidade computacional das soluções. Caso o tempo permita, mencionaremos algumas variantes estocásticas.

TLDR: Amostra de resultados interessantes/importantes em otimização sobre estruturas discretas (como grafos ou hipergrafos) e/ou envolvendo variáveis binárias ou inteiras (incluindo relaxações contínuas convexas).

Objetivos

Adquirir conhecimento em problemas clássicos e ubíquos de otimização discreta (envolvendo grafos, sistemas de conjuntos finitos, hipercubos booleanos, reticulados inteiros) – alguns que possuem e outros que não é sabido se admitem soluções algorítmicas com tempo polinomial no tamanho da instância. Aprender a demonstrar a existência de propriedades estruturais que impactam/simplificam a solução do problema, e aplicar as variadas técnicas de solução apresentadas, com atenção especial a semelhanças e diferenças entre elas. Ser capaz de identificar problemas/situações em que o uso de certa técnica pode ser frutífero e argumentar corretamente sobre o resultado obtido. Absorver a notação e nomenclatura da área.

Recomendação

Algoritmos em Grafos, Análise de Algoritmos I + II, Otimização Linear, e todos os demais cursos que são requisitos para esses quarto (incluindo Matemática Discreta, Funções de Uma/Várias Variáveis e Álgebra Linear).

Importante

• Há uma crença de que disciplinas OLs não possuem pré-requisitos, mas a realidade é bastante diferente – por exemplo, este curso tem um nível avançado para graduação e de introdutório a intermediário para uma pós-graduação na área em questão.
• Dito isso, o que realmente se espera para este curso é maturidade matemática e algorítmica: familiaridade e desenvoltura com definições, provas, contra-exemplos, estruturas discretas, pensamento algorítmico e complexidade computacional. Quanto maior a lista de pré-requisitos cumpridos, maior o seu conforto com os itens descritos.

Avaliações e critérios

• listas de exercícios serão disponibilizadas no Moodle no decorrer do quadrimestre;
  devem ser feitas (fazem parte do seu estudo), mas não valem nota;
  
• duas provas regulares $P_1$ e $P_2$ e uma prova substitutiva $P_3$ aberta;
  média aritmética das 2 melhores dentre as 3 possibilidades
  • P1 : Sex 03/07 @ 10-12h (D) ou 21-23h (N)
  • P2 : Sex 14/08 @ 10-12h (D) ou 21-23h (N)
  • P3 : Ter 18/08 @ 10-12h (D) ou 21-23h (N, a checar se 19-21h é possível)

Nota nominal: $$ N = \frac{1}{2}\max\left\{\sum_{j\in S}P_j\,:\,S\in\binom{[3]}{2}\right\} = \frac{1}{2}\max\left\{P_1+P_2,P_1+P_3,P_2+P_3\right\}, $$ com $P_i\in[0,10]$.

Conceito nominal ($C_N$): reflete o seu desempenho frente ao material apresentado e às avaliações realizadas; obtido pelo encaixe de $N$ em um dos intervalos: $$-\infty < \mathbf{F} < 5.0 \leq \mathbf{D} \leq 6.0 < \mathbf{C} \leq 7.0 < \mathbf{B} \leq 8.5 < \mathbf{A} < \infty.$$

Recuperação

Caso seu conceito $C_N$ seja $\mathbf{D}$ ou $\mathbf{F}$, você tem direito a uma prova de recuperação $P_R$ a ser marcada no início do Q2026.3. Esta será única e contemplará toda a matéria do quadrimestre. Uma nova nota nominal $\overline{N}=(N+P_R)/2$ será utilizada para gerar um novo conceito (nominal) final pós-recuperação $\overline{C}_N$. Note que seu conceito final pós-recuperação pode ser menor que o pré-recuperação: uma vez feita, a recuperação é parte integrante da sua avaliação.

Bibliografia

Pela natureza do curso, não seguiremos uma referência bibliográfica específica (única).
As primárias serão mais próximas, mas faremos algumas incursões em secundárias quando oportuno.
Detalhes serão incluídos no Moodle quando relevante.

Primária

• [BV] BOYD, VENDENBERGHE, Convex Optimization, Cambridge University Press, 2004.
• [BW] BERTSIMAS, WEISMANTEL, Optimization over Integers, Dynamic Ideas, 2005.
• [CCPS] COOK, CUNNINGHAM, PULLEYBLANK, SCHRIJVER, Combinatorial Optimization, Wiley, 1997.
• [KV] KORTE, VYGEN, Combinatorial Optimization: Theory and Algorithms, 6th ed., Springer, 2018.
• [Sch2] SCHRIJVER, Theory of Linear and Integer Programming, Wiley, 1986.

Secundária

• [BT] BERTSIMAS, TSITSIKLIS, Introduction to Linear Optimization, Athena Scientific, 1997.
• [Fra] FRANK, Connections in Combinatorial Optimization, Oxford University Press, 2011.
• [GM] GÄRTNER, MATOUSEK, Approximation Algorithms and Semidefinite Programming, Springer, 2012.
• [Law] LAWLER, Combinatorial Optimization: Networks and Matroids, Dover Publications, 2001.
• [Lee] LEE, A First Course in Combinatorial Optimization, Cambridge University Press, 2004.
• [NW] NEMHAUSER, WOLSEY, Integer and Combinatorial Optimization, Wiley, 1999.
• [PS] PAPADIMITRIOU, STEIGLITZ, Combinatorial Optimization: Algorithms and Complexity, Dover Publications, 1998.
• [Sch1] SCHRIJVER, Combinatorial Optimization: Polyhedra and Efficiency (A, B, C), Springer, 2003.
• [WS] WILLIAMSON, SHMOYS, The Design of Approximation Algorithms, Cambridge University Press, 2011.

Lista de tópicos possíveis

As aulas versarão sobre um subconjunto dos tópicos listados abaixo. Esperamos cobrir um pouco mais da metade deles.
As escolhas serão feitas no decorrer do quadrimestre, já que dependem de alguns fatores.

[%] Por ser uma OL, este curso não tem uma lista pré-fixada do material que será coberto aula a aula, mas indicações serão colocadas com certa antecedência no Moodle e os detalhes das aulas (com os tópico que foram cobertos em qual data) serão devidamente atualizados ao longo do quadrimestre.

• Breve revisão de programação linear, teorema da dualidade, lema de Farkas, algoritmo dos elipsóides; revisão de teoria da complexidade.
• Introdução à programação inteira, visão geral de algoritmos básicos. Introdução à combinatória poliédrica.
• Algoritmos gulosos, sistemas de independência, matróides, otimização submodular.
• Teoria de emparelhamentos, teoremas de Petersen, Berge, König-Egerváry, Frobenius e Hall. Descrições algébricas e poliédricas, teoremas de Tutte, Berge, Lovász, Gallai, Edmonds, Hoffman e Kruskal, Balinski, Nemhauser e Trotter; o método húngaro, algoritmo de contração de flores de Edmonds e algoritmo de Lovász.
• Aplicações de emparelhamentos: coberturas por cadeias e anticadeias e o teorema de Dilworth; matrizes duplamente estocásticas, teorema de Birkhoff-von Neumann; o problema do caixeiro-viajante (TSP) euclidiano e a heurística de Christofides; cortes máximos em grafos planares.
• Emparelhamentos estáveis, teorema de Gale-Shapley, resultados poliédricos.
• Problema da mochila, programação dinâmica e algoritmos de aproximação.
• Problemas de corte de estoque, algoritmo de Gilmore-Gomory, problemas de empacotamento (ou bin-packing) e aproximações, teoremas de de la Vega e Lueker, Garey, Graham, Johnson e Yao, e Karmarkar e Karp.
• Problemas de cobertura de conjuntos, algoritmos exatos e de aproximação, teoremas de Lovász e Stein, Chvátal, Johnson, e Papadimitriou e Steiglitz.
• Programação inteira geral e binária, relaxação linear, arredondamento. Enumeração implícita e técnicas de branch-and-bound (ramificar e limitar).
• Unimodularidade, unimodularidade total, sistemas TDI (dualmente inteiros por completo); teoremas de Hoffman e Kruskal, Veinott e Dantzig, Ghouila-Houri, e Edmonds e Giles.
• Bases de Hilbert, versão inteira dos teoremas de Helly e Carathéodory; resultados de Gordan, Doignon, Bell e Scarf, e Cook, Fonlupt e Schrijver.
• Função valor, dualidade subaditiva, substituta (surrogate) e lagrangiana.
• Desigualdades válidas, planos de corte, algoritmo de Gomory, cortes de Chvátal, algoritmos de lift-and-project (elevar e projetar) de Lovász e Schrijver, e de Balas, Cornuéjols e Ceria.
• Introdução à programação semidefinida, condições de dualidade e complementaridade, a função teta de Lovász, o algoritmo de aproximação de Goemans-Williamson para o MAXCUT (corte máximo) e problemas relacionados, conexão com polinômios positivos (SOS) e problemas de momentos.

Calendário das aulas (sem atribuições; veja [%] acima)

Estudando para esta disciplina

Como dito acima, esta é uma disciplina de nível avançado para graduação e será tratada como tal. Você deve assistir às aulas, estudar a bibliografia indicada, e dedicar-se às listas de exercícios.

Caso seus pré-requisitos não estejam tão sólidos quanto desejável (falta de familiaridade com formalismo matemático e raciocínio algorítmico, atitude passiva com relação ao aprendizado, tempo dedicado insuficiente, etc.), será possível fazer confusões e sentir-se perdido.

Alguns procedimentos que costumam funcionar em cursos introdutórios para mitigar os motivos relacionados também costumam funcionar por aqui:

• Refaça os exemplos e re-prove os resultados fornecidos em sala de aula.
• Preste atenção aos processos de solução (aprenda-os!) e não foque somente nos resultados finais.
• Assista ativamente às aulas; resolva os exercícios nelas propostos e os contidos nas listas.
• Estude a bibliografia indicada, monte grupos de estudo, e faça um bom uso dos horários de atendimento.
• Tenha sempre em mente que aprendizado é uma tarefa ativa; não fique somente assistindo. “Ouvir” às aulas e “ler” os livros tem pouco ou nenhum efeito neste curso – e em qualquer disciplina matemática/algorítmica que o valha.
• Se ainda assim, sentir-se perdido, repita os passos acima. Mais cedo ou mais tarde, eles convergirão à compreensão.

Note que você não será convidado a regurgitar respostas fornecidas em aula ou presente nos livros. As questões em listas e provas testarão sua capacidade de entender os problemas e apresentar uma solução para eles. Às vezes, serão uma adaptação simples ou uma extensão direta do que foi visto. Outras, será necessário relacionar dois ou mais métodos ou conceitos apresentados. Outras ainda, irão requerer análise e raciocínio mais profundo (o que leva tempo, então não deixe nada para a última hora!).

Tenha em mente: além do escrito acima, para aproveitar bem este curso, você deve familiarizar-se com o material na leitura sugerida correspondentes antes da aula, e estudá-los com afinco depois.

Integridade acadêmica e transgressões

O Artigo 25 do Código de Ética da UFABC estabelece, à página 23: “Quanto aos trabalhos acadêmicos, é eticamente inaceitável que os discentes:

• I - fraudem avaliações;
• II - fabriquem ou falsifiquem dados;
• III - plageiem ou não creditem devidamente autoria;
• IV - aceitem autoria de material acadêmico sem participação na produção;
• V - vendam ou cedam autoria de material acadêmico próprio a pessoas que não participaram da produção.”

Trabalhos (listas, provas, programas) suspeitos de cópia ou de outra representação fraudulenta acarretarão aos envolvidos conceitos $\mathbf{F}$ (falha) no curso. A atividade será reportada à Comissão Disciplinar Discente da universidade para que sejam tomadas todas as providências disciplinares cabíveis.

LLMs

Representam um grande avanço da inteligência artificial generativa. O uso para estudo é encorajado, mas cuidado com alucinações e respostas incorretas. Note que o uso de tais ferramentas durante avaliações enquadram-se no Artigo 25 acima.

Para pensar ao longo do curso: Do que adianta as máquinas aprenderem e os alunos não?