Otimização combinatória (2016/2)

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. (Laszlo Lovasz)

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

Informações gerais

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 8.30, sala 113, prédio 43425 (73).
Consultas: Seg/Qua 15.30, sala 201, prédio 43425 (73).
Detalhes: Programa.

Resultados

Notícias

Prova de recuperação: dia 19 de dezembro.

Materiais

Página da disciplina em 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.
Notas de aula (atualizado: 13/05/2015)

Aulas

No.	Data	Tópicos	Notas pág.	Exercícios	Soluções	Leitura
		Programação linear
1	01/08	Administrativa, Introdução: Exemplos e solução gráfica.	9-11,17-20	E1, Q1		V1,MF1,2
2	03/08	Formulação e exemplos.	11-13	Q2		V1,MF2
3	08/08	Laboratório de formulação (102/67).	14	E2, S2
4	10/08	Forma matricial e normal. Introdução método Simplex.	27-35	Q3		V2.1,MF2,3
5	15/08	Método simplex: sistemas ilimitados, fase I.	35-40	Q4		V2.2,2.3,MF3.{1,2}
6	17/08	Método simplex: Pivô tool, Sistemas degenerados.	40-46	Q5		V2.{2,3,4},MF3.{1,2,3}
	22/08	Sem aula
	24/08	Sem aula
7	29/08	Revisão e exercícios.				V3,MF3.6
8	31/08	Prova 1		P1	SP1
9	05/09	Dualidade: Introdução, teoremas de dualidade.	51-59	Q6		V5.{1,2,3,4,6},MF4
	07/09	Proclamação da indepedência
	12/09	Semana acadêmica
	14/09	Semana acadêmica
10	19/09	Dualidade: Folgas complementares. Método simplex dual.	60-71	Q7
11	21/09	Método simplex dual. Analise de sensibilidade.	60-67	Q8		V6.{1,2,3},V7.1
12	26/09	Analise de sensibilidade.	72-79	Q9		V6.{1,2,3},V7.1
	28/09	Sem aula
		Programação inteira
13	03/10	Introdução e aplicações.	87-102	Q10		W1.{1-4},PS13.1
14	05/10	Formulação e exemplos.	103-110	Q11		W1.{5-7},PS13.1
15	10/10	Laboratório de formulação (102/67).
	12/10	Nossa senhora aparecida
16	17/10	Formulação, revisão e exercícios.
17	19/10	Prova 2		P2	SP2
		Heurísticas e aproximação
18	24/10	Busca local, Simulated annealing.	153-167
19	26/10	GRASP, Busca Tabu, VNS.	167-179
20	31/10	Algoritmos genéticos, meméticos.	181-190
		Programação inteira
	02/11	Finados
21	07/11	Matrizes totalmente unimodulares.	119-125	Q12		W3.{1,2},K5.4,PS13.2
22	09/11	Problemas com solução simples.	126-128	Q13		W3.{3,4},PS13.2
23	14/10	Desigualdades válidas.	128-134	Q14		W8.{1-4}
24	16/11	Algoritmos de planos de corte.	135-139	Q15		W8.{5,6},PS14.1
25	21/11	Branch-and-bound.	140-145	Q16		W7,G5.2.3
26	23/11	Revisão e exercícios.
27	28/11	Prova 3		P3	SP3
28	30/11	Algoritmos de aproximação.
29	05/12	Apresentação de trabalhos.
30	07/12	Apresentação de trabalhos.
	19/12	Prova de recuperação.
	21/12	Término oficial das aulas.

Livros: V=Vanderbei, MF=Maculan,Fampa, W=Wolsey, G=Goldbarg, K=Korte, PS=Papadimitriou/Steiglitz.

Material

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

Ferramentas

Bibliografia

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.