Ricerca operativa

PRIN-kakuro e programmazione lineare intera

2012-01-29T19:07:00.000+01:00

Oggi vi voglio segnalare una applicazione molto originale della programmazione lineare intera. Non sono un esperto, ma pare che l'assegnazione dei bandi PRIN abbia o abbia avuto delle regole molto strane, tanto da ricadere nei problemi NP-completi. Moreno Marzolla ha descritto in un suo interessante post, dal titolo Risolvere il PRIN-kakuro con la programmazione lineare, un modello in GNU MathProg.

Buona lettura e buona esercitazione con glpk.

Reti di teleriscaldamento 'intelligenti'

2012-01-25T22:35:00.000+01:00

Che la ricerca operativa può dare tanto nel settore delle smart grid è una cosa che, ormai, credo si possa dire assodata. Finalmente questa idea sembra essere arrivata a chi ci lavora con le smart grid, anzi meglio dire le smart thermal grid.

Un nuovo progetto per l'utilizzo intelligente della rete di teleriscaldamento è partito da pochi giorni; è guidato da Iren Energia con la collaborazione del Politecnico di Torino e il Consorzio Interuniversitario per la Ottimizzazione e la ricerca operativa (I.C.O.O.R).

"Voglio ringraziare l'Ateno per la grande attenzione con cui ha accolto la mia proposta di avviare questi progetti di ricerca sulle 'Smart Thermal Grid - sottolinea l'amministratore delegato di Iren Roberto Garbati - Iren Energia vuole rafforzare la propria leadership nel settore del teleriscaldamento e questa efficace collaborazione con il Politecnico consentirà di condividere e incrementare le competenze, consentendo di migliorare ulteriormente la qualità del servizio, ottimizzando la gestione di un sistema complesso quale e' quello cittadino, che già oggi serve più della metà della volumetria complessiva di Torino. Non ultimo - conclude - come obiettivo delle suddette attività anche la riduzione del prezzo di vendita del teleriscaldamento". "I progetti di ricerca - spiega Marco Masoero, direttore del Dipartimento Energia del Politecnico di Torino - segnano l'avvio della collaborazione con il Gruppo Iren sulle problematiche inerenti le reti di teleriscaldamento intelligenti e siamo certi che stiamo ponendo le basi per la definizione di un partenariato più strutturato per una progettazione anche a medio e lungo periodo"

Maggiori dettagli sono disponibili su agi.it.

Sistemi di supporto alle decisioni in Snam Rete Gas

2012-01-05T23:24:00.000+01:00

Nel codice di rete di Snam Rete Gas, documento che descrive le procedure e le modalità di erogazione dei servizi da parte dell'azienda, si trovano illustrati una serie di sistemi di supporto alle decisioni:

CASSANDRA
Elabora la previsione del gas riconsegnato dalla rete, valida per i cinque giorni successivi, sulla base delle previsioni meteorologiche.
Il modello è comprensivo di una serie di eventi (festività o altri eventi) che gestiscono le diminuzioni di prelievo, anche importanti, ad essi associati.
I parametri del modello vengono periodicamente aggiornati sulla base dell’evolversi dell’andamento delle quantità giornaliere riconsegnate nel corso degli anni.
La metodologia applicata è Box-Jenkins ed i modelli prodotti sono di tipo ARIMA (AutoRegressive Integrated Moving Average).
L’utilizzo di questo programma consente al Trasportatore di effettuare valutazioni circa l'evoluzione dei quantitativi oggetto di trasporto, così da predisporsi a far fronte ad eventuali variazioni di scenario di significativa entità.
MELAMPO
Il programma calcola la previsione dei quantitativi complessivi in riconsegna per il Giorno-gas in corso con aggiornamento orario, sulla base delle serie storiche del quantitativo complessivamente riconsegnato nel giorno e del dato cumulato del quantitativo riconsegnato oggetto di consuntivo nel corso del Giorno-gas, sino all’ora precedente.
L’applicativo contiene 24 modelli, uno per ogni ora del Giorno-gas.
Il modello è comprensivo di una serie di eventi (festività o altri eventi) che gestiscono le diminuzioni di prelievo, anche importanti, ad essi associati.
I parametri del modello vengono periodicamente aggiornati sulla base dell’evolversi dell’andamento delle quantità giornaliere riconsegnate nel corso degli anni.
La metodologia applicata è Box-Jenkins ed i modelli prodotti sono di tipo ARIMA (AutoRegressive Integrated Moving Average).
L'analisi integrata della previsione formulata dal programma e dell'andamento orario del line pack (e quindi delle pressioni in rete) consente al Dispacciamento di valutare, a fronte di uno sbilanciamento fisico della rete, la necessità di attivare le opportune azioni correttive.
SSDD
Il sistema di ottimizzazione SSDD (Sistema di Supporto alle Decisioni del Dispacciamento) è uno strumento, che lavora in regime stazionario, progettato allo scopo di soddisfare il trasporto rispettando le condizioni al contorno programmate e ricercando il miglior assetto delle centrali di compressione, minimizzando il consumo di fuel gas, attraverso l'utilizzo di due sottosistemi (ARGO ed OTTIMO).
Per ogni singola unità (turbina, compressore) si forniscono punti di lavoro in modo che il sistema possa calcolare, in base a tecniche di regressione, le curve caratteristiche.
A partire dalle telemisure acquisite si può verificare se la centrale sta lavorando nella zona limite di funzionamento e se l’impianto globalmente sta operando in condizioni ottimali di consumo di combustibile.
SIMONE
Il sistema di simulazione/ottimizzazione SIMONE è uno strumento che consente di effettuare simulazioni del trasporto sia in regime stazionario sia in regime dinamico. Inoltre consente di effettuare ottimizzazioni del trasporto in regime stazionario sia su reti complesse sia su singole centrali.

Per maggiori dettagli, rimando al documento completo.

I modelli della ricerca operativa nella realizzazione di processi decisionali attraverso agenti autonomi

2012-01-02T21:53:00.000+01:00

Credo che possa interessare il seguente articolo, di Mario Lucertini, apparso sul Bollettino dell'Unione Matematica Italiana.

Lucertini Modelli Ricerca Operativa Ad Agenti Autonomi

Modelli e algoritmi di ottimizzazione applicati ai sistemi energetici

2011-12-31T12:39:00.000+01:00

L'ottimizzazione applicata ai sistemi energetici è un tema che mi sta particolarmente a cuore, visto che è l'argomento principale del mio lavoro. E' per questo che mi fa piacere leggere che sarà anche l'oggetto del progetto di dottorato di Chiara Bordin:

Lo scopo del progetto di ricerca proposto è quello di sfruttare le potenzialità offerte dalla ricerca operativa per studiare e modellizzare sistemi energetici complessi quali reti di teleriscaldamento, impianti solari termici e centrali di co / trigenerazione, nonché analizzare la possibilità di progettazioni ottimizzate di reti di fonti energetiche integrate.

Per maggiori dettagli rimando al seguente pdf.

Algoritmi esatti e di approssimazione per problemi di ottimizzazione combinatoria - “Rif. 366/2011”

2011-12-04T22:46:00.001+01:00

Scade il 7 dicembre 2011 il bando per assegno di ricerca, dalla seguente descrizione sintetica:

Il programma di ricerca prevede lo svolgimento di attività di ricerca e sviluppo nell'ambito degli algoritmi esatti e di approssimazione per problemi di difficili di ottimizzazione combinatoria. Gran parte dei problemi di ottimizzazione combinatoria di rilevanza pratica sono per l'appunto NP-hard e per molti di questi problemi non sono noti o addirittura è fortemente improbabile che esistano algoritmi euristici per i quali sia possibile anche solo identificare un rapporto di approssimazione costante. In quest'ambito, verranno affrontati vari problemi per i quali verranno proposti algoritmi esatti ed approssimati che saranno analizzati in termini di complessità di caso peggiore (worst-case complexity analysis). Particolare attenzione verrà data all'analisi di complessità di caso peggiore di algoritmi approssimati di bassa complessità esponenziale per problemi non approssimabili in tempo polinomiale.

Per maggiori informazioni, rimando ai seguenti link:

Ottimizzazione in Logistics e Green Logistics - “Rif. 382/2011”

2011-12-04T22:41:00.002+01:00

Il 12 dicembre 2011 scade il bando per assegno di ricerca, dalla seguente descrizione sintetica:

Obiettivo
Definizione di modelli innovativi per l’ottimizzazione della Logistics e della Green Logistics.
Oggetto
Stima e integrazione di informazioni di tipo ambientale all'interno dei modelli di trasporto e logistica esistenti, al fine di permettere ai decisori (amministratori pubblici ed aziende) di esplicitare i vantaggi ambientali delle soluzioni proposte.
Definizione di nuovi modelli di trasporto per filiere logistiche corte (trasporto agro-alimentare a km 0, filiere agro-alimentari di eccellenza), al fine di massimizzarne il vantaggio in termini di riduzione del traffico e di impatto ambientale della catena logistica urbana sulla quale tali filiere impattano.

Per maggiori dettagli, rimando ai seguenti siti:

Nemsys

2011-11-01T22:28:00.001+01:00

Nemsys, che sta per Network Models and System Optimization, è una azienda fondata nel 1997 con sede a Cesena. Obiettivi principali dell'azienda sono lo sviluppo di software di ottimizzazione e consulenza nella logistica. Dal sito dell'azienda:

Nemsys Srl è specializzata nella consulenza e nello sviluppo di Sistemi di Supporto alle Decisioni (D.S.S.) per la soluzione di complessi problemi logistici. In particolare Nemsys si è occupata di:

Pianificazione della distribuzione e/o raccolta di merci

Programmazione dei carichi

Gestione ottimale delle risorse

Analisi di reti di trasporto e localizzazione di depositi

e ancora:

Nemsys è proprietaria del marchio Routemate®, sistema software di supporto alle decisioni per il settore trasporti, ed è particolarmente attiva nei seguenti ambiti:

Taglio bidimensionale di forme regolari (per l'industria del vetro e del legno) e irregolari (per l'industria tessile e di abbigliamento e arredamento in pelle).

Pianificazione degli equipaggi per il trasporto pubblico e privato e nel trasporto aereo.

Pianificazione dei viaggi, in presenza di più depositi, per il trasporto pubblico e le aziende di autotrasporto.

Sistemi di supporto alle decisioni e GIS (Geographic Information Systems) con applicazioni alla pianificazione delle reti idriche e della raccolta dei rifiuti su scala regionale.

Per maggiori informazioni, rimando al sito web aziendale, ricco di notizie ed informazioni, su competenze e prodotti.

Simplesso didattico

2011-10-19T23:15:00.000+02:00

Da un lavoro di Gionata Massi del 2003, segnalo questa implementazione del simplesso in PHP.
Credo che questo semplice programma possa essere molto utile per insegnare il funzionamento dell'algoritmo del simplesso. Infatti, dalla pagina sopra citata, è possibile inserire manualmente un problema di programmazione lineare ed avere in output tutti i passi risolutivi.

Dalla documentazione del software:

Il programma è stato implementato allo scopo di fornire in output la risoluzione passo passo di un problema di programmazione lineare, in molto del tutto simile all'analisi eseguita manualmente. Si è scelto, anche per facilitare le operazioni di debugging e di riscontro della correttezza dell'algoritmo, di rappresentare tutti i passaggi: visualizzazione del problema immesso, del problema portato prima in forma standard e successivamente in forma canonica, rappresentazione del tableau anche nel caso eventuale di utilizzo del metodo delle due fasi con indicazione ad ogni passo dell'insieme degli indici di base e del valore della soluzione di base associata ad ogni tabella. Si è scelto di risolvere il problema di programmazione lineare intera mediante il metodo dei piani di taglio. Inoltre per evitare i problemi di convergenza nelle operazioni di pivoting, quindi fornire una soluzione corretta e conforme all'analisi eseguita manualmente, anziché usare l'aritmetica in virgola mobile del calcolatore si è fatto uso di operazioni su numeri razionali implementando un'apposita classe. In aggiunta, sempre per rimanere aderenti alla soluzione su carta di semplici problemi, si rappresenta l'analisi grafica dei problemi che coinvolgono due sole variabili di decisione.

Buon lavoro a tutti gli studenti e un grazie a Gionata Massi per aver condiviso il suo lavoro.

KKT Unexpected Improvements

2011-10-12T23:47:00.000+02:00

Nasce a Firenze, da una idea di Alessandro Lori, Mirko Maischberger e Fabio Schoen, KKT Unexpected Improvements. Dalla pagina del profilo aziendale è chiara la missione di KKT:

KT srl nasce da un'idea consolidata, la Ricerca Operativa, la ricerca della miglior pianificazione delle operazioni con metodi scientifici e modelli matematici in grado di fornire utili indicazioni a Director of Operations, Manager, e decisori in genere. L'esperienza maturata dai tre soci paritari in campo internazionale ha fatto emergere il chiaro bisogno, sul mercato italiano, di un operatore in grado di spaziare dalla modellazione matematica dei processi produttivi e distributivi, alla creazione di algoritmi ad-hoc per la loro soluzione, con un forte background informatico.

Due le offerte principali pubblicizzate:

Assegnazione degli ordini per il settore moda
Pianificazione della produzione ottimizzata

Credo che possa essere molto interessante visitare KKT presso lo SMAU2011 (Milano, 19-21 ottobre), quale occasione di approfondimento e conoscenza di chi ha fatto della ricerca operativa il proprio lavoro.

Analysis, Control and Optimization of complex dynamical systems - 1 Assistant Professor Position

2011-10-11T21:04:00.000+02:00

L'IMT di Lucca, Institutions Markets Technologies, ha un bando aperto per un ricercatore universitario in Dynamical Systems, Control, and Optimization. Di seguito un estratto del bando:

MT Institute for Advanced Studies Lucca invites applications for an Assistant Professor position in the area of analysis, control and optimization of complex dynamical systems. Candidates with a sound knowledge of control and optimization methods and an interest in both theoretical research and applications to practical problems are desired. Research experience is expected in at least one of the following areas: model predictive control, dynamic optimization, stochastic optimization, control systems design based on optimization methods. Previous experience with applications of control/optimization to smart grids and energy markets is a plus, but candidates with experience in other application areas are welcome. Candidates with a Ph.D. in engineering or mathematics with a focus on control oroptimization are preferable, and they should have an excellent record of high-impact international publications.

The Assistant Professor will be a part of the Research Unit "DynamicalSystems, Control, and Optimization" (DYSCO, http://dysco.lab.imtlucca.it/) in the Computer Science and Applications area of the Institute, and will perform research activities, tutorship and mentoring of Ph.D. students, limited teaching of graduate courses and participation in the development of the research activities of the Institute.

Appointment compensation packages will depend on the candidates and their records of accomplishment, but are competitive on an international level. Applicants mustbe able to teach graduate courses in English; knowledge of Italian is not required.

Interested candidates must apply before October 31st, 2011 12:00 pm CET byfilling in the online application form at http://www.imtlucca.it/faculty/positions under "Junior Faculty Recruitment Program". They will also be asked to submit a CV, research paper (published or working) and the name and contact details of three referees.

For further information about the position, applicants can refer to the website, or can contact Sara Olson, e-mail: researchers.opening@imtlucca.it.

I termini per l'iscrizione scadono il 31 ottobre 2011.
Per maggiori informazioni fare riferimento ai seguenti link:

In bocca al lupo agli interessati.

Metodi di Decomposizione e Riformulazione di Problemi di Programmazione Lineare Intera

2011-10-09T22:43:00.000+02:00

In oggetto trovate l'oggetto di un bando di concorso per un assegno di ricerca presso l'Università di Bologna. Le candidature devono essere presentate entro il 21/10.
Per maggiori dettagli vi rimando a questo link: http://bandi.miur.it/bandi.php/public/fellowship/id_fellow/5157

Questa la descrizione sintetica del bando:

Il progetto di ricerca si prefigge lo scopo di studiare e analizzare i metodi di Decomposizione e Riformulazione per Problemi di Programmazione Lineare Intera. In particolare lo studio avrà l'obiettivo di valutare l'efficacia di tale metodologia ed il potenziale impatto rispetto agli algoritmi classici di risoluzione.
La ricerca partirà dai recenti risultati sul tema per poi sviluppare approcci e metodi innovativi. In particolare l'accento sarà posto sugli aspetti di Decomposizione e Riformulazione Automatica per problemi di Programmazione Lineare Intera generici. Punto cruciale sarà quindi la caratterizzazione di una buona decomposizione sia in termini di rafforzamento del modello matematico, sia in termini di difficoltà risolutiva e tempi di calcolo computazionale.
Il fine ultimo del progetto sarà quindi lo sviluppo di un pacchetto software innovativo capace di decomporre e riformulare efficacemente i problemi di Programmazione Lineare Intera in maniera automatica.

Esercizi di ricerca operativa

2011-09-21T22:28:00.000+02:00

Oggi vi segnalo questa raccolta molto interessante di esercizi a cura del dott. Antonio Cuduli, del dipartimento di matematica dell'Università della Calabria.

Dalla prefazione del libro:

Il presente testo è una raccolta di tracce d'esame sottoposte agli studenti dei corsi di Laurea in Informatica (Università della Calabria), Ingegneria Gestionale, Ingegneria Informatica e Ingegneria Meccanica (Università di Lecce) nell'ambito dell'insegnamento di “Ricerca Operativa”, e agli studenti del corso di laurea in Ingegneria Informatica e Biomedica (Università “Magna Graecia”di Catanzaro) nell'ambito dell'insegnamento di “Analisi Probabilistica e Metodi Quantitativi”. Alcuni esercizi (quelli individuati dal simbolo ⋆) sono svolti per intero, per altri (quelli individuati dal simbolo ) è riportata la soluzione in appendice, mentre di altri ancora è riportata solo la traccia per dare l'opportunità agli studenti (e/o al docente) di risolverli interattivamente in aula durante le lezioni.

Agli studenti auguro un in bocca al lupo! e buona lettura a tutti.

Eserciziario

L'ottimizzazione in metropolitana

2011-09-18T19:00:00.001+02:00

Il controllo del traffico ferroviario in una rete metropolitana è un altro degli innumerevoli esempi di applicazioni della ricerca operativa. Nello specifico, stiamo parlando della metropolitana di Milano e delle linee 1 e 2: le due linee che presentano delle derivazione ad Y e che quindi necessitano di un maggior controllo sul traffico dei veicoli.

Il progetto è stato commissionato dalla ATM e realizzato dalla Bombardier Transportation con la consulenza del prof. Carlo Mannino.

Per maggiori informazioni:

Dodici tipiche sciocchezze sulla Ricerca Operativa

2011-07-05T22:29:00.000+02:00

Segnalo un interessante lavoro del prof. Giovanni Righini dal titolo "Dodici tipiche sciocchezze sulla Ricerca Operativa". Dal sito del professore, riporto un piccolo estratto che ci permette di capire l'intento con cui sono state scritte queste riflessioni:

Perché in Italia non si insegna la R.O. nella scuola

Reduce da innumerevoli frustranti esperienze nei panni di ricercatore operativo e in particolare di responsabile AIRO per le scuole, ho pensato bene di mettere per iscritto una volta per tutte le "Dodici tipiche sciocchezze sulla Ricerca Operativa", nella speranza che il lettore acquisisca qualche informazione in più e si astenga dal diventare a sua volta un ennesimo acritico ripetitore delle sciocchezze medesime. Se mi sono fermato a dodici è soltanto perché mi ero riproposto di arrivare a dieci e ad un certo punto mi sono accorto di aver già sforato...

Le dodici sciocchezze sono:

La Ricerca Operativa non esiste
La Ricerca Operativa non è ben definita
La Ricerca Operativa non è importante
La Ricerca Operativa è una branca dell'Informatica, è cosa da tecnici
La Ricerca Operativa è astratta, è cosa da matematici
La Ricerca Operativa è una nicchia
La Ricerca Operativa è solo per pochi, non piace agli studenti, non attira i giovani
La Ricerca Operativa non offre prospettive lavorative interessanti
La Ricerca Operativa è morta
La Ricerca Operativa richiede una formazione non fondamentale ma specialistica, di livello universitario
Non c'è domanda di Ricerca Operativa
La Ricerca Operativa non funziona

Gruppo italiano per il ROADEF/EURO Challenge 2012

2011-07-05T10:42:00.000+02:00

Si accettano adesioni per mettere su uno o più gruppi italiani per partecipare alla gara ROADEF/EURO Challenge 2012.

Il problema di quest'anno è il machine reassignment, ovvero spostare dei processi che risiedono su alcune macchine su altre, con lo scopo di migliorare l'uso dell'intero parco macchine, tenendo in conto i vincoli dati dall'uso delle risorse e dal fatto che migrare un processo ha un costo. Tutti i dettagli sono reperibili su questa pagina. Il partner industriale di questa gara è, guarda caso, Google che, a questo punto ovviamente, potrebbe avere un grosso vantaggio nella ottimizzazione dell'assegnamento dei processi nella sua grande nuvola.

La registrazione dei gruppi è già partita. Le categorie a disposizioni sono tre: Junior, Senior, Open Source.

Le adesioni possono arrivare come commento a questo articolo, oppure possono essere inviate per posta elettronica: poderico at gmail dot com.

Dimensionamento idraulico

2011-06-28T22:43:00.001+02:00

Gli appunti che trovate a questo link, a cura del prof. Carlo Ciaponi, descrivono un problema molto semplice, ma allo stesso tempo interessante, sul dimensionamento di una rete idraulica risolto con la programmazione lineare:

Posizione del problema
Rete da progettare di cui è noto il tracciato e la struttura topologica.
E’ prefissata l'erogazione che si vuole garantire (erogazione di progetto)
SCOPO:
calcolare i diametri dei tronchi al fine di garantire che le pressioni nei nodi
assumano valori conformi ai requisiti richiesti

Quante altre applicazioni della ricerca operativa si possono trovare alle reti idrauliche?

Investire nella matematica applicata

2011-06-16T22:31:00.000+02:00

Come non dare ragione ad Andrea Pollini e sulla sua visione che può essere sintetizzata come: Matematica Applicata: Un investimento

Mi permetto di citare una parte di un suo articolo:

Visto che ogni realtà aziendale è unica, con il suo processo produttivo specifico, con il suo personale particolare, con le particolarità che si sono create come abitudini nel corso degli anni, ogni problema sarà un problema unico.

Anche la mia particolare esperienza è concorde con questa semplice ma fondamentale osservazione.

Reactive Search: l'azienda

2011-06-13T22:00:00.000+02:00

Legato al lavoro di Battiti e Brunato, che più volte ho avuto modo di citare sulle pagine di questo blog, c'è una azienda di tecnologie dell'ottimizzazione: Reactive Search.

I principali prodotti sono due:

Grapheur - Visualizzazione interattiva e data mining;
Reactive Search - Sover di ottimizzazione continua.

Colgo l'occasione per segnalare la disponibilità di due posizioni lavorative aperte: segno che, pur trattandosi ancora di una start-up, la crescita di questa azienda segna un buon segno più.

Ottimizzazione su reti

2011-06-12T21:14:00.001+02:00

Ottima fonte di software per la risoluzione di problemi di ottimizzazione su reti e il CRIFOR, il Centro di Ricerca e Formazione per l'Ottimizzazione su Reti.

Per il software disponibile dobbiamo ringraziare gli autori:

Crifor - sezione Cagliari Antonio Manca
Crifor - sezione Cagliari Giovanni Sechi
Crifor - sezione Cagliari Paola Zuddas
Crifor - sezione Cagliari Di Francesco Massimo
Crifor - sezione Pisa Antonio Frangioni
IASI - Roma Claudio Gentile
DEI - Padova Matteo Fischetti
Università di Brescia - Brescia Claudia Archetti

Ottimizzare la moda

2011-05-11T22:37:00.000+02:00

Voglio segnalarvi una breve presentazione curata dal prof. Fabio Schoen dal titolo "La Ricerca Operativa al servizio della moda", che descrive in maniera chiara e sintetica due applicazioni della ricerca operativa nel settore industriale della moda:

abbinamento ordini/magazzino
pianificazione ottimale della produzione

Non è chiaro se gli esempi riportati siano reali o realisti, ma sono comunque degli ottimi esempi di applicazione della programmazione lineare intera: infatti queste tecniche sono state presentate al it4fashion 2011 a Firenze.

Valutazione dei progetti di investimento

2011-05-01T23:33:00.000+02:00

Il tema in oggetto è chiaramente uno dei campi d'azione della programmazione lineare. Traggo spunto dal programma del corso di Finanza Strategia della MIDIacademy, per citare alcuni temi trattati durante le esercitazioni:

scelta tra investimenti di durata diversa
valutazione della convenienza circa la sostituzione di un impianto o di un macchinario
decidere di investire in condizione di risorse finanziarie limitate

Quasi sicuramente, le applicazioni più interessanti vanno trattate e risolte con qualche strumento più potente che la semplice programmazione lineare, ma si tratta sicuramente di un ottimo punto di partenza.

OptimJ Free Edition

2011-04-06T23:17:00.000+02:00

Per gli amanti di Java, tra i quali non ci sono io :-), vi voglio segnalare la disponibilità dell'edizione gratuita di OptimJ.

OptimJ è una libreria di classi Java per la modellazione ad oggetti di problemi di programmazione lineare. OptimJ Free Edition comprende:

integrazione in eclipse
pre-elaborazione dei dati
prototipazione rapida di interfacce grafiche
la possibilità di utilizzare i solver GLPK e lp_solve
supporto dei file in formato LP e MPS

Non ho mai avuto la possibilità di utilizzare OptimJ, quindi sarò lieto di ospitare ogni contributo in tal senso.

Maximum diversity problem

2011-03-31T22:29:00.001+02:00

Quante cose si possono imparare dalle tesi di laurea? Sembra proprio tante! Oggi possiamo approfittare della tesi di laurea di Yari Melanzi:

"UN ALGORITMO DI TABU SEARCH PER IL MAXIMUM DIVERSITY PROBLEM"

Relatori: Roberto Aringhieri e Roberto Cordone.

L'indice della tesi è il seguente:

1 Introduzione
1.1 Definizione del problema
1.2 Applicazioni
1.2.1 Salvaguardia della Biodiversità
1.2.2 Trattamenti medici
1.2.3 La varietà nell'agricoltura
1.2.4 Corretto ridimensionamento di un'impresa
1.2.5 Composizione di una giuria
1.2.6 Diversity Data Mining
1.3 Descrizione ed obiettivi del lavoro

2 Maximum Diversity Problem
2.1 Formulazioni Matematiche
2.1.1 Una formulazione lineare intera
2.2 Algoritmi euristici
2.3 Greedy Randomized Adaptive Search Procedure
2.4 Fase costruttiva
2.4.1 K Larger Distances
2.4.2 Most Distant Insertion
2.4.3 Euristica di Ghosh
2.4.4 Euristica di Andrade
2.5 Fase di ricerca locale
2.5.1 Scambio di un elemento
2.5.2 Scambio di coppie di elementi
2.5.3 GRASP con Path-Relinking
2.6 Un primo test computazionale

3 Tabu Search
3.1 Componenti di base dell'algoritmo
3.1.1 Costruzione di una soluzione iniziale
3.1.2 Intorno di una soluzione
3.1.3 Liste tabu
3.2 Short Term Memory
3.3 Long Term Memory

4 Discussione dei risultati sperimentali
4.1 Strumenti e dati utilizzati
4.2 Risultati
4.2.1 Tabu a due liste
4.2.2 Tabu con Short Term Memory
4.2.3 Tabu con Long Term Memory
4.2.4 Confronto tra gli algoritmi

5 Conclusioni

A Modellazione di MDP con linguaggio AMPL
A.1 Il file del modello.mod
A.2 Il file dei dati.dat

Feasibility pump

2011-03-30T23:22:00.000+02:00

Voglio segnalarvi una tesi di laurea interessante dal punto di vista tecnologico.

"INTERFACING A MIP HEURISTIC BASED ON ILOG CPLEX WITH DIFFERENT LP SOLVERS"

di Davide Baracco, relatore Matteo Fischetti.

Dico interessante dal punto di vista tecnologico, perché in un unico testo possiamo imparare come funziona una delle più famose euristiche per trovare soluzioni a problemi lineari a variabili intere; come funziona CPLEX; come funziona Xpres-MP e come funziona GLPK.

Per meglio specificare i contenuti della tesi ne riporto l'indice:

1 The Feasibility Pump
1.1 Introduction
1.2 Computational experiments
1.3 FP variants
1.3.1 Reducing the computing time
1.3.2 Improving the solution quality
1.3.3 Computational results
2 ILOG CPLEX
2.1 Introduction
2.2 ILOG CPLEX Technologies
2.3 CPLEX Algorithms
2.3.1 CPLEX Simplex Optimizers
2.3.2 CPLEX Barrier Optimizers
2.3.3 CPLEX Mixed Integer Optimizer
3 Xpress-MP by Dash Optimization
3.1 Xpress-MP overview
4 GLPK by Andrew Makhorin
4.1 GLPK overview
4.2 Problem (LP-MIP) formulation
4.3 API Routines
4.4 LPX: The Problem Object
5 The interfaces
5.1 Description of the interfaces
5.2 Step-by-step interfaces development
5.3 The functions
5.3.1 Creating problems
5.3.2 Optimizing problems
5.3.3 Accessing LP/MIP results
5.3.4 Problem modi¯cation
5.3.5 Accessing problem data
5.3.6 File reading/writing
5.3.7 Parameters setting and querying routines
5.3.8 General utilities
6 Test
6.1 Testbed
6.2 Test description
6.3 Computational Results
7 Conclusions
A Interface for GLPK (code)
A.1 interface.h
A.2 ifc imp.c
B Interface for Xpress (code)
B.1 interface.h
B.2 ifc imp.c
Bibliography