Docente:

Novidades

Última actualização: 25 de Julho de 2003

• O exame de época especial será dia 24 de Setembro às 14 horas.
• O último trabalho de casa está descrito aqui e contribuirá como dois trabalhos de casa na avaliação final. Os melhores trabalhos serão analisados para possível publicação em revista portuguesa de divulgação matemática.
• Para o estudo de formulações de problemas de Optimização Discreta recomendo o Capítulo 10 do livro de Bertsimas e Tsitsiklis mencionado na bibliografia.
• Exames de anos anteriores: 2000: normal (.pdf), recurso (.pdf); 2001: normal (.pdf), recurso (.pdf); 2002: normal (.pdf), recurso (.pdf); 2003: normal (.pdf), recurso (.pdf).

Textos (distribuídos nas aulas ou disponíveis nesta página):

1. Folha Introdutória (.pdf) - Informaçao sobre programa, bibliografia e avaliação.
2. Bibliografia adicional (.pdf) - Lista de livros sobre Optimização existentes na Biblioteca Matemática.
3. Trabalho 1 (.pdf) - Formulações e Heurísticas.
4. Capítulo 1 do livro adoptado (e acetatos) - Formulações
5. Capítulo 2 do livro adoptado (e acetatos) - Optimalidade, Relaxações e Limites
6. Capítulo 3 do livro adoptado (e acetatos) - Conjuntos Poliédricos Inteiros e Submodularidade.
7. Caminho mais curto num grafo dirigido (.pdf)
8. A matriz de incidência de um grafo bipartido é TU (.pdf)
9. Resolução do exercício 4, página 50 do livro base (.pdf)
10. Trabalho 2 (.pdf) - Matrizes TU e o algoritmo Guloso. (ajuda:.xls)
11. Submodularidade (.pdf)
12. Integralidade Dual Total (.pdf)
13. Trabalho 3 (.pdf) - Submodularidade e TDI.
14. Capítulo 4 do livro adoptado (e acetatos) - Emparelhamentos e Afectação.
15. Emparelhamentos e Afectações (.pdf)
16. O Carteiro Chinês (.pdf)
17. Trabalho 4 (.pdf) - Formulações, Emparelhamentos e TDI.
18. Sistemas de Equações Lineares Diofantinas (.pdf)
19. Algoritmo de Euclides (.pdf) - Leitura facultativa
20. Aproximação Diofantina (.pdf) - Leitura facultativa
21. Faces, facetas e vértices de poliedros (.pdf) - Suave introdução à Teoria Poliedral.
22. Capítulo 5 do livro adoptado (e acetatos) - Programação Dinâmica
23. Trabalho 5 (.pdf) - Afectação, Carteiro Chinês e Sistemas de Equações Lineares Diofantinas
24. Trabalho 6 (.pdf) - Exercícios de exames de anos anteriores e exercício de modelação.
25. Trabalho 7 (até 21 de Maio) - Exercícios 3 e 4 da última secção do Texto de Apoio sobre Teoria Poliedral + exercício 6 do exame de 18/Junho/2002.
26. Capítulo 7 do livro adoptado (e acetatos) - Método de enumeração exaustiva (do inglês, Branch-and-Bound).
27. Capítulo 8 do livro adoptado (e acetatos) - Métodos de planos cortantes.
28. O Procedimento de Gomory (.pdf)
29. Resolução em Excel do exercício 7 do Capítulo 7 do livro base (.xls)

Sumários:

• Aulas teóricas (2ª, 11.30-13.00 na sala 4.4 e 6ª, 11.30-13.00, na sala 4.4)
• Aulas teórico-práticas (4ª, 11.30-13.00 na sala 4.4)

Ligações:

1. OPTIMA newsletter
2. Texto de Apoio para utilização do solver do Excel.
3. Dificuldades em aceder ou processar documentos em formatos .pdf, .ps ou .dvi? Clique aqui.
4. Gralhas do livro base da disciplina - página web mantida pelo autor.
5. Paths, trees and Flowers
6. PORTA, a polyhedral representation algorithm. If you provide the algorithm with an integer programming problem, it will return a list of all the extreme points and information about the facets. Also available from the same site is SMAPO, a library of linear descriptions of polytopes of small instances of various integer programming problems.
7. Computational Materials for Combinatorial Optimization, maintained by Jon Lee.
8. AMPL is a mathematical programming and optimization modeling language. You can input your model into AMPL in a reasonably intuitive way and it will use a solver (such as MINOS or CPLEX) for solving the problem. It is capable of solving linear, nonlinear, and integer programs. Here is local information about AMPL, including information about using it on RCS. You can download the first chapter of the book.
9. A compendium of NP optimization problems.
10. Myths and counterexamples in optimization. This site shows that you have to be careful about your assumptions when you state some things that are "obvious" in optimization.
11. An amusing interview with Vasek Chvatal regarding cutting plane methods for the TSP.
12. Here is a page on the history of the TSP, with pictures (including one involving Car 54 and one of the optimal tour for a graph with 15,112 cities). This is part of a larger site on the TSP. Two further references for this problem are TSPBIB and Vasek Chvatal's page on the TSP. Instances of TSP can be obtained from the TSPLIB. Hamilton called the problem of finding a route through the vertices of a icosahedron the Icosian game. A similar problem was posed by Euler: Is it possible for a knight to visit every square of a chessboard without visiting any square twice?
13. A list of operations research sites.
14. Integer Programming and Recreational Mathematics.
15. Online book on Discrete Mathematics and Combinatorial Optimization: The Algorithm Design Manual