Risorse di ricerca operativa

Persone con background diversi nel team di ricerca operativa di Google. Alcuni sono dottori di ricerca e noti nel loro campo, altri sono ingegneri del software eccellenti, entusiasti dell'apprendimento dell'ottimizzazione matematica.

A volte gli ingegneri del software chiedono agli esperti di OR come ottenere ulteriori informazioni sull'operatore OR. Abbiamo iniziato a raccogliere le nostre risposte in un documento, estratto di seguito. Queste sono le opinioni dei singoli Googler, non le raccomandazioni ufficiali di Google. Ci auguriamo che ti piaccia ascoltare il nostro team.

MOOC

Corso	Autore	Note	Commenti
Corso Coursera sull'ottimizzazione discreta	Van Hentenryck	MIP e CP	Kvothe@: Adoro. Tuttavia non hai ancora completato la configurazione finale del problema.
Modellazione di base per l'ottimizzazione discreta	Lee e Stuckey	Più attenzione alle CP
Modellazione avanzata per l'ottimizzazione discreta	Lee e Stuckey
Risolvere gli algoritmi per l'ottimizzazione discreta	Lee e Stuckey
Modellazione e risoluzione dei problemi di IA in Picat	Barták
OR(1): Modelli e applicazioni	Kung		Zaphod@: Questi e i prossimi due sono un'ottima introduzione a tutto ciò che riguarda LP/IP.
OR(2): algoritmi di ottimizzazione	Kung
OR(3): Teoria	Kung

Nozioni di base su LP e MIP

Cover	Titolo	Autore	Commenti
	Introduzione all'ottimizzazione lineare	Bertsima e Tsitsikli	BlackLotus@: Per LP (e in misura minore MIP), penso che questo libro sia il migliore. Patrick@: Dare un voto negativo a Bertsimas-Tsitsiklis in quanto è più un "secondo corso " sulla programmazione lineare, e per questo è probabilmente l'opzione migliore in combinazione con Introduzione all'ottimizzazione lineare. BadBoy@: Devo dare un'occhiata a questo. Di solito non mi piace il modo in cui questi ragazzi presentano le cose, ma potrei sbagliarmi. Kvothe@: I capitoli 10 ("Formulazioni di programmazione con numeri interi") e 11 ("Metodi di programmazione con numeri interi") sono fantastici.
	Programmazione lineare	Vanderbei
	Ottimizzazione combinatoria: poliedri ed efficienza	Schrijver	SpiderWoman@: Ricordo che quando in passato mi piaceva "Ottimizzazione combinatoria" di Schrijver, ma è molto matematica e non è una cosa che consiglierei ad esempio a qualcuno che si unisce al team...
	Teoria della programmazione lineare e con numeri interi	Schrijver	BadBoy@: Fantastico per comparire nella tua raccolta, mentre fai un'intervista o per stupire qualcuno. Molto probabilmente non lo leggerai e non ti piacerà, a meno che tu non abbia un dottorato di ricerca in matematica pura e due volte distillata. Quindi non la cosa con cui iniziare LP o MIP. Detto questo, contiene una grande quantità di prove e informazioni interessanti. Fattori come le matrici completamente unimodulari e cosa implicano. La Biblioteca, inoltre, è incredibilmente dettagliata, con citazioni nelle lingue originali. È una sorta di arte della programmazione informatica di Knuth. Solo questo non è digeribile. Kvothe@: Non l'ho letto, ma diffidato solo del carattere.
	Un primo corso di ottimizzazione lineare	Qual è il colmo per un negoziante?	Disponibile senza costi con licenza CC.
	Introduzione all'ottimizzazione matematica	Fischetti	BadBoy@: Ho esaminato la versione in italiano. Molto bene. Adoro quello che fa Fischetti in generale.
	Programmazione lineare	Chvatal	BadBoy@: Il libro non mi piace ma è lì che ho imparato tutto l'LP e l'annotazione è ottima.
	Ottimizzazione combinatoria	Papadimitriou e Steiglitz	BadBoy@: Mi è piaciuto molto. È obsoleto, ma dovresti leggerlo. Kvothe@: Un po' asciutto per i miei gusti.
	Programmazione di numeri interi	Wolsey	Unicorn@: Molto conciso, ma copre la maggior parte degli aspetti interessanti del campo (dal punto di vista del risolutore)
	Programmazione di numeri interi	Conforti, Cornuéjols e Zambelli	Patrick@: Probabilmente il libro più aggiornato sulla teoria/metodologia della MIP.
	Faccette dell'ottimizzazione combinatoria	Jünger e Reinelt	Patrick@: Più sul lato teorico e pregiudicato verso il lavoro dell'ex direttore dello ZIB Martin Grötschel (è per i festeggiamenti del suo 65° compleanno), ma include quella che penso sia l'ultima versione di questo sondaggio MIP computazionale: "Tobias Achterberg e Roland Wunderling. Programmazione di numeri interi misti: analisi di 12 anni di progressi".
	50 anni di programmazione completa: 1958-2008	Jünger et al., ed.	Patrick@: Un po' superata, ma un'ottima recensione della storia e del MIP all'avanguardia.
	Algoritmi flusso di rete	Williamson	Unicorn@: Un buon libro con molti risultati molto recenti sui flussi di rete, pur essendo intuitivo. Solo per i flussi di rete, però, quindi non così generici. Recensione più completa in francese.
	Spiegazione degli algoritmi: algoritmi per problemi NP-Hard	Campo da giardinaggio	Unicorn@: Probabilmente non è il libro più avanzato del branco! Fornisce comunque un'introduzione ad alcuni algoritmi OR (dal punto di vista di un corso sugli algoritmi). Molto leggibile. Recensione più completa in francese.
	Ottimizzazione pratica	Gill, Murray e Wright	Unicorn@: Vecchio libro di riferimento sull'ottimizzazione continua. Se hai bisogno di una spiegazione su questa famiglia di algoritmi, consulta questo libro. (Recensione più completa in francese.)
	Introduzione all'ottimizzazione e al calcolo semidifferenziale di Hadamard	Delfour	Unicorn@: Libro molto formale sull'ottimizzazione semidifferenziale. Non è facile entrare. Recensione più completa in francese.
	La gerarchia Momento-SOS: lezioni di probabilità, statistica, geometria computazionale, controlli e PDE non lineari	Henrion, Korda e Lasserre	Unicorn@: Se hai intenzione di ottimizzare usando i polinomi o ti stai chiedendo fino a che punto puoi arrivare a utilizzarli, imparerai le nozioni di base della gerarchia SoS e delle applicazioni sconosciute. Recensione più completa in francese.
	Introduzione alla ricerca operativa	Hillier e Lieberman	Kvothe@: Un buon mix di teoria e pratica. Un buon primo testo per le persone che non hanno mai lavorato sul campo, con esempi pratici e tanti esercizi, alcuni con risposte sul retro del libro. Svantaggio: il libro cerca un po' troppo di incanalare gli utenti verso il suo sito web e utilizza risolutori obsoleti.

Revisioni di ricerca

Riepilogo	Autore	Commenti
175 anni di programmazione lineare	Chandru e Rao	BadBoy@: Una serie di articoli eccezionale. Ne ho fatto conoscenza all'inizio degli anni '90. Non so chi per primo abbia avuto l'idea di presentare una programmazione lineare come questa, ma sono stati coinvolti anche Vijay Chandru e Jean-Louis Lassez. La cosa bella è che basta solo l'algebra lineare di livello base per capirla e che puoi dimostrare quasi tutti i teoremi importanti in LP con le nozioni di base. Il migliore sarebbe un libro su LP con questo, più alcuni Chvatal, alcuni Vanderbei, e poi problemi di implementazione e riferimenti ai libri in questione. Chvatal e Vanderbei non dispongono di solide basi matematiche. È vecchio e dovrebbe presto essere ribattezzato 200 anni di programmazione lineare. È possibile che ci siano stati tentativi precedenti.

Articoli di ricerca

Articolo	Autore	Commenti
Un nuovo algoritmo di tempo polinomiale per la programmazione lineare	Karmarkar	BadBoy@: L'articolo di Karmarkar sull'algoritmo di Karmarkar. L'esempio di come non si dovrebbe scrivere un articolo. Ci sono voluti anni per ottenere un'implementazione efficace e nel frattempo si è scoperto che si trattava di un altro metodo basato sull'interno.

Definizione del modello

MIP

Cover	Titolo	Autore	Commenti
	Creazione di modelli nella programmazione matematica	Williams	Un'attenzione particolare a LP e MIP. Temere@: Non mi è piaciuto molto. La struttura è strana (e aumenta artificialmente il numero di pagine). Ed è fortemente radicato nelle "applicazioni OR classiche" (concentrati sull'economia o sulla pianificazione dall'aspetto simile a un giocattolo) con poca pertinenza ai modelli MIP che solitamente facciamo in Google Azalee@: Concordato. BadBoy@: Penso ancora che il libro sia stato fantastico all'epoca. L'ho visto forse 2 anni fa, e cavoli. È obsoleto. Inoltre, conosco l'autore dal 1990 e ci siamo ricollegati all'ISMP 2015. È un ragazzo bravo, è andato in pensione, si reca a conferenze con i suoi soldi e continua a fare fantastiche presentazioni. I suoi articoli erano fantastici, in particolare sull'eliminazione di Fourier. Ha una visione molto ampia di cosa sia LP. È stato determinante per l'avvio di XpressMP.
	Applicazioni dell'ottimizzazione con XpressMP	Guéret, Prins, Sevaux e Heipcke

Guide per la creazione dei modelli rilasciate dal risolutore

Guida	Descrizione	Commenti
Libro di ricette MOSEK per la modellazione	Si concentra sull'ottimizzazione convessa conica.	Unicorn@ Un riferimento reale per me quando si sviluppano modelli non lineari.
Libro di ricette per il portfolio MOSEK	Modelli conici per l'ottimizzazione del portafoglio

Revisioni della ricerca: MIP

Riepilogo	Autore	Descrizione
Tecniche di formulazione della programmazione lineare con numeri interi misti	Vielma	Si concentra sulla forza e sulle dimensioni delle formulazioni con numeri interi misti per l'unione di funzioni lineari a tratti simili a poliedri. Più dal lato teorico, ma include alcune tecniche pratiche come le formule incrementali nella sezione 8.
Funzioni lineari a tratti non convesse: formule avanzate e strumenti di modellazione semplici.	Huchette e Vielma	Tecniche più recenti per funzioni lineari a tratti che non sono incluse nella revisione sopra riportata.

Recensioni di ricerca: MINLP

Riepilogo	Autore	Descrizione
Rappresentabilità convessa di numeri interi misti	Lubin, Vielma e Zadik	Solo per rilassamenti convessi.

Ottimizzazione in fase di incertezza

Ottimizzazione stocastica

Cover	Titolo	Autore	Commenti
	Lezioni sulla programmazione stocastica: modellazione e teoria	Shapiro, Dentcheva e Ruszczynski
	Introduzione alla programmazione stocastica	Birge e Louveaux	Unicorn@: Un'introduzione più teorica all'argomento. Non lo consiglio tanto quanto le lezioni sulla programmazione stocastica.

Revisioni di ricerca

Riepilogo	Autore
Ottimizzazione del valore a rischio condizionale	Rockafellar e Uryasev

Ottimizzazione efficace

Cover	Titolo	Autore	Commenti
	Ottimizzazione efficace	Ben-Tal, El Ghaoui e Nemirovski	PDF. Unicorn@: è un ottimo riferimento se le recensioni seguenti non sono sufficientemente dettagliate. Una parte in gran parte è dedicata ai problemi non lineari (in genere non presentati nelle recensioni). Mi piace molto la sezione 1.1.2, perché mostra numericamente che piccole deviazioni dei coefficienti possono rendere grandi infattibilità.
	Ottimizzazione solida e adattiva	Bertsimas e Dick Den Hertog	PDF. Unicorn@: Ottimo riferimento su tutto ciò che riguarda una solida ottimizzazione. È abbastanza accurato, potrebbe fare con un po' di più dal punto di vista degli algoritmi. Recensione più completa in francese.

Revisioni di ricerca

Riepilogo	Autore
Guida pratica all'ottimizzazione efficace	Gorissen, Yanıkoğlu e den Hertog
Teoria e applicazioni di una solida ottimizzazione	Bertsimas, Brown e Caramanis

Articoli di ricerca

Articolo	Autore
Analisi stocastica tracciabile in dimensioni elevate tramite un'ottimizzazione solida (PDF)	Bandi e Bertsimas

StackExchange

Quali sono dei buoni libri di riferimento per un'introduzione alla ricerca operativa?

Libri/materiali consigliati per le applicazioni pratiche della ricerca operativa nel settore