Recursos de pesquisa operacional

Pessoas com origens diferentes se juntam à equipe de pesquisa operacional do Google. Alguns são doutorados e conhecidos na área; outros são excelentes engenheiros de software entusiasmados com o aprendizado da otimização matemática.

Às vezes, os engenheiros de software perguntam aos especialistas em OR como saber mais sobre o OR. Começamos a coletar nossas respostas em um documento, com trecho abaixo. Essas são opiniões dos Googlers individuais, não endossos oficiais do Google. Esperamos que você goste de ouvir nossa conversa em equipe.

MOOCs

Curso Autor Observações Comentários
Aula do Coursera sobre otimização discreta Van Hentenryck MIP e CP Kvothe@: Adorei. Ainda não terminei o problema final definido.
Modelagem básica para otimização discreta Lee e Stuckey Foco maior na CP
Modelagem avançada para otimização discreta Lee e Stuckey
Solução de algoritmos para otimização discreta Lee e Stuckey
Como modelar e resolver problemas de IA no Picat Barták
OR(1): modelos e aplicativos Kung Zaphod@: Esses e os dois próximos são uma ótima introdução a tudo relacionado a LP/IP.
OR(2): Algoritmos de otimização Kung
OR(3): teoria Kung

Princípios básicos de LP e MIP

Capa Título Autor Comentários
Capa de introdução à otimização linear Introdução à otimização linear Bertsimas e Tsitsiklis BlackLotus@: Para LP (e, em menor medida, MIP), esse livro é o melhor.

Patrick@: Reprovando Bertsimas-Tsitsiklis, porque se trata mais de um "Segundo curso" sobre programação linear. Para isso, é melhor fazer isso com Introdução à otimização linear.

BadBoy@: Preciso dar uma olhada nisso. Geralmente eu não gosto da forma como esses caras apresentam as coisas, mas posso estar errada.

Kvothe@: Os capítulos 10 ("Fórmulas de programação com números inteiros") e 11 ("Métodos de programação com números inteiros") são ótimos.
Capa de Programação Linear Programação linear Vanderbei
Capa de Otimização Combinatória Otimização Combinatória: polihedra e eficiência Schrijver SpiderWoman@: Eu me lembro de gostar da "Otimização Combinatória" de Schrijver quando ela era, mas é muito matemática e não é algo que eu recomendaria a alguém que entrasse na equipe, por exemplo...
Capa da Teoria da Programação de Linear e Inteiro Teoria da programação de números inteiros e lineares Schrijver BadBoy@: É legal mostrar na sua biblioteca, ao fazer uma entrevista, ou para impressionar alguém. Você provavelmente não vai ler nem gostar dele, a menos que tenha um PhD em matemática pura e destilada. Então não é uma coisa com que começar LP ou MIP. Dito isso, ele contém muitas provas e informações interessantes. Coisas como matrizes totalmente unimodulares e o que elas implicam. E a bibliografia é incrivelmente bem detalhada, com citações nos idiomas originais. É uma espécie de arte da programação computacional do Knuth. Só que este não é fácil de ler.

Kvothe@: Não li, mas desconfiei pelo uso apenas da família tipográfica.
Imagem da capa de um primeiro curso de otimização linear Um primeiro curso de otimização linear Lee Disponível sem custo financeiro sob uma licença CC.
Capa de introdução à otimização matemática Introdução à otimização matemática Fischetti BadBoy@: Analisei a versão em italiano. Está muito bom. Adoro o que Fischetti faz em geral.
Capa de Programação Linear Programação linear Chvatal BadBoy@: Não gosto do livro, mas é onde aprendi tudo sobre LP, e a notação é ótima.
Capa de Otimização Combinatória Otimização combinada Papadimitriou e Steiglitz BadBoy@: Adorei. Ela está desatualizada, mas precisa ser lida.

Kvothe@: Um pouco seco para o meu gosto.
Capa da programação de números inteiros Programação de números inteiros Wolsey Unicorn@: Muito conciso, mas abrange a maioria das partes interessantes da área (do ponto de vista de solucionadores)
Capa da programação de números inteiros Programação de números inteiros Conforti, Cornuéjols e Zambelli Patrick@: Provavelmente o livro mais atualizado sobre a teoria/metodologia de MIP.
Capa das Facetas da Otimização Combinatória Facetas da otimização Combinatória Jünger e Reinelt Patrick@: Mais sobre o lado teórico e voltado para o trabalho do ex-diretor da ZIB, Martin Grötschel, em sua comemoração de 65 anos, mas inclui o que eu acho que é a versão mais recente desta pesquisa computacional MIP: "Tobias Achterberg e Roland Wunderling. Programação de números inteiros mista: análise de 12 anos de progresso".
Cover de 50 anos de programação de números inteiros 50 anos de programação de números inteiros: 1958-2008 Jünger et al., ed. Patrick@: Um pouco desatualizado, mas uma revisão muito boa do histórico e da tecnologia de ponta do MIP.
Referência sobre algoritmos de fluxo de rede Algoritmos de fluxo de rede Williamson Unicorn@: Um bom livro com muitos resultados recentes sobre fluxos de rede, ainda que seja intuitivo. Mas apenas para fluxos de rede, então não é tão genérico. Resenha mais completa em francês.
Resumo sobre algoritmos Algoritmos iluminados: algoritmos para problemas difíceis de NP Ruygarden Unicorn@: Provavelmente não é o livro mais avançado do grupo. Ainda assim, fornece uma introdução a alguns algoritmos OR (do ponto de vista de um curso sobre algoritmos). Muito legível. Resenha mais completa em francês.
Capa de Otimização prática Otimização prática Gill, Murray e Wright Unicorn@: Livro de referência antigo sobre otimização contínua. Se precisar de alguma explicação sobre essa família de algoritmos, este livro é para você. (Resenha mais completa em francês.)
Capa de Introdução à Otimização e ao Cálculo Semidiferencial de Hadamard Introdução à otimização e ao cálculo semidiferencial de Hadamard Delfour Unicorn@: Livro muito formal sobre otimização semidiferencial. Não é fácil entrar nessa. Resenha mais completa em francês.
Capa da hierarquia do momento-SOS A hierarquia Moment-SOS: palestras sobre probabilidade, estatística, geometria computacional, controle e PDEs não lineares Henrion, Korda e Lasserre Unicorn@: se você estiver otimizando com polinômios ou se perguntando até onde pode chegar com eles, vai aprender o básico sobre a hierarquia SoS e aplicações que não conhecem. Resenha mais completa em francês.
Capa de Introdução à Pesquisa Operacional Introdução à pesquisa operacional Hillier e Lieberman Kvothe@: Uma boa mistura de teoria e prática. Um bom primeiro texto para pessoas novas no campo, com exemplos treinados e muitos exercícios, alguns com respostas no final do livro. Desvantagens: é um pouco difícil direcionar os usuários ao site e usa solucionadores obsoletos.

Avaliações de pesquisa

Revisão Autor Comentários
175 anos de programação linear Chandru e Rao BadBoy@: É uma ótima série de artigos. Fui exposto a isso na IBM no início dos anos 90. Não sei quem primeiro teve a ideia de apresentar a programação linear como essa, mas Vijay Chandru e Jean-Louis Lassez também estavam envolvidos.

O bom disso é que você só precisa de álgebra linear básica para entendê-la, e você pode provar quase qualquer teorema importante em LP com o básico. O melhor seria um livro sobre LP com isso, mais um pouco do Chvatal, alguns Vanderbei, depois problemas de implementação e referências aos livros relevantes. O Chvatal e o Vanderbei não têm um pouco de fundamento matemático.

Ele é antigo e logo será renomeado como 200 anos de Programação Linear. Provavelmente houve tentativas anteriores.

Artigos de pesquisa

Artigo Autor Comentários
Um novo algoritmo de tempo polinomial para programação linear Karmarkar BadBoy@: artigo de Karmarkar sobre o algoritmo de Karmarkar. O exemplo de como um artigo não deve ser escrito. Levou anos para fazer uma implementação funcional e, enquanto isso, eles descobriram que era mais um método de ponto interno.

Modelagem

MPC

Capa Título Autor Comentários
Capa de Criação de modelos em programação matemática Criação de modelos em programação matemática Williams Foco em LP e MIP.

Temere@: Não gostei de verdade. A estrutura é estranha (e aumenta artificialmente o número de páginas). E é fortemente enraizado em "aplicações OR clássicas" (foco em planejamento de economia ou quase algo parecido com brinquedos) com pouca relevância para modelos MIP que geralmente temos no Google

Azalee@: Concordo.

BadBoy@: Ainda acho que o livro era ótimo antes. Eu dei uma olhada lá há uns dois anos, e caramba. Está desatualizado. Além disso, conheço o autor desde 1990 e nos reconectamos no ISMP 2015. Ele é um ótimo cara, aposentado, viajando para conferências com seu dinheiro e ainda faz ótimas apresentações. Os documentos dele eram excelentes, especialmente sobre a eliminação de Fourier. Ele tem uma visão muito ampla do que é LP e foi fundamental para iniciar o XpressMP.
Capa de aplicações de otimização com XpressMP Aplicações de otimização com o XpressMP Guéret, Prins, Sevaux e Heipcke

Guias de modelagem fornecidos pelo solucionador

Guia Descrição Comentários
Manual de modelagem do MOSEK Foca a otimização convexa cônica. Unicorn@ Uma referência real para mim ao fazer modelos não lineares.
Manual do portfólio MOSEK Modelos cônicos para otimização de portfólio

Avaliações de pesquisa: MIP

Revisão Autor Descrição
Técnicas de formulação de programação linear de números inteiros mistas Vielma Concentra-se na força e no tamanho de formulações de números inteiros mistos para uniões de funções lineares em partes semelhantes às poliedras. Mais sobre o lado teórico, mas inclui algumas técnicas práticas, como formulações incrementais na seção 8.
Funções lineares em partes não convexas: formulações avançadas e ferramentas de modelagem simples. Huchette e Vielma Técnicas mais recentes para funções lineares em partes que não estão incluídas na revisão acima.

Análises de pesquisa: MINLP

Revisão Autor Descrição
Representabilidade convex de números inteiros mistos Lubin, Vielma e Zadik Somente para relaxamento convexo.

Otimização sob incerteza

Otimização estocástico

Capa Título Autor Comentários
Capa de palestras sobre programação estocástico Palestras sobre programação estocástica: modelagem e teoria Shapiro, Dentcheva e Ruszczynski
Capa de Introdução à programação estocástico Introdução à programação estocástico Birge e Louveaux Unicorn@: uma introdução mais teórica ao tópico. Não recomendo tanto quanto as palestras sobre programação estocástico.

Avaliações de pesquisa

Revisão Autor
Otimização do valor em risco condicional Rockafellar e Uryasev

Otimização robusta

Capa Título Autor Comentários
Capa de otimização robusta Otimização robusta Ben-Tal, El Ghaoui e Nemirovski PDF
Unicorn@: uma ótima referência se as avaliações abaixo não forem detalhadas o suficiente. Uma grande parte é dedicada a problemas não lineares (normalmente não apresentados nas avaliações).
Gosto muito da Seção 1.1.2 porque ela mostra numericamente que pequenos desvios de coeficiente podem gerar grandes inviabilidades.
Capa de Otimização robusta e adaptável Otimização robusta e adaptável Bertsimas e Dick Den Hertog PDF
Unicorn@: Excelente referência sobre qualquer questão de otimização robusta! É bastante completo e poderia ser melhor se complementando os algoritmos. Resenha mais completa em francês.

Avaliações de pesquisa

Revisão Autor
Um guia prático para uma otimização robusta Gorissen, Yanıkoğlu e den Hertog
Teoria e aplicações da otimização robusta Bertsimas, Brown e Caramanis

Artigos de pesquisa

Artigo Autor
Análise estocástico tracionável em dimensões altas por meio de otimização robusta (PDF) Bandi e Bertsimas

StackExchange

Quais são bons livros de referência para introdução à pesquisa operacional?

Livros/materiais recomendados para aplicações práticas de pesquisa operacional no setor