Algorithms for network design and routing problems

In this thesis we study three combinatorial optimization problems belonging to the classes of Network Design and Vehicle Routing problems that are strongly linked in the context of the design and management of transportation networks: the Non-Bifurcated Capacitated Network Design Problem (NBP), the Period Vehicle Routing Problem (PVRP) and the Pickup and Delivery Problem with Time Windows (PDPTW). These problems are NP-hard and contain as special cases some well known difficult problems such as the Traveling Salesman Problem and the Steiner Tree Problem. Moreover, they model the core structure of many practical problems arising in logistics and telecommunications. The NBP is the problem of designing the optimum network to satisfy a given set of traffic demands. Given a set of nodes, a set of potential links and a set of point-to-point demands called commodities, the objective is to select the links to install and dimension their capacities so that all the demands can be routed between their respective endpoints, and the sum of link fixed costs and commodity routing costs is minimized. The problem is called non- bifurcated because the solution network must allow each demand to follow a single path, i.e., the flow of each demand cannot be splitted. Although this is the case in many real applications, the NBP has received significantly less attention in the literature than other capacitated network design problems that allow bifurcation. We describe an exact algorithm for the NBP that is based on solving by an integer programming solver a formulation of the problem strengthened by simple valid inequalities and four new heuristic algorithms. One of these heuristics is an adaptive memory metaheuristic, based on partial enumeration, that could be applied to a wider class of structured combinatorial optimization problems. In the PVRP a fleet of vehicles of identical capacity must be used to service a set of customers over a planning period of several days. Each customer specifies a service frequency, a set of allowable day-combinations and a quantity of product that the customer must receive every time he is visited. For example, a customer may require to be visited twice during a 5-day period imposing that these visits take place on Monday-Thursday or Monday-Friday or Tuesday-Friday. The problem consists in simultaneously assigning a day- combination to each customer and in designing the vehicle routes for each day so that each customer is visited the required number of times, the number of routes on each day does not exceed the number of vehicles available, and the total cost of the routes over the period is minimized. We also consider a tactical variant of this problem, called Tactical Planning Vehicle Routing Problem, where customers require to be visited on a specific day of the period but a penalty cost, called service cost, can be paid to postpone the visit to a later day than that required. At our knowledge all the algorithms proposed in the literature for the PVRP are heuristics. In this thesis we present for the first time an exact algorithm for the PVRP that is based on different relaxations of a set partitioning-like formulation. The effectiveness of the proposed algorithm is tested on a set of instances from the literature and on a new set of instances. Finally, the PDPTW is to service a set of transportation requests using a fleet of identical vehicles of limited capacity located at a central depot. Each request specifies a pickup location and a delivery location and requires that a given quantity of load is transported from the pickup location to the delivery location. Moreover, each location can be visited only within an associated time window. Each vehicle can perform at most one route and the problem is to satisfy all the requests using the available vehicles so that each request is serviced by a single vehicle, the load on each vehicle does not exceed the capacity, and all locations are visited according to their time window. We formulate the PDPTW as a set partitioning-like problem with additional cuts and we propose an exact algorithm based on different relaxations of the mathematical formulation and a branch-and-cut-and-price algorithm. The new algorithm is tested on two classes of problems from the literature and compared with a recent branch-and-cut-and-price algorithm from the literature.

Biofilms on exposed monumental stones: mechanism of formation and development of new control methods

Within the stone monumental artefacts artistic fountains are extremely favorable to formation of biofilms, giving rise to biodegradation processes related with physical-chemical and visual aspect alterations, because of their particular exposure conditions. Microbial diversity of five fountains (two from Spain and three from Italy) was investigated. It was observed an ample similarity between the biodiversity of monumental stones reported in literature and that one found in studied fountains. Mechanical procedures and toxic chemical products are usually employed to remove such phototrophic patinas. Alternative methods based on natural antifouling substances are recently experimented in the marine sector, due to their very low environmental impact and for the bio settlement prevention on partially immersed structures of ships. In the present work groups of antibiofouling agents (ABAs) were selected from literature for their ability to interfere, at molecular level, with the microbial communication system “quorum sensing”, inhibiting the initial phase of biofilm formation. The efficacy of some natural antibiofoulants agents (ABAs) with terrestrial (Capsaicine - CS, Cinnamaldehyde - CI) and marine origin (Zosteric Acid - ZA, poly-Alkyl Pyridinium Salts – pAPS and Ceramium botryocarpum extract - CBE), incorporated into two commercial coatings (Silres BS OH 100 - S and Wacker Silres BS 290 - W) commonly used in stone conservation procedures were evaluated. The formation of phototrophic biofilms in laboratory conditions (on Carrara marble specimens and Sierra Elvira stone) and on two monumental fountains (Tacca’s Fountain 2 - Florence, Italy and Fountain from Patio de la Lindaraja - Alhambra Palace, Granada, Spain) has been investigated in the presence or absence of these natural antifouling agents. The natural antibiofouling agents, at tested concentrations, demonstrated a certain inhibitory effect. The silane-siloxane based silicone coating (W) mixing with ABAs was more suitable with respect to ethyl silicate coating (S) and proved efficacy against biofilm formation only when incompletely cured. The laboratory results indicated a positive action in inhibiting the patina formation, especially for poly-alkyl pyridinium salts, zosteric acid and cinnamaldehyde, while on site tests revealed a good effect for zosteric acid.

Hybrid Methods for Resource Allocation and Scheduling Problems in Deterministic and Stochastic Environments

This work presents exact, hybrid algorithms for mixed resource Allocation and Scheduling problems; in general terms, those consist into assigning over time finite capacity resources to a set of precedence connected activities. The proposed methods have broad applicability, but are mainly motivated by applications in the field of Embedded System Design. In particular, high-performance embedded computing recently witnessed the shift from single CPU platforms with application-specific accelerators to programmable Multi Processor Systems-on-Chip (MPSoCs). Those allow higher flexibility, real time performance and low energy consumption, but the programmer must be able to effectively exploit the platform parallelism. This raises interest in the development of algorithmic techniques to be embedded in CAD tools; in particular, given a specific application and platform, the objective if to perform optimal allocation of hardware resources and to compute an execution schedule. On this regard, since embedded systems tend to run the same set of applications for their entire lifetime, off-line, exact optimization approaches are particularly appealing. Quite surprisingly, the use of exact algorithms has not been well investigated so far; this is in part motivated by the complexity of integrated allocation and scheduling, setting tough challenges for ``pure'' combinatorial methods. The use of hybrid CP/OR approaches presents the opportunity to exploit mutual advantages of different methods, while compensating for their weaknesses. In this work, we consider in first instance an Allocation and Scheduling problem over the Cell BE processor by Sony, IBM and Toshiba; we propose three different solution methods, leveraging decomposition, cut generation and heuristic guided search. Next, we face Allocation and Scheduling of so-called Conditional Task Graphs, explicitly accounting for branches with outcome not known at design time; we extend the CP scheduling framework to effectively deal with the introduced stochastic elements. Finally, we address Allocation and Scheduling with uncertain, bounded execution times, via conflict based tree search; we introduce a simple and flexible time model to take into account duration variability and provide an efficient conflict detection method. The proposed approaches achieve good results on practical size problem, thus demonstrating the use of exact approaches for system design is feasible. Furthermore, the developed techniques bring significant contributions to combinatorial optimization methods.

Automated Segmentation and Non-Rigid Registration for the Quantitative Evaluation of Myocardial Perfusion from Magnetic Resonance Images

Myocardial perfusion quantification by means of Contrast-Enhanced Cardiac Magnetic Resonance images relies on time consuming frame-by-frame manual tracing of regions of interest. In this Thesis, a novel automated technique for myocardial segmentation and non-rigid registration as a basis for perfusion quantification is presented. The proposed technique is based on three steps: reference frame selection, myocardial segmentation and non-rigid registration. In the first step, the reference frame in which both endo- and epicardial segmentation will be performed is chosen. Endocardial segmentation is achieved by means of a statistical region-based level-set technique followed by a curvature-based regularization motion. Epicardial segmentation is achieved by means of an edge-based level-set technique followed again by a regularization motion. To take into account the changes in position, size and shape of myocardium throughout the sequence due to out of plane respiratory motion, a non-rigid registration algorithm is required. The proposed non-rigid registration scheme consists in a novel multiscale extension of the normalized cross-correlation algorithm in combination with level-set methods. The myocardium is then divided into standard segments. Contrast enhancement curves are computed measuring the mean pixel intensity of each segment over time, and perfusion indices are extracted from each curve. The overall approach has been tested on synthetic and real datasets. For validation purposes, the sequences have been manually traced by an experienced interpreter, and contrast enhancement curves as well as perfusion indices have been computed. Comparisons between automatically extracted and manually obtained contours and enhancement curves showed high inter-technique agreement. Comparisons of perfusion indices computed using both approaches against quantitative coronary angiography and visual interpretation demonstrated that the two technique have similar diagnostic accuracy. In conclusion, the proposed technique allows fast, automated and accurate measurement of intra-myocardial contrast dynamics, and may thus address the strong clinical need for quantitative evaluation of myocardial perfusion.

Spectral theory of differential operators on finite metric graphs and on bounded domains

Die vorliegende Arbeit widmet sich der Spektraltheorie von Differentialoperatoren auf metrischen Graphen und von indefiniten Differentialoperatoren auf beschränkten Gebieten. Sie besteht aus zwei Teilen. Im Ersten werden endliche, nicht notwendigerweise kompakte, metrische Graphen und die Hilberträume von quadratintegrierbaren Funktionen auf diesen betrachtet. Alle quasi-m-akkretiven Laplaceoperatoren auf solchen Graphen werden charakterisiert, und Abschätzungen an die negativen Eigenwerte selbstadjungierter Laplaceoperatoren werden hergeleitet. Weiterhin wird die Wohlgestelltheit eines gemischten Diffusions- und Transportproblems auf kompakten Graphen durch die Anwendung von Halbgruppenmethoden untersucht. Eine Verallgemeinerung des indefiniten Operators $-tfrac{d}{dx}sgn(x)tfrac{d}{dx}$ von Intervallen auf metrische Graphen wird eingeführt. Die Spektral- und Streutheorie der selbstadjungierten Realisierungen wird detailliert besprochen. Im zweiten Teil der Arbeit werden Operatoren untersucht, die mit indefiniten Formen der Art $langlegrad v, A(cdot)grad urangle$ mit $u,vin H_0^1(Omega)subset L^2(Omega)$ und $OmegasubsetR^d$ beschränkt, assoziiert sind. Das Eigenwertverhalten entspricht in Dimension $d=1$ einer verallgemeinerten Weylschen Asymptotik und für $dgeq 2$ werden Abschätzungen an die Eigenwerte bewiesen. Die Frage, wann indefinite Formmethoden für Dimensionen $dgeq 2$ anwendbar sind, bleibt offen und wird diskutiert.

Visual hallucinations in dementia with Lewy bodies: a transcranial magnetic stimulation study

BACKGROUND: The aetiology of visual hallucinations is poorly understood in dementia with Lewy bodies. Pathological alterations in visual cortical excitability may be one contributory mechanism. AIMS: To determine visual cortical excitability in people with dementia with Lewy bodies compared with aged-matched controls and also the relationship between visual cortical excitability and visual hallucinations in dementia with Lewy bodies. METHOD: Visual cortical excitability was determined by using transcranial magnetic stimulation (TMS) applied to the occiput to elicit phosphenes (transient subjective visual responses) in 21 patients with dementia with Lewy bodies and 19 age-matched controls. RESULTS: Phosphene parameters were similar between both groups. However, in the patients with dementia with Lewy bodies, TMS measures of visual cortical excitability correlated strongly with the severity of visual hallucinations (P = 0.005). Six patients with dementia with Lewy bodies experienced visual hallucination-like phosphenes (for example, seeing people or figures on stimulation) compared with none of the controls (P = 0.02). CONCLUSIONS: Increased visual cortical excitability in dementia with Lewy bodies does not appear to explain visual hallucinations but it may be a marker for their severity.

CT patterns of fungal pulmonary infections of the lung: Comparison of standard-dose and simulated low-dose CT

To assess the effect of radiation dose reduction on the appearance and visual quantification of specific CT patterns of fungal infection in immuno-compromised patients.

Coping With a Family Member's Death: Parenting, Religiosity, and Parent-Child Communication

The present study had three major aims. First, this study was a basic descriptive exploration of the frequency and nature of parent-child communication about death. Second, this study conducted a quantitative analysis to identify predictors of communication and bereaved children¿s emotional and behavioral problems. Third, this study was also a qualitative analysis of parents¿ descriptions of how religious views shape conversations about death and how conversations are beneficial. Based on prior research, it was predicted that positive child outcomes would be associated with parental warmth, religiosity, adaptive coping, positive religious coping, and frequent parent-child communication about death. Conversely, it was predicted that negative child outcomes would be associated with parental psychological control, maladaptive coping, negative religious coping, and less frequent parent-child communication about death. Additionally, it was hypothesized that parents¿ religious and spiritual views would shape parent-child communication about death, and parents would describe numerous benefits of discussing death with children. Parents completed a series of survey measures assessing their religiosity, coping strategies, parent-child communication about death, and their children¿s emotional and behavioral symptoms. Almost 80% of parent-child dyads discussed death at least once a week, and children initiated approximately half of these conversations. Parent-child communication about death was predicted by parents¿ warmth toward and acceptance of their children and inversely predicted by children¿s hyperactivity and social problem solving. Higher levels of children¿s social problem solving could predict lower frequency of parent-child communication about death if children were holding frequent, meaningful, and comforting conversations with friends and other adults. Higher levels of parents¿ psychological control predicted more emotional and behavioral problems in the child. Parents¿ adaptive coping had significant relationships with all of the dimensions of parent-child communication about death. Qualitative analyses revealed that parents perceived their religious beliefs as shaping conversations about death and grief as an individualized journey. A majority of parents described the emotional, social, and intellectual benefits of holding parent-child conversations about death. This study contributes to the literature by further describing parent-child communication about death, identifying its predictors, and investigating parents¿ religiosity and coping strategies in relation to child well-being. Overall, this study revealed the importance of assessing global parenting characteristics (i.e., warmth/acceptance and psychological control) when examining parent-child relationships and communication about death. Furthermore, this unique study illustrates the value of qualitative data when examining parent-child communication about death and religiosity.

Comparative Analysis of Russian and French Prosodies: Theoretical, Experimental and Applied Aspects"

Experience shows that in teaching the pronunciation of a foreign language, it is the native syllable stereotype that resists correction most strongly. This is because the syllable is the basic unit of the perception and production of speech, and syllabic production is highly automatic and to some degree determines the prosody of speech at all levels: accent, rhythm, phrase, etc. The results of psycho-physiological studies show that the human acoustic analyser is a typical contemplator organ and new acoustic qualities are perceived through their inclusion into the already existing system of values characteristic to the mother tongue. This results in the adaptation of the perception and so production of foreign speech to native patterns. The less conscious the perception of the unit and the more 'primitive' its status, the greater the degree of its auditory assimilation, and the syllable is certainly among the less controllable linguistic units. The group carried out a complex investigation of the French and Russian languages at the level of syllable realisation, focusing on the stressed syllable of both open and closed types. The useful acoustic characteristics of the French/Russian syllable pattern were determined through identifying a typical syllable pattern within the system of each of the two languages, comparing these patterns to establish their contrasting features, and observing and systematising deviations from the pattern typical of the French/Russian language teaching situation. The components of the syllable pattern shown to need particular attention in teaching French pronunciation to Russian native speakers were intensity, fundamental frequency, and duration. The group then developed a method of correction which combines the auditory and visual canals of sound signal perception and tested this method with groups of Russian students of different levels.

Clinicopathologic correlations of silent corticotroph adenomas of the pituitary: report of four cases and literature review

Silent corticotroph adenomas (SCA) are rare pituitary tumors with histologic hallmarks of corticotroph differentiation, including ACTH immunoreactivity, but lacking clinical evidence of Cushing's syndrome. We report on four female patients, aged 19-66 years, each presenting with a nonfunctional macroadenoma. Leading symptoms were headache in two cases and visual field deficits in one. One patient was incidentally diagnosed while undergoing cranial MRI for an unrelated condition. Three patients had marked obesity; none of them presented constitutional signs of Cushing's syndrome. Serum cortisol levels were moderately elevated in the two patients systematically tested in this respect. Marginal to moderate hyperprolactinemia was present in two cases. Two patients also were shown to be deficient in either gonadotroph or thyrotroph axis, while a third had a combined insufficiency of both gonadotroph and thyrotroph axis. MRI scans revealed intratumoral hemorrhage and/or cystic change in three cases, as well as tumor-related occlusive hydrocephalus in one. The latter patient was biopsied only, while the remaining underwent gross total resection. Histologically, all four lesions were diagnosed as SCA subtype I displaying intense immunoreactivity for ACTH. In three tumors, scattered cells coexpressed PRL as well. In addition, Crooke's hyaline change was noted in a significant number of tumor cells and in residual non-neoplastic corticotrophs in one case each. With MIB-1 labeling indices of 1-3%, none of the tumors qualified as atypical adenoma. We conclude that SCAs are more likely to be discovered as expansile tumors, whose advanced local space-occupying character at surgery rather than an inherently aggressive growth potential may negatively influence the clinical outcome. Subtle morphologic evidence of corticotroph suppression in residual pituitary adjacent to tumor lends further support to literature data indicating minimal or intermittent functional activity in this tumor type.

Visual function in human ocular toxoplasmosis

AIM: To assess functional impairment in terms of visual acuity reduction and visual field defects in inactive ocular toxoplasmosis. METHODS: 61 patients with known ocular toxoplasmosis in a quiescent state were included in this prospective, cross-sectional study. A complete ophthalmic examination, retinal photodocumentation and standard automated perimetry (Octopus perimeter, program G2) were performed. Visual acuity was classified on the basis of the World Health Organization definition of visual impairment and blindness: normal (> or =20/25), mild (20/25 to 20/60), moderate (20/60 to 20/400) and severe (<20/400). Visual field damage was correspondingly graded as mild (mean defect <4 dB), moderate (mean defect 4-12 dB) or severe (mean defect >12 dB). RESULTS: 8 (13%) patients presented with bilateral ocular toxoplasmosis. Thus, a total of 69 eyes was evaluated. Visual field damage was encountered in 65 (94%) eyes, whereas only 28 (41%) eyes had reduced visual acuity, showing perimetric findings to be more sensitive in detecting chorioretinal damage (p<0.001). Correlation with the clinical localisation of chorioretinal scars was better for visual field (in 70% of the instances) than for visual acuity (33%). Moderate to severe functional impairment was registered in 65.2% for visual field, and in 27.5% for visual acuity. CONCLUSION: In its quiescent stage, ocular toxoplasmosis was associated with permanent visual field defects in >94% of the eyes studied. Hence, standard automated perimetry may better reflect the functional damage encountered by ocular toxoplasmosis than visual acuity.

Behavioral and anatomical abnormalities in a sodium iodate-induced model of retinal pigment epithelium degeneration

We characterized changes in the visual behavior of mice in which a loss of the retinal pigment epithelium (RPE) was experimentally induced with intravenous (i.v.) administration of sodium iodate (NaIO3). We compared and correlated these changes with alterations in neural retinal structure and function. RPE loss was induced in 4-6 week old male C57BL/6 mice with an i.v. injection of 1% NaIO3 at three concentrations: 35, 50, or 70 mg/kg. At 1, 3, 7, 14, 21, and 28 days (d) as well as 6 months post injection (PI) a behavioral test was performed in previously trained mice to evaluate visual function. Eye morphology was then assessed for changes in both the RPE and neural retina. NaIO3-induced RPE degeneration was both dose and PI time dependent. Our low dose showed no effects, while our high dose caused the most damage, as did longer PI times at our intermediate dose. Using the intermediate dose, no changes were detectable in either visual behavior or retinal morphology at 1 d PI. However, at 3 d PI visual behavior became abnormal and patchy RPE cell loss was observed. From 7 d PI onward, changes in retinal morphology and visual behavior became more severe. At 6 months PI, no recovery was seen in any of these measures in mice administered the intermediate dose. These results show that NaIO3 dosage and/or time PI can be varied to produce different, yet permanent deficits in retinal morphology and visual function. Thus, this approach should provide a unique system in which the onset and severity of RPE damage, and its consequences can be manipulated. As such, it should be useful in the assessment of rescue or mitigating effects of retinal or stem cell transplantation on visual function.

Pontocerebellar hypoplasia type 2: variability in clinical and imaging findings

We report 24 children (14 girls) who presented with the typical neuroimaging findings of pontocerebellar hypoplasia (PCH) to describe the clinical spectrum of type 2. Twenty-one presented with the classical form described by Barth; characteristic features (15/21) were breathing and/or sucking problems during neonatal period and early onset hyperkinetic movement disorder. Eighteen were normocephalic at birth, but all developed microcephaly during infancy. Development was severely affected with none of the children being capable of sitting, walking, or talking. Social contact and visual fixation were persistently poor. Dyskinetic movement disorder was present in all, in some together with mild spasticity. Seizures occurred in 14 (in 7 as neonates). Eight children died (age 1 day-6 years). Neuroimaging showed an absent or severely flattened pons, different degrees of vermian hypoplasia, with cerebellar hemispheres (wing-like structures) being equally or more affected. Three (all girls) were less severely affected clinically and did not develop the dyskinetic movement disorder, motor and cognitive development were somewhat better. Microcephaly was also a prominent sign. Severity of pontocerebellar neuroimaging findings did not differentiate between the typical and atypical clinical group and did not correlate with clinical outcome.

Trypanosomes and mammalian sperm: one of a kind?

Flagellar-mediated motility is an indispensable function for cell types as evolutionarily distant as mammalian sperm and kinetoplastid parasites, a large group of flagellated protozoa that includes several important human pathogens. Despite the obvious importance of flagellar motility, little is known about the signalling processes that direct the frequency and wave shape of the flagellar beat, or those that provide the motile cell with the necessary environmental cues that enable it to aim its movement. Similarly, the energetics of the flagellar beat and the problem of a sufficient ATP supply along the entire length of the beating flagellum remain to be explored. Recent proteome projects studying the flagella of mammalian sperm and kinetoplastid parasites have provided important information and have indicated a surprising degree of similarities between the flagella of these two cell types.

[Titanium-alloy vs. CoCr-alloy in removable prosthodontics--a clinical study]

Different types of titanium-alloys instead of CoCr-alloys have been tested as material for the framework of removable partial dentures (RPD). Adequate casting and processing techniques have been developed which enable to fabricate frameworks of complex designs and the problem limits porosity. This opened new possibilities for the use of titanium-alloys with improved properties (E-module). The aim of this study was to summarise the use of titanium in removable prosthodontics and to evaluate prospectively the use of the Ti6A17Nb-alloy for RPDs in a small group of patients. Two identically designed RPDs from CoCr-alloy (remanium GM 800+) and Ti6A17Nb-alloy (girotan L) were produced for ten patients. They had to wear each RPD during six months, first the CoCr-RPD and then the Ti6A17Nb-RPD. A questionnaire (visual analogue scale = VAS) was completed by the patients after one, three and six months of function for each RPD. Prosthetic complications and service needed were recorded. After the end of the entire observation period of twelve months, the patients remained with the Ti6A17Nb-RPD and answered the questionnaire after another six months. All parameters regarding the design of the RPDs were positively estimated by the dentist. Minimal, not significant differences were noted by the patients concerning comfort, stability and retention (VAS). Clinically, no differences in technical aspects or regarding biological complications were observed after six-months periods. The Ti6A17Nb-alloy (girotan L) for the framework of RPDs was judged by patients and professionals to be equivalent to RPDs made from CoCr-alloy. No differences in material aspects could objectively be observed. The Ti6A17Nb-alloy can be beneficial for patients with allergies or incompatibility with one or several components of the CoCr-alloy.