Optimization heuristic solutions, how good can they be? : With empirical applications in location problems

Combinatorial optimization problems, are one of the most important types of problems in operational research. Heuristic and metaheuristics algorithms are widely applied to find a good solution. However, a common problem is that these algorithms do not guarantee that the solution will coincide with the optimum and, hence, many solutions to real world OR-problems are afflicted with an uncertainty about the quality of the solution. The main aim of this thesis is to investigate the usability of statistical bounds to evaluate the quality of heuristic solutions applied to large combinatorial problems. The contributions of this thesis are both methodological and empirical. From a methodological point of view, the usefulness of statistical bounds on p-median problems is thoroughly investigated. The statistical bounds have good performance in providing informative quality assessment under appropriate parameter settings. Also, they outperform the commonly used Lagrangian bounds. It is demonstrated that the statistical bounds are shown to be comparable with the deterministic bounds in quadratic assignment problems. As to empirical research, environment pollution has become a worldwide problem, and transportation can cause a great amount of pollution. A new method for calculating and comparing the CO2-emissions of online and brick-and-mortar retailing is proposed. It leads to the conclusion that online retailing has significantly lesser CO2-emissions. Another problem is that the Swedish regional division is under revision and the border effect to public service accessibility is concerned of both residents and politicians. After analysis, it is shown that borders hinder the optimal location of public services and consequently the highest achievable economic and social utility may not be attained.

How does data quality in a network affect heuristic solutions?

To have good data quality with high complexity is often seen to be important. Intuition says that the higher accuracy and complexity the data have the better the analytic solutions becomes if it is possible to handle the increasing computing time. However, for most of the practical computational problems, high complexity data means that computational times become too long or that heuristics used to solve the problem have difficulties to reach good solutions. This is even further stressed when the size of the combinatorial problem increases. Consequently, we often need a simplified data to deal with complex combinatorial problems. In this study we stress the question of how the complexity and accuracy in a network affect the quality of the heuristic solutions for different sizes of the combinatorial problem. We evaluate this question by applying the commonly used p-median model, which is used to find optimal locations in a network of p supply points that serve n demand points. To evaluate this, we vary both the accuracy (the number of nodes) of the network and the size of the combinatorial problem (p). The investigation is conducted by the means of a case study in a region in Sweden with an asymmetrically distributed population (15,000 weighted demand points), Dalecarlia. To locate 5 to 50 supply points we use the national transport administrations official road network (NVDB). The road network consists of 1.5 million nodes. To find the optimal location we start with 500 candidate nodes in the network and increase the number of candidate nodes in steps up to 67,000 (which is aggregated from the 1.5 million nodes). To find the optimal solution we use a simulated annealing algorithm with adaptive tuning of the temperature. The results show that there is a limited improvement in the optimal solutions when the accuracy in the road network increase and the combinatorial problem (low p) is simple. When the combinatorial problem is complex (large p) the improvements of increasing the accuracy in the road network are much larger. The results also show that choice of the best accuracy of the network depends on the complexity of the combinatorial (varying p) problem.

Herbrand's Theorem and Equational Reasoning: Problems and Solutions

The famous Herbrand's theorem of mathematical logic plays an important role in automated theorem proving. In the first part of this article, we recall the theorem and formulate a number of natural decision problems related to it. Somewhat surprisingly, these problems happen to be equivalent. One of these problems is the so-called simultaneous rigid E-unification problem. In the second part, we survey recent result on the simultaneous rigid E-unification problem.

From XML to relational view updates: applying old solutions to solve a new problem

XML has become an important medium for data exchange, and is frequently used as an interface to - i.e. a view of - a relational database. Although lots of work have been done on querying relational databases through XML views, the problem of updating relational databases through XML views has not received much attention. In this work, we give the rst steps towards solving this problem. Using query trees to capture the notions of selection, projection, nesting, grouping, and heterogeneous sets found throughout most XML query languages, we show how XML views expressed using query trees can be mapped to a set of corresponding relational views. Thus, we transform the problem of updating relational databases through XML views into a classical problem of updating relational databases through relational views. We then show how updates on the XML view are mapped to updates on the corresponding relational views. Existing work on updating relational views can then be leveraged to determine whether or not the relational views are updatable with respect to the relational updates, and if so, to translate the updates to the underlying relational database. Since query trees are a formal characterization of view de nition queries, they are not well suited for end-users. We then investigate how a subset of XQuery can be used as a top level language, and show how query trees can be used as an intermediate representation of view de nitions expressed in this subset.

Contractual solutions to the holdup problem: a survey

In this survey, we presented the general idea and main results from what we understand that are the most important contributions to contractual solutions to the holdup problem literature. The aim of this paper is to push the previous analysis, uniform the notation and provide a snapshot on the most recent literature, as well as bring topics for future inquires on this issue.

Graph analysis of verbal fluency test discriminate between patients with Alzheimer’s disease, Mild Cognitive Impairment and normal elderly controls

Verbal fluency is the ability to produce a satisfying sequence of spoken words during a given time interval. The core of verbal fluency lies in the capacity to manage the executive aspects of language. The standard scores of the semantic verbal fluency test are broadly used in the neuropsychological assessment of the elderly, and different analytical methods are likely to extract even more information from the data generated in this test. Graph theory, a mathematical approach to analyze relations between items, represents a promising tool to understand a variety of neuropsychological states. This study reports a graph analysis of data generated by the semantic verbal fluency test by cognitively healthy elderly (NC), patients with Mild Cognitive Impairment – subtypes amnestic(aMCI) and amnestic multiple domain (a+mdMCI) - and patients with Alzheimer’s disease (AD). Sequences of words were represented as a speech graph in which every word corresponded to a node and temporal links between words were represented by directed edges. To characterize the structure of the data we calculated 13 speech graph attributes (SGAs). The individuals were compared when divided in three (NC – MCI – AD) and four (NC – aMCI – a+mdMCI – AD) groups. When the three groups were compared, significant differences were found in the standard measure of correct words produced, and three SGA: diameter, average shortest path, and network density. SGA sorted the elderly groups with good specificity and sensitivity. When the four groups were compared, the groups differed significantly in network density, except between the two MCI subtypes and NC and aMCI. The diameter of the network and the average shortest path were significantly different between the NC and AD, and between aMCI and AD. SGA sorted the elderly in their groups with good specificity and sensitivity, performing better than the standard score of the task. These findings provide support for a new methodological frame to assess the strength of semantic memory through the verbal fluency task, with potential to amplify the predictive power of this test. Graph analysis is likely to become clinically relevant in neurology and psychiatry, and may be particularly useful for the differential diagnosis of the elderly.

Expression of MyoD, myogenin, myostatin and Hsp70 transcripts in chicken embryos submitted to mild cold or heat

The expression of the MyoD, myogenin, myostatin and Hsp70 genes was estimated in chicken embryos submitted to mild cold (36 +/- 0.5degreesC) or heat (44 +/- 0.5degreesC) for 1 h. 2. Marked decreases in MyoD, myogenin and myostatin transcript levels were observed in embryos exposed to high temperature, contrasting to the higher expression of the Hsp70 mRNA detected in heat-stressed embryos. 3. The exposure of chicken embryos to low temperature significantly affected only the abundance of myogenin mRNA. 4. These findings suggest that myogenic proliferation and differentiation events are compromised by variations in environmental temperature during avian embryogenesis. (C) 2003 Elsevier B.V. Ltd. All rights reserved.

Transmissão do Cowpea mild mottle virus pela mosca branca Bemisia tabaci biótipo B para plantas de feijão e soja

A necrose da haste da soja é causada por um vírus do gênero Carlavirus transmitido pela mosca branca Bemisia tabaci, também infectante de feijão e identificado como Cowpea mild mottle virus (CpMMV). Neste trabalho foram realizados testes para determinação do número de moscas-brancas B. tabaci biótipo B necessários para transmissão do vírus em feijoeiro e soja. Na sequência foram realizados dois outros testes, com 10 insetos por planta. Avaliaram-se períodos de acesso à aquisição (PAA) de 'Jalo' para 'Jalo', e o efeito de períodos de acesso à inoculação (PAI). Foram visualmente constatados sintomas típicos do carlavírus como mosaico, clareamento de nervuras, necrose sistêmica e redução de crescimento. Houve transmissão do vírus para 'BT-2' de feijão e 'BRS-132' de soja com apenas um inseto por planta, sendo mais eficaz nesta última espécie. A taxa de transmissão do vírus foi maior com o aumento do número de insetos por planta. E o PAA foi determinado após 15' de tempo para aquisição, e o PAI com 5 min e aumentando os períodos de acesso a aquisição e inoculação aumentou-se a taxa de transmissão.

Migration of diethylhexyl phthalate from PVC bags into intravenous cyclosporine solutions

The migration of diethylhexyl phthalate (DEHP) from PVC bags into LVPS (0.9% NaCl) and LVPS with cyclosporine at concentrations of 2.5 and 0.5 mg/ml was studied. PVC bags were placed in contact with these solutions and stored at 25 1 degrees C. They were taken for analysis each 30 min during 6 h and after this period at each 1 h until 12 h of contact. Water was used as reference, and exposed and analyzed under the same conditions. After contact, the solutions were submitted to extraction with hexane and analyzed by GC-FID. The results showed that DEHP did not migrate into water and LVPS during all the time. Also, no measurable amount of DEHP was detected during the first 3 h of contact between the PVC bag and the diluted cyclosporine solution. However, the amount of released DEHP reached a detectable level after 4 It of contact, increased until 6 h, stabilized, and increased again after 9-10 h. The 12 h of contact showed the highest DEHP levels for both cyclosporine concentrations. The DEHP migrated was 0.02-0.08% of that present in the bag. (c) 2005 Elsevier B.V. All rights reserved.

Raman and photoluminescence of Er3+-doped SnO2 obtained via the sol-gel technique from solutions with distinct pH

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Bounded solutions of fermions in the background of mixed vector-scalar inversely linear potentials

The problem of a fermion subject to a general mixing of vector and scalar potentials in a two-dimensional world is mapped into a Sturm-Liouville problem. Isolated bounded solutions are also searched. For the specific case of an inversely linear potential, which gives rise to an effective Kratzer potential in the Sturm-Liouville problem, exact bounded solutions are found in closed form. The case of a pure scalar potential with their isolated zero-energy solutions, already analyzed in a previous work, is obtained as a particular case. The behavior of the upper and lower components of the Dirac spinor is discussed in detail and some unusual results are revealed. The nonrelativistic limit of our results adds a new support to the conclusion that even-parity solutions to the nonrelativistic one-dimensional hydrogen atom do not exist. (c) 2004 Elsevier B.V. All rights reserved.