Survivable Virtual Topology Routing under Shared Risk Link Groups in WDM Networks

Network survivability is one of the most important issues in the design of optical WDM networks. In this work we study the problem of survivable routing of a virtual topology on a physical topology with Shared Risk Link Groups (SRLG). The survivable virtual topology routing problem against single-link failures in the physical topology is proved to be NP-complete in [1]. We prove that survivable virtual topology routing problem against SRLG/node failures is also NP-complete. We present an improved integer linear programming (ILP) formulation (in comparison to [1]) for computing the survivable routing under SRLG/node failures. Using an ILP solver, we computed the survivable virtual topology routing against link and SRLG failures for small and medium sized networks efficiently. As even our improved ILP formulation becomes intractable for large networks, we present a congestion-based heuristic and a tabu search heuristic (which uses the congestion-based heuristic solution as the initial solution) for computing survivable routing of a virtual topology. Our experimental results show that tabu search heuristic coupled with the congestion based heuristic (used as initial solution) provides fast and near-optimal solutions.

New Insights on Nontechnical Losses Characterization Through Evolutionary-Based Feature Selection

Although nontechnical losses automatic identification has been massively studied, the problem of selecting the most representative features in order to boost the identification accuracy and to characterize possible illegal consumers has not attracted much attention in this context. In this paper, we focus on this problem by reviewing three evolutionary-based techniques for feature selection, and we also introduce one of them in this context. The results demonstrated that selecting the most representative features can improve a lot of the classification accuracy of possible frauds in datasets composed by industrial and commercial profiles.

Enhanced Mixed Integer Programming Techniques and Routing Problems

Mixed integer programming is up today one of the most widely used techniques for dealing with hard optimization problems. On the one side, many practical optimization problems arising from real-world applications (such as, e.g., scheduling, project planning, transportation, telecommunications, economics and finance, timetabling, etc) can be easily and effectively formulated as Mixed Integer linear Programs (MIPs). On the other hand, 50 and more years of intensive research has dramatically improved on the capability of the current generation of MIP solvers to tackle hard problems in practice. However, many questions are still open and not fully understood, and the mixed integer programming community is still more than active in trying to answer some of these questions. As a consequence, a huge number of papers are continuously developed and new intriguing questions arise every year. When dealing with MIPs, we have to distinguish between two different scenarios. The first one happens when we are asked to handle a general MIP and we cannot assume any special structure for the given problem. In this case, a Linear Programming (LP) relaxation and some integrality requirements are all we have for tackling the problem, and we are ``forced" to use some general purpose techniques. The second one happens when mixed integer programming is used to address a somehow structured problem. In this context, polyhedral analysis and other theoretical and practical considerations are typically exploited to devise some special purpose techniques. This thesis tries to give some insights in both the above mentioned situations. The first part of the work is focused on general purpose cutting planes, which are probably the key ingredient behind the success of the current generation of MIP solvers. Chapter 1 presents a quick overview of the main ingredients of a branch-and-cut algorithm, while Chapter 2 recalls some results from the literature in the context of disjunctive cuts and their connections with Gomory mixed integer cuts. Chapter 3 presents a theoretical and computational investigation of disjunctive cuts. In particular, we analyze the connections between different normalization conditions (i.e., conditions to truncate the cone associated with disjunctive cutting planes) and other crucial aspects as cut rank, cut density and cut strength. We give a theoretical characterization of weak rays of the disjunctive cone that lead to dominated cuts, and propose a practical method to possibly strengthen those cuts arising from such weak extremal solution. Further, we point out how redundant constraints can affect the quality of the generated disjunctive cuts, and discuss possible ways to cope with them. Finally, Chapter 4 presents some preliminary ideas in the context of multiple-row cuts. Very recently, a series of papers have brought the attention to the possibility of generating cuts using more than one row of the simplex tableau at a time. Several interesting theoretical results have been presented in this direction, often revisiting and recalling other important results discovered more than 40 years ago. However, is not clear at all how these results can be exploited in practice. As stated, the chapter is a still work-in-progress and simply presents a possible way for generating two-row cuts from the simplex tableau arising from lattice-free triangles and some preliminary computational results. The second part of the thesis is instead focused on the heuristic and exact exploitation of integer programming techniques for hard combinatorial optimization problems in the context of routing applications. Chapters 5 and 6 present an integer linear programming local search algorithm for Vehicle Routing Problems (VRPs). The overall procedure follows a general destroy-and-repair paradigm (i.e., the current solution is first randomly destroyed and then repaired in the attempt of finding a new improved solution) where a class of exponential neighborhoods are iteratively explored by heuristically solving an integer programming formulation through a general purpose MIP solver. Chapters 7 and 8 deal with exact branch-and-cut methods. Chapter 7 presents an extended formulation for the Traveling Salesman Problem with Time Windows (TSPTW), a generalization of the well known TSP where each node must be visited within a given time window. The polyhedral approaches proposed for this problem in the literature typically follow the one which has been proven to be extremely effective in the classical TSP context. Here we present an overall (quite) general idea which is based on a relaxed discretization of time windows. Such an idea leads to a stronger formulation and to stronger valid inequalities which are then separated within the classical branch-and-cut framework. Finally, Chapter 8 addresses the branch-and-cut in the context of Generalized Minimum Spanning Tree Problems (GMSTPs) (i.e., a class of NP-hard generalizations of the classical minimum spanning tree problem). In this chapter, we show how some basic ideas (and, in particular, the usage of general purpose cutting planes) can be useful to improve on branch-and-cut methods proposed in the literature.

Computer-Simulationen zur Strukturbildung von einzelnen Polymerketten

In dieser Arbeit wurden die Phasenübergänge einer einzelnen Polymerkette mit Hilfe der Monte Carlo Methode untersucht. Das Bondfluktuationsmodell wurde zur Simulation benutzt, wobei ein attraktives Kastenpotential zwischen allen Monomeren der Polymerkette gewirkt hat. Drei Arten von Bewegungen sind eingeführt worden, um die Polymerkette richtig zu relaxieren. Diese sind die Hüpfbewegung, die Reptationsbewegung und die Pivotbewegung. Um die Volumenausschlußwechselwirkung zu prüfen und um die Anzahl der Nachbarn jedes Monomers zu bestimmen ist ein hierarchischer Suchalgorithmus eingeführt worden. Die Zustandsdichte des Modells ist mittels des Wang-Landau Algorithmus bestimmt worden. Damit sind thermodynamische Größen berechnet worden, um die Phasenübergänge der einzelnen Polymerkette zu studieren. Wir haben zuerst eine freie Polymerkette untersucht. Der Knäuel-Kügelchen Übergang zeigt sich als ein kontinuierlicher Übergang, bei dem der Knäuel zum Kügelchen zusammenfällt. Der Kügelchen-Kügelchen Übergang bei niedrigeren Temperaturen ist ein Phasenübergang der ersten Ordnung, mit einer Koexistenz des flüssigen und festen Kügelchens, das eine kristalline Struktur hat. Im thermodynamischen Limes sind die Übergangstemperaturen identisch. Das entspricht einem Verschwinden der flüssigen Phase. In zwei Dimensionen zeigt das Modell einen kontinuierlichen Knäuel-Kügelchen Übergang mit einer lokal geordneten Struktur. Wir haben ferner einen Polymermushroom, das ist eine verankerte Polymerkette, zwischen zwei repulsiven Wänden im Abstand D untersucht. Das Phasenverhalten der Polymerkette zeigt einen dimensionalen crossover. Sowohl die Verankerung als auch die Beschränkung fördern den Knäuel-Kügelchen Übergang, wobei es eine Symmetriebrechung gibt, da die Ausdehnung der Polymerkette parallel zu den Wänden schneller schrumpft als die senkrecht zu den Wänden. Die Beschränkung hindert den Kügelchen-Kügelchen Übergang, wobei die Verankerung keinen Einfluss zu haben scheint. Die Übergangstemperaturen im thermodynamischen Limes sind wiederum identisch im Rahmen des Fehlers. Die spezifische Wärme des gleichen Modells aber mit einem abstoßendem Kastenpotential zeigt eine Schottky Anomalie, typisch für ein Zwei-Niveau System.

Metodi euristici per il problema dei trasporti con costi fissi

In questa tesi viene considerato il problema dei trasporti con costi fissi (FCTP) che, assieme al Traveling Salesman Problem (TSP), è uno dei problemi nobili dell’ottimizzazione combinatoria. Esso generalizza il ben noto problema dei trasporti (TP) imponendo che il costo per spedire prodotti da un’origine ad una destinazione sia composto da un costo fisso ed un costo proporzionale alla quantità spedita. Il FCTP è stato formulato per la prima volta in un articolo di Hirsch e Dantzig (1968) ed è stato da allora oggetto di studio per la ricerca di nuovi e sempre migliori algoritmi di risoluzione. Nessuno dei metodi esatti fin ora pubblicati è in grado di risolvere istanze con più di 15 origini e 15 destinazioni. Solo recentemente, Roberti et al. (2013), in un paper in corso di pubblicazione, hanno presentato un metodo esatto basato su una nuova formulazione matematica del problema, il quale è in grado di risolvere istanze di FCTP con 70 origini e 70 destinazioni. La crescita esponenziale dello sforzo computazionale richiesto dai metodi esatti ne ha confinato l’applicazione a problemi di dimensioni ridotte. Tali limitazioni hanno portato allo studio e alla ricerca di approcci approssimativi, euristici e metaeuristici i quali sfruttano varie strategie di local search. Fra i molteplici metodi euristici presentati in letteratura, meritano particolare attenzione quelli di Sun et al. (1998) e Glover et al. (2005). Recentemente, Buson et al. (2013) hanno presentato un nuovo euristico che domina tutti i precedenti sui problemi test proposti in letteratura. In questa tesi viene presentato un approccio Tabu Search che migliora il metodo originalmente proposto da Sun et al. (1998). I risultati computazionali ottenuti con un codice prototipale indicano che l’algoritmo sviluppato è migliore del metodo originario di Sun et al. (1998) e competitivo con il più recente metodo proposto da Buson et al. (2013).

Performance analysis of reconstruction algorithms for breast microwave imaging

The problem of localizing a scatterer, which represents a tumor, in a homogeneous circular domain, which represents a breast, is addressed. A breast imaging method based on microwaves is considered. The microwave imaging involves to several techniques for detecting, localizing and characterizing tumors in breast tissues. In all such methods an electromagnetic inverse scattering problem exists. For the scattering detection method, an algorithm based on a linear procedure solution, inspired by MUltiple SIgnal Classification algorithm (MUSIC) and Time Reversal method (TR), is implemented. The algorithm returns a reconstructed image of the investigation domain in which it is detected the scatterer position. This image is called pseudospectrum. A preliminary performance analysis of the algorithm vying the working frequency is performed: the resolution and the signal-to-noise ratio of the pseudospectra are improved if a multi-frequency approach is considered. The Geometrical Mean-MUSIC algorithm (GM- MUSIC) is proposed as multi-frequency method. The performance of the GMMUSIC is tested in different real life computer simulations. The performed analysis shows that the algorithm detects the scatterer until the electrical parameters of the breast are known. This is an evident limit, since, in a real life situation, the anatomy of the breast is unknown. An improvement in GM-MUSIC is proposed: the Eye-GMMUSIC algorithm. Eye-GMMUSIC algorithm needs no a priori information on the electrical parameters of the breast. It is an optimizing algorithm based on the pattern search algorithm: it searches the breast parameters which minimize the Signal-to-Clutter Mean Ratio (SCMR) in the signal. Finally, the GM-MUSIC and the Eye-GMMUSIC algorithms are tested on a microwave breast cancer detection system consisting of an dipole antenna, a Vector Network Analyzer and a novel breast phantom built at University of Bologna. The reconstruction of the experimental data confirm the GM-MUSIC ability to localize a scatterer in a homogeneous medium.

Algoritmi di ottimizzazione per il bus touring problem.

Nel campo della Ricerca Operativa e dei problemi di ottimizzazione viene presentato un problema, denominato Bus Touring Problem (BTP), che modella una problematica riguardante il carico e l’instradamento di veicoli nella presenza di di vincoli temporali e topologici sui percorsi. Nel BTP, ci si pone il problema di stabilire una serie di rotte per la visita di punti di interesse dislocati geograficamente da parte di un insieme di comitive turistiche, ciascuna delle quali stabilisce preferenze riguardo le visite. Per gli spostamenti sono disponibili un numero limitato di mezzi di trasporto, in generale eterogenei, e di capacitá limitata. Le visite devono essere effettuate rispettando finestre temporali che indicano i periodi di apertura dei punti di interesse; per questi, inoltre, é specificato un numero massimo di visite ammesse. L’obiettivo é di organizzare il carico dei mezzi di trasporto e le rotte intraprese in modo da massimizzare la soddisfazione complessiva dei gruppi di turisti nel rispetto dei vincoli imposti. Viene presentato un algoritmo euristico basato su Tabu Search appositamente ideato e progettato per la risoluzione del BTP. Vengono presentati gli esperimenti effettuati riguardo la messa appunto dei parametri dell'algoritmo su un insieme di problemi di benchmark. Vengono presentati risultati estesi riguardo le soluzioni dei problemi. Infine, vengono presentate considerazioni ed indicazioni di sviluppo futuro in materia.

Hierarchical Approach for Survivable Network Design

A central design challenge facing network planners is how to select a cost-effective network configuration that can provide uninterrupted service despite edge failures. In this paper, we study the Survivable Network Design (SND) problem, a core model underlying the design of such resilient networks that incorporates complex cost and connectivity trade-offs. Given an undirected graph with specified edge costs and (integer) connectivity requirements between pairs of nodes, the SND problem seeks the minimum cost set of edges that interconnects each node pair with at least as many edge-disjoint paths as the connectivity requirement of the nodes. We develop a hierarchical approach for solving the problem that integrates ideas from decomposition, tabu search, randomization, and optimization. The approach decomposes the SND problem into two subproblems, Backbone design and Access design, and uses an iterative multi-stage method for solving the SND problem in a hierarchical fashion. Since both subproblems are NP-hard, we develop effective optimization-based tabu search strategies that balance intensification and diversification to identify near-optimal solutions. To initiate this method, we develop two heuristic procedures that can yield good starting points. We test the combined approach on large-scale SND instances, and empirically assess the quality of the solutions vis-à-vis optimal values or lower bounds. On average, our hierarchical solution approach generates solutions within 2.7% of optimality even for very large problems (that cannot be solved using exact methods), and our results demonstrate that the performance of the method is robust for a variety of problems with different size and connectivity characteristics.

Quality evaluation of tandem mass spectral libraries

Tandem mass spectral libraries are gaining more and more importance for the identification of unknowns in different fields of research, including metabolomics, forensics, toxicology, and environmental analysis. Particularly, the recent invention of reliable, robust, and transferable libraries has increased the general acceptance of these tools. Herein, we report on results obtained from thorough evaluation of the match reliabilities of two tandem mass spectral libraries: the MSforID library established by the Oberacher group in Innsbruck and the Weinmann library established by the Weinmann group in Freiburg. Three different experiments were performed: (1) Spectra of the libraries were searched against their corresponding library after excluding either this single compound-specific spectrum or all compound-specific spectra prior to searching; (2) the libraries were searched against each other using either library as reference set or sample set; (3) spectra acquired on different mass spectrometric instruments were matched to both libraries. Almost 13,000 tandem mass spectra were included in this study. The MSforID search algorithm was used for spectral matching. Statistical evaluation of the library search results revealed that principally both libraries enable the sensitive and specific identification of compounds. Due to higher mass accuracy of the QqTOF compared with the QTrap instrument, matches to the MSforID library were more reliable when comparing spectra with both libraries. Furthermore, only the MSforID library was shown to be efficiently transferable to different kinds of tandem mass spectrometers, including "tandem-in-time" instruments; this is due to the coverage of a large range of different collision energy settings-including the very low range-which is an outstanding characteristics of the MSforID library.

MODEL UPDATING AND STRUCTURAL HEALTH MONITORING OF HORIZONTAL AXIS WIND TURBINES VIA ADVANCED SPINNING FINITE ELEMENTS AND STOCHASTIC SUBSPACE IDENTIFICATION METHODS

Wind energy has been one of the most growing sectors of the nation’s renewable energy portfolio for the past decade, and the same tendency is being projected for the upcoming years given the aggressive governmental policies for the reduction of fossil fuel dependency. Great technological expectation and outstanding commercial penetration has shown the so called Horizontal Axis Wind Turbines (HAWT) technologies. Given its great acceptance, size evolution of wind turbines over time has increased exponentially. However, safety and economical concerns have emerged as a result of the newly design tendencies for massive scale wind turbine structures presenting high slenderness ratios and complex shapes, typically located in remote areas (e.g. offshore wind farms). In this regard, safety operation requires not only having first-hand information regarding actual structural dynamic conditions under aerodynamic action, but also a deep understanding of the environmental factors in which these multibody rotating structures operate. Given the cyclo-stochastic patterns of the wind loading exerting pressure on a HAWT, a probabilistic framework is appropriate to characterize the risk of failure in terms of resistance and serviceability conditions, at any given time. Furthermore, sources of uncertainty such as material imperfections, buffeting and flutter, aeroelastic damping, gyroscopic effects, turbulence, among others, have pleaded for the use of a more sophisticated mathematical framework that could properly handle all these sources of indetermination. The attainable modeling complexity that arises as a result of these characterizations demands a data-driven experimental validation methodology to calibrate and corroborate the model. For this aim, System Identification (SI) techniques offer a spectrum of well-established numerical methods appropriated for stationary, deterministic, and data-driven numerical schemes, capable of predicting actual dynamic states (eigenrealizations) of traditional time-invariant dynamic systems. As a consequence, it is proposed a modified data-driven SI metric based on the so called Subspace Realization Theory, now adapted for stochastic non-stationary and timevarying systems, as is the case of HAWT’s complex aerodynamics. Simultaneously, this investigation explores the characterization of the turbine loading and response envelopes for critical failure modes of the structural components the wind turbine is made of. In the long run, both aerodynamic framework (theoretical model) and system identification (experimental model) will be merged in a numerical engine formulated as a search algorithm for model updating, also known as Adaptive Simulated Annealing (ASA) process. This iterative engine is based on a set of function minimizations computed by a metric called Modal Assurance Criterion (MAC). In summary, the Thesis is composed of four major parts: (1) development of an analytical aerodynamic framework that predicts interacted wind-structure stochastic loads on wind turbine components; (2) development of a novel tapered-swept-corved Spinning Finite Element (SFE) that includes dampedgyroscopic effects and axial-flexural-torsional coupling; (3) a novel data-driven structural health monitoring (SHM) algorithm via stochastic subspace identification methods; and (4) a numerical search (optimization) engine based on ASA and MAC capable of updating the SFE aerodynamic model.

Searching for the majority: algorithms of voluntary control.

Voluntary control of information processing is crucial to allocate resources and prioritize the processes that are most important under a given situation; the algorithms underlying such control, however, are often not clear. We investigated possible algorithms of control for the performance of the majority function, in which participants searched for and identified one of two alternative categories (left or right pointing arrows) as composing the majority in each stimulus set. We manipulated the amount (set size of 1, 3, and 5) and content (ratio of left and right pointing arrows within a set) of the inputs to test competing hypotheses regarding mental operations for information processing. Using a novel measure based on computational load, we found that reaction time was best predicted by a grouping search algorithm as compared to alternative algorithms (i.e., exhaustive or self-terminating search). The grouping search algorithm involves sampling and resampling of the inputs before a decision is reached. These findings highlight the importance of investigating the implications of voluntary control via algorithms of mental operations.

MASCG: Multi-Atlas Segmentation Constrained Graph method for accurate segmentation of hip CT images

This paper addresses the issue of fully automatic segmentation of a hip CT image with the goal to preserve the joint structure for clinical applications in hip disease diagnosis and treatment. For this purpose, we propose a Multi-Atlas Segmentation Constrained Graph (MASCG) method. The MASCG method uses multi-atlas based mesh fusion results to initialize a bone sheetness based multi-label graph cut for an accurate hip CT segmentation which has the inherent advantage of automatic separation of the pelvic region from the bilateral proximal femoral regions. We then introduce a graph cut constrained graph search algorithm to further improve the segmentation accuracy around the bilateral hip joint regions. Taking manual segmentation as the ground truth, we evaluated the present approach on 30 hip CT images (60 hips) with a 15-fold cross validation. When the present approach was compared to manual segmentation, an average surface distance error of 0.30 mm, 0.29 mm, and 0.30 mm was found for the pelvis, the left proximal femur, and the right proximal femur, respectively. A further look at the bilateral hip joint regions demonstrated an average surface distance error of 0.16 mm, 0.21 mm and 0.20 mm for the acetabulum, the left femoral head, and the right femoral head, respectively.

Bathymetric map of Heron Reef, Australia, derived from airborne hyperspectral data at 1 m resolution

A simple method for efficient inversion of arbitrary radiative transfer models for image analysis is presented. The method operates by representing the shape of the function that maps model parameters to spectral reflectance by an adaptive look-up tree (ALUT) that evenly distributes the discretization error of tabulated reflectances in spectral space. A post-processing step organizes the data into a binary space partitioning tree that facilitates an efficient inversion search algorithm. In an example shallow water remote sensing application, the method performs faster than an implementation of previously published methodology and has the same accuracy in bathymetric retrievals. The method has no user configuration parameters requiring expert knowledge and minimizes the number of forward model runs required, making it highly suitable for routine operational implementation of image analysis methods. For the research community, straightforward and robust inversion allows research to focus on improving the radiative transfer models themselves without the added complication of devising an inversion strategy.

Learning an L1-regularized Gaussian Bayesian Network in the Equivalence Class Space

Learning the structure of a graphical model from data is a common task in a wide range of practical applications. In this paper, we focus on Gaussian Bayesian networks, i.e., on continuous data and directed acyclic graphs with a joint probability density of all variables given by a Gaussian. We propose to work in an equivalence class search space, specifically using the k-greedy equivalence search algorithm. This, combined with regularization techniques to guide the structure search, can learn sparse networks close to the one that generated the data. We provide results on some synthetic networks and on modeling the gene network of the two biological pathways regulating the biosynthesis of isoprenoids for the Arabidopsis thaliana plant

Solving Incidents in Telecommunications Using a Multiagent System

This article presents the model and implementation of a multiagent fuzzy system (MAFS), to automate the search of solutions of incidents in telecommunications, expressed by the users in an imprecise way and, later, registered in a a knowledge base keeping their original vaguenesses and the relationships between the incidents considered as ancestors and descendants. The process of the fuzzy incidents, no matter their causes, is based on the application of a formula which transforms the intervals of the fuzzy incidents to a computational language and in the interaction between the different kinds of software agents and the humans. To search and suggest solutions of the incident originally stated, a search algorithm is used and illustrated with an example. The preliminary results obtained show the users' satisfaction, in a great percentage of the presented cases. The system is adaptive and allows to record new solutions for future users.