Ph.D. Thesis

--> Thesis <--

--> Source code and user guide <-- for the Valves Placement (Section 3 in the thesis)

Abstract

Many real life problems in the hydraulic engineering literature can be modelled as constrained optimisation problems. Often, they are addressed in the literature through genetic algorithms, although other techniques have been proposed.

In this thesis, we address two of these real life problems through a variety of techniques taken from the Artificial Intelligence and Operations Research areas, such as Mixed Integer Linear Programming, Logic Programming, Genetic Algorithms and Path Relinking, together with hybridization amongst these technologies and with hydraulic simulators. For the first time, an Answer Set Programming formulation of hydroinformatics problems is proposed.

The two real life problems addressed hereby are the optimisation of the response in case of contamination events, and the optimisation of the positioning of the isolation valves.

The constraints of the former describe the feasible region of the Multiple Travelling Salesman Problem, while the objective function is computed by a hydraulic simulator. A simulation--optimisation approach based on Genetic Algorithms, mathematical programming, and Path Relinking, and a thorough experimental analysis are discussed hereby.

The constraints of the latter problem describe a graph partitioning enriched with a maximum flow, and it is a new variant of the common graph partitioning. A new mathematical model plus a new formalization in logic programming are discussed in this work. In particular, the technologies adopted are Mixed Integer Linear Programming and Answer Set Programming.

Addressing these two real applications in hydraulic engineering as constrained optimisation problems has allowed for i) computing applicable solutions to the real case, ii) computing better solutions than the ones proposed in the hydraulic literature, iii) exploiting graph theory for modellization and solving purposes, iv) solving the problems by well suited technologies in Operations Research and Artificial Intelligence, and v) designing new integrated and hybrid architectures for a more effective solving.

Sinossi

Spesso nella letteratura dell'ingegneria idraulica tali problemi vengono affrontati tramite algoritmi genetici, sebbene esistano altre tecniche. In questa tesi vengono affrontati due problemi reali dell'ingegneria idraulica attraverso diverse tecniche della Ricerca Operativa e dell'Intelligenza Artificiale, come ad esempio la programmazione matematica, la programmazione logica, gli algoritmi genetici e il path relinking; vengono discusse inoltre delle ibridizzazioni di tali tecniche, alcune delle quali con i simulatori idraulici. Inoltre, questa tesi propone per la prima volta delle codifiche in Answer Set Programming per dei problemi di idroinformatica.

Le due applicazioni reali sono: l'ottimizzazione del piano di intervento in caso di contaminazione della rete idrica, l'ottimizzazione del posizionamento delle valvole di isolamento.

I vincoli del primo problema di ottimizzazione descrivono la regione ammissibile del noto Multiple Travelling Salesman Problem, mentre la funzione obiettivo può essere calcolata da un simulatore idraulico. Questo lavoro propone un approccio di simulazione-ottimizzazione che integra Algoritmi Genetici, programmazione matematica, Path Relinking, e ne discute inoltre un'estesa analisi sperimentale.

I vincoli del secondo problema descrivono un Graph Partitioning arricchito da un problema di flusso massimo, ed è una versione inedita del classico problema di partizionamento. Questo lavoro propone diversi nuovi modelli matematici e logici, sviluppati in Mixed Integer Linear Programming e Answer Set Programming.

Le due applicazioni reali in ingegneria idraulica in esame sono state quindi modellate come problemi di ottimizzazione vincolata permettendo di i) calcolare soluzioni applicabili al caso reale, ii) calcolare soluzioni migliori rispetto a quelle presenti nella letteratura idraulica, iii) sfruttare concetti di teoria dei grafi per la modellazione e la risoluzione dei problemi, iv) risolvere i modelli attraverso l'utilizzo di tecnologie molto efficaci della Ricerca Operativa e dell'Intelligenza Artificiale, v) progettare nuove architetture integrate o ibride che permettono una risoluzione più efficace del problema.