Efficient certification of feasibility and objective value of linear programs and its applications

The use of linear programming in various areas has increased with the significant improvement of specialized solvers. Linear programs are used as such to model practical problems, or as subroutines in algorithms such as formal proofs or branch-and-cut frameworks. In many situations a certified answer is needed, for example the guarantee that the linear program is feasible or infeasible, or a provably safe bound on its objective value. Most of the available solvers work with floating-point arithmetic and are thus subject to its shortcomings such as rounding errors or underflow, therefore they can deliver incorrect answers. While adequate for some applications, this is unacceptable for critical applications like flight controlling or nuclear plant management due to the potential catastrophic consequences. We propose a method that gives a certified answer whether a linear program is feasible or infeasible, or returns unknown'. The advantage of our method is that it is reasonably fast and rarely answers unknown'. It works by computing a safe solution that is in some way the best possible in the relative interior of the feasible set. To certify the relative interior, we employ exact arithmetic, whose use is nevertheless limited in general to critical places, allowing us to rnremain computationally efficient. Moreover, when certain conditions are fulfilled, our method is able to deliver a provable bound on the objective value of the linear program. We test our algorithm on typical benchmark sets and obtain higher rates of success compared to previous approaches for this problem, while keeping the running times acceptably small. The computed objective value bounds are in most of the cases very close to the known exact objective values. We prove the usability of the method we developed by additionally employing a variant of it in a different scenario, namely to improve the results of a Satisfiability Modulo Theories solver. Our method is used as a black box in the nodes of a branch-and-bound tree to implement conflict learning based on the certificate of infeasibility for linear programs consisting of subsets of linear constraints. The generated conflict clauses are in general small and give good rnprospects for reducing the search space. Compared to other methods we obtain significant improvements in the running time, especially on the large instances.

The Making of a Shiite Bourgeoisie in Lebanon Political Mobilisation, Economic Resources and Formation of a Social Group

The thesis analyses the making of the Shiite middle- and upper/entrepreneurial-class in Lebanon from the 1960s till the present day. The trajectory explores the historical, political and social (internal and external) factors that brought a sub-proletariat to mobilise and become an entrepreneurial bourgeoisie in the span of less than three generations. This work proposes the main theoretical hypothesis to unpack and reveal the trajectory of a very recent social class that through education, diaspora, political and social mobilisation evolved in a few years into a very peculiar bourgeoisie: whereas Christian-Maronite middle class practically produced political formations and benefited from them and from Maronite’s state supremacy (National Pact, 1943) reinforcing the community’s status quo, Shiites built their own bourgeoisie from within, and mobilised their “cadres” (Boltanski) not just to benefit from their renovated presence at the state level, but to oppose to it. The general Social Movement Theory (SMT), as well as a vast amount of the literature on (middle) class formation are therefore largely contradicted, opening up new territories for discussion on how to build a bourgeoisie without the state’s support (Social Mobilisation Theory, Resource Mobilisation Theory) and if, eventually, the middle class always produces democratic movements (the emergence of a social group out of backwardness and isolation into near dominance of a political order). The middle/upper class described here is at once an economic class related to the control of multiple forms of capital, and produced by local, national, and transnational networks related to flows of services, money, and education, and a culturally constructed social location and identity structured by economic as well as other forms of capital in relation to other groups in Lebanon.

Development of Solid Oxide Fuel Cell Electrodes with High Conductivity and Enhanced Redox Stability

The intent of this study was the development of new ceramic SOFC anode materials which possess electrical conductivity as well as redox stability.

A randomised controlled trial of spinal manipulative therapy in acute low back pain

OBJECTIVE: To determine whether treatment with spinal manipulative therapy (SMT) administered in addition to standard care is associated with clinically relevant early reductions in pain and analgesic consumption. METHODS: 104 patients with acute low back pain were randomly assigned to SMT in addition to standard care (n = 52) or standard care alone (n = 52). Standard care consisted of general advice and paracetamol, diclofenac or dihydrocodeine as required. Other analgesic drugs or non-pharmacological treatments were not allowed. Primary outcomes were pain intensity assessed on the 11-point box scale (BS-11) and analgesic use based on diclofenac equivalence doses during days 1-14. An extended follow-up was performed at 6 months. RESULTS: Pain reductions were similar in experimental and control groups, with the lower limit of the 95% CI excluding a relevant benefit of SMT (difference 0.5 on the BS-11, 95% CI -0.2 to 1.2, p = 0.13). Analgesic consumptions were also similar (difference -18 mg diclofenac equivalents, 95% CI -43 mg to 7 mg, p = 0.17), with small initial differences diminishing over time. There were no differences between groups in any of the secondary outcomes and stratified analyses provided no evidence for potential benefits of SMT in specific patient groups. The extended follow-up showed similar patterns. CONCLUSIONS: SMT is unlikely to result in relevant early pain reduction in patients with acute low back pain.

Multicentric hepatic EBV-associated smooth muscle tumors in an AIDS patient: a case report, investigation of mTOR activation and review of the literature.

Epstein-Barr virus (EBV) - associated smooth muscle tumors (EBV-SMT) are a rare, recently recognized distinct group of mesenchymal tumors that develop exclusively in patients with immunosuppression. It is believed that tumorigenesis is, at least in part, through the activation of the Akt/mammalian target of rapamycin (mTOR) signal pathway. We describe the clinicopathologic and immunohistochemical features of a multifocal hepatic EBV-SMT in a 34-year-old acquired immunodeficiency syndrome (AIDS) patient and investigate the activation status of the mTOR signal pathway in this tumor. In addition, we provide a review of the literature on the clinicopathologic findings of hepatic EBV-SMT in adult AIDS patients, and discuss their biologies and possible therapeutic strategies.

Methane concentration profiles and isotopic composition of sediment cores from the Black Sea

We present high resolution profiles for the methane concentration and the carbon isotope composition of methane from surface sediments and from the sediment-water transition in the Black Sea. At shallow water sites methane migrates from the sediment into the water column, and the magnitude of this upward migrating flux depends on the depth of the sulfate-methane transition (SMT) in the sediment. The isotope data reveal that the sediments at shallow water sites are a source for methane depleted in 13C relative to the isotope composition of methane in the water column. At deep water sites the methane concentration first decreases with depth in the sediment to reach lowest values at the Unit I to Unit II transition. Below this transition the concentration increases again. Numerical modeling of methane concentration and isotope data shows that high methane oxidation rates occur in the surface sediment layer, indicating that the removal of methane in the surface sediments is not related to the anaerobic oxidation of methane coupled to sulfate reduction that occurs a few meters deep in the sediment, at the SMT. Instead, near-surface methane consumption in the euxinic Black Sea sediments appears to be related to lithological stratification. Furthermore, a map of the diffusive methane fluxes in the Black Sea surface sediments indicates that approximately half of the Black Sea seafloor acts as a sink for methane and thus limits the flux of methane to the atmosphere.

Geochemical data and magnetic measurements of IODP Expedition 308, Hole U1319A from the Gulf of Mexico

A 160 m mostly turbiditic late Pleistocene sediment sequence (IODP Expedition 308, Hole U1319A) from the Brazos-Trinity intraslope basin system off Texas was investigated with paleo- and rock magnetic methods. Numerous layers depleted in iron oxides and enriched by the ferrimagnetic iron-sulfide mineral greigite (Fe3S4) were detected by diagnostic magnetic properties. From the distribution of these layers, their stratigraphic context and the present geochemical zonation, we develop two conceptual reaction models of greigite formation in non-steady depositional environments. The "sulfidization model" predicts single or twin greigite layers by incomplete transformation of iron monosulfides with polysulfides around the sulfate methane transition (SMT). The "oxidation model" explains greigite formation by partial oxidation of iron monosulfides near the iron redox boundary during periods of downward shifting oxidation fronts. The stratigraphic record provides evidence that both these greigite formation processes act here at typical depths of about 12-14 mbsf and 3-4 mbsf. Numerous "fossil" greigite layers most likely preserved by rapid upward shifts of the redox zonation denote past SMT and sea floor positions characterized by stagnant hemipelagic sedimentation conditions. Six diagenetic stages from a pristine magnetite-dominated to a fully greigite-dominated magnetic mineralogy were differentiated by combination of various hysteresis and remanence parameters.

Geochemical and rock magnetic investigation of sediment cores of the western South Atlantic

Geochemical and rock magnetic investigations of sediments from three sites on the continental margin off Argentina and Uruguay were carried out to study diagenetic alteration of iron minerals driven by anaerobic oxidation of methane (AOM). The western Argentine Basin represents a suitable sedimentary environment to study nonsteady-state processes because it is characterized by highly dynamic depositional conditions. Mineralogic and bulk solid phase data document that the sediment mainly consists of terrigenous material with high contents of iron minerals. As a typical feature of these deposits, distinct minima in magnetic susceptibility (k) are observed. Pore water data reveal that these minima in susceptibility coincide with the current depth of the sulfate/methane transition (SMT) where HS- is generated by the process of AOM. The released HS- reacts with the abundant iron (oxyhydr)oxides resulting in the precipitation of iron sulfides accompanied by a nearly complete loss of magnetic susceptibility. Modeling of geochemical data suggest that the magnetic record in this area is highly influenced by a drastic change in mean sedimentation rate (SR) which occurred during the Pleistocene/Holocene transition. We assume that the strong decrease in mean SR encountered during this glacial/interglacial transition induced a fixation of the SMT at a specific depth. The stagnation has obviously enhanced diagenetic dissolution of iron (oxyhydr)oxides within a distinct sediment interval. This assumption was further substantiated by numerical modeling in which the mean SR was decreased from 100 cm/kyr during glacial times to 5 cm/kyr in the Holocene and the methane flux from below was fixed to a constant value. To obtain the observed geochemical and magnetic patterns, the SMT must remain at a fixed position for ~9000 yrs. This calculated value closely correlates to the timing of the Pleistocene/Holocene transition. The results of the model show additionally that a constant high mean SR would cause a concave-up profile of pore water sulfate under steady state conditions.

Geochemistry of sediments from the Eastern Cape Basin

Sediment cores retrieved in the Benguela coastal upwelling system off Namibia show very distinct enrichments of solid phase barium at the sulfate/methane transition (SMT). These barium peaks represent diagenetic barite (BaSO4) fronts which form by the reaction of upwardly diffusing barium with interstitial sulfate. Calculated times needed to produce these barium enrichments indicate a formation time of about 14,000 yr. Barium spikes a few meters below the SMT were observed at one of the investigated sites (GeoB 8455). Although this sulfate-depleted zone is undersaturated with respect to barite, the dominant mineral phase of these buried barium enrichments was identified as barite by scanning electron microscopy (SEM). This is the first study which reports the occurrence/preservation of pronounced barite enrichments in sulfate-depleted sediments buried a few meters below the SMT. At site GeoB 8455 high concentrations of dissolved barium in pore water as well as barium in the solid phase were observed. Modeling the measured barium concentrations at site GeoB 8455 applying the numerical model CoTReM reveals that the dissolution rate of barite directly below the SMT is about one order of magnitude higher than at the barium enrichments deeper in the sediment core. This indicates that the dissolution of barite at these deeper buried fronts must be retarded. Thus, the occurrence of the enrichments in solid phase barium at site GeoB 8455 could be explained by decreased dissolution rates of barite due to the changes in the concentration of barite in the sediment, as well as changes in the saturation state of fluids. Furthermore, the alteration of barite into witherite (BaCO3) via the transient phase barium sulfide could lead to the preservation of a former barite front as BaCO3. The calculations and modeling indicate that a relocation of the barite front to a shallower depth occurred between the last glacial maxium (LGM) and the Pleistocene/Holocene transition. We suggest that an upward shift of the SMT occurred at that time, most likely as a result of an increase in the methanogenesis rates due to the burial of high amounts of organic matter below the SMT.

Solid phase analysis of sediment core GeoB9309-1 from the Zambezi (or Mozambique) deep-sea fan

The Zambezi deep-sea fan, the largest of its kind along the east African continental margin, is poorly studied to date, despite its potential to record marine and terrestrial climate signals in the southwest Indian Ocean. Therefore, gravity core GeoB 9309-1, retrieved from 1219 m water depth, was investigated for various geophysical (magnetic susceptibility, porosity, colour reflectance) and geochemical (pore water and sediment geochemistry, Fe and P speciation) properties. Onboard and onshore data documented a sulphate/methane transition (SMT) zone at ~ 450-530 cm sediment depth, where the simultaneous consumption of pore water sulphate and methane liberates hydrogen sulphide and bi-carbonate into the pore space. This leads to characteristic changes in the sediment and pore water chemistry, as the reduction of primary Fe (oxyhydr)oxides, the precipitation of Fe sulphides, and the mobilization of Fe (oxyhydr)oxide-bound P. These chemical processes also lead to a marked decrease in magnetic susceptibility. Below the SMT, we find a reduction of porosity, possibly due to pore space cementation by authigenic minerals. Formation of the observed geochemical, magnetic and mineralogical patterns requires a fixation of the SMT at this distinct sediment depth for a considerable time-which we calculated to be ~ 10 000 years assuming steady-state conditions-following a period of rapid upward migration towards this interval. We postulate that the worldwide sea-level rise at the last glacial/interglacial transition (~ 10 000 years B.P.) most probably caused the fixation of the SMT at its present position, through drastically reduced sediment delivery to the deep-sea fan. In addition, we report an internal redistribution of P occurring around the SMT, closely linked to the (de)coupling of sedimentary Fe and P, and leaving a characteristic pattern in the solid P record. By phosphate re-adsorption onto Fe (oxyhydr)oxides above, and formation of authigenic P minerals (e.g. vivianite) below the SMT, deep-sea fan deposits may potentially act as long-term sinks for P.

Low-temperature experiments of sediment core GeoB6229-6 at the South American continental margin off the Rio de la Plata estuary

With various low-temperature experiments performed on magnetic mineral extracts of marine sedimentary deposits from the Argentine continental slope near the Rio de la Plata estuary, a so far unreported style of partial magnetic self-reversal has been detected. In these sediments the sulphate-methane transition (SMT) zone is situated at depths between 4 and 8 m, where reductive diagenesis severely alters the magnetic mineral assemblage. Throughout the sediment column magnetite and ilmenite are present together with titanomagnetite and titanohematite of varying compositions. In the SMT zone (titano-)magnetite only occurs as inclusions in a siliceous matrix and as intergrowths with lamellar ilmenite and titanium-rich titanohematite, originating from high temperature deuteric oxidation within the volcanic host rocks. These abundant structures were visualized by scanning electron microscopy and analysed by energy dispersive spectroscopy. Warming of field-cooled and zero-field-cooled low-temperature saturation remanence displays magnetic phase transitions of titanium-rich titanohematite below 50 K and the Verwey transition of magnetite. A prominent irreversible decline characterizes zero-field cooling of room temperature saturation remanence. It typically sets out at ~210 K and is most clearly developed in the lower part of the SMT zone, where low-temperature hysteresis measurements identified ~210 K as the blocking temperature range of a titanohematite phase with a Curie temperature of around 240 K. The mechanism responsible for the marked loss of remanence is, therefore, sought in partial magnetic self-reversal by magnetostatic interaction of (titano-)magnetite and titanohematite. When titanohematite becomes ferrimagnetic upon cooling, its spontaneous magnetic moments order antiparallel to the (titano-)magnetite remanence causing an drastic initial decrease of global magnetization. The loss of remanence during subsequent further cooling appears to result from two combined effects (1) magnetic interaction between the two phases by which the (titano-)magnetite domain structure is substantially modified and (2) low-temperature demagnetization of (titano-)magnetite due to decreasing magnetocrystalline anisotropy. The depletion of titanomagnetite and superior preservation of titanohematite is characteristic for strongly reducing sedimentary environments. Typical residuals of magnetic mineral assemblages derived from basaltic volcanics will be intergrowths of titanohematite lamellae with titanomagnetite relics. Low-temperature remanence cycling is, therefore, proposed as a diagnostic method to magnetically characterize such alteration (palaeo-)environments.

Combining statistical and semantic approaches to the translation of ontologies and taxonomies

Ontologies and taxonomies are widely used to organize concepts providing the basis for activities such as indexing, and as background knowledge for NLP tasks. As such, translation of these resources would prove useful to adapt these systems to new languages. However, we show that the nature of these resources is significantly different from the "free-text" paradigm used to train most statistical machine translation systems. In particular, we see significant differences in the linguistic nature of these resources and such resources have rich additional semantics. We demonstrate that as a result of these linguistic differences, standard SMT methods, in particular evaluation metrics, can produce poor performance. We then look to the task of leveraging these semantics for translation, which we approach in three ways: by adapting the translation system to the domain of the resource; by examining if semantics can help to predict the syntactic structure used in translation; and by evaluating if we can use existing translated taxonomies to disambiguate translations. We present some early results from these experiments, which shed light on the degree of success we may have with each approach

Using Cross-Lingual Explicit Semantic Analysis for Improving Ontology Translation

Semantic Web aims to allow machines to make inferences using the explicit conceptualisations contained in ontologies. By pointing to ontologies, Semantic Web-based applications are able to inter-operate and share common information easily. Nevertheless, multilingual semantic applications are still rare, owing to the fact that most online ontologies are monolingual in English. In order to solve this issue, techniques for ontology localisation and translation are needed. However, traditional machine translation is difficult to apply to ontologies, owing to the fact that ontology labels tend to be quite short in length and linguistically different from the free text paradigm. In this paper, we propose an approach to enhance machine translation of ontologies based on exploiting the well-structured concept descriptions contained in the ontology. In particular, our approach leverages the semantics contained in the ontology by using Cross Lingual Explicit Semantic Analysis (CLESA) for context-based disambiguation in phrase-based Statistical Machine Translation (SMT). The presented work is novel in the sense that application of CLESA in SMT has not been performed earlier to the best of our knowledge.