Search

Although optimization is the longstanding algorithmic backbone of machine learning, new models still require the time-consuming implementation of new solvers. As a result, there are thousands of implementations of optimization algorithms for machine learning problems. A natural question is, if it is always necessary to implement a new solver, or if there is one algorithm that is sufficient for most models. Common belief suggests that such a one-algorithm-fits-all approach cannot work, because this algorithm cannot exploit model specific structure and thus cannot be efficient and robust on a wide variety of problems. Here, we challenge this common belief. We have designed and implemented the optimization framework GENO (GENeric Optimization) that combines a modeling language with a generic solver. GENO generates a solver from the declarative specification of an optimization problem class. The framework is flexible enough to encompass most of the classical machine learning problems. We show on a wide variety of classical but also some recently suggested problems that the automatically generated solvers are (1) as efficient as well-engineered specialized solvers, (2) more efficient by a decent margin than recent state-of-the-art solvers, and (3) orders of magnitude more efficient than classical modeling language plus solver approaches.

This paper presents the most important results of a research project whichfocused on the use of crystallization modifiers mixed in lime mortar to mitigatesalt crystallization damage. The research focused on two of the most damagingsalts, sodium chloride and sodium sulfate, and suitable crystallization modifiers (sodium ferrocyanide and borax). We report the major findings related to the effectiveness of the modifiers when mixed in the mortar, and the results of characterization of the additivated mortars in comparison with reference mortars. Moreover, the durability of the developed mortars to salt decay is discussed, based on the results of an accelerated salt weathering test carried out in laboratory. No major effects of the modifiers on the fresh and hardened mortar properties were observed which might restrain the application of crystallization modifiers in restoration mortars. Additionally, the mortars with mixed-in modifiers showed a considerable improvement of the salt resistance when compared to reference mortars. Considering these results an outlook for future research pathways is given.

We address the problem of solving convex optimization problems with many convex constraints in a distributed setting. Our approach is based on an extension of the alternating direction method of multipliers (ADMM) that recently gained a lot of attention in the Big Data context. Although it has been invented decades ago, ADMM so far can be applied only to unconstrained problems and problems with linear equality or inequality constraints. Our extension can handle arbitrary inequality constraints directly. It combines the ability of ADMM to solve convex optimization problems in a distributed setting with the ability of the Augmented Lagrangian method to solve constrained optimization problems, and as we show, it inherits the convergence guarantees of ADMM and the Augmented Lagrangian method.

In 1992-1996 an investigation was carried out to understand the salt damages in the crypt of St.Maria im Kapitol in Cologne: Damages of stones and wallpaintings have been caused by cycliccrystallization and dissolution of the salts halite [NaCl] and nitratine [NaNO3] due to climatechanges through heating the crypt. In the crypt the dissolution or crystallisation of halite andnitratine takes place when 65-75% of relative humidity is reached, depending on thethermodynamic properties of the saltmixture halite/nitratine. For ten years the Department ofRestoration architects, scientists and restorers have been working together to solve thequestion, how to diminish the damages and salt concentrations in the crypt. In order to preventmajor salt deteriorations in the crypt, the heating system was adapted and the environmentalconditions were changed step by step in order to reach values of around 67% relative humidityresulting in a more stable climate and mitigating the deterioration process. A monitoring systemwas installed to monitor the effects of the climate changes in the crypt.

Mechatronische Pumpensysteme sind die treibende Kraft in fast allen Produktionsanlagen der verfahrenstechnischen Industrie und bestimmen in hohem Maße die Verfügbarkeit der Anlagen. Der Zuverlässigkeit von Pumpensystemen kommt demzufolge ein ganz besonderer Stellenwert zu. Daher wird seit Oktober 2006 im Verbundforschungsprojekt ReMain an einem weitergehenden Ansatz bezüglich Diagnose und Restlebensdauerprognose von Pumpensystemen gearbeitet.

This thesis deals with a number of geometric optimization problems which are all NP-hard. The first problem we consider is the set cover problem for polytopes in R3. Here, we are given a set of points in R3 and a fixed set of translates of an arbitrary polytope. We would like to select a subset of the given polytopes such that each input point is covered by at least one polytope and the number of selected polytopes is minimal. By using epsilon-nets, we provide the first constant-factor approximation algorithm for this problem. The second set of problems that we consider are power assignment problems in wireless networks. Ad hoc wireless networks are a priori unstructured in a sense that they lack a predetermined interconnectivity. We consider a number of typical connectivity requirements and either give the first algorithms that compute a (1 + )-approximate energy efficient solution to them, or drastically improve upon existing algorithms in running time. The algorithms are based on coresets. We then extend the algorithms from the Euclidean case to metrics of bounded-doubling dimension and study metric spaces of bounded-doubling dimension more in-depth. The last problem that we consider is the k-hop minimum spanning tree, that is, we are given a graph and a specified root node and we would like to find a minimum spanning tree of the graph such that each root-leaf path contains at most k edges. We give the first PTAS for the problem in the Euclidean plane.

Suppose we are given a finite set of points $P$ in $\R^3$ and a collection of polytopes $\mathcal{T}$ that are all translates of the same polytope $T$. We consider two problems in this paper. The first is the set cover problem where we want to select a minimal number of polytopes from the collection $\mathcal{T}$ such that their union covers all input points $P$. The second problem that we consider is finding a hitting set for the set of polytopes $\mathcal{T}$, that is, we want to select a minimal number of points from the input points $P$ such that every given polytope is hit by at least one point. We give the first constant-factor approximation algorithms for both problems. We achieve this by providing an epsilon-net for translates of a polytope in $R^3$ of size $\bigO(\frac{1{��)$.

A fundamental class of problems in wireless communication is concerned with the assignment of suitable transmission powers to wireless devices/stations such that the resulting communication graph satisfies certain desired properties and the overall energy consumed is minimized. Many concrete communication tasks in a wireless network like broadcast, multicast, point-to-point routing, creation of a communication backbone, etc. can be regarded as such a power assignment problem. This paper considers several problems of that kind; for example one problem studied before in (Vittorio Bil{\`o} et al: Geometric Clustering to Minimize the Sum of Cluster Sizes, ESA 2005) and (Helmut Alt et al.: Minimum-cost coverage of point sets by disks, SCG 2006) aims to select and assign powers to $k$ of the stations such that all other stations are within reach of at least one of the selected stations. We improve the running time for obtaining a $(1+\epsilon)$-approximate solution for this problem from $n^{((\alpha/\epsilon)^{O(d)})}$ as reported by Bil{\`o} et al. (see Vittorio Bil{\`o} et al: Geometric Clustering to Minimize the Sum of Cluster Sizes, ESA 2005) to $O\left( n+ {\left(\frac{k^{2d+1}}{\epsilon^d}\right)}^{ \min{\{\; 2k,\;\; (\alpha/\epsilon)^{O(d)} \;\}} } \right)$ that is, we obtain a running time that is \emph{linear} in the network size. Further results include a constant approximation algorithm for the TSP problem under squared (non-metric!) edge costs, which can be employed to implement a novel data aggregation protocol, as well as efficient schemes to perform $k$-hop multicasts.