### Refine

#### Year of publication

#### Document Type

- Doctoral Thesis (38)
- Preprint (27)
- Article (4)
- Other (2)
- Working Paper (2)
- Bachelor Thesis (1)
- Book (1)

#### Keywords

- Kombinatorik (10)
- integral distances (6)
- Algebraische Geometrie (5)
- Nichtlineare Optimierung (5)
- Operations Research (5)
- erschöpfende Suche (5)
- exhaustive search (5)
- ganzzahlige Abstände (5)
- ganzzahlige Punktmengen (5)
- Branch-and-Bound-Methode (4)

#### Institute

- Mathematik (75) (remove)

- New Trust Region SQP Methods for Continuous and Integer Optimization (2013)
- In this thesis new algorithms are presented that address nonlinear optimization problems. The algorithms belong to the class of sequential quadratic programming (SQP) methods. Two problem formulations that arise frequently in real-world applications are considered. Both have in common that functions are nonlinear and the formulations contain equality and inequality constraints. For the one class of problems the domain of all variables is R. These problems are called nonlinear programming (NLP) problems. Many applications also require that some of the featured variables are restricted to the domain Z. Problems with additional integer variables are called mixed-integer nonlinear programs (MINLP) and are also considered here. This work is motivated by the advancement of an algorithm for solving MINLPs that was first discussed by Exler and Schittkowski (2007). The algorithm adapts concepts of SQP methods to mixed-integer nonlinear optimization. The new approach replaces the continuous quadratic problems by mixed-integer quadratic problems. The aim is to profit from the fast local convergence properties of SQP methods at least with respect to the continuous variables when integer variables remain fixed. Two new versions of the underlying algorithm of Exler and Schittkowski are presented. It is well-known that SQP methods might not converge for any arbitrary starting point. To obtain global convergence, techniques of trust region methods are employed by the new algorithms. The first version of an algorithm for MINLPs presented in this thesis employs the Linf-penalty function as merit function. Applying this penalty function might lead to a slow convergence. The so-called Maratos effect requires the reduction of the step length so that fast convergence is lost. Hence, safeguards have to be added. The presented algorithm calculates additional second order correction (SOC) steps. Calculating SOC steps is a frequently used approach to obtain fast local convergence. There also exist other techniques. The SOC steps require additional function evaluations. Frequently, function values of mixed-integer problems arising in the field of engineering are evaluated by running time-consuming simulation tools, where a single function evaluation can take minutes or even hours. Thus, the goal of the development of an efficient method has to be that the number of needed function evaluations is as small as possible. For that reason the investigation of methods that obtain fast local convergence without calculating SOC steps is the key aspect of this thesis. As a fundamental theory is available for NLPs, whereas MINLPs lack in most of these concepts, the main part of this thesis presents and analyzes a new trust region SQP algorithm addressing NLPs. The algorithm proposed here avoids the calculation of SOC steps by using an augmented Lagrangian function as merit function. In trust region methods a differentiable merit function, such as an augmented Lagrangian function, was employed in the past for equality constrained problems. Methods that also treat inequality constraints, transform these constraints into equality constraints. The new algorithm does not reformulate the underlying problem. The proposed algorithm for NLPs is described in detail. The global and local convergence properties of the new algorithm are investigated. Under suitable assumptions it is shown that for any arbitrary starting point the sequence of generated iterates contains at least one accumulation point that is a Karush-Kuhn-Tucker point of the underlying NLP. Under certain conditions fast local convergence is proved, as full SQP steps will be accepted close to a solution. Thus, no additional SOC steps are required. Due to the insight that is gained by the development of the algorithm for NLPs, an additional version of the algorithm for MINLPs can be stated. The second algorithm also enhances the algorithm of Exler and Schittkowski (2007), but does not calculate SOC steps anymore and the extra function evaluations are avoided. All presented algorithms are implemented in FORTRAN and completely documented. The code is evaluated on a set of almost 500 test problems. Numerical results show the good performance of the new algorithms. The numerical tests of the algorithm for NLPs indicate that the theoretical convergence results hold in practice. Moreover, the efficiency of the second algorithm for MINLPs that does not calculate SOC steps has improved compared to the first version with SOC steps

- Computational Bounds for Elevator Control Policies by Large Scale Linear Programming (2013)
- We computationally assess policies for the elevator control problem by a new column-generation approach for the linear programming method for discounted infinite-horizon Markov decision problems. By analyzing the optimality of given actions in given states, we were able to provably improve the well-known nearest-neighbor policy. Moreover, with the method we could identify an optimal parking policy. This approach can be used to detect and resolve weaknesses in particular policies for Markov decision problems.

- On Efficient Solution Methods for Mixed-Integer Nonlinear and Mixed-Integer Quadratic Optimization Problems (2013)
- In this thesis we focus on solution methods for convex mixed-integer nonlinear optimization problems (MINLP). As one main result, we propose a new algorithm guaranteeing global optimality for convex MINLPs under standard assumptions. The new algorithm called MIQP-supported outer approximation (MIQPSOA) incorporates the successive solution of convex mixed-integer quadratic programs (MIQP) in a linear outer approximation framework. An extensive numerical competitive study based on several different MINLP solvers shows, that a first implementation of the new method performs well in terms of both the reliability and the efficiency. Since the new method is designed to solve simulation-based optimization problems arising in practical engineering applications, the main performance criterion is the number of function evaluations required to solve a problem. Furthermore, the test results indicate, that the integration of mixed-integer search steps, resulting from the solution of convex MIQPs, significantly improves the reliability and the efficiency compared to well-known linear outer approximation methods. After reviewing available solution techniques for convex MINLP problems, we present the algorithmic set-up as well as the convergence proof of MIQPSOA. As pointed out in this dissertation, MIQPSOA is a first step towards a convergent MINLP solution method, that solely relies on the successive solution of convex MIQPs as proposed by Exler and Schittkowski. Finally, we present an extensive numerical test case study considering different solution methods for convex MINLPs. The second part of this thesis deals with efficient solution techniques for convex mixed-integer quadratic programs, that arise as subproblems during the solution of MINLPs by MIQP-based algorithms, such as MIQPSOA. First, we briefly review latest developments in state-of-the-art mixed-integer linear (MILP) solvers, since we want to develop a MIQP solver that incorporates the most successful components of MILP solvers. As we focus on branch-and-bound methods, one main component is an efficient and robust sub-solver for continuous quadratic programs, which is able to perform warmstarts. On the other hand, cutting planes have led to a tremendous speed-up of mixed-integer linear solvers during the last 20 years. As a consequence, we extend an efficient construction method for disjunctive cutting planes, such that it can be applied for MIQPs. Extensive numerical tests show, that the performance of a branch-and-bound solver can be significantly increased by exploiting warmstarts. Furthermore, it turns out, that in a majority of the test cases, where disjunctive cutting planes exist, the calculation times are reduced up to a factor of more than 5. Nevertheless there are also instances, where the presents of disjunctive cutting planes significantly slows down the performance. Due to the efficient cut generation method developed within this thesis, the generation of cutting planes has almost no influence on the calculation time, if no disjunctive cuts exist, which is the case in about 45 \% of all test instances. As a consequence, the application of cutting planes for MIQPs needs further attention and especially a dynamic cut management might be very profitable. Finally, we compare the performance of our branch-and-cut solver MIQL with the solver SCIP, which is one of the state-of-the-art MILP solvers, that can also solve MIQPs. These tests indicate, that MIQL outperforms SCIP on hard MIQP instances, while SCIP is faster for simpler test cases.

- Optimal sensor placement for linear systems (2013)
- The aim of sensor placement is to observe the state of a dynamical system while using only a small part of the available output information. Thus, the observer does not need sensors at every possible node of the system. We use sensor placement because it is not practical for large-scale networks, such as power grids, to place sensors at each node. With an optimal sensor placement we obtain a subset of sensors which minimizes the observer error in comparison to any other subset of the same size. This means we generate an optimal observation with the given number of sensors. We compute the observer error, for the linear dynamical systems we consider, with the H2-norm of the observer error system. In this approach, we optimize both the subset of selected sensors and the observer gain matrix in parallel. The optimization problem is non-convex both in a constraint, which bounds the H2-norm, as well as in the objective function which uses a l0-norm to count the used sensors. To obtain a semidefinite program, we first relax the l0-norm by an iterative reweighted l1-norm. Second, we use a reformulation of the H2-norm with linear matrix inequalities to replace an occuring bilinear and therefore non-convex term. We use this computationally efficient formulation of the sensor placement problem to derive three algorithms. Furthermore, existing algorithms, which do not use the convex reformulation of the optimization problem, were implemented. The algorithms are compared extensively relating to execution time, performance of the chosen sensors, and the applicability on a practical problem. The practical problem is a model of a high-voltage power grid with the aim to measure the phase angles and the frequencies at every node. The result of the comparison is that a algorithm with a greedy approach solves the optimization problem fast and usually with a good solution. However, this algorithm is problematic because the shortsighted greedy approach cannot exclude that a worst case solution is generated. The best results in general were produced by a novel approach made in this thesis. This novel algorithm iteratively solves the relaxed optimization problem and finds near-optimal sensor subsets.

- Ein Verfahren der sequentiellen, konvexen Optimierung mit kombinierter Trust-Region- und Moving-Asymptotes-Stabilisierung zur Lösung nichtlinearer, restringierter Optimierungsprobleme (2013)
- Ein neues Verfahren der sequentiellen konvexen Optimierung (SCP) zur Lösung allgemeiner kontinuierlicher und restringierter nichtlinearer Optimierungsprobleme (NLP) wird vorgestellt, das die Approximation der "Method of Moving Asymptotes" (MMA) mit einer Trust-Region-Strategie kombiniert. Als Trust-Region für diese Methode wird das Gebiet zwischen den MMA-Asymptoten abzüglich einem festen Sicherheitsabstand definiert, um die Beschränktheit der Approximationen zu gewährleisten. Die Asymptoten, die notwendig für das Aufstellen der Approximationen sind, werden implizit über die Steuerung des Trust-Region-Radius im Sinne einer Trust-Region-Methode erzeugt. Der Algorithmus "Trust-Region Sequential Convex Programming - TRSCP" wird vorgestellt und die globale Konvergenzeigenschaft des neuen Verfahrens wird nachgewiesen. TRSCP ist sowohl ein SCP-Verfahren, als auch eine Trust-Region-Methode. Im Unterschied zu anderen Ansätzen auf diesem Gebiet, benötigt TRSCP keine explizite Trust-Region zusätzlich zu den MMA-Asymptoten. Darüber hinaus behindert eine aktive Trust-Region nicht die globale Konvergenzeigenschaft des neuen Verfahrens. TRSCP ist im Programm TRSCP1.0 implementiert. Es wird gezeigt, daß TRSCP1.0 ein leistungsfähiges Programm zur Lösung von nichtlinearen Optimierungsproblemen ist und ein Vergleich mit einer Line-Search-Methode wird durchgeführt.

- Über eine Erweiterung der Methode von Soshnikov zur Untersuchung des größten Eigenwerts auf unsymmetrische Verteilungen (2013)
- Seit der Entdeckung des Halbkreisgesetzes durch Wigner werden reell-symmetrische Zufallsmatrix-Ensembles untersucht. Soshnikov hat in einer bahnbrechenden Arbeit gezeigt, dass für Wigner-Ensembles $A_n=(\xi_\ij)_{1\le i\le j\le n}$ mit symmetrisch verteilten Einträgen die Verteilung des größten Eigenwerts in einer geeigneten Skalierung für $n\to\infty$ universelles Verhalten zeigt und schwach gegen die Tracy-Widom-Verteilung, die Verteilung des Gauß'schen orthogonalen Ensembles, konvergiert. Für den Beweis nutzt Soshnikov die Momentenmethode. Hierbei wird die Analyse der Verteilungsfunktion des größten Eigenwerts auf die Analyse von Erwartungswerten von Spuren hoher Matrixpotenzen zurückgeführt (die Exponenten wachsen mit $n^{2/3}$). Die Spuren werden via $\tr A_n^{p_n}=\sum_{(i_0,\ldots,i_{p-1})\in[n]^p}\xi_{i_0,i_1}\xi_{i_1,i_2}\ldots\xi_{i_{p-1},i_0}$ als Summe über geschlossene Pfade kombinatorisch interpretiert. In der Analyse gilt es herauszufinden, welche Klassen von Pfaden (die mit den Momenten der Matrixeinträge in Verbindung stehen) die Spuren in der Asymptotik $n\to\infty$ dominieren. Es stellt sich heraus das dies Pfade sind, die jede ihrer Kanten genau zweimal durchlaufen. Das bedeutet, dass die Spuren asymptotisch nur von den für alle Matrixeinträge gleichen zweiten Momenten abhängen, sie sind also asymptotisch für alle betrachteten Ensembles universell. Diese Methode wird in der vorliegenden Arbeit auf Wigner-Ensembles mit nicht notwendig symmetrischen Verteilungen der Einträge erweitert. Die Kombinatorik ist in diesem Fall komplexer. Resultat der Arbeit ist, dass die Methode von Soshnikov funktioniert, wenn folgende Bedingungen erfüllt sind: die ersten und dritten Momente der Einträge sind~0 für die 97.\ Momente existiert eine in~$n$ gleichmäßige Schranke.

- Integrated size and price optimization for a fashion retailer (2013)
- This thesis is the result of a collaboration with a German fashion retailer which lasted for several years. The aim was the development of a decision-support system for the supply of the about 1300 branches in Germany. There are some specialties about the situation at our industrial partner: The branches are supplied by prepackaged size-assortments of a product which we call lot-types. With the objective to economize handling cost, these lot-types are already composed at the respective low-wage country where the article is also produced. The expense at the German central warehouse is further reduced by allowing only four or five different lot-types for the delivery of one product. Moreover, each branch is supplied by a certain quantity of a single lot-type. For the most fashion articles replenishment is not possible. The sales success of a product is a priori unknown. Historical sales data can only be used on a higher aggregation level, e.g., the average historical demand on the commodity group level. Demand estimation is therefore very vague. Under- and oversupplies are unavoidable. Influence over the sales process is possible by marking down prices. To compensate for an oversupply of a product, weekly the price can be reduced to predefined price steps which depend on the starting price of the product. Mark-downs for an article are performed simultaneously for all branches and sizes. Within the cooperation mathematical problem formulations with the aim to minimize measures for the deviation of supply from estimated demand had been developed. In these measures the selling process is not or only very vaguely regarded. Now we include the possibility of marking down prices during the selling time already when deciding on the supply. The result is the two-stage stochastic program ISPO: The so-called first stage decision is the determination of a supply policy. The second stage decision, or recourse, is the decision on mark-downs during the selling time. ISPO yields an expected revenue maximizing supply strategy and corresponding optimal mark-down strategies for the considered scenarios. ISPO it too complex to solve it via standard approaches. Customized methods had to be devised to solve ISPO. On the one side we present an exact solver for benchmarking. On the other side a fast heuristic was developed for practical use at our partner. The basic idea of our exact solver is to enumerate all possible mark-down strategies. With this it is possible to reduce ISPO to a former formulation for the optimization of supply, which can be solved via standard approaches. In practice enumeration of all valid mark-down strategies for the purpose of solving ISPO is for reasons of time impossible. Therefore the idea is extended to a customized Branch&Bound approach. In this context we derived dual bounds for general two-stage stochastic programs which are based on the so-called wait-and-see solution from stochastic programming. We show that in general our bounds are tighter. The heuristic, beginning with a valid second stage decision, determines an optimal first stage decision and alternates between solving the first stage and the second stage until convergence is reached. The optimality gap is small enough to justify a practical use at the industrial partner. In practice the by ISPO proposed mark-down strategies are not applied; instead latest sales figures are exploited. According to these and an updated demand estimation weekly a new optimal mark-down strategy for the remaining selling time of the product is determined. For this purpose we propose an algorithm which relies on dynamic programming and tries to exclude non-optimal solutions a priori by dominance checks. ISPO, more precisely our heuristic approach, together with the weekly adaption of the mark-down strategy forms our decision support system for integrated size and price optimization DISPO. We tested DISPO in a five-month field study, performed as a statistical experiment, at our partner where pairs of similar branches were compared. At one branch of each pair, the test branch, supply and mark-down decisions came from ISPO. With respect to latest sales figures the mark-down decisions were weekly updated via our dynamic programming approach. At the other branch, the control branch, these decisions were not integrated: Supply was determined according to a strategy resulting from a former model that disregarded the selling process and mark-downs were handled manually by our partner. For the branches at which the decisions of ISPO were implemented an average raise of 1.5 percentage points of relative revenue was observed.

- THE INDEX THEOREM FOR QUASI-TORI (2013)
- The Index theorem for holomorphic line bundles on complex tori asserts that some cohomology groups of a line bundle vanish according to the numbers of negative and positive eigenvalues of the associated hermitian form. In this thesis, this theorem is generalized to quasi-tori, i.e. connected complex abelian Lie groups which are not necessarily compact. In view of the Remmert–Morimoto decomposition of quasi-tori as well as the Künneth formula, it suffices to consider only Cousin-quasi-tori, i.e. quasi-tori which have no non-constant holomorphic functions. The Index theorem is generalized to holomorphic line bundles, both linearizable and non-linearizable, on Cousin-quasi-tori using L2-methods coupled with the Kazama–Dolbeault isomorphism and Bochner–Kodaira formulas.

- Geometrische Konstruktionen linearer Codes über Galois-Ringen der Charakteristik 4 von hoher homogener Minimaldistanz (2012)
- In dieser Arbeit werden vier neue unendliche Serien von linearen Codes über Galois-Ringen der Charakteristik 4 konstruiert. Hinsichtlich der Minimaldistanz übertreffen die Gray-Bilder der konstruierten Codes alle bekannten vergleichbaren linearen Codes. In den Konstruktionen wird die Theorie der projektiven Hjelmslev-Geometrien, der Assoziationsschemata sowie der symmetrischen Bilinearformen in endlichdimensionalen GF(2)-Vektorräumen benutzt.

- The Integrated Size and Price Optimization problem (2012)
- We present the Integrated Size and Price Optimization Problem (ISPO) for a fashion discounter with many branches. Based on a two-stage stochastic programming model with recourse, we develop an exact algorithm and a production-compliant heuristic that produces small optimality gaps. In a field study we show that a distribution of supply over branches and sizes based on ISPO solutions is significantly better than a one-stage optimization of the distribution ignoring the possibility of optimal pricing.