====== Otimização combinatória (2020/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. (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:** Seg/Qua 10.30, Zoom, [[http://mapa.ufrgs.br/index.php?verb=pan&building=1885|prédio 43413]] (67).\\
**Consultas:** Qui 13.30, Zoom, [[http://mapa.ufrgs.br/index.php?verb=pan&building=44|prédio 43425]].\\
**Detalhes:** {{sy.pdf|Programa}}.

===== Resultados =====

  * [[2020-1-FF|Frequência]]
  * [[2020-1-Notas|Notas]]
  * [[2020-1-Trabalhos|Trabalhos]]
  * [[2020-1-Quiz|Quiz]]

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

  * 29 de julho: [[http://www.inf.ufrgs.br/~mrpritt/oc/ere.pdf|Informações sobre ERE]]
  * 29 de julho: Prazo para definição do trabalho!
  * 13 de julho: Definição do trabalho prático aberto!
  * 1 de maio: {{SyEad-approved.pdf|Plano de atuação aprovado pela COMGRAD}}
  * 16 de março: As aulas foram suspensas.
  * Otimização: [[https://youtu.be/Dc38La-Xvog|tudo que você consegue fazer eu faço melhor]]. 8-)

===== Materiais =====

  * {{notas-10993.pdf|Notas de aula (Julho de 2020)}}.
  * Página da disciplina em [[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 pág. ^  Exercícios  ^  Soluções 	 ^ Leitura ^ Prazos ^
|     |       | ** Programação linear **                                                         ||||||
|   1 | 09/03 | Administrativa, Introdução: Exemplos e solução gráfica.                          |     9-11 |  {{q0120201.pdf|Q1}}, {{e0120201.pdf|E1}}  |  {{e0120201.pdf|S1}}  | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_1|V1]],MF1,2             |
|   2 | 11/03 | Formulação e exemplos.                                                           |    11-13 |  {{q0220201.pdf|Q2}}                       |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_1|V1]],MF2               |
|  ** :!: Cronograma para aulas não presenciais **                                               |||||||
|   3 | 11/05 | [[:inf05010:2020-1-lab1|Laboratório de formulação.]]                                    |       14 |  {{e0220201.pdf|L1}}                       |  {{se0220201.pdf|SL1}}  |                      |
|   4 | 13/05 | [[:inf05010:2020-1-simplex1|Forma matricial e normal, introdução método simplex.]]      |    15-20 |  [[https://forms.gle/RdzdYs1XjpFwQV7PA|Q3]],{{q0320201.pdf|SQ3}}  |  {{q0320201.pdf|SQ3}}   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_2|V2]].1,MF2,3           |
|   5 | 18/05 | [[:inf05010:2020-1-simplex2|Método simplex. Sistemas ilimitados.]]                      |    27-35 |  [[https://forms.gle/ENthrcHzAGBYkiPG6|Q4]],{{q0420201.pdf|SQ4}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_2|V2]].2,2.3,MF3.{1,2}   |
|   6 | 20/05 | [[:inf05010:2020-1-simplex3|Método simplex. Pivô tool, fase I. Soluções degeneradas.]]  |    35-46 |  [[https://forms.gle/DKvgosVaWNmVKxiy7|Q5]],{{q0520201.pdf|SQ5}}  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_2|V2]].4,MF3.3           |
|   7 | 25/05 | [[:inf05010:2020-1-dualidade1|Dualidade: Introdução, teoremas de dualidade.]]           |    35-42 |  [[https://forms.gle/P16jajqAZbzeWbSJ6|Q6]]  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_5|V5]].{1,2,3,4,6},MF4   |
|   8 | 27/05 | [[:inf05010:revisao120201|Revisão e exercícios.]]                                |          |  {{e0320201.pdf|E2}}                         |  {{s0320201.pdf|S2}}  |                                                                        | <del>Prazo A4Q3</del> |
|   9 | 01/06 | [[:inf05010:2020-1-dualidade2|Dualidade: Folgas complementares. Método simplex dual.]]  |    51-59 |  [[https://forms.gle/zFUq4aXGnHqoBVbj7|Q7]]  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_3|V3]],MF3.6             | <del>Prazo A5Q4</del> |
|  10 | 03/06 | **Prova 1**                                                                      |          |  [[https://forms.gle/nLTh7iN6fhB6Tu3U7|Formulário]] |  {{sp0120201.pdf|SP1}}  |                      | <del>Prazo A6Q5</del> |
|  11 | 08/06 | [[:inf05010:2020-1-dualidade3|Método simplex dual. Analise de sensibilidade.]]          |    60-17 |  [[https://forms.gle/mXjJoAUxSmDWavccA|Q8]]  |   | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_6|V6]].{1,2,3},[[http://dx.doi.org/10.1007/978-1-4614-7630-6_7|V7]].1      | <del>Prazo A7Q6</del> |
|  12 | 10/06 | [[:inf05010:2020-1-dualidade4|Analise de sensibilidade.]]                               |    72-79 |  [[https://forms.gle/F4xoWZFvqDKhNirVA|Q9]], {{e0420201.pdf|E3}}  |  {{s0420201.pdf|S3}}  | [[http://dx.doi.org/10.1007/978-1-4614-7630-6_6|V6]].{1,2,3},[[http://dx.doi.org/10.1007/978-1-4614-7630-6_7|V7]].1      | <del>Prazo A8E2</del> |
| || ** Programação inteira I **                                                                    ||||||
|  13 | 15/06 | [[:inf05010:2020-1-pi1|Introdução e aplicações.]]                                       |   87-103 |  [[https://forms.gle/LT6ZwSW3m2EVgP6b9|Q10]]  |   | W1.{1-4},PS13.1      | <del>Prazo A9Q7</del> |
|  14 | 17/06 | [[:inf05010:2020-1-pi2|Formulação e exemplos.]]                                         |  105-112 |  [[https://forms.gle/GWHASxUCSrDH76kC8|Q11]], {{e0520201.pdf|E4}}  |  {{s0520201.pdf|S4}}  | W1.{5-7},PS13.1      | <del>Prazo A11Q8</del> |
|  15 | 22/06 | [[:inf05010:2020-1-pi3|Laboratório de formulação.]]                                     |          |  {{l0620201.pdf|L2}}  |  {{sl0620201.pdf|SL2}}  |                      | <del>Prazo A12Q9</del> |
|  16 | 24/06 | [[:inf05010:revisao220201|Revisão e exercícios.]]                                |          |   |   |                      | <del>Prazo A13Q10</del> |
|  17 | 29/06 | **Prova 2**                                                                      |          |  [[https://forms.gle/C8ScxcaLzmX8b1Rk8|Formulário]]  |  {{sp0220201.pdf|SP2}}  |                      |
| || ** Heurísticas e aproximação **                                                                ||||||
|  18 | 06/07 | [[:inf05010:2020-1-mh1|Busca local.]]                                                   |  155-169 |  [[https://forms.gle/xJwmSSxs4oyXjNpT7|Q12]]  |  [[http://nbviewer.jupyter.org/url/www.inf.ufrgs.br/~mrpritt/oc/D01-tsp-h1.ipynb|D1]]  |                      | <del>Prazo A14Q11</del>   |
|  19 | 08/07 | [[:inf05010:2020-1-mh2|GRASP, Simulated annealing, Busca local iterada, VNS.]]          |  169-179 |  [[https://forms.gle/1L2TGSpv6X4kXAk1A|Q13]]  |  [[http://nbviewer.jupyter.org/url/www.inf.ufrgs.br/~mrpritt/oc/D02-tsp-h2.ipynb|D2]]  |                      | <del>Prazo A15L2</del>    |
|  20 | 13/07 | [[:inf05010:2020-1-mh3|Busca Tabu, Algoritmos genéticos, meméticos.]]                   |  181-190 |  [[https://forms.gle/X228668qouojA9WL6|Q14]]  |   |                      | <del>Prazo A16E3/E4</del> |
| || ** Programação inteira II **                                                                    ||||||
|  21 | 15/07 | [[:inf05010:2020-1-pi4|Matrizes totalmente unimodulares.]]                              |  121-128 |  [[https://forms.gle/vSjZXX1b2eNU8pfB8|Q15]]  |   | W3.{1,2},K5.4,PS13.2 |
|  22 | 20/07 | [[:inf05010:2020-1-pi5|Problemas com solução simples.]]                                 |  128-130 |  [[https://forms.gle/8Wy2mHGN3yKmbide6|Q16]]  |   | W3.{3,4},PS13.2      | <del>Prazo A18Q12</del>   |
|  23 | 22/07 | [[:inf05010:2020-1-pi6|Desigualdades válidas.]]                                         |  130-136 |  [[https://forms.gle/uCQya6zGggcKXPFh7|Q17]]  |   | W8.{1-4}             | <del>Prazo A19Q13</del>   |
|  24 | 27/07 | [[:inf05010:2020-1-pi7|Algoritmos de planos de corte.]]                                 |  137-141 |  [[https://forms.gle/vvbtcjWkdyjMmqw8A|Q18]]  |   | W8.{5,6},PS14.1      | <del>Prazo A20Q14</del>   |
|  25 | 29/07 | [[:inf05010:2020-1-pi8|Algoritmos de Branch-and-bound.]]                                |  141-147 |  [[https://forms.gle/kMu8NNotJ1W26dLg9|Q19]]  |   | W7,G5.2.3            | <del>Prazo A21Q15</del>   |
|  26 | 03/08 | [[:inf05010:revisao320201|Revisão e exercícios.]]                                |          |  {{l0720201.pdf|E5}}  |  {{sl0720201.pdf|S5}}  |                      | <del>Prazo A22Q16</del>   |
|  27 | 05/08 | [[:inf05010:2020-1-apr|Algoritmos de aproximação.]]                                     |          |   |   |                      | <del>Prazo A23Q17</del>   |
|  28 | 10/08 | **Prova 3**                                                                      |          |  [[https://forms.gle/sFTd9MGV9YYN2Luv6|Formulário]]  |   |  {{sp0320201.pdf|SP3}}  | <del>Prazo A24Q18</del>   |
|     | 12/08 | [[:inf05010:2020-1-qa1|Sessão de dúvidas trabalho.]]                                    |          |   |   |                      | <del>Prazo A25Q19</del>   |
|  29 | 17/08 | Apresentação de trabalhos.                                                       |          |   |   |                      | <del>Prazo A26E5</del>    |
|  30 | 19/08 | Apresentação de trabalhos.                                                       |          |   |   |                      | <del>Prazo A27Q20</del>   |
|     | 31/08 | Prova de recuperação.                                                            |          |   |   |                      |                |
|  ** Cronograma ERE para quem não participou nas provas e trabalhos **                   ||||||||
|     || ** Programação linear **                                                         ||||||
|     | 24/08 | Sessão de perguntas e respostas unidade 1                                 ||||||
|     | 02/09 | Revisão unidade 1							  ||||||
|     | 09/09 | **Prova 1**                                                               ||||  {{sp0120201a.pdf|SP1}}  ||
|     | 21/09 | Sessão de perguntas e respostas unidade 2				  ||||||
|     || ** Programação inteira I **                                                      ||||||
|     | 05/10 | Revisão unidade 2							  ||||||
|     | 07/10 | **Prova 2**                                                               ||||  {{sp0220201a.pdf|SP2}}  ||
|     || ** Heurísticas e aproximação **                                                  ||||||
|     | 19/10 | Sessão de perguntas e respostas Heurísticas				  ||||||
|     || ** Programação inteira II **                                                     ||||||
|     | 26/10 | Sessão de perguntas e respostas unidade 3				  ||||||
|     | 09/11 | Revisão unidade 3							  ||||||
|     | 11/11 | **Prova 3**                                                               ||||  {{sp0320201a.pdf|SP3}}  ||
|     | 23/11 | Apresentação de trabalhos.                                                ||||||
|     | 30/11 | Prova de recuperação.                                                     ||||||
|     | 02/12 | [[https://www.inf.ufrgs.br/~mrpritt/R025-27-07-2020.html#anexo|Término oficial das aulas.]]   ||||||
|  ** :!: Final da suspensão atual: 31 de dezembro **                                     ||||||||

Livros: [V] Vanderbei, [MF] Maculan, Fampa, [W] Wolsey, [G] Goldbarg, [K] Korte, Vygen, [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]]
  * 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>