If one would take statistics about which mathematical problem is using up most of the computer time in the world, then … the answer would probably be linear programming. (László Lovász)

Bem-vindo à otimização combinatória.

Carga horária: 60 h (em 30 aulas de 2h)
Créditos: 4
Súmula: Modelagem matemática, programação linear e não-linear. Programação inteira e solução via métodos exatos. Algoritmos de aproximação e heurísticas.
Turma: A.
Horário/Sala: Seg/Qua 10.30, 109 (43425).
Consultas: a combinar.

• Trabalhos

• As aulas recomeçam no dia 1 de julho.
• Otimização: tudo que você consegue fazer eu faço melhor.
• Primeiro dia de aula: 18 de março.

• Notas de aula (Abril de 2024).
• Página da disciplina em 2023/2, 2023/1, 2022/2, 2022/1, 2021/2, 2021/1, 2020/2, 2020/1, 2019/2, 2019/1, 2018/2, 2018/1, 2017/2, 2017/1, 2016/2, 2016/1, 2015/2, 2015/1, 2014/2, 2014/1, 2013/2, 2013/1, 2012/2, 2012/1, 2011/2, 2011/1, 2010/2, 2010/1, 2009/2, 2009/1, 2008/2, 2008/1 e 2007/2.
• Anki flashcards para unidade 1, unidade 2 e unidade 3.

No.	Data	Tópicos	Notas cáp.	Exercícios	Soluções	Leitura
		Heurísticas
1	18/03	Administrativa, Introdução, Busca local.	10.1,10.2	Q1	SQ1, D1
2	20/03	GRASP, Simulated annealing, Busca local iterada, VNS.	10.3-10.6	Q2	SQ2, D2
3	25/03	Busca Tabu, Algoritmos genéticos, meméticos.	11	Q3	SQ3, D3
		Programação linear
4	27/03	Introdução: Exemplos e solução gráfica.	1.1,1.3	Q4	SQ4	V1,MF1,2
5	01/04	Formulação e exemplos.	1.1	E1, Q5	SQ5, SE1	V1,MF2
6	03/04	Laboratório de formulação (sala 101/43413).	1.1,B.2	E2	SE2
7	08/04	Forma matricial e normal, introdução método simplex.	1.2,2.1,2.2	Q6	SQ6	V2,V6,MF2,3
8	10/04	Método simplex. Sistemas ilimitados.	2.3,2.4	Q7	SQ7	V2,MF3.{1,2}
9	15/04	Método simplex. Pivô tool, fase I. Soluções degeneradas.	2.5	Q8	SQ8	V2,MF3.3
10	17/04	Revisão e exercícios.		E3	SE3	V3,MF3.6
11	22/04	Prova 1		P1	SP1
12	24/04	Dualidade: Introdução, teoremas de dualidade.	3.1-3.3	Q9	SQ9	V5,MF4
13	29/04	Dualidade: Folgas complementares. Método simplex dual.	3.2 3.4	Q10	SQ10
	01/05	Dia do Trabalho
		06/05-30/06: Suspensão
14	01/07	Método simplex dual. Analise de sensibilidade.	3.5,3.6	Q11	SQ11	V6,V7.1
15	03/07	Analise de sensibilidade.	3.7	Q12	SQ12	V6,V7.1
		Programação inteira
16	08/07	Introdução e aplicações.	5, 6.1	Q13	SQ13	V23,W1.{1-4},PS13.1
17	10/07	Formulação e exemplos.	6.1-6.3	Q14, E4	SQ14, SE4	W1.{5-7},PS13.1
18	15/07	Formulação e demonstrações.	B.2
19	17/07	Revisão e exercícios.		E5	SE5
20	22/07	Prova 2		P2	SP2
21	24/07	Matrizes totalmente unimodulares.	7.1	Q15	SQ15	W3.{1,2},K5.4,PS13.2
22	29/07	Problemas com solução simples, desigualdades válidas.	7.2-3	Q16	SQ16	W3.{3,4},PS13.2,W8.{1-4}
23	31/07	Algoritmos de planos de corte.	7.4	Q17, E6	SQ17, SE6	W8.{5,6},PS14.1
24	05/08	Algoritmos de Branch and bound 1.	7.5			W7,G5.2.3
25	07/08	Algoritmos de Branch and bound 2.	7.5	E7	SE7	W7,G5.2.3
26	12/08	Revisão e exercícios.		E8
27	14/08	Prova 3		P3	SP3
28	19/08	Algoritmos de aproximação.
29	21/08	Apresentação de trabalhos.
30	23/08	Apresentação de trabalhos.
		Provas de recuperação.
	31/08	Término oficial das aulas.

V: vanderbei, W: Wolsey, PS: Papadimitriou/Steiglitz MF: Maculan/Fampa

• Template em LaTeX para a lista de exercícios e uma versão compilada.
• Uma referéncia rápida de GLPK e MathProg

• Visualização de LPs GILP
• Vanderbei's simple pivot tool and advanced pivot tool.
• GNU Linear programming kit

• Nelson Maculan and Marcia H. Costa Fampa. Otimização linear. Editora UnB, 2006. INF 65.012.122 M175o.
• Marco Cesar Goldbarg. Otimização combinatória e programação linear : modelos e algoritmos. Campus, 2005. INF 65.012.122 G618o2.
• David G. Luenberger. Linear and nonlinear programming. Springer, 2nd edition, 2003.
• Bernhard H. Korte and Jens Vygen. Combinatorial optimization theory and algorithms. Springer, 4th edition, 2008. INF 65.012.122 K85c.
• Mokhtar S. Bazaraa, John J. Jarvis, and Hanif D. Sherali. Linear programming and network flows. Wiley, 3rd edition, 2004. ENG 519.852 B362l.
• Laurence A. Wolsey and George L. Nemhauser. Integer and Combinatorial Optimization. Wiley, 1999.
• Dimitri P. Bertsekas. Nonlinear programming. Athena, 2nd edition, 1999. INF 65.012.122 B551n.
• Laurence A. Wolsey. Integer Programming. Wiley, 1998.
• Christos H. Papadimitriou and Kenneth Steiglitz. Combinatorial optimization: Algorithms and complexity. Prentice-Hall, dover edition, 1982.
• G. Ausiello, P. Crescenzi, G. Gambosi, V. Kann, A. Marchetti-Spaccamela, and M. Protasi. Complexity and approximation – Combinatorial Optimization Problems and their Approximability Properties. Springer-Verlag, 1999. INF 510.5 C737.
• Robert J. Vanderbei. Linear programming: Foundations and Extensions. Kluwer, 2nd edition, 2001.
• Juraj Hromkovic. Algorithmics for hard problems. Springer, 2001. INF 65.012.122 H873a.