Otimiza˘c~ao Combinat oria: Aplica˘c~oes e desa o · Otimiza˘c~ao I E o ato de obter o melhor resultado sobre uma dada circunstancia. I Pode ser de nida como o processo de achar

Otimizacao Combinatoria: Aplicacoes e desafio

Luidi Gelabert [email protected]

http://cos.ufrj.br/~luidi/

PESC - COPPE - UFRJCoordenador ECI - Escola Politecnica UFRJ

Seminario CEFET - RJ - 2019

Luidi G. Simonetti (PESC/UFRJ) Otimizacao Combinatoria: Aplicacoes e desafio Seminario CEFET - RJ - 2019 1 / 40

http://cos.ufrj.br/~luidi/

Otimizacao

?Luidi G. Simonetti (PESC/UFRJ) Otimizacao Combinatoria: Aplicacoes e desafio Seminario CEFET - RJ - 2019 2 / 40

Otimizacao

I E o ato de obter o melhor resultado sobre uma dada circunstancia.

I Pode ser definida como o processo de achar as condicoes que dao omaximo e mınimo de uma funcao

I Os metodos de busca pelo otimo sao conhecidos como tecnicas deprogramacao matematica e normalmente estudados como parte dapesquisa operacional.


Otimizacao - Pesquisa Operacional

I E um ramo interdisciplinar da matematica aplicada que faz uso demodelos matematicos, estatısticos e de algoritmos na ajuda a tomadade decisoes

I E usada sobretudo para analisar sistemas complexos do mundo real,tipicamente com o objetivo de melhorar ou otimizar a performance


Origem - Pesquisa Operacional

I A investigacao operacional nasceu durante a II guerra mundial,quando os Aliados se viram confrontados com problemas (logıstica emilitar) de grande dimensao e complexidade.

I Aplicaram o metodo cientıfico aos problemas que lhes foram sendocolocados e criaram modelos matematicos que lhes permitissemavaliar o resultado hipotetico de estrategias ou decisoes alternativas.

I Com o fim do conflito e sucesso obtido, os grupos de cientistastransferiram a nova metodologia na abordagem de problemas para asempresas.

I Com a evolucao observada na informatica criaram-se condicoes deconcretizacao algorıtmica e velocidade de processamento adaptados aimaginacao dos profissionais da pesquisa operacional.


Desenvolvimento Historico - Otimizacao

Isaac Newton (1643 - 1727)Calculo Diferencial, ...

Joseph-Louis Lagrange (1736 - 1813)Calculo variacional, minimizacao funcional,metodo de otimizacao para problemas restritos, ...

Augustin-Louis Cauchy (1789 - 1857)Solucao por substituicao direta,metodo do gradiente (ou metodo do maximo declive), ...



Leonhard Euler (1707 - 1783)Calculo variacional, minimizacao funcional,...

Gottfried Leibnitz (1646 - 1716)Calculo Diferencial, ...

George Bernard Dantzig (1914 - 2005)Programacao Linear, metodo Simplex (1947),...



Harold William Kuhn (1925 - 2014)Condicoes necessarias e suficientes da solucao otimade problemas de programacao matematica,teoria de jogos, ...

Albert William Tucker (1905 - 1995)Condicoes necessarias e suficientes da solucao otimade problemas de programacao matematica,Programacao nao linear, teoria de jogos (Orientou JohnNash [PhD]), ...



Richard Bellman (1920 - 1984)Principio de otimalidade em programacao dinamica,...

John Von Neumann (1903 - 1957)Teoria dos jogos,...


Exemplo de Programacao Nao Linear Restrita

I O problema geral de otimizacao consiste em

min f (x) ← funcao objetivo

s.a. H(x) = 0, ← restricoes

G (x) ≤ 0.

I onde f : Rn → R, hi : Rn → R, i ∈ IH , e gi : Rn → R, i ∈ IG .

I O conjunto viavel Ω = x ∈ Rn | H(x) = 0, G (x) ≤ 0.

I Normalmente temos um conjunto infinito de solucoes viaveis.

Luidi G. Simonetti (PESC/UFRJ) Otimizacao Combinatoria: Aplicacoes e desafioSeminario CEFET - RJ - 2019 10 / 40

Exemplo Programacao Nao Linear Restrita

min f (x) = (x1 − 2)2 + (x2 − 1)2

s.a. g1(x) = x1 + x2 − 2 ≤ 0,

g2(x) = x21 − x2 ≤ 0.

x2

x1


Definicoes

CombinatoriaI e um ramo da matematica que estuda colecoes finitas de elementos

que satisfazem criterios especıficos determinados e se preocupa, emparticular, com a “contagem”de elementos nessas colecoes.

Otimizacao Combinatoria

I e um ramo da ciencia da computacao, pesquisa operacional e damatematica aplicada que estuda problemas de otimizacao emconjuntos finitos.



I Em muitos problemas, a busca exaustiva nao e tratavel. (Mesmotendo um conjunto de solucoes finito)

I A otimizacao combinatoria e um subconjunto da otimizacaomatematica relacionada a pesquisa operacional, a algoritmos e ateoria da complexidade computacional.

I Possui aplicacoes importantes em varios campos, incluindointeligencia artificial, aprendizado de maquina, teoria de leiloes eengenharia de software.


Historia Combinatoria

I Conceitos combinatorios basicos e resultados enumerativosapareceram em todo o mundo antigo.

I No seculo VI AC, o antigo medico indiano Sushruta afirma que 63combinacoes podem ser feitas de 6 gostos diferentes, calculandotodas as 26 − 1 possibilidades.

I O historiador grego Plutarco discute uma discussao entre Crisipo(seculo III AC) e Hiparco (seculo 2 AC) de um problema enumerativobastante delicado, que mais tarde se mostrou relacionado aosnumeros de Schroder – Hipparchus.

I Arquimedes (seculo 3 AC) considera um quebra-cabeca de azulejos.

I O matematico indiano Mahavıra (850) forneceu formulas para onumero de permutacoes e combinacoes, e essas formulas podem tersido familiares aos matematicos indianos no inıcio do seculo VI.

I ...Luidi G. Simonetti (PESC/UFRJ) Otimizacao Combinatoria: Aplicacoes e desafioSeminario CEFET - RJ - 2019 14 / 40

Historia Combinatoria

I Durante o Renascimento, junto com o resto da matematica e dasciencias, a combinatoria teve um renascimento. Os trabalhos dePascal, Newton, Jacob Bernoulli e Euler tornaram-se fundamentais nocampo emergente.

I A teoria dos grafos tambem teve uma explosao de interesse ao mesmotempo, especialmente em relacao ao problema das quatro cores.

I O crescimento rapido eliminaram as fronteiras entre combinatoria epartes da matematica e da ciencia da computacao, mas ao mesmotempo levou a uma fragmentacao parcial do campo.


Complexidade

PNP

NPC

NPD

NP = P

NPD


Dificuldade Computacional

P

NP

NP-difícil

=?

NP-completoTSP, Ciclo HamiltonianoTetris, etc.

TSP, Ciclo HamiltonianoTetris, etc.

XadrezXadrez Problemada paradaProblemada parada


Otimizacao Combinatoria - Forca Bruta

I Tentando resolver por enumeracaoI Normalmente o numero de solucoes viaveis sao n! ou 2n.

n log n n2 2n n!10 3.32 102 1.02x103 3.6x106

100 6.64 104 1.27x1030 9.33x10157

1000 9.97 106 1.07x10301 4.02x102567

I Num supercomputador atual (1016 flops) seria necessario 2.95x10134

anos (100!) e 1.27x102544 anos (1000!).

Obs: o universo tem 13.82x109 anos e 6x1079 atomos de hidrogenio.

I Usando enumeracao completa so revolvemos problemas para n muitopequeno!!

I Obs: Numero de solucoes nao e absoluto!Ex. Arvore geradora x Caminho hamiltoniano


Problema da Mochila 0-1

I Versao 1:I Um ladrao tem n possıveis itens para roubarI Cada item i tem um valor ci e peso aiI O ladrao tem um limite maximo de peso que consegue levar bI Objetivo: selecionar os itens com maior valor

I Versao 2:I Uma empresa tem n possıveis projetos para investirI Cada projeto tem um custo ai e um retorno ciI O orcamento da empresa para investir e limitado bI Objetivo: selecionar um portfolio de projeto de maximo retorno

I Um problema pode ser “adaptado” para outros problemas “reais”



I Uma empresa tem n possıveis projetos para investir

I Cada projeto tem um custo ai e um retorno ciI O orcamento da empresa para investir e limitado b

I Objetivo: selecionar um portfolio de projeto de maximo retorno

I Formulacao Matematica

max

n∑

i=1

cixi : x ∈ P ∩ Bn

Onde P e dado por:n∑

i=1

aixi ≤ b

0 ≤ xi ≤ 1, ∀i ∈ 1, . . . , n






I Exemplo de Heurıstica Gulosa

9

347

53 32

12 8 17 11 6 2 2

=⇒

1. ordenar os n elementos em ordem decrescente da razaocjaj

2. adicionar os elementos nessa ordem ate o limite ser estourado

I Solucao heurıstica - custo 22

I Solucao otima - custo 23







75

3 3 4

3

2

12 8 17 11 6 2 2 22

=⇒











4

5

3

7

3 32

12 8 17 11 6 2 2 23

=⇒






Problema com multiplas Mochilas

I n itens e m mochilas

I Cada item i um retorno ciI Cada item i tem um custo cij para ser adicionado a mochila j

I Cada mochila j tem uma capacidade bjI Objetivo: selecionar os itens que maximizem o retorno

I Essas multiplas mochilas podem ser necessarias para o problema oupodem garantir um grau de diversidade.


Problema da Mochila quadratica

I Um estudante tem n possıveis itens para escolher

I Cada item tem um peso ai e um retorno ciI A capacidade da mochila e b

I Alem do retorno de cada item temos o retorno de escolher dois itensconjugados

I Objetivo: selecionar os itens que levem ao maximo retorno


Problema do Caixeiro Viajante (Traveling SalesmanProblem, TSP)

I E o mais famoso problema em Otimizacao Inteira e Combinatoria!

I Um conjunto de cidades N = 1, . . . , n e dado.

I O tempo de viagem entre quaisquer duas cidades e conhecido.

I Um caixeiro viajante deve visitar cada cidade uma unica vez eretornar ao ponto de partida.

I Objetivo: Definir uma ordem de visita de forma a retornar ao pontode partida o mais rapido possıvel.

I uma solucao viavel do TSP e chamado de um tour e, no grafo,corresponde a um ciclo hamiltoniano.



5 4

62

31



5 4

62

31


Problema do Caixeiro Viajante (Traveling SalesmanProblem, TSP)USA - 13509 cidades


Problema do Caixeiro Viajante (Traveling SalesmanProblem, TSP)USA - 13509 cidades


Problema do Caixeiro Viajante (Traveling SalesmanProblem, TSP)Alemanha - 15112 cidades


Problema do Caixeiro Viajante (Traveling SalesmanProblem, TSP)Alemanha - 15112 cidades



I Por que estudar um problema que nao tem mais tanta aplicacaopratica?

I Um metodo desenvolvido para um problema “normalmente”pode seradaptado para outros

I Na verdade o TSP tem diversas aplicacoes atuaisI A principal aplicacao vem de subproblemas em varias aplicacoes de

transporte e logıstica (Onibus escolar, equipamento agrıcola para testede solo, visita agendada em firma de cabo, delivery de refeicao parapessoas “restritas” em casa, planejamento de retroescavadeira emarmazens, etc)

I planejamento de uma maquina de furar uma placa de circuitoI Otimizar a sequencia de imagens de objetos celestesI Coleta de moedas em telefones publicosI . . .


Problema do Caixeiro Viajante (Traveling SalesmanProblem, TSP)Placa de circuito - 7397 pontos






Exemplo: Roteamento de veıculos


Exemplo: Roteamento de veıculos


Exemplo: Roteamento de veıculosVariacoes - Capacitado - Ex: 20


Exemplo: Roteamento de veıculosVariacoes - Coleta e Entrega - Ex: 20


Exemplo: Roteamento de veıculosVariacoes - Multiplos Depositos


Roteamento de veıculos

Realidade

I Janela de tempo

I Ordem dos itens nocaminhao

I Empacotamento (2d ou3d)

I Trafego

I ...


Corte e Empacotamento


Corte e Empacotamento


Arvore Geradora com numero maximo de folhasDefinicao

DadoUm grafo G = (V ,E )

AcharA arvore geradora T do grafo com maior numero de folhas

FolhaVertice adjacente a um unico vertice


Arvore Geradora com numero maximo de folhasDefinicao

DadoUm grafo G = (V ,E )

AcharA arvore geradora T do grafo com maior numero de folhas

FolhaVertice adjacente a um unico vertice


Arvore Geradora com numero maximo de folhasExemplo

G (V ,E )



Solucao (4 folhas)



Pior caso



Melhor caso


Arvore Geradora com numero maximo de folhasEquivalente ao problema

Conjunto dominante Mınimo de G : C ⊂ V tal queI para todo i ∈ V \ C : existe uma aresta com uma extremidade em i e outra em C .

I encontrar o conjunto dominante de G com o mınimo numero de vertices possıvel.

Mınimo conjunto dominante conexoI Implica numa arvore de G sem os vertices folhas T .

I Facil gerar a arvore geradora com maior numero de folhas de G.


Arvore Geradora com numero maximo de folhasEquivalente ao problema

Conjunto dominante Mınimo de G : C ⊂ V tal queI para todo i ∈ V \ C : existe uma aresta com uma extremidade em i e outra em C .

I encontrar o conjunto dominante de G com o mınimo numero de vertices possıvel.

Mınimo conjunto dominante conexoI Implica numa arvore de G sem os vertices folhas T .

I Facil gerar a arvore geradora com maior numero de folhas de G.


Mınimo conjunto dominante conexoMotivacao

I Modela rede de telecomunicacaoEx: Wireless Ad Hoc Networks

I Layoult de circuitos


Problema de Alocacao de Frequencias de celulares

I Problema de alocar frequencias a antenas de transmissaoI Antenas de transmissaoI Zona de cobertura (antenas possuem intersecoes entre as zonas)I Antenas com intersecao nas zonas de cobertura devem receber

frequencias respeitando as distancias para nao gerar interferencias)I Objetivo: 1) Minimizar a faixa de frequencias utilizadas 2) Minimizar a

interferencia





interferencia





interferencia





interferencia





interferencia


RWA (Routing and Wavelength Assignment)

I Em redes de computadores de alto desempenho, dados saotransmitidos entre terminais

I para haver comunicacao entre 2 terminais temos 1) criacao de umcaminho 2) estabelecer qual frequencia os dados serao transmitidos

I Uma fibra optica pode transmitir dados em varias frequenciasdiferentes

I Interferencia

I Objetivo : 1) Roteamento das comunicacoes a serem realizadas 2)Atribuicao de frequencias sem interferencia






I InterferenciaI Objetivo : 1) Roteamento das comunicacoes a serem realizadas 2)

Atribuicao de frequencias sem interferencia






























Arranjo Submarino


Aplicacoes

I Em todas as areas de industria e servicos

I Os problemas classicos ainda sao usados como parte de solucoes deproblemas mais complexos ou com uma simplificacao

I Novos problemas surgem com novas tecnologias, industria ou servicosI IoTI IAI Industria 4.0 (5.0)I Aplicativos (servicos)I Analytics



Obrigado


Documents

Otimiza˘c~ao Combinat oria: Aplica˘c~oes e desa o · Otimiza˘c~ao I E o ato de obter o melhor resultado sobre uma dada circunstancia. I Pode ser de nida como o processo de achar