====== Otimização combinatória (2024/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. (László Lovász)//

:!: 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, 13:30-15:10, 109/43425.\\
**Consultas:** a combinar.\\

===== Resultados =====

  * [[2024-2-Trabalhos|Trabalhos]]

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

  * Otimização: [[https://youtu.be/Dc38La-Xvog|tudo que você consegue fazer eu faço melhor]]. 8-)
  * Primeiro dia de aula: 24 de setembro.

===== Materiais =====

  * {{notas-e76bc7.pdf|Notas de aula (Abril de 2024)}}.
  * Página da disciplina em [[2024-1|2024/1]], [[2023-2|2023/2]], [[2023-1|2023/1]], [[2022-2|2022/2]], [[2022-1|2022/1]], [[2021-2|2021/2]], [[2021-1|2021/1]], [[2020-2|2020/2]], [[2020-1|2020/1]], [[2019-2|2019/2]], [[2019-1|2019/1]], [[2018-2|2018/2]], [[2018-1|2018/1]], [[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]].
  * [[https://apps.ankiweb.net|Anki]] flashcards para [[http://www.inf.ufrgs.br/~mrpritt/oc/Otimização combinatória_U1.apkg|unidade 1]], [[http://www.inf.ufrgs.br/~mrpritt/oc/Otimização combinatória_U2.apkg|unidade 2]] e [[http://www.inf.ufrgs.br/~mrpritt/oc/Otimização combinatória_U3.apkg|unidade 3]].

==== Aulas ====

^ No.^ Data        ^ Tópicos                                                 ^ Notas cáp. ^  Exercícios                                  ^  Soluções                                      ^ Leitura                                                                ^
|     || ** Heurísticas **                                  |||||
|   1 | 24/09 | Administrativa, Introdução, Busca local.                  |    10.1,10.2  |  {{qh0120242.pdf|Q1}}                          |  {{sqh0120242.pdf|SQ1}}, [[https://nbviewer.org/url/www.inf.ufrgs.br/~mrpritt/oc/D01-tsp-h1.ipynb|D1]]  |                                                                         |
|   2 | 26/09 | GRASP, Simulated annealing, Busca local iterada, VNS.     |    10.3-10.6  |  {{qh0220242.pdf|Q2}}                          |  {{sqh0220242.pdf|SQ2}}, [[https://nbviewer.org/url/www.inf.ufrgs.br/~mrpritt/oc/D02-tsp-h2.ipynb|D2]]  |                                                                         |
|   3 | 01/10 | Busca Tabu, Algoritmos genéticos, meméticos.              |           11  |  {{qh0320242.pdf|Q3}}                          |  {{sqh0320242.pdf|SQ3}}, [[https://nbviewer.org/url/www.inf.ufrgs.br/~mrpritt/oc/D03-tsp-h3.ipynb|D3]]  |                                                                         |
|     || ** Programação linear **                                  |||||		                                             
|   4 | 03/10 | Introdução: Exemplos e solução gráfica.                   |      1.1,1.3  |  {{q0120242.pdf|Q4}}                           |  {{sq0120242.pdf|SQ4}}                                      | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_1|V1]],MF1,2              |
|   5 | 08/10 | Formulação e exemplos, parte 1.                           |          1.1  |  {{e0120242.pdf|E1}}, {{q0220242.pdf|Q5}}      |  {{se0120242.pdf|S1}}, {{sq0220242.pdf|SQ5}}                | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_1|V1]],MF2                |
|   6 | 10/10 | Formulação e exemplos, parte 2 (+AA).                     |      1.1,B.2  |  AA={{e0220242.pdf|E2}}+{{l0220242.pdf|L2}}    |  {{se0220242.pdf|S2}}, {{sl0220242.pdf|SL2}}                |                                                                         |
|   7 | 15/10 | Forma matricial e normal, introdução método simplex.      |  1.2,2.1,2.2  |  {{q0320242.pdf|Q6}}     |  {{sq0320242.pdf|SQ6}}                                                            | [[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  |
|   8 | 17/10 | Método simplex. Sistemas ilimitados.                      |      2.3,2.4  |  {{q0420242.pdf|Q7}}     |  {{sq0420242.pdf|SQ7}}                                                            | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_2|V2]],MF3.{1,2}          |
|   9 | 22/10 | Método simplex. Pivô tool, fase I. Soluções degeneradas.  |          2.5  |  {{q0520242.pdf|Q8}}     |  {{sq0520242.pdf|SQ8}}                                                            | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_2|V2]],MF3.3              |
|  10 | 24/10 | Revisão e exercícios.                                     |               |  {{e0320242.pdf|E3}}     |  {{se0320242.pdf|S3}}                                                             | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_3|V3]],MF3.6              |
|  11 | 29/10 | **Prova 1**                                               |               |  {{p0120242.pdf|P1}}     |  {{sp0120242.pdf|SP1}}                                                            |                                                                         |
|  12 | 31/10 | Dualidade: Introdução, teoremas de dualidade.             |      3.1-3.3  |  {{q0620242.pdf|Q9}}     |  {{sq0620242.pdf|SQ9}}                                                            | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_5|V5]],MF4                |
|  13 | 05/11 | [[:inf05010:dualidade2|Dualidade: Folgas complementares. Método simplex dual.]]  |  3.2 3.4  |  {{q0720242.pdf|Q10}}     |  {{sq0720242.pdf|SQ10}}                                        |                                                                         |
|  14 | 07/11 | [[:inf05010:dualidade3|Método simplex dual. Analise de sensibilidade.]]          |  3.5,3.6  |  {{q0820242.pdf|Q11}}     |  {{sq0820242.pdf|SQ11}}                                        | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_6|V6]],V7.1               |
|  15 | 12/11 | Analise de sensibilidade.                                 |          3.7  |  {{q0920242.pdf|Q12}}, {{e0420242.pdf|E4}}   |  {{sq0920242.pdf|SQ12}}, {{se0420242.pdf|S4}}                  | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_6|V6]],V7.1               |
|     || ** Programação inteira **                                  |||||
|  16 | 14/11 | Introdução, aplicações e formulação.                      |       5, 6.1  |  {{q1020242.pdf|Q13}}, {{e0520242.pdf|E5}}   |  {{sq1020242.pdf|SQ13}}, {{se0520242.pdf|S5}}                  | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_23|V23]],[[https://onlinelibrary.wiley.com/doi/10.1002/9781119606475.ch1|W1.{1-4}]],PS13.1  |
|  17 | 19/11 | Formulação, exemplos, e demonstrações.                    |      6.1-6.3  |  {{q1120242.pdf|Q14}}                        |  {{sq1120242.pdf|SQ14}}                                        | [[https://onlinelibrary.wiley.com/doi/10.1002/9781119606475.ch1|W1.{5-7}]],PS13.1    |
|  18 | 21/11 | Revisão e exercícios.                                     |               |  {{e0620242.pdf|E6}}                         |  {{se0620242.pdf|S6}}                                          |                                                                         |
|  19 | 26/11 | **Prova 2**                                               |               |  {{p0220242.pdf|P2}}                         |  {{sp0220242.pdf|SP2}}                                         |                                                                         |
|  20 | 28/11 | Matrizes totalmente unimodulares.                         |          7.1  |                                              |                                                                | [[https://onlinelibrary.wiley.com/doi/10.1002/9781119606475.ch1|W3.{1,2}]],K5.4,PS13.2       |
|  21 | 03/12 | Problemas com solução simples, desigualdades válidas.     |        7.2-3  |  {{e0720242.pdf|E7}}                         |  {{se0720242.pdf|S7}}                                          | [[https://onlinelibrary.wiley.com/doi/10.1002/9781119606475.ch1|W3.{3,4}]],PS13.2,W8.{1-4}   |
|  22 | 05/12 | Algoritmos de planos de corte.                            |          7.4  |                                              |                                                                | [[https://onlinelibrary.wiley.com/doi/10.1002/9781119606475.ch8|W8.{5,6}]],PS14.1            |
|  23 | 10/12 | Algoritmos de Branch and bound 1.                         |          7.5  |  {{e0820242.pdf|E8}}                         |  {{se0820242.pdf|S8}}                                          | [[https://onlinelibrary.wiley.com/doi/10.1002/9781119606475.ch7|W7]],G5.2.3                  |
|  24 | 12/12 | Algoritmos de Branch and bound 2.                         |          7.5  |                                              |                                                                | [[https://onlinelibrary.wiley.com/doi/10.1002/9781119606475.ch7|W7]],G5.2.3                  |
|  25 | 17/12 | Revisão e exercícios.                                     |               |  {{e0920242.pdf|E9}}                         |  {{se0920242.pdf|S9}}                                          |										|                             
|  26 | 19/12 | **Prova 3**                                               |               |  {{p0320242.pdf|P3}}                         |  {{sp0320242.pdf|SP3}}                                         |                                                                         |
|   23/12-04/01 || **Recesso Escolar** |||||
|  27 | 07/01 | Apresentação de trabalhos (EAD).                          |               |                                             |                                                                                                         |                                                                         |
|  28 | 09/01 | Apresentação de trabalhos (EAD).                          |               |                                             |                                                                                                         |                                                                         |
|  29 | 14/01 | [[:inf05010:apr|Algoritmos de aproximação.]]              |               |                                             |                                                                                                         |                                                                         |
|     |       | Provas de recuperação.                                    |               |                                             |                                                                                                         |                                                                         |
|     | 18/01 | Término oficial das aulas.                                |               |                                             |                                                                                                         |                                                                         |
V: Vanderbei, W: Wolsey, PS: Papadimitriou/Steiglitz MF: Maculan/Fampa

==== 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}} de GLPK e MathProg

==== Ferramentas ====

  * Visualização de LPs [[https://gilp.henryrobbins.com/en/latest/examples/index.html|GILP]]
  * Vanderbei's  [[http://www.princeton.edu/~rvdb/JAVA/pivot/simple.html|simple pivot tool]] and [[https://vanderbei.princeton.edu/JAVA/pivot/advanced.html|advanced 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>