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.

Analyse von Middleware-Technologien bzgl. Performanz und ihrer Eignung für lose und eng gekoppelte verteilte Anwendungen

Die vorliegende Dissertation analysiert die Middleware- Technologien CORBA (Common Object Request Broker Architecture), COM/DCOM (Component Object Model/Distributed Component Object Model), J2EE (Java-2-Enterprise Edition) und Web Services (inklusive .NET) auf ihre Eignung bzgl. eng und lose gekoppelten verteilten Anwendungen. Zusätzlich werden primär für CORBA die dynamischen CORBA-Komponenten DII (Dynamic Invocation Interface), IFR (Interface Repository) und die generischen Datentypen Any und DynAny (dynamisches Any) im Detail untersucht. Ziel ist es, a. konkrete Aussagen über diese Komponenten zu erzielen, und festzustellen, in welchem Umfeld diese generischen Ansätze ihre Berechtigung finden. b. das zeitliche Verhalten der dynamischen Komponenten bzgl. der Informationsgewinnung über die unbekannten Objekte zu analysieren. c. das zeitliche Verhalten der dynamischen Komponenten bzgl. ihrer Kommunikation zu messen. d. das zeitliche Verhalten bzgl. der Erzeugung von generischen Datentypen und das Einstellen von Daten zu messen und zu analysieren. e. das zeitliche Verhalten bzgl. des Erstellens von unbekannten, d. h. nicht in IDL beschriebenen Datentypen zur Laufzeit zu messen und zu analysieren. f. die Vorzüge/Nachteile der dynamischen Komponenten aufzuzeigen, ihre Einsatzgebiete zu definieren und mit anderen Technologien wie COM/DCOM, J2EE und den Web Services bzgl. ihrer Möglichkeiten zu vergleichen. g. Aussagen bzgl. enger und loser Koppelung zu tätigen. CORBA wird als standardisierte und vollständige Verteilungsplattform ausgewählt, um die o. a. Problemstellungen zu untersuchen. Bzgl. seines dynamischen Verhaltens, das zum Zeitpunkt dieser Ausarbeitung noch nicht oder nur unzureichend untersucht wurde, sind CORBA und die Web Services richtungsweisend bzgl. a. Arbeiten mit unbekannten Objekten. Dies kann durchaus Implikationen bzgl. der Entwicklung intelligenter Softwareagenten haben. b. der Integration von Legacy-Applikationen. c. der Möglichkeiten im Zusammenhang mit B2B (Business-to-Business). Diese Problemstellungen beinhalten auch allgemeine Fragen zum Marshalling/Unmarshalling von Daten und welche Aufwände hierfür notwendig sind, ebenso wie allgemeine Aussagen bzgl. der Echtzeitfähigkeit von CORBA-basierten, verteilten Anwendungen. Die Ergebnisse werden anschließend auf andere Technologien wie COM/DCOM, J2EE und den Web Services, soweit es zulässig ist, übertragen. Die Vergleiche CORBA mit DCOM, CORBA mit J2EE und CORBA mit Web Services zeigen im Detail die Eignung dieser Technologien bzgl. loser und enger Koppelung. Desweiteren werden aus den erzielten Resultaten allgemeine Konzepte bzgl. der Architektur und der Optimierung der Kommunikation abgeleitet. Diese Empfehlungen gelten uneingeschränkt für alle untersuchten Technologien im Zusammenhang mit verteilter Verarbeitung.

Sustainable development in Darjeeling Hills, India : ecological and socio-economic aspects for small-scale farmers with supportive observations from Kanagawa, Japan

Organic farming means a holistic application of agricultural land-use, hence, this study aimed to assess ecological and socio-economic aspects that show benefits of the strategy and achievements of organic farming in comparison to conventional farming in Darjeeling District, State of West Bengal, India and Kanagawa Prefecture/Kanto in Central Japan. The objective of this study has been empirically analysed on aspects of crop diversity, yield, income and sales prices in the two study regions, where 50 households each, i.e. in total 100 households were interviewed at farm-level. Therefore, the small sample size does not necessarily reflect the broad-scale of the use and benefit of organic farming in both regions. The problems faced in mountainous regions in terms of agriculture and livelihoods for small-scale farmers, which are most affected and dependant on their immediate environment, such as low yields, income and illegal felling leading to soil erosion and landslides, are analyzed. Furthermore, factors such as climate, soils, vegetation and relief equally play an important role for these farmers, in terms of land-use. To supplement and improve the income of farmers, local NGOs have introduced organic farming and high value organic cash crops such as ginger, tea, orange and cardamom and small income generating means (floriculture, apiary etc.). For non-certified and certified organic products the volume is given for India, while for Japan only certified organic production figures are given, as there are several definitions for organic in Japan. Hence, prior to the implementation of organic laws and standards, even reduced chemical input was sold as non-certified organic. Furthermore, the distribution and certification system of both countries are explained in detail, including interviews with distribution companies and cooperatives. Supportive observations from Kanagawa Prefecture and the Kanto region are helpful and practical suggestions for organic farmers in Darjeeling District. Most of these are simple and applicable soil management measures, natural insect repelling applications and describe the direct marketing system practiced in Japan. The former two include compost, intercropping, Effective Microorganisms (EM), clover, rice husk charcoal and wood vinegar. More supportive observations have been made at organic and biodynamic tea estates in Darjeeling District, which use citronella, neem, marigold, leguminous and soil binding plants for soil management and natural insect control. Due to the close ties between farmers and consumers in Japan, certification is often neither necessary nor wanted by the producers. They have built a confidence relationship with their customers; thus, such measures are simply not required. Another option is group certification, instead of the expensive individual certification. The former aims at lower costs for farmers who have formed a cooperative or a farmers' group. Consumer awareness for organic goods is another crucial aspect to help improve the situation of organic farmers. Awareness is slightly more advanced in Kanto than in Darjeeling District, as it is improved due to the close (sales) ties between farmers and consumers in Kanto. Interviews conducted with several such cooperatives and companies underline the positive system of TEIKEI. The introduction of organic farming in the study regions has shown positive effects for those involved, even though it still in its beginning stages in Darjeeling District. This study was only partly able to assess the benefits of organic agriculture at its present level for Darjeeling District, while more positively for the organic farmers of Kanto. The organic farming practice needs further improvement, encouragement and monitoring for the Darjeeling District farmers by locals, consumers, NGOs and politicians. The supportive observations from Kanagawa Prefecture and the Kanto region are a small step in this direction, showing how, simple soil improvements and thus, yield and income increases, as well as direct sales options can enhance the livelihood of organic farmers without destroying their environment and natural resources.