====== Otimização combinatória (2009/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:** Segunda/Quarta, 8.30-10.10, Sala 113, [[http://www.inf.ufrgs.br/cei/nscad/images/stories/mapa_2006.jpg|prédio 43425]].\\
**Consultas:** Segunda, 14.30-16.30.\\
**Detalhes:** {{sy.pdf|Programa}}.

===== Resultados =====
  * [[2009-2-FF|Freqüência]]
  * [[2009-2-Notas|Notas]]
  * [[2009-2-Trabalhos|Trabalhos]]

===== Notícias =====

  * 17 de agosto: Primeira aula.

===== Materiais =====

  * Página da disciplina em [[2009-1|2009/1]], [[2008-2|2008/2]], [[2008-1|2008/1]] e [[2007-2|2007/2]].
  * {{Notas.pdf|Notas de aula}} (atualizado: 30/11/2009)

==== Aulas ====

^ No.^ Data  ^ Tópicos                               ^ Notas pág.         ^  Exercícios  ^  Soluções   ^ Leitura ^
|     |       | ** Programação linear **              |
|   1 | 17/08 | Exemplos e solução gráfica.           |                7-9 |  {{e01.pdf|E1}}   |  {{s01.pdf|S1}}   | V1,MF1,2             |
|   2 | 19/08 | Formalização, exemplos.               |              10-11 |  {{e01a.pdf|E2}}  |  {{s01a.pdf|S2}}  | V1,MF2               |
|   3 | 24/08 | Laboratório de formulação (101).      |                    |  {{e02a.pdf|E3}}  |  {{s02a.pdf|S3}}  |                      |
|   4 | 26/08 | Forma matricial, normal. Introdução Simplex.  |      11-17 |  V2.{1,2,8,9,12}  |                   |                      |
|   5 | 31/08 | Método simplex. Sistemas ilimitados.  |              17-19,22 |    |   | V2.1,MF2,3           |
|     | 02/09 | //Sem aula//                          |                    |   |   |                      |
|     | 07/09 | [[wppt>Independência do Brasil]]      |                    |   |   |                      |
|   6 | 09/09 | Método simplex. Pivot tool. Fase I.   |              20-25 |  V2.{3-7,10,11}  |   | V2.{2,3,4},MF3.{1,2,3}   |
|   7 | 14/09 | Soluções degeneradas.                 |              25-30 |  V3.{1-3,7}  |   | V3,MF3.6             |
|   8 | 16/09 | Revisão e exercícios.                 |                    |  {{e03b.pdf|E4}}  |  {{s03b.pdf|S4}}  |                      |
|   9 | 21/09 | ** Prova 1**                          |                    |  {{p01e.pdf|P1}}  |  {{sp01e.pdf|SP1}}  |                      |
|  10 | 23/09 | Dualidade.                            |              33-42 |  V5.1,V6.6  |   | V5.{1,2,3,4,6},MF4   |
|  11 | 28/09 | //Sem aula//                          |                    |   |   |                      |
|  12 | 30/09 | Folgas complementares, Método simplex dual  |        42-46 |  V5.5  |   | V6.{1,2,3},V7.1      |
|  13 | 05/10 | Forma matricial e sensitividade.      |              46-51 |  V6.{1,2},V7.{1,2,3}, {{E05.pdf|E5}} |  {{S05.pdf|S5}}  | V6.{1,2,3},V7.1      |
|     |       | ** Programação inteira **             |
|  14 | 07/10 | Introdução e aplicações.              |              67-81 |   |   | W1.{1-4},PS13.1      |
|     | 12/10 | //Nossa senhora aparecida//           |                    |   |   |                      |
|  15 | 14/10 | Exemplos e formulações.               |              83-88 |   |   | W1.{5-7},PS13.1      |
|     | 19/10 | //[[http://semac.inf.ufrgs.br | Semana acadêmica]]// |     |   |   |                      |
|  16 | 21/10 | Laboratório de formulação (101).      |                    |  {{e06a.pdf|E5}}  |  {{s06av1.pdf|S5}}  |                      |
|     | 26/10 | Aula de revisão                       |                    |  {{e07b.pdf|E6}}  |  {{s07b.pdf|S6}}  |                      |
|  17 | 28/10 | **Prova 2**                           |                    |  {{p02d.pdf|P2}}  |  {{sp02d-1.pdf|SP2}} |                      | 
|     | 02/11 | Finados                               |                    |   |   |                      |
|     | 04/11 | //Sem aula//                          |                    |   |   |                      |
|  18 | 09/11 | Matrizes totalmente unimodulares.     |              89-95 |   |   | W3.{1,2},K5.4,PS13.2 |
|  19 | 11/11 | Problemas com solução simples.        |                    |   |   | W3.{3,4},PS13.2      |
|  20 | 16/11 | Desigualdades válidas.                |              96-99 |   |   | W8.{1-4}             | **Trabalhos definidos** | 
|  21 | 18/11 | Algoritmos de planos de corte.        |             99-103 |   |   | W8.{5,6},PS14.1      |
|  22 | 23/11 | Branch-and-bound.                     |            103-107 |   |   | W7,G5.2.3            |
|  23 | 25/11 | Branch-and-bound.                     |            103-107 |  {{e09.pdf|E7}}  |  {{s09.pdf|S7}}  | W7,G5.2.3            | **Definição grupos e escolha trabalhos** |
|     |       | ** Heurísticas e aproximação **       |
|  24 | 30/11 | Busca local, Simulated annealing.     |            113-127 |   |   |                      |
|  25 | 02/12 | **Prova 3**                           |                    |  {{p03.pdf|P3}}  |  {{sp03.pdf|SP3}}  |                      |
|  26 | 07/12 | GRASP, Busca Tabu, VNS.               |            127-135 |   |   |                      |
|  27 | 09/12 | Algoritmos genéticos, meméticos.      |            137-146 |   |   |                      | **11/12: Proposta trabalho **|
|  28 | 14/12 | Algoritmos de aproximação.            |                    |  {{e10.pdf|E8}}  |  {{s10.pdf|S8}}  |                      |
|  29 | 16/12 | Apresentação de trabalhos.            |                    |  {{p03a.pdf|P3}}  |  {{sp03a.pdf|SP3}}  |                      |
|  30 | 21/12 | Apresentação de trabalhos.            |                    |   |   |                      |
|     | 23/12 | Apresentação de trabalhos.            |                    |   |   |                      |
|     |       |                                       |                    |   |   |                      |
|     | 23/12 | Término oficial das aulas.            |                    |   |   |                      |

**Legenda** Livros na coluna leitura: V: Vanderbei. W: Wolsey.

==== Ferramentas ====
  * [[http://www.maths.ed.ac.uk/LP-Explorer|LP explorer]]
  * [[http://campuscgi.princeton.edu/~rvdb/JAVA/pivot/simple.html|Vanderbei's simple pivot tool]] 

==== Bibliografia ====
<html>
<!-- BEGIN BIBLIOGRAPHY livros -->
<!--
    DO NOT MODIFY THIS BIBLIOGRAPHY BY HAND!  IT IS MAINTAINED AUTOMATICALLY!
    YOUR CHANGES WILL BE LOST THE NEXT TIME IT IS UPDATED!
-->
<!-- Generated by: /home/ritt/arch/share/bin/bib2xhtml -s unsortlist livros.bib livros.html -->
<ul class="bib2xhtml">

<!-- Authors: Nelson Maculan and Marcia H Costa Fampa -->
<li><a name="Maculan.Fampa/2006">Nelson</a> Maculan and Marcia
  H.&nbsp;Costa Fampa.
<cite>Otimização linear</cite>.
Editora UnB, 2006.
INF 65.012.122 M175o.</li>

<!-- Authors: Marco Cesar Goldbarg -->
<li><a name="Goldbarg/2005">Marco</a>&nbsp;Cesar Goldbarg.
<a href="http://www.dimap.ufrn.br/~gold/livrootimiza.htm"><cite>Otimização
  combinatória e programação linear : modelos e algoritmos</cite></a>.
Campus, 2005.
INF 65.012.122 G618o2.</li>

<!-- Authors: David G Luenberger -->
<li><a name="Luenberger/2003">David</a>&nbsp;G. Luenberger.
<a href="http://www.stanford.edu/dept/MSandE/people/faculty/luenberger/linear.html"><cite>Linear and nonlinear programming</cite></a>.
Springer, 2nd edition, 2003.</li>

<!-- Authors: Bernhard H Korte and Jens Vygen -->
<li><a name="Korte/2005">Bernhard</a>&nbsp;H. Korte and Jens Vygen.
<a href="http://www.or.uni-bonn.de/~vygen/co.html"><cite>Combinatorial
  optimization theory and algorithms</cite></a>.
Springer, 4th edition, 2008.
INF 65.012.122 K85c.</li>

<!-- Authors: Mokhtar S Bazaraa and John J Jarvis and Hanif D Sherali -->
<li><a name="Mokhtar.Jarvis/2004">Mokhtar</a>&nbsp;S. Bazaraa, John&nbsp;J.
  Jarvis, and Hanif&nbsp;D. Sherali.
<cite>Linear programming and network flows</cite>.
Wiley, 3rd edition, 2004.
ENG 519.852 B362l.</li>

<!-- Authors: Laurence A Wolsey and George L Nemhauser -->
<li><a name="Wolsey.Nemhauser/1999">Laurence</a>&nbsp;A. Wolsey and
  George&nbsp;L. Nemhauser.
<cite>Integer and Combinatorial Optimization</cite>.
Wiley, 1999.</li>

<!-- Authors: Dimitri P Bertsekas -->
<li><a name="Bertsekas/1999">Dimitri</a>&nbsp;P. Bertsekas.
<a href="http://www.athenasc.com/nonlinbook.html"><cite>Nonlinear
  programming</cite></a>.
Athena, 2nd edition, 1999.
INF 65.012.122 B551n.</li>

<!-- Authors: Laurence A Wolsey -->
<li><a name="Wolsey/1998">Laurence</a>&nbsp;A. Wolsey.
<cite>Integer Programming</cite>.
Wiley, 1998.</li>

<!-- Authors: Christos H Papadimitriou and Kenneth Steiglitz -->
<li><a name="Papadimitriou.Steiglitz/1982">Christos</a>&nbsp;H.
  Papadimitriou and Kenneth Steiglitz.
<cite>Combinatorial optimization: Algorithms and complexity</cite>.
Prentice-Hall, dover edition, 1982.</li>

<!-- Authors: G Ausiello and P Crescenzi and G Gambosi and V Kann and A
  Marchetti Spaccamela and M Protasi -->
<li><a name="Ausiello.etal/1999">G</a>.&nbsp;Ausiello, P.&nbsp;Crescenzi,
  G.&nbsp;Gambosi, V.&nbsp;Kann, A.&nbsp;Marchetti-Spaccamela, and M.&nbsp;Protasi.
<a href="http://www.nada.kth.se/~viggo/approxbook"><cite>Complexity and
  approximation &ndash; Combinatorial Optimization Problems and their
  Approximability Properties</cite></a>.
Springer-Verlag, 1999.
INF 510.5 C737.</li>

<!-- Authors: Robert J Vanderbei -->
<li><a name="Vanderbei/2001">Robert</a>&nbsp;J. Vanderbei.
<a href="http://www.princeton.edu/~rvdb/LPbook"><cite>Linear programming:
  Foundations and Extensions</cite></a>.
Kluwer, 2nd edition, 2001.</li>

<!-- Authors: Juraj Hromkovivc -->
<li><a name="Hromkovic/2001">Juraj</a> Hromkovic.
<cite>Algorithmics for hard problems</cite>.
Springer, 2001.
INF 65.012.122 H873a.</li>

</ul>

<!-- END BIBLIOGRAPHY livros -->

</html>

<html>
<a href="http://www2.clustrmaps.com/counter/maps.php?url=http://www.inf.ufrgs.br/~mrpritt" id="clustrMapsLink"><img width=1 src="http://www2.clustrmaps.com/counter/index2.php?url=http://www.inf.ufrgs.br/~mrpritt" style="border:1px solid;" alt="Locations of visitors to this page" title="Locations of visitors to this page" id="clustrMapsImg" onError="this.onError=null; this.src='http://clustrmaps.com/images/clustrmaps-back-soon.jpg'; document.getElementById('clustrMapsLink').href='http://clustrmaps.com'" />
</a>
</html>