====== Otimização combinatória (2014/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 10.30, sala 108, [[http://www.ufrgs.br/ufrgs/localize/mapas/vale/pop_vale.asp?mapa=5|prédio 43413]].\\
**Consultas:** Seg/Qua 10.00, sala 201, prédio 43424.\\
**Detalhes:** {{sy.pdf|Programa}}.


===== Resultados =====
  * [[2014-2-FF|Frequência]]
  * [[2014-2-Notas|Notas]]
  * [[2014-2-Trabalhos|Trabalhos]]
  * [[2014-2-Quiz|Quiz]]

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

  * **Laboratório** no dia 22 de setembro: 102.

===== Materiais =====

  * Página da disciplina em [[2014-1|2014/1]], [[2013-2|2013/2]], [[2013-1|2013/1]], [[2012-2|2012/2]], [[2012-1|2012/1]], [[2011-2|2011/2]], [[2011-1|2011/1]], [[2010-2|2010/2]], [[2010-1|2010/1]], [[2009-2|2009/2]], [[2009-1|2009/1]], [[2008-2|2008/2]], [[2008-1|2008/1]] e [[2007-2|2007/2]].
  * {{notas-5498.pdf|Notas de aula}} (atualizado: 3/11/2014)

===== Cronograma =====

^ No.^ Data  ^ Tópicos                               ^ Notas pág.         ^  Exercícios  ^  Soluções   ^ Leitura ^
|    |       | ** Programação linear **                                                      |             |                                          |                       |                        |
|  1 | 04/08 | Administrativa, Introdução: Exemplos e solução gráfica.                       |        9-11 | {{e0120142.pdf|E1}}, {{q0120142.pdf|Q1}} | {{s0120142.pdf|S1}}   | V1,MF1,2               |
|  2 | 06/08 | Formulação e exemplos.                                                        |       11-13 | {{q0220142.pdf|Q2}}                      |                       | V1,MF2                 |
|  3 | 11/08 | Laboratório de formulação (102).                                              |             | {{e0220142.pdf|E2}}                      | {{s0220142.pdf|S2}}   |                        |
|  4 | 13/08 | Forma matricial e normal. Introdução método Simplex. Pivot tool.              | 13-15,25-30 | {{q0320142.pdf|Q3}}                      |                       | V2.1,MF2,3             |
|  5 | 18/08 | Método simplex. Sistemas ilimitados. Fase I.                                  |       30-33 | {{q0420142.pdf|Q4}}                      |                       | V2.2,2.3,MF3.{1,2}     |
|  6 | 20/08 | Método simplex. Sistemas degenerados.                                         |       33-37 | {{q0520142.pdf|Q5}}                      |                       | V2.{2,3,4},MF3.{1,2,3} |
|  7 | 25/08 | Revisão e exercícios.                                                         |       37-43 |                                          |                       | V3,MF3.6               |
|  8 | 27/08 | ** Prova 1**                                                                  |             | {{p0120142.pdf|P1}}                      | {{sp0120142.pdf|SP1}} |                        |
|  9 | 01/09 | Dualidade: Introdução, teoremas de dualidade.                                 |       47-55 | {{q0620142.pdf|Q6}}                      |                       | V5.{1,2,3,4,6},MF4     |
| 10 | 03/09 | Dualidade: Folgas complementares. Método simplex dual.                        |       55-60 | {{q0720142.pdf|Q7}}                      |                       |                        |
| 11 | 08/09 | Método simplex dual. Analise de sensibilidade.                                |       60-67 | {{q0820142.pdf|Q8}}                      |                       | V6.{1,2,3},V7.1        |
| 12 | 10/09 | Analise de sensibilidade.                                                     |       67-73 | {{q0920142.pdf|Q9}}                      |                       | V6.{1,2,3},V7.1        |
|    |       | ** Programação inteira **                                                     |             |                                          |                       |                        |
| 13 | 15/09 | Introdução e aplicações.                                                      |      83-101 | {{q1020142.pdf|Q10}}                     |                       | W1.{1-4},PS13.1        |
| 14 | 17/09 | [[Técnicas de formulação com exemplos|Formulação e exemplos (aula a distância).]] |     103-110 | {{q1120142.pdf|Q11}}                     |                       | W1.{5-7},PS13.1        |
| 15 | 22/09 | Laboratório de formulação (102).                                              |             | {{e0620142.pdf|E3}}                      | {{s0620142.pdf|S3}}   |                        |
| 16 | 24/09 | Formulação, revisão e exercícios.                                             |             |                                          |                       |                        |
| 17 | 29/09 | **Prova 2**                                                                   |             | {{p0220142.pdf|P2}}                      | {{sp0220142.pdf|SP2}} |                        |
|    |       | ** Heurísticas e aproximação **                                               |             |                                          |                       |                        |
| 18 | 01/10 | Busca local, Simulated annealing.                                             |     149-163 |                                          |                       |                        |
| 19 | 06/10 | GRASP, Busca Tabu, VNS.                                                       |     163-173 |                                          |                       |                        |
| 20 | 08/10 | Algoritmos genéticos, meméticos.                                              |     175-184 |                                          |                       |                        |
|    |       | ** Programação inteira **                                                     |             |                                          |                       |                        |
| 21 | 13/10 | Matrizes totalmente unimodulares.                                             |     119-124 | {{q1220142.pdf|Q12}}                     |                       | W3.{1,2},K5.4,PS13.2   |
| 22 | 15/10 | Problemas com solução simples.                                                |     124-127 | {{q1320142.pdf|Q13}}                     |                       | W3.{3,4},PS13.2        |
|    | 20/10 | //[[http://semac.inf.ufrgs.br|Semana acadêmica]]//                                |             |                                          |                       |                        |
|    | 22/10 | //[[http://semac.inf.ufrgs.br|Semana acadêmica]]//                                |             |                                          |                       |                        |
| 23 | 27/10 | Desigualdades válidas.                                                        |     127-132 | {{q1420142.pdf|Q14}}                     |                       | W8.{1-4}               |
| 24 | 29/10 | Algoritmos de planos de corte.                                                |     132-136 | {{q1520142.pdf|Q15}}                     |                       | W8.{5,6},PS14.1        |
| 25 | 03/11 | Branch-and-bound.                                                             |     136-141 | {{q1620142.pdf|Q16}}                     |                       | W7,G5.2.3              |
| 26 | 05/11 | Revisão e exercícios.                                                         |             |                                          |                       |                        |
| 27 | 10/11 | **Prova 3**                                                                   |             |  {{p0320142.pdf|P3}}  |  {{sp0320142.pdf|SP3}}  |    |
| 28 | 12/11 | Algoritmos de aproximação.                                                    |             |                                          |                       |                        |
| 29 | 24/11 | Apresentação de trabalhos.                                                    |             |                                          |                       |                        |
| 30 | 26/11 | Apresentação de trabalhos.                                                    |             |                                          |                       |                        |
|    | 10/12 | Prova de recuperação.                                                         |             |  {{prn.pdf|PR}}  |  {{sprn.pdf|SPR}}  |                       |                        |
|    | 20/12 | Término oficial das aulas.                                                    |             |                                          |                       |                        |

==== Material ====
  * {{r.tex|Template em LaTeX}} para a lista de exercícios e {{r.pdf|uma versão compilada}}.


==== 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]]
  * [[http://www.gnu.org/software/glpk|GNU Linear programming kit]]


==== 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>