Hybrid constraint programming and metaheuristic methods for large scale optimization problems

This work presents hybrid Constraint Programming (CP) and metaheuristic methods for the solution of Large Scale Optimization Problems; it aims at integrating concepts and mechanisms from the metaheuristic methods to a CP-based tree search environment in order to exploit the advantages of both approaches. The modeling and solution of large scale combinatorial optimization problem is a topic which has arisen the interest of many researcherers in the Operations Research field; combinatorial optimization problems are widely spread in everyday life and the need of solving difficult problems is more and more urgent. Metaheuristic techniques have been developed in the last decades to effectively handle the approximate solution of combinatorial optimization problems; we will examine metaheuristics in detail, focusing on the common aspects of different techniques. Each metaheuristic approach possesses its own peculiarities in designing and guiding the solution process; our work aims at recognizing components which can be extracted from metaheuristic methods and re-used in different contexts. In particular we focus on the possibility of porting metaheuristic elements to constraint programming based environments, as constraint programming is able to deal with feasibility issues of optimization problems in a very effective manner. Moreover, CP offers a general paradigm which allows to easily model any type of problem and solve it with a problem-independent framework, differently from local search and metaheuristic methods which are highly problem specific. In this work we describe the implementation of the Local Branching framework, originally developed for Mixed Integer Programming, in a CP-based environment. Constraint programming specific features are used to ease the search process, still mantaining an absolute generality of the approach. We also propose a search strategy called Sliced Neighborhood Search, SNS, that iteratively explores slices of large neighborhoods of an incumbent solution by performing CP-based tree search and encloses concepts from metaheuristic techniques. SNS can be used as a stand alone search strategy, but it can alternatively be embedded in existing strategies as intensification and diversification mechanism. In particular we show its integration within the CP-based local branching. We provide an extensive experimental evaluation of the proposed approaches on instances of the Asymmetric Traveling Salesman Problem and of the Asymmetric Traveling Salesman Problem with Time Windows. The proposed approaches achieve good results on practical size problem, thus demonstrating the benefit of integrating metaheuristic concepts in CP-based frameworks.

Characterization of geothermal reservoirs’ parameters by inverse problem resolution and geostatistical simulations

BTES (borehole thermal energy storage)systems exchange thermal energy by conduction with the surrounding ground through borehole materials. The spatial variability of the geological properties and the space-time variability of hydrogeological conditions affect the real power rate of heat exchangers and, consequently, the amount of energy extracted from / injected into the ground. For this reason, it is not an easy task to identify the underground thermal properties to use when designing. At the current state of technology, Thermal Response Test (TRT) is the in situ test for the characterization of ground thermal properties with the higher degree of accuracy, but it doesn’t fully solve the problem of characterizing the thermal properties of a shallow geothermal reservoir, simply because it characterizes only the neighborhood of the heat exchanger at hand and only for the test duration. Different analytical and numerical models exist for the characterization of shallow geothermal reservoir, but they are still inadequate and not exhaustive: more sophisticated models must be taken into account and a geostatistical approach is needed to tackle natural variability and estimates uncertainty. The approach adopted for reservoir characterization is the “inverse problem”, typical of oil&gas field analysis. Similarly, we create different realizations of thermal properties by direct sequential simulation and we find the best one fitting real production data (fluid temperature along time). The software used to develop heat production simulation is FEFLOW 5.4 (Finite Element subsurface FLOW system). A geostatistical reservoir model has been set up based on literature thermal properties data and spatial variability hypotheses, and a real TRT has been tested. Then we analyzed and used as well two other codes (SA-Geotherm and FV-Geotherm) which are two implementation of the same numerical model of FEFLOW (Al-Khoury model).

Rituali indigeni in Mesoamerica. La festa di Petición de Lluvias nella Montaña di Guerrero (Messico)

Questa tesi di carattere antropologico in ambito dottorale riguarda i rituali comunitari nelle comunità indigene messicane. Il principale oggetto della ricerca è il rituale della pioggia o di Petición de Lluvia, caratterizzato sia dal sacrificio animale che da una specifica relazione di causa-effetto con l’ambiente circostante. La ricerca etnografica è cominciata dall’ipotesi di voler verificare la persistenza nel tempo, e dunque nell’attualità, di procedure cerimoniali non appartenenti, almeno nella loro forma più lineare, alla religione cattolico-cristiana. Il luogo nel quale è avvenuta tale ricerca è la regione La Montaña di Guerrero, situata nel Messico sud-occidentale, e più precisamente la zona in cui vivono le comunità di etnia Nahua di San Pedro Petlacala, Acuilpa, e Xalpatláhuac che si trovano nelle vicinanze della cittadina di Tlapa de Comonfort. In un contesto ambientale profondamente rurale come quello della Montaña di Guerrero, la persistenza dei rituali evidenzia come le risorse naturali e gli agenti atmosferici - pioggia, vento, nubi - continuino a rappresentare gli elementi centrali che condizionano le variabili economiche di sussistenza e della riproduzione sociale. Il rituale di Petición de Lluvia rappresenta il momento di congiunzione tra la stagione secca e quella piovosa, tra la semina ed il raccolto del mais. Definito come una pratica religiosa nella quale il gruppo si identifica e partecipa con varie donazioni (ofrenda o deposito rituale), suddivisibili in alimenti/oggetti/preghiere ed azioni rituali, la cerimonia esprime l’auspicio di piogge abbondanti, con le quali irrigare i campi e continuare le attività umane. Il destinatario dell’offerta è la stessa divinità della pioggia, Tlaloc per le antiche civiltà mesoamericane, invocato sotto le mentite spoglie del santo patrono del 25 aprile, San Marcos. Il rituale è contraddistinto per tutta la sua durata dalla presenza del principale specialista religioso, sacerdote in lingua spagnola oppure «Tlahmáquetl» in lingua náhuatl.

L’abitare come relazione sociale: il significato della casa e i processi di coesione sociale di vicinato

Se le trasformazioni sociali in atto tendono a esasperare il senso di incertezza, sradicamento ed individualismo, sussistono pratiche che si contrappongono alle tendenze dominanti, finalizzate a ricucire i legami sociali su scala locale. La progettazione urbano-architettonica interiorizza il nuovo bisogno di comunità originando soluzioni abitative tese a favorire gli scambi informali fra vicini, facendo leva sul concetto di capitale sociale, attaccamento al quartiere, identità del luogo e partecipazione. La casa, simbolo di stabilità e sicurezza ma anche di privacy, privatismo familiare, diventa sempre più oggetto di studi, domanda sociale e intervento politico. Soprattutto è sempre più intesa come un nodo di relazioni familiari in una rete di relazioni sociali più ampie. Casa e quartiere incidono nella esperienza di benessere e socialità familiare? In che modo gli spazi urbani e architettonici influenzano la coesione sociale? Quale il ruolo degli abitanti nello sviluppare socialità e integrazione? Sono queste le domande che ci siamo posti per rilevare le dinamiche sociali e culturali dell’abitare attraverso uno studio di caso condotto in due quartieri simili. Dalla ricerca emerge come il significato della casa non sia univoco ma cambi rispetto al ciclo di vita familiare e a quello economico e ciò incide nella partecipazione alle attività di quartiere. Mostriamo inoltre come lo spazio fisico costruito crea importanti opportunità per gli scambi informali e per il benessere familiare e individuale dei bambini ma che, il contesto sociale sia una discriminate fondamentale. Nel quartiere dove è presente una organizzazione di abitanti il numero delle relazioni di vicinato aumenta, cambiano anche la qualità delle relazioni e le distanze fisiche fra i vicini. Emerge inoltre che la reciprocità è il principale strumento di costruzione della coesione comunitaria interna e crea un atteggiamento di apertura e fiducia che va al di là dei confini di quartiere.

La ricostruzione dell'assetto topografico della VI regio augustea di Roma dal periodo repubblicano all'età tardoantica

La VI regio augustea di Roma rappresenta uno dei settori urbani maggiormente investiti dalle modifiche radicali compiute dall’uomo nel processo di urbanizzazione della città che ne hanno modificato profondamente la situazione altimetrica e la conformazione originaria. Questi notevoli cambiamenti ebbero origine sin dall’età antica, ma si intensificarono profondamente soprattutto nel periodo rinascimentale quando a partire da Pio IV e soprattutto con Sisto V, attivo in tante altre zone della città, si svilupparono numerose opere di rinnovamento urbanistico che incisero notevolmente sul volto e sulle caratteristiche della zona in esame. A partire dal Rinascimento fino ad arrivare ai grandi scavi della fine del 1800 tutto il quartiere incominciò a “popolarsi” di numerosi edifici di grande mole che andarono ad intaccare completamente le vestigia del periodo antico: la costruzione del Palazzo del Quirinale e dei vari palazzi nobiliari ma soprattutto la costruzione dei numerosi ministeri e della prima stazione Termini alla fine dell’800 comportarono numerosi sventramenti senza la produzione di una adeguata documentazione delle indagini di scavo. Questa ricerca intende ricostruire, in un’ottica diacronica, la topografia di uno dei quartieri centrali della Roma antica attraverso l’analisi dei principali fenomeni che contraddistinguono l’evoluzione del tessuto urbano sia per quanto riguarda le strutture pubbliche che in particolar modo quelle private. Infatti, il dato principale che emerge da questa ricerca è che questa regio si configura, a partire già dal periodo tardo-repubblicano, come un quartiere a vocazione prevalentemente residenziale, abitato soprattutto dall’alta aristocrazia appartenente alle più alte cariche dello Stato romano; oltre a domus ed insulae, sul Quirinale, vennero costruiti lungo il corso di tutta l’età repubblicana alcuni tra i più antichi templi della città che con la loro mole occuparono parte dello spazio collinare fino all’età tardoantica, rappresentando così una macroscopica e costante presenza nell’ingombro dello spazio edificato.