Provably Good Task Assignment for Two-Type Heterogeneous Multiprocessors Using Cutting Planes

Consider scheduling of real-time tasks on a multiprocessor where migration is forbidden. Specifically, consider the problem of determining a task-to-processor assignment for a given collection of implicit-deadline sporadic tasks upon a multiprocessor platform in which there are two distinct types of processors. For this problem, we propose a new algorithm, LPC (task assignment based on solving a Linear Program with Cutting planes). The algorithm offers the following guarantee: for a given task set and a platform, if there exists a feasible task-to-processor assignment, then LPC succeeds in finding such a feasible task-to-processor assignment as well but on a platform in which each processor is 1.5 × faster and has three additional processors. For systems with a large number of processors, LPC has a better approximation ratio than state-of-the-art algorithms. To the best of our knowledge, this is the first work that develops a provably good real-time task assignment algorithm using cutting planes.

Deterministic approach for multiple-source tsunami hazard assessment for Sines, Portugal

In this paper, we present a deterministic approach to tsunami hazard assessment for the city and harbour of Sines, Portugal, one of the test sites of project ASTARTE (Assessment, STrategy And Risk Reduction for Tsunamis in Europe). Sines has one of the most important deep-water ports, which has oil-bearing, petrochemical, liquid-bulk, coal, and container terminals. The port and its industrial infrastructures face the ocean southwest towards the main seismogenic sources. This work considers two different seismic zones: the Southwest Iberian Margin and the Gloria Fault. Within these two regions, we selected a total of six scenarios to assess the tsunami impact at the test site. The tsunami simulations are computed using NSWING, a Non-linear Shallow Water model wIth Nested Grids. In this study, the static effect of tides is analysed for three different tidal stages: MLLW (mean lower low water), MSL (mean sea level), and MHHW (mean higher high water). For each scenario, the tsunami hazard is described by maximum values of wave height, flow depth, drawback, maximum inundation area and run-up. Synthetic waveforms are computed at virtual tide gauges at specific locations outside and inside the harbour. The final results describe the impact at the Sines test site considering the single scenarios at mean sea level, the aggregate scenario, and the influence of the tide on the aggregate scenario. The results confirm the composite source of Horseshoe and Marques de Pombal faults as the worst-case scenario, with wave heights of over 10 m, which reach the coast approximately 22 min after the rupture. It dominates the aggregate scenario by about 60 % of the impact area at the test site, considering maximum wave height and maximum flow depth. The HSMPF scenario inundates a total area of 3.5 km2. © Author(s) 2015.

GPU implementation of the simplex identification via split augmented Lagrangian

Hyperspectral imaging can be used for object detection and for discriminating between different objects based on their spectral characteristics. One of the main problems of hyperspectral data analysis is the presence of mixed pixels, due to the low spatial resolution of such images. This means that several spectrally pure signatures (endmembers) are combined into the same mixed pixel. Linear spectral unmixing follows an unsupervised approach which aims at inferring pure spectral signatures and their material fractions at each pixel of the scene. The huge data volumes acquired by such sensors put stringent requirements on processing and unmixing methods. This paper proposes an efficient implementation of a unsupervised linear unmixing method on GPUs using CUDA. The method finds the smallest simplex by solving a sequence of nonsmooth convex subproblems using variable splitting to obtain a constraint formulation, and then applying an augmented Lagrangian technique. The parallel implementation of SISAL presented in this work exploits the GPU architecture at low level, using shared memory and coalesced accesses to memory. The results herein presented indicate that the GPU implementation can significantly accelerate the method's execution over big datasets while maintaining the methods accuracy.

Despacho Económico de um SEE com coordenação Hidrotérmica Departamento de Engenharia Electrotécnica

O Despacho económico de um sistema eléctrico de energia com a coordenação hidrotérmica tem como objectivo alcançar a operação óptima do sistema em um determinado período de tempo, ao menor custo possível, e com alto grau de fiabilidade. O problema é muito complexo, pois depende do grau de dificuldade em se prever os caudais dos afluentes, e da capacidade das albufeiras das centrais hídricas. De um modo geral, a produção térmica é determinada de modo a proporcionar o uso mais racional possível da água, dentro do contexto de incertezas quanto às afluências futuras, de modo a, por um lado manter o sistemas o mais económico possível, e por outro, evitar o desperdício energético implícito em descarregamentos de volumes de água turbináveis. Neste trabalho é proposta uma metodologia baseada em programação linear para a solução da coordenação hidrotérmica de curto prazo, e que permite obter custos-sombra de água em centrais hídricas com armazenamento. Esta metodologia foi posteriormente implementado num programa computacional em Microsoft Excel 2010 para a solução numa primeira fase, da rede de 24 barramentos do IEEE, e numa segunda fase, para a solução da Rede Nacional de Transporte referente ao ano de 2010. Para efeitos de análise e validação de dados, os dados provenientes do programa, são depois comparados aos dados dos relatórios da REN. Por último, os dados provenientes do programa em Excel são colocados e analisados no programa PowerWorld Simulator 8.0.

The influence of menopausal status on bone turnover and disease control in breast cancer patients with metastatic bone disease treated with chemotherapy plus zoledronic acid : an exploratory retrospective cohort study

RESUMO: Introdução: Uma meta-análise recente demonstrou que uso adjuvante de ácido zoledrónico (AZ) em mulheres pós-menopáusicas com cancro da mama precoce (CM) conduz a redução do risco de morte por CM em 17%. Investigámos o efeito do estado hormonal (pré [PrM] vs pós-menopausa tardia [PoM]) na remodelação óssea e controlo de doença em mulheres com CM e metástases ósseas (MO) tratadas com AZ e quimioterapia (QT). Métodos: Neste estudo de coorte retrospetivo, colhemos variáveis clinico-patológicas e quantificámos o telopéptido N-terminal (NTX) urinário e marcadores tumorais (MT) séricos em mulheres com CM e MO tratadas com QT e AZ. As doentes foram divididas em PrM (<45 anos) e PoM (>60 anos). Endpoints do estudo: variação do NTX, CA15.3 e CEA nos meses 3, 6 e 9, tempo até falência de QT de primeira-linha e sobrevivência. Quando apropriado foram usados os testes de Wilcoxon rank-sum, modelo de efeitos lineares mistos, teste log-rank e modelo de Cox. Resultados: Quarenta doentes foram elegíveis para análise (8 PrM e 32 PoM). Depois da introdução de AZ e QT, os níveis de NTX e MT caíram no coorte global. O perfil de resposta não diferiu entre grupos no mês 3 ou em tempos posteriores (valor-p para interação tempo-estado hormonal no mês 3=0.957). Ademais, o perfil de resposta dos MT também não diferiu entre grupos. O tempo mediano até falência de primeira-linha de QT em PrM e PoM foi de 15.2 e 17.4 meses, respetivamente. Não foi identificada diferença significativa entre grupos, quer em análise univariada quer após controlo para envolvimento visceral (p=0.399 e 0.469, respetivamente). Igualmente, não houve diferenças em termos de sobrevivência. Conclusões: Neste coorte, não foram identificadas diferenças no controlo de NTX ou MT em função do estado menopausico. Igualmente, não foi identificada diferença no tempo até falência de primeira-linha de CT ou sobrevivência.----------- ABSTRACT: Background: A recent meta-analysis showed that the adjuvant use of zoledronic acid (ZA) in postmenopausal women with early breast cancer (BC) leads to a reduction in the risk of breast cancer death by 17%. We investigated the effect of the hormonal status (pre [PrM] vs late post menopause [PoM]) on bone turnover and disease control among women with BC and boné metastases (BM) treated with ZA and chemotherapy (CT). Methods: In this retrospective cohort study, we collected clinicopathologic variables, urinary Nterminal telopeptide (NTX) and serum tumor marker levels from women with BC and BM treated with CT and ZA. Patients were divided in PrM (<45 years) and PoM (>60 years). Study endpoints were NTX, CA15.3 and CEA variation at 3, 6 and 9 months, and time to first-line CT failure and survival. We performed multilevel mixed-effects linear regression models to assess the variation of repeated measures and cox regression models for time to event outcomes. Results: Forty patients were eligible for analysis (8 PrM and 32 PoM). After introduction of ZA and CT, NTX and tumor markers declined in the overall cohort. Response profile was similar between menopausal groups at month 3 and at later time points (p-value for time-hormonal status interaction at month 3=0.957). Furthermore, tumor markers response profile was also equal between groups. Median time to first-line CT failure in PrM and PoM women was 15.2 and 17.4 months, respectively. No significant difference between groups was found, either using a univariate analysis or after controlling for visceral disease involvement (p=0.399 and 0.469, respectively). Likewise, no differences in survival were found. Conclusions: In this cohort, no differences were found in terms of NTX or tumor markers control according to menopausal status. Similarly, no difference in time to first-line CT failure or survival was found.

An evolutionary multi-objective optimization system for earthworks

Earthworks involve the levelling or shaping of a target area through the moving or processing of the ground surface. Most construction projects require earthworks, which are heavily dependent on mechanical equipment (e.g., excavators, trucks and compactors). Often, earthworks are the most costly and time-consuming component of infrastructure constructions (e.g., road, railway and airports) and current pressure for higher productivity and safety highlights the need to optimize earthworks, which is a nontrivial task. Most previous attempts at tackling this problem focus on single-objective optimization of partial processes or aspects of earthworks, overlooking the advantages of a multi-objective and global optimization. This work describes a novel optimization system based on an evolutionary multi-objective approach, capable of globally optimizing several objectives simultaneously and dynamically. The proposed system views an earthwork construction as a production line, where the goal is to optimize resources under two crucial criteria (costs and duration) and focus the evolutionary search (non-dominated sorting genetic algorithm-II) on compaction allocation, using linear programming to distribute the remaining equipment (e.g., excavators). Several experiments were held using real-world data from a Portuguese construction site, showing that the proposed system is quite competitive when compared with current manual earthwork equipment allocation.

Development of an intelligent earthwork optimization system

Tese de Doutoramento em Engenharia Civil.

Verfahren zur direkten Implementierung von Algorithmen auf Gatterebene

Bit serial, processing, digital signal processing, transmission, time division, linear programming, linear optimization

General equilibrium with asymmetric information: a dual approach

We study markets where the characteristics or decisions of certain agents are relevant but not known to their trading partners. Assuming exclusive transactions, the environment is described as a continuum economy with indivisible commodities. We characterize incentive efficient allocations as solutions to linear programming problems and appeal to duality theory to demonstrate the generic existence of external effects in these markets. Because under certain conditions such effects may generate non-convexities, randomization emerges as a theoretic possibility. In characterizing market equilibria we show that, consistently with the personalized nature of transactions, prices are generally non-linear in the underlying consumption. On the other hand, external effects may have critical implications for market efficiency. With adverse selection, in fact, cross-subsidization across agents with different private information may be necessary for optimality, and so, the market need not even achieve an incentive efficient allocation. In contrast, for the case of a single commodity, we find that when informational asymmetries arise after the trading period (e.g. moral hazard; ex post hidden types) external effects are fully internalized at a market equilibrium.

A dual characterization of incentive efficiency

We show that incentive efficient allocations in economies with adverse selection and moral hazard can be determined as optimal solutions to a linear programming problem and we use duality theory to obtain a complete characterization of the optima. Our dual analysis identifies welfare effects associated with the incentives of the agents to truthfully reveal their private information. Because these welfare effects may generate non-convexities, incentive efficient allocations may involve randomization. Other properties of incentive efficient allocations are also derived.

Which prior knowledge? Quantification of in vivo brain 13C MR spectra following 13C glucose infusion using AMARES.

The recent developments in high magnetic field 13C magnetic resonance spectroscopy with improved localization and shimming techniques have led to important gains in sensitivity and spectral resolution of 13C in vivo spectra in the rodent brain, enabling the separation of several 13C isotopomers of glutamate and glutamine. In this context, the assumptions used in spectral quantification might have a significant impact on the determination of the 13C concentrations and the related metabolic fluxes. In this study, the time domain spectral quantification algorithm AMARES (advanced method for accurate, robust and efficient spectral fitting) was applied to 13 C magnetic resonance spectroscopy spectra acquired in the rat brain at 9.4 T, following infusion of [1,6-(13)C2 ] glucose. Using both Monte Carlo simulations and in vivo data, the goal of this work was: (1) to validate the quantification of in vivo 13C isotopomers using AMARES; (2) to assess the impact of the prior knowledge on the quantification of in vivo 13C isotopomers using AMARES; (3) to compare AMARES and LCModel (linear combination of model spectra) for the quantification of in vivo 13C spectra. AMARES led to accurate and reliable 13C spectral quantification similar to those obtained using LCModel, when the frequency shifts, J-coupling constants and phase patterns of the different 13C isotopomers were included as prior knowledge in the analysis.

Devolution dynamics of Spanish local government

Over the last few years, ther has been a devolutionary tendency in many developed and developing countries. In this article we propose a methodology to decompose whether the benefits in terms of effciency derived from transfers of powers from higher to municipal levels of government "the "economic dividend" of devolution) might increase over time. This methodology is based on linear programming approaches for effciency measurement. We provide anapplication to Spanish municipalities, which have had to adapt to both the European Stability and Growth Pact as well as to domestic regulation seeking local governments balanced budget. Results indicate that efficiency gains from enhaced decentralization have increased over time. However, the way through which these gains accrue differs across municipalities -in some cases technical change is the main component, whereas in others catching up dominates.

The Multiple-partners assignment game with heterogeneous sales and multi-unit demands: competitive equilibria

A multiple-partners assignment game with heterogeneous sales and multiunit demands consists of a set of sellers that own a given number of indivisible units of (potentially many different) goods and a set of buyers who value those units and want to buy at most an exogenously fixed number of units. We define a competitive equilibrium for this generalized assignment game and prove its existence by using only linear programming. In particular, we show how to compute equilibrium price vectors from the solutions of the dual linear program associated to the primal linear program defined to find optimal assignments. Using only linear programming tools, we also show (i) that the set of competitive equilibria (pairs of price vectors and assignments) has a Cartesian product structure: each equilibrium price vector is part of a competitive equilibrium with all optimal assignments, and vice versa; (ii) that the set of (restricted) equilibrium price vectors has a natural lattice structure; and (iii) how this structure is translated into the set of agents' utilities that are attainable at equilibrium.

Quality of life depends on the drinking pattern in alcohol-dependent patients.

AIMS: In patients with alcohol dependence, health-related quality of life (QOL) is reduced compared with that of a normal healthy population. The objective of the current analysis was to describe the evolution of health-related QOL in adults with alcohol dependence during a 24-month period after initial assessment for alcohol-related treatment in a routine practice setting, and its relation to drinking pattern which was evaluated across clusters based on the predominant pattern of alcohol use, set against the influence of baseline variables METHODS: The Medical Outcomes Study 36-Item Short-Form Survey (MOS-SF-36) was used to measure QOL at baseline and quarterly for 2 years among participants in CONTROL, a prospective observational study of patients initiating treatment for alcohol dependence. The sample consisted of 160 adults with alcohol dependence (65.6% males) with a mean (SD) age of 45.6 (12.0) years. Alcohol use data were collected using TimeLine Follow-Back. Based on the participant's reported alcohol use, three clusters were identified: 52 (32.5%) mostly abstainers, 64 (40.0%) mostly moderate drinkers and 44 (27.5%) mostly heavy drinkers. Mixed-effect linear regression analysis was used to identify factors that were potentially associated with the mental and physical summary MOS-SF-36 scores at each time point. RESULTS: The mean (SD) MOS-SF-36 mental component summary score (range 0-100, norm 50) was 35.7 (13.6) at baseline [mostly abstainers: 40.4 (14.6); mostly moderate drinkers 35.6 (12.4); mostly heavy drinkers 30.1 (12.1)]. The score improved to 43.1 (13.4) at 3 months [mostly abstainers: 47.4 (12.3); mostly moderate drinkers 44.2 (12.7); mostly heavy drinkers 35.1 (12.9)], to 47.3 (11.4) at 12 months [mostly abstainers: 51.7 (9.7); mostly moderate drinkers 44.8 (11.9); mostly heavy drinkers 44.1 (11.3)], and to 46.6 (11.1) at 24 months [mostly abstainers: 49.2 (11.6); mostly moderate drinkers 45.7 (11.9); mostly heavy drinkers 43.7 (8.8)]. Mixed-effect linear regression multivariate analyses indicated that there was a significant association between a lower 2-year follow-up MOS-SF-36 mental score and being a mostly heavy drinker (-6.97, P < 0.001) or mostly moderate drinker (-3.34 points, P = 0.018) [compared to mostly abstainers], being female (-3.73, P = 0.004), and having a Beck Inventory scale score ≥8 (-6.54, P < 0.001), at baseline. The mean (SD) MOS-SF-36 physical component summary score was 48.8 (10.6) at baseline, remained stable over the follow-up and did not differ across the three clusters. Mixed-effect linear regression univariate analyses found that the average 2-year follow-up MOS-SF-36 physical score was increased (compared with mostly abstainers) in mostly heavy drinkers (+4.44, P = 0.007); no other variables tested influenced the MOS-SF-36 physical score. CONCLUSION: Among individuals with alcohol dependence, a rapid improvement was seen in the mental dimension of QOL following treatment initiation, which was maintained during 24 months. Improvement was associated with the pattern of alcohol use, becoming close to the general population norm in patients classified as mostly abstainers, improving substantially in mostly moderate drinkers and improving only slightly in mostly heavy drinkers. The physical dimension of QOL was generally in the normal range but was not associated with drinking patterns.

Assessing the Relationship between the Baseline Value of a Continuous Variable and Subsequent Change over Time

Analyzing the relationship between the baseline value and subsequent change of a continuous variable is a frequent matter of inquiry in cohort studies. These analyses are surprisingly complex, particularly if only two waves of data are available. It is unclear for non-biostatisticians where the complexity of this analysis lies and which statistical method is adequate.With the help of simulated longitudinal data of body mass index in children,we review statistical methods for the analysis of the association between the baseline value and subsequent change, assuming linear growth with time. Key issues in such analyses are mathematical coupling, measurement error, variability of change between individuals, and regression to the mean. Ideally, it is better to rely on multiple repeated measurements at different times and a linear random effects model is a standard approach if more than two waves of data are available. If only two waves of data are available, our simulations show that Blomqvist's method - which consists in adjusting for measurement error variance the estimated regression coefficient of observed change on baseline value - provides accurate estimates. The adequacy of the methods to assess the relationship between the baseline value and subsequent change depends on the number of data waves, the availability of information on measurement error, and the variability of change between individuals.