{"id":4307,"date":"2019-12-13T14:25:24","date_gmt":"2019-12-13T17:25:24","guid":{"rendered":"http:\/\/www.inf.ufrgs.br\/profcomp\/?page_id=4307"},"modified":"2019-12-13T14:25:24","modified_gmt":"2019-12-13T17:25:24","slug":"cmp608","status":"publish","type":"page","link":"https:\/\/www.inf.ufrgs.br\/profcomp\/lista-de-disciplinas\/cmp608\/","title":{"rendered":"CMP608"},"content":{"rendered":"<p><strong>Disciplina: T\u00f3picos especiais em computa\u00e7\u00e3o:<\/strong><\/p>\n<p><strong>Programa\u00e7\u00e3o linear inteira: formula\u00e7\u00f5es, t\u00e9cnicas e aplica\u00e7\u00f5es.<\/strong><\/p>\n<p><strong>Professor respons\u00e1vel: Santiago Vald\u00e9s Ravelo.<\/strong><\/p>\n<p><strong>Pr\u00e9-requisitos: N\u00e3o h\u00e1<\/strong><\/p>\n<p><strong>Carga hor\u00e1ria: 60 horas.<\/strong><\/p>\n<p><strong>Cr\u00e9ditos: 4.<\/strong><\/p>\n<p><strong>Semestre oferecido: 2020\/1.<\/strong><\/p>\n<p><strong>S\u00famula<\/strong><\/p>\n<p>Abordagem de problemas combinat\u00f3rios sob a \u00f3tica de programa\u00e7\u00e3o linear inteira. Estudo de diferentes t\u00e9cnicas de otimiza\u00e7\u00e3o baseadas em formula\u00e7\u00f5es matem\u00e1ticas dos problemas.<\/p>\n<p>&nbsp;<\/p>\n<p><strong>Objetivos<\/strong><\/p>\n<p>Ao final da disciplina se espera que o aluno seja capaz de:<\/p>\n<ul>\n<li>Modelar\/formular problemas de otimiza\u00e7\u00e3o como de programa\u00e7\u00e3o linear inteira.<\/li>\n<li>Solucionar de forma exata esses problemas usando as formula\u00e7\u00f5es propostas e pacotes prontos (ex. CEPLEX, Gurobi).<\/li>\n<li>Projetar matheur\u00edsticas e\/ou algoritmos de aproxima\u00e7\u00e3o que explorem os modelos propostos para os problemas.<\/li>\n<\/ul>\n<p><strong>Programa<\/strong><\/p>\n<p><strong>Semana 1 <\/strong>Introdu\u00e7\u00e3o e apresenta\u00e7\u00e3o da disciplina.<\/p>\n<p><strong>Semana<\/strong> 2 &#8211; 3 Programa\u00e7\u00e3o linear.<\/p>\n<p><strong>Semana <\/strong>\u00a04- Programa\u00e7\u00e3o linear inteira.<\/p>\n<p><strong>Semana<\/strong> 5 &#8211; 6 Relaxa\u00e7\u00f5es<\/p>\n<p><strong>Semana<\/strong> 7 &#8211; 8 \u00a0M\u00e9todos exatos e pacotes.<\/p>\n<p><strong>Semana<\/strong>\u00a0 9 &#8211; 12 Matheur\u00edsticas: hibridiza\u00e7\u00e3o de heur\u00edsticas e metaheur\u00edsticas com modelos matem\u00e1ticos.<\/p>\n<p><strong>Semana<\/strong>\u00a0 13 &#8211; 16 Algoritmos de aproxima\u00e7\u00e3o baseados em formula\u00e7\u00f5es matem\u00e1ticas.<\/p>\n<p><strong>Semana<\/strong>\u00a0 17 \u2013 18 Apresenta\u00e7\u00e3o de semin\u00e1rios e entrega dos trabalhos \ufb01nais.<\/p>\n<p><strong>Crit\u00e9rios de avalia\u00e7\u00e3o<\/strong><\/p>\n<p>Os estudantes ser\u00e3o avaliados a partir da entrega de listas de exerc\u00edcios sobre os diferentes t\u00f3picos e de um trabalho a ser desenvolvido ao longo da disciplina. Considerando que alunos de diferentes \u00e1reas se inscrevam, a disciplina prop\u00f5e que cada um desenvolva um trabalho que una os conte\u00fados da disciplina e de sua \u00e1rea de pesquisa. Desta forma, cada estudante selecionar\u00e1 um problema de otimiza\u00e7\u00e3o combinat\u00f3ria relacionado \u00e0 sua \u00e1rea de pesquisa e sobre ele dever\u00e1:<\/p>\n<ol>\n<li>a) Entregar relat\u00f3rios descrevendo resultados parciais obtidos para o problema ap\u00f3s o estudo dos diferentes t\u00f3picos.<\/li>\n<li>b) Entregar um trabalho \ufb01nal (em formato de artigo cient\u00ed\ufb01co) compilando os resultados produzidos para o problema ao longo da disciplina.<\/li>\n<li>c) Apresentar os resultados de forma oral.<\/li>\n<\/ol>\n<p>A m\u00e9dia \ufb01nal ser\u00e1 calculada como segue, ponderando os itens acima relacionados, al\u00e9m da entrega de listas de exerc\u00edcios sobre os diferentes t\u00f3picos: o item a) com peso 3, o b) com peso 3, o c) com peso 2 e as listas de exerc\u00edcios com peso 2.<\/p>\n<p>&nbsp;<\/p>\n<p>Bibliogra\ufb01a<\/p>\n<p>[1 ] Vanderbei, Robert J. \u201cLInear Programming: foundations and extensions\u201d. Springer.<\/p>\n<p>[2 ] Papadimitriou, Christos and Steiglitz, Kenneth. \u201cCombinatorial Optimizaton: Algorithms and Complexity\u201d. Prentice Hall.<\/p>\n<p>[3 ] Nemhauser, George L. and Wolsey, Laurence A.. \u201cInteger and combinatorial optimization\u201d. John Wiley &amp; Sons.<\/p>\n<p>[4 ] Gar\ufb01nkel, Robert and Nemhauser, George L.. \u201cInteger Programming\u201d. John Wiley &amp; Sons.<\/p>\n<p>[5 ] Fischetti, Martina and Fischetti, Matteo. \u201cMatheuristics\u201d. Springer.<\/p>\n<p>[6 ] Maniezzo, Vittorio, Stu\u00a8tzle, Thomas and Voss, Stefan. \u201cMatheuristics Hybridizing Metaheuristics and Mathematical Programming\u201d. Springer.<\/p>\n<p>[7 ] Williamson, David P. and Shmoys, David B.. \u201cThe Design of Approximation Algorithms\u201d. Cambridge University Press.<\/p>\n<p>&nbsp;<\/p>\n<p>&nbsp;<\/p>\n","protected":false},"excerpt":{"rendered":"<p>Disciplina: T\u00f3picos especiais em computa\u00e7\u00e3o: Programa\u00e7\u00e3o linear inteira: formula\u00e7\u00f5es, t\u00e9cnicas e aplica\u00e7\u00f5es. Professor respons\u00e1vel: Santiago Vald\u00e9s Ravelo. Pr\u00e9-requisitos: N\u00e3o h\u00e1 Carga hor\u00e1ria: 60 horas. Cr\u00e9ditos: 4. Semestre oferecido: 2020\/1. S\u00famula Abordagem de problemas combinat\u00f3rios sob a \u00f3tica de programa\u00e7\u00e3o linear inteira. Estudo de diferentes t\u00e9cnicas de otimiza\u00e7\u00e3o baseadas em formula\u00e7\u00f5es matem\u00e1ticas dos problemas. &nbsp; Objetivos [&hellip;]<\/p>\n","protected":false},"author":11,"featured_media":0,"parent":462,"menu_order":608,"comment_status":"closed","ping_status":"closed","template":"","meta":[],"_links":{"self":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/4307"}],"collection":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/users\/11"}],"replies":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/comments?post=4307"}],"version-history":[{"count":1,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/4307\/revisions"}],"predecessor-version":[{"id":4308,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/4307\/revisions\/4308"}],"up":[{"embeddable":true,"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/pages\/462"}],"wp:attachment":[{"href":"https:\/\/www.inf.ufrgs.br\/profcomp\/wp-json\/wp\/v2\/media?parent=4307"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}