====== Otimização combinatória (2018/1) ======

//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:** Ter/Qui 8.30, sala 109, [[http://mapa.ufrgs.br/index.php?verb=pan&building=44|prédio 43425]] (73).\\
**Consultas:** Qui 14.30, sala 216, [[http://mapa.ufrgs.br/index.php?verb=pan&building=44|prédio 43425]] (73).\\
**Detalhes:** {{sy.pdf|Programa}}.

===== Resultados =====
  * [[2018-1-FF|Frequência]]
  * [[2018-1-Notas|Notas]]
  * [[2018-1-Trabalhos|Trabalhos]]
  * [[2018-1-Quiz|Quiz]]

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

  * Resultados finais disponíveis.

===== Materiais =====

  * Página da disciplina em [[2017-2|2017/2]], [[2017-1|2017/1]], [[2016-2|2016/2]], [[2016-1|2016/1]], [[2015-2|2015/2]], [[2015-1|2015/1]], [[2014-2|2014/2]], [[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-9348.pdf|Notas de aula (Junho de 2018)}}.

==== Aulas ====

^ No.  ^ Data   ^ Tópicos                                              ^ Notas cáp.  ^  Exercícios  ^  Soluções 	 ^ Leitura cáp. ^
|     |       | ** Programação linear **                                 |                |   |   |                      |
|  1  | 06/03 | Administrativa, Introdução: Exemplos e solução gráfica.  |        1.1,1.3 |  {{q0120181.pdf|Q1}}, {{e0120181.pdf|E1}}   |  {{s0120181.pdf|S1}}  | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_1|V1]],MF1,2             |
|  2  | 08/03 | Formulação e exemplos.                                   |            1.1 |  {{q0220181.pdf|Q2}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_1|V1]],MF2               |
|  3  | 13/03 | Laboratório de formulação (sala 102, 67).                |        1.1,B.2 |  {{e0220181.pdf|E2}}, {{u02.pdf|UJ}}  |  {{s0220181.pdf|S2}}  |                      |
|  4  | 15/03 | Forma matricial e normal, introdução método simplex.     |    1.2,2.1,2.2 |  {{q0320181.pdf|Q3}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_2|V2]],[[http://dx.doi.org/10.1007/978-1-4614-7630-6_6|V6]],MF2,3           |
|  5  | 20/03 | Método simplex. Sistemas ilimitados, fase I              |        2.3,2.4 |  {{q0420181.pdf|Q4}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_2|V2]],2.3,MF3.{1,2}   |
|  6  | 22/03 | Método simplex. Pivô tool. Soluções degeneradas.         |            2.5 |  {{q0520181.pdf|Q5}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_3|V3]],MF3.3           |
|  7  | 27/03 | Dualidade: Introdução, teoremas de dualidade.            |        3.1-3.3 |  {{q0620181.pdf|Q6}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_5|V5]],MF4   |
|  8  | 29/03 | Revisão e exercícios.                                    |                |   |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_3|V3]],MF3.6             |
|     | 03/04 | //Sem aula//                                             |                |   |   |                      |
|  9  | 05/04 | **Prova 1**                                              |                |  {{p0120181.pdf|P1}}  |  {{sp0120181.pdf|SP1}}  |                      |
| 10  | 10/04 | Dualidade: Folgas complementares. Método simplex dual.   |        3.2,3.4 |  {{q0720181.pdf|Q7}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_5|V5]]  |
| 11  | 12/04 | Método simplex dual. Analise de sensibilidade.           |        3.5,3.6 |  {{q0820181.pdf|Q8}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_5|V5]],[[http://dx.doi.org/10.1007/978-1-4614-7630-6_7|V7]]      |
| 12  | 17/04 | Analise de sensibilidade.                                |            3.7 |  {{q0920181.pdf|Q9}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_7|V7]]      |
|     |       | ** Programação inteira I **                              |                |   |   |                      |
| 13  | 19/04 | Introdução e aplicações.                                 |         5, 6.1 |  {{q1020181.pdf|Q10}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_23|V23]],W1.{1-4},PS13.1      |
| 14  | 24/04 | Formulação e exemplos.                                   |        6.1-6.3 |  {{q1120181.pdf|Q11}}  |   | W1.{5-7},PS13.1      |
| 15  | 26/04 | Laboratório de formulação (sala 102, 67).                |            B.2 |  {{e0320181.pdf|E3}}  |  {{s0320181.pdf|S3}}  |                      |
|     | 01/05 | [[wppt>Dia do Trabalhador]]                              |                |   |   |                      |
| 16  | 03/05 | Revisão e exercícios.                                    |                |   |   |                      |
| 17  | 08/05 | **Prova 2**                                              |                |  {{p0220181.pdf|P2}}  |  {{sp0220181.pdf|SP2}}   |                      |
|     |       | ** Heurísticas e aproximação **                          |                |   |   |                      |
| 18  | 10/05 | Busca local, Simulated annealing.                        |      10.1,10.2 |  {{qh0120181.pdf|QH1}}  |  [[http://nbviewer.jupyter.org/url/www.inf.ufrgs.br/~mrpritt/oc/D01-tsp-h1.ipynb|D1]]  |                      |
| 19  | 15/05 | GRASP, Busca Tabu, VNS.                                  |      10.3-10.6 |  {{qh0220181.pdf|QH2}}  |  [[http://nbviewer.jupyter.org/url/www.inf.ufrgs.br/~mrpritt/oc/D02-tsp-h2.ipynb|D2]]  |                      |
| 20  | 17/05 | Algoritmos genéticos, meméticos.                         |             11 |  {{qh0320181.pdf|QH3}}  |   |                      |
|     |       | ** Programação inteira II **                             |                |   |   |                      |
| 21  | 22/05 | Matrizes totalmente unimodulares.                        |            7.1 |  {{q1220181.pdf|Q12}}  |   | W3.{1,2},K5.4,PS13.2 |
| 22  | 24/05 | Problemas com solução simples.                           |            7.2 |  {{q1320181.pdf|Q13}}  |   | W3.{3,4},PS13.2      |
|     | 29/05 | [[https://www.youtube.com/watch?v=r235gwc_dxk|Sem aula]]  |                |   |   |                      |
|     | 31/05 | [[wppt>Corpus Christi]]                                  |                |   |   |                      |
| 23  | 05/06 | Desigualdades válidas.                                   |            7.3 |  {{q1420181.pdf|Q14}}  |   | W8.{1-4}             |
| 24  | 07/06 | Algoritmos de planos de corte.                           |            7.4 |  {{q1520181.pdf|Q15}}  |   | W8.{5,6},PS14.1      |
| 25  | 12/06 | Algoritmos de Branch-and-bound.                          |            7.5 |  {{q1620181.pdf|Q16}}  |   | W7,G5.2.3            |
| 26  | 14/06 | Revisão e exercícios.                                    |                |   |   |                      |
| 27  | 19/06 | **Prova 3**                                              |                |  {{p0320181.pdf|P3}}  |  {{sp0320181.pdf|SP3}}  |                      |
| 28  | 21/06 | Algoritmos de aproximação.                               |                |   |   |                      |
| 29  | 26/06 | Apresentação de trabalhos.                               |                |   |   |                      |
| 30  | 28/06 | Apresentação de trabalhos.                               |                |   |   |                      |
|     | 10/07 | Prova de recuperação.                                    |                |  {{pr20181.pdf|PR}}  |  {{spr20181.pdf|SPR}}  |                      |
|     |       |                                                          |                |   |   |                      |
|     | 21/07 | Término oficial das aulas.                               |                |   |   |                      |

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

==== Material ====

  * {{r.tex|Template em LaTeX}} para a lista de exercícios e {{r.pdf|uma versão compilada}}.
  * Uma {{GLPK-quickref.pdf|referência rápida}} para o GLPK e MathProg

==== Ferramentas ====

  * [[http://www.maths.ed.ac.uk/LP-Explorer|LP explorer]]
  * [[http://www.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>