24 resultados para Branch and Bound algorithms
em BORIS: Bern Open Repository and Information System - Berna - Suiça
Resumo:
Currently several thousands of objects are being tracked in the MEO and GEO regions through optical means. The problem faced in this framework is that of Multiple Target Tracking (MTT). In this context both, the correct associations among the observations and the orbits of the objects have to be determined. The complexity of the MTT problem is defined by its dimension S. The number S corresponds to the number of fences involved in the problem. Each fence consists of a set of observations where each observation belongs to a different object. The S ≥ 3 MTT problem is an NP-hard combinatorial optimization problem. There are two general ways to solve this. One way is to seek the optimum solution, this can be achieved by applying a branch-and- bound algorithm. When using these algorithms the problem has to be greatly simplified to keep the computational cost at a reasonable level. Another option is to approximate the solution by using meta-heuristic methods. These methods aim to efficiently explore the different possible combinations so that a reasonable result can be obtained with a reasonable computational effort. To this end several population-based meta-heuristic methods are implemented and tested on simulated optical measurements. With the advent of improved sensors and a heightened interest in the problem of space debris, it is expected that the number of tracked objects will grow by an order of magnitude in the near future. This research aims to provide a method that can treat the correlation and orbit determination problems simultaneously, and is able to efficiently process large data sets with minimal manual intervention.
Resumo:
The variability of results from different automated methods of detection and tracking of extratropical cyclones is assessed in order to identify uncertainties related to the choice of method. Fifteen international teams applied their own algorithms to the same dataset - the period 1989-2009 of interim European Centre for Medium-Range Weather Forecasts (ECMWF) Re-Analysis (ERAInterim) data. This experiment is part of the community project Intercomparison of Mid Latitude Storm Diagnostics (IMILAST; see www.proclim.ch/imilast/index.html). The spread of results for cyclone frequency, intensity, life cycle, and track location is presented to illustrate the impact of using different methods. Globally, methods agree well for geographical distribution in large oceanic regions, interannual variability of cyclone numbers, geographical patterns of strong trends, and distribution shape for many life cycle characteristics. In contrast, the largest disparities exist for the total numbers of cyclones, the detection of weak cyclones, and distribution in some densely populated regions. Consistency between methods is better for strong cyclones than for shallow ones. Two case studies of relatively large, intense cyclones reveal that the identification of the most intense part of the life cycle of these events is robust between methods, but considerable differences exist during the development and the dissolution phases.
Resumo:
This paper deals with scheduling batch (i.e., discontinuous), continuous, and semicontinuous production in process industries (e.g., chemical, pharmaceutical, or metal casting industries) where intermediate storage facilities and renewable resources (processing units and manpower) of limited capacity have to be observed. First, different storage configurations typical of process industries are discussed. Second, a basic scheduling problem covering the three above production modes is presented. Third, (exact and truncated) branch-and-bound methods for the basic scheduling problem and the special case of batch scheduling are proposed and subjected to an experimental performance analysis. The solution approach presented is flexible and in principle simple, and it can (approximately) solve relatively large problem instances with sufficient accuracy.
Resumo:
We study a real-world scheduling problem arising in the context of a rolling ingots production. First we review the production process and discuss peculiarities that have to be observed when scheduling a given set of production orders on the production facilities. We then show how to model this scheduling problem using prescribed time lags between operations, different kinds of resources, and sequence-dependent changeovers. A branch-and-bound solution procedure is presented in the second part. The basic principle is to relax the resource constraints by assuming infinite resource availability. Resulting resource conflicts are then stepwise resolved by introducing precedence relationships among operations competing for the same resources. The algorithm has been implemented as a beam search heuristic enumerating alternative sets of precedence relationships.
Resumo:
Retinal vein occlusion is a leading cause of visual impairment. Experimental models of this condition based on laser photocoagulation of retinal veins have been described and extensively exploited in mammals and larger rodents such as the rat. However, few reports exist on the use of this paradigm in the mouse. The objective of this study was to investigate a model of branch and central retinal vein occlusion in the mouse and characterize in vivo longitudinal retinal morphology alterations using spectral domain optical coherence tomography. Retinal veins were experimentally occluded using laser photocoagulation after intravenous application of Rose Bengal, a photo-activator dye enhancing thrombus formation. Depending on the number of veins occluded, variable amounts of capillary dropout were seen on fluorescein angiography. Vascular endothelial growth factor levels were markedly elevated early and peaked at day one. Retinal thickness measurements with spectral domain optical coherence tomography showed significant swelling (p<0.001) compared to baseline, followed by gradual thinning plateauing two weeks after the experimental intervention (p<0.001). Histological findings at day seven correlated with spectral domain optical coherence tomography imaging. The inner layers were predominantly affected by degeneration with the outer nuclear layer and the photoreceptor outer segments largely preserved. The application of this retinal vein occlusion model in the mouse carries several advantages over its use in other larger species, such as access to a vast range of genetically modified animals. Retinal changes after experimental retinal vein occlusion in this mouse model can be non-invasively quantified by spectral domain optical coherence tomography, and may be used to monitor effects of potential therapeutic interventions.
Resumo:
Background—Pathology studies on fatal cases of very late stent thrombosis have described incomplete neointimal coverage as common substrate, in some cases appearing at side-branch struts. Intravascular ultrasound studies have described the association between incomplete stent apposition (ISA) and stent thrombosis, but the mechanism explaining this association remains unclear. Whether the neointimal coverage of nonapposed side-branch and ISA struts is delayed with respect to well-apposed struts is unknown. Methods and Results—Optical coherence tomography studies from 178 stents implanted in 99 patients from 2 randomized trials were analyzed at 9 to 13 months of follow-up. The sample included 38 sirolimus-eluting, 33 biolimus-eluting, 57 everolimus-eluting, and 50 zotarolimus-eluting stents. Optical coherence tomography coverage of nonapposed side-branch and ISA struts was compared with well-apposed struts of the same stent by statistical pooled analysis with a random-effects model. A total of 34 120 struts were analyzed. The risk ratio of delayed coverage was 9.00 (95% confidence interval, 6.58 to 12.32) for nonapposed side-branch versus well-apposed struts, 9.10 (95% confidence interval, 7.34 to 11.28) for ISA versus well-apposed struts, and 1.73 (95% confidence interval, 1.34 to 2.23) for ISA versus nonapposed side-branch struts. Heterogeneity of the effect was observed in the comparison of ISA versus well-apposed struts (H=1.27; I2=38.40) but not in the other comparisons. Conclusions—Coverage of ISA and nonapposed side-branch struts is delayed with respect to well-apposed struts in drug-eluting stents, as assessed by optical coherence tomography.
Resumo:
We present new algorithms for M-estimators of multivariate scatter and location and for symmetrized M-estimators of multivariate scatter. The new algorithms are considerably faster than currently used fixed-point and related algorithms. The main idea is to utilize a second order Taylor expansion of the target functional and to devise a partial Newton-Raphson procedure. In connection with symmetrized M-estimators we work with incomplete U-statistics to accelerate our procedures initially.
Resumo:
The role of gap junction channels on cardiac impulse propagation is complex. This review focuses on the differential expression of connexins in the heart and the biophysical properties of gap junction channels under normal and disease conditions. Structural determinants of impulse propagation have been gained from biochemical and immunocytochemical studies performed on tissue extracts and intact cardiac tissue. These have defined the distinctive connexin coexpression patterns and relative levels in different cardiac tissues. Functional determinants of impulse propagation have emerged from electrophysiological experiments carried out on cell pairs. The static properties (channel number and conductance) limit the current flow between adjacent cardiomyocytes and thus set the basic conduction velocity. The dynamic properties (voltage-sensitive gating and kinetics of channels) are responsible for a modulation of the conduction velocity during propagated action potentials. The effect is moderate and depends on the type of Cx and channel. For homomeric-homotypic channels, the influence is small to medium; for homomeric-heterotypic channels, it is medium to strong. Since no data are currently available on heteromeric channels, their influence on impulse propagation is speculative. The modulation by gap junction channels is most prominent in tissues at the boundaries between cardiac tissues such as sinoatrial node-atrial muscle, atrioventricular node-His bundle, His bundle-bundle branch and Purkinje fibers-ventricular muscle. The data predict facilitation of orthodromic propagation.
Resumo:
Terminal sialic acid residues on surface-associated glycoconjugates mediate host cell interactions of many pathogens. Addition of sialic acid-rich fetuin enhanced, and the presence of the sialidiase inhibitor 2-deoxy-2,3-dehydro-N-acetylneuraminic acid reduced, the physical interaction of Neospora caninum tachyzoites and bradyzoites with Vero cell monolayers. Thus, Neospora extracts were subjected to fetuin-agarose affinity chromatography in order to isolate components potentially interacting with sialic acid residues. SDS-PAGE and silver staining of the fetuin binding fraction revealed the presence of a single protein band of approximately 65 kDa, subsequently named NcFBP (Neospora caninum fetuin-binding protein), which was localized at the apical tip of the tachyzoites and was continuously released into the surrounding medium in a temperature-independent manner. NcFBP readily interacted with Vero cells and bound to chondroitin sulfate A and C, and anti-NcFBP antibodies interfered in tachyzoite adhesion to host cell monolayers. In additon, analysis of the fetuin binding fraction by gelatin substrate zymography was performed, and demonstrated the presence of two bands of 96 and 140 kDa exhibiting metalloprotease-activity. The metalloprotease activity readily degraded glycosylated proteins such as fetuin and bovine immunoglobulin G heavy chain, whereas non-glycosylated proteins such as bovine serum albumin and immunoglobulin G light chain were not affected. These findings suggest that the fetuin-binding fraction of Neospora caninum tachyzoites contains components that could be potentially involved in host-parasite interactions.
Resumo:
The development of susceptibility maps for debris flows is of primary importance due to population pressure in hazardous zones. However, hazard assessment by process-based modelling at a regional scale is difficult due to the complex nature of the phenomenon, the variability of local controlling factors, and the uncertainty in modelling parameters. A regional assessment must consider a simplified approach that is not highly parameter dependant and that can provide zonation with minimum data requirements. A distributed empirical model has thus been developed for regional susceptibility assessments using essentially a digital elevation model (DEM). The model is called Flow-R for Flow path assessment of gravitational hazards at a Regional scale (available free of charge under http://www.flow-r.org) and has been successfully applied to different case studies in various countries with variable data quality. It provides a substantial basis for a preliminary susceptibility assessment at a regional scale. The model was also found relevant to assess other natural hazards such as rockfall, snow avalanches and floods. The model allows for automatic source area delineation, given user criteria, and for the assessment of the propagation extent based on various spreading algorithms and simple frictional laws. We developed a new spreading algorithm, an improved version of Holmgren's direction algorithm, that is less sensitive to small variations of the DEM and that is avoiding over-channelization, and so produces more realistic extents. The choices of the datasets and the algorithms are open to the user, which makes it compliant for various applications and dataset availability. Amongst the possible datasets, the DEM is the only one that is really needed for both the source area delineation and the propagation assessment; its quality is of major importance for the results accuracy. We consider a 10 m DEM resolution as a good compromise between processing time and quality of results. However, valuable results have still been obtained on the basis of lower quality DEMs with 25 m resolution.
Resumo:
A social Semantic Web empowers its users to have access to collective Web knowledge in a simple manner, and for that reason, controlling online privacy and reputation becomes increasingly important, and must be taken seriously. This chapter presents Fuzzy Cognitive Maps (FCM) as a vehicle for Web knowledge aggregation, representation, and reasoning. With this in mind, a conceptual framework for Web knowledge aggregation, representation, and reasoning is introduced along with a use case, in which the importance of investigative searching for online privacy and reputation is highlighted. Thereby it is demonstrated how a user can establish a positive online presence.
Resumo:
BPAG1a and BPAG1b (BPAG1a/b) constitute two major isoforms encoded by the dystonin (Dst) gene and show homology with MACF1a and MACF1b. These proteins are members of the plakin family, giant multi-modular proteins able to connect the intermediate filament, microtubule and microfilament cytoskeletal networks with each other and to distinct cell membrane sites. They also serve as scaffolds for signaling proteins that modulate cytoskeletal dynamics. To gain better insights into the functions of BPAG1a/b, we further characterized their C-terminal region important for their interaction with microtubules and assessed the role of these isoforms in the cytoskeletal organization of C2.7 myoblast cells. Our results show that alternative splicing does not only occur at the 5' end of Dst and Macf1 pre-mRNAs, as previously reported, but also at their 3' end, resulting in expression of additional four mRNA variants of BPAG1 and MACF1. These isoform-specific C-tails were able to bundle microtubules and bound to both EB1 and EB3, two microtubule plus end proteins. In the C2.7 cell line, knockdown of BPAG1a/b had no major effect on the organization of the microtubule and microfilament networks, but negatively affected endocytosis and maintenance of the Golgi apparatus structure, which became dispersed. Finally, knockdown of BPAG1a/b caused a specific decrease in the directness of cell migration, but did not impair initial cell adhesion. These data provide novel insights into the complexity of alternative splicing of Dst pre-mRNAs and into the role of BPAG1a/b in vesicular transport, Golgi apparatus structure as well as in migration in C2.7 myoblasts.
Resumo:
Plectin, a cytolinker of the plakin family, anchors the intermediate filament (IF) network formed by keratins 5 and 14 (K5/K14) to hemidesmosomes, junctional adhesion complexes in basal keratinocytes. Genetic alterations of these proteins cause epidermolysis bullosa simplex (EBS) characterized by disturbed cytoarchitecture and cell fragility. The mechanisms through which mutations located after the documented plectin IF-binding site, composed of the plakin-repeat domain (PRD) B5 and the linker, as well as mutations in K5 or K14, lead to EBS remain unclear. We investigated the interaction of plectin C terminus, encompassing four domains, the PRD B5, the linker, the PRD C, and the C extremity, with K5/K14 using different approaches, including a rapid and sensitive fluorescent protein-binding assay, based on enhanced green fluorescent protein-tagged proteins (FluoBACE). Our results demonstrate that all four plectin C-terminal domains contribute to its association with K5/K14 and act synergistically to ensure efficient IF binding. The plectin C terminus predominantly interacted with the K5/K14 coil 1 domain and bound more extensively to K5/K14 filaments compared with monomeric keratins or IF assembly intermediates. These findings indicate a multimodular association of plectin with K5/K14 filaments and give insights into the molecular basis of EBS associated with pathogenic mutations in plectin, K5, or K14 genes.Journal of Investigative Dermatology advance online publication, 10 July 2014; doi:10.1038/jid.2014.255.
Resumo:
Increasing antibiotic resistance among uropathogenic Escherichia coli (UPEC) is driving interest in therapeutic targeting of nonconserved virulence factor (VF) genes. The ability to formulate efficacious combinations of antivirulence agents requires an improved understanding of how UPEC deploy these genes. To identify clinically relevant VF combinations, we applied contemporary network analysis and biclustering algorithms to VF profiles from a large, previously characterized inpatient clinical cohort. These mathematical approaches identified four stereotypical VF combinations with distinctive relationships to antibiotic resistance and patient sex that are independent of traditional phylogenetic grouping. Targeting resistance- or sex-associated VFs based upon these contemporary mathematical approaches may facilitate individualized anti-infective therapies and identify synergistic VF combinations in bacterial pathogens.