phd theses

2025

1. Algorithm Engineering and Integer Programming for the Maximum Cut Problem

   Jonas Klaus Charfreitag

   Universität Bonn, 2025

   External reviewer

   Abs DOI

   The maximum cut problem, MaxCut for short, is one of the fundamental problems in combinatorial optimization. It is part of a large family of graph partitioning problems that ask for a division of all vertices of the graph into disjoint sets. In its optimization form MaxCut is about finding a bipartition that maximizes the value of a cut. A cut in the context of a vertex partition is defined as the set of edges connecting vertices of different partitions. The value of a cut is the sum of all weights associated with the edges of the cut. Although MaxCut allows for a compact description, it has highly relevant modeling power. Many real-world applications for MaxCut have been described in the literature over the years; these range from chip design to scheduling sports leagues and, more recently, the benchmarking of certain quantum algorithms and computers. Depending on the application, good solutions do not suffice and practitioners and researchers are interested in optimal solutions. Unfortunately, MaxCut is NP-hard in general, and it is still unknown whether we can solve NP-hard problems fast, that is, in time polynomial in the input size. However, practical algorithms for solving MaxCut to optimality have been designed in the past, and this thesis aims to improve them and develop new ones. We focus especially on techniques for sparse graphs, as real-world instances often turn out to be sparse. An important way to speed up algorithms for hard problems is to reduce the search space before even exploring it. The process of performing these reductions without sacrificing optimal solutions is called presolving. We develop new presolving algorithms for MaxCut in three categories. One of these is based on vertex separators that have not been explicitly considered for MaxCut so far. For exploring and further pruning of the search space for MaxCut we resort to integer programming and the branch-and-cut algorithm, which has yielded good results for exact MaxCut algorithms in the past. We extend previous work and suggest a refined integer program. This model has implications for other modules part of the branch-and-cut algorithm that we present in detail. Examples are the generation of cutting planes and problem-specific branching rules. From these we derive new and concrete algorithms that can be employed in MaxCut solvers based on branch-and-cut. To evaluate the practical relevance of our new techniques, we perform elaborate experimental studies and compare them against the state of the art. For this we carefully engineered a new solver that contains state-of-the-art techniques and our new ones. The solver is competitive to the fastest MaxCut solver in general and clearly outperforms the state of the art for certain inputs. In detailed ablation studies, we track these improvements down to our new techniques. Especially, our presolving and cutting plane generation offers significant speed-up potential of up to one order of magnitude over the state of the art.

2024

1. Algorithms and Certificates for Exact Mixed Integer Programming

   Leon Dorian Eifler

   TU Berlin, Nov 2024

   Abs DOI

   Mixed Integer Programming (MIP) is a powerful tool for solving optimization problems with discrete decisions. Although the problem class of mixed integer programs is NP-hard, MIP solvers have made significant progress in solving large-scale instances through decades of dedicated research and complex algorithmic improvements. In practice, virtually all algorithms to solve MIP problems are based on floating-point arithmetic due to its rapid computation times and robust numerical capabilities. Using error tolerances, MIP solvers avoid numerical issues and maintain a solution quality that is sufficient for most practical applications. There are, however, applications where exact solutions are required, such as when MIPs are employed as a tool in computer-assisted proofs. In such cases, exact, certified MIP solvers are a necessity. This thesis delves into the study and development of exact, certified mixed integer programming methods. The primary contribution of this thesis is an algorithmic framework for exact rational mixed integer programming. This framework incorporates safe dual bounding techniques, exact rational presolving, an exact repair step for heuristic solutions, and a novel exact Gomory mixed integer cut generator. We validate the effectiveness of our framework through experiments on a diverse set of benchmark instances. We take great care to measure the similarities and differences with corresponding techniques in the floating-point setting. Furthermore, we incorporate certification techniques into the framework to provide rigorous guarantees on the correctness of the computed solutions. We also provide a comprehensive algorithmic and computational study of the solver-independent verification of these certificates. We also present a framework for applying exact MIP as a tool for computer-assisted mathematics, using Chvátal’s conjecture as an illustrative example. Another significant contribution of this thesis is a new algorithm for solving linear programs exactly. This algorithm combines two state-of-the-art techniques for exact linear programming: precision boosting and LP iterative refinement. Combining these techniques can significantly improve the performance of exact linear programming solvers, and we prove that the algorithm is theoretically guaranteed to terminate with an exact solution.

2023

1. Cutting Plane Selection for Mixed-Integer Linear Programming

   Mark Turner

   TU Berlin, Dec 2023

   Abs DOI

   Mixed-Integer Linear Programming (MILP) is a ubiquitous and practical modelling paradigm that is essential for optimising a broad range of real-world systems. The backbone of all modern MILP solvers is the branch-and-cut algorithm, which is a hybrid of the branch-and-bound and cutting planes algorithms. Cutting planes (cuts) are linear inequalities that tighten the relaxation of a MILP. While a lot of research has gone into deriving valid cuts for MILPs, less emphasis has been put on determining which cuts to select. Cuts in general are generated in rounds, and a subset of the generated cuts must be added to the relaxation. The decision on which subset of cuts to add is called cut selection. This is a crucial task since adding too many cuts makes the relaxation large and slow to optimise over. Conversely, adding too few cuts results in an insufficiently tightened relaxation, and more relaxations need to be enumerated. To further emphasise the difficulty, the effectiveness of an applied cut is both dependent on the other applied cuts, and the state of the MILP solver. In this thesis, we present theoretical results on the importance and difficulty of cut selection, as well as practical results that use cut selection to improve general MILP solver performance. Improving general MILP solver performance is of great importance for practitioners and has many runoff effects. Reducing the solve time of currently solved systems can directly improve efficiency within the application area. In addition, improved performance enables larger systems to be modelled and optimised, and MILP to be used in areas where it was previously impractical due to time restrictions. Each chapter of this thesis corresponds to a publication on cut selection, where the contributions of this thesis can naturally be divided into four components. The first two components are motivated by instance-dependent performance. In practice, for each subroutine, including cut selection, MILP solvers have adjustable parameters with hard-coded default values. It is ultimately unrealistic to expect these default values to perform well for every instance. Rather, it would be ideal if the parameters were dependent on the given instance. To show this motivation is well founded, we first introduce a family of parametric MILP instances and cuts to showcase worst-case performance of cut selection for any fixed parameter value. We then introduce a graph neural network architecture and reinforcement learning framework for learning instance-dependent cut scoring parameters. In the following component, we formalise language for determining if a cut has theoretical usefulness from a polyhedral point of view in relation to other cuts. In addition, to overcome issues of infeasible projections and dual degeneracy, we introduce analytic center based distance measures. We then construct a lightweight multi-output regression model that predicts relative solver performance of an instance for a set of distance measures. The final two components are motivated by general MILP solver improvement via cut selection. Such improvement was shown to be possible, albeit difficult to achieve, by the first half of this thesis. We relate branch-and-bound and cuts through their underlying disjunctions. Using a history of previously computed Gomory mixed-integer cuts, we reduce the solve time of SCIP over the 67% of affected MIPLIB 2017 instances by 4%. In the final component, we introduce new cut scoring measures and filtering methods based on information from other MILP solving processes. The new cut selection techniques reduce the solve time of SCIP over the 97% of affected MIPLIB 2017 instances by 5%.

2. Modeling and solving real-world transient gas network transport problems using mathematical programming

   Felix Paul Hennings

   TU Berlin, May 2023

   Abs DOI

   This thesis considers the transient gas network control optimization problem for on-shore pipeline-based transmission networks with numerous gas routing options. As input, the problem is given the network’s topology, its initial state, and future demands at the boundaries of the network, which prescribe the gas flow exchange and potentially the pressure values. The task is to find a set of future control measures for all the active, i.e., controllable, elements in the network that minimizes a combination of different penalty functions. The problem is examined in the context of a decision support tool for gas network dispatchers. This results in detailed models featuring a diverse set of constraints, large and challenging real-world instances, and demanding time limit requirements. All these factors further complicate the problem, which is already difficult to solve in theory due to the inherent combination of non-linear and combinatorial aspects. Our contributions concern different steps of the process of solving the problem. Regarding the model formulation, we investigate the validity of two common approximations of the gas flow description in transport pipes: neglecting the inertia term and assuming a friction term that linearly depends on the gas flow and the pressure. For both, we examine if they can be applied under real-world conditions by evaluating a large amount of historical state data of the network of our project partner, the gas network operator Open Grid Europe. While we can confirm that it is reasonable to ignore the influence of the inertia term, the friction term linearization leads to significant errors and, as a consequence, cannot be used for describing the general gas flow behavior in transport pipes. As another topic of this thesis, we introduce the target value concept as a more realistic approach to express control actions of dispatchers regarding regulators and compressor stations. Here, we derive the mechanisms defined for target values based on the gas flow principles in pipes and develop a mixed-integer programming model capturing their behavior. The accuracy of this model is demonstrated in comparison to a target-value-based industry-standard simulator. Furthermore, we present two heuristics for the transient gas network control optimization problem featuring target values that are based on approximative models for the target-value-based control and determine the final decisions in a post-processing step. To compare the performance of the two heuristics with the approach of directly solving the corresponding model, we evaluate them on a set of artificially created test instances. Finally, we develop problem-specific algorithms for two variants of the described problem. One considers the control optimization for a single network station, which represents a local operation site featuring a large number of active elements. The used transient model is very detailed and includes a sophisticated representation of the compressor stations. Based on the shortness of the pipes in the station, the corresponding algorithm finds valid solutions by solving a series of stationary model variants as well as a transient rolling horizon approach. As the second variant, we consider the problem on the entire network but assume an approximative model representing the control capabilities of network stations. Aside from a new description of the compression capabilities, we introduce an algorithm that uses a combination of sequential mixed-integer programming, two heuristics based on reduced time horizons, and a specialized dynamic branch-and-bound node limit to determine promising values for the binary variables of the model. Complete solutions for the problem are obtained by fixing the binary values and solving the remaining non-linear program. Both algorithms are investigated in extensive empirical studies based on real-world instances of the corresponding model variants.

3. Linear Programming in MILP Solving: A Computational Perspective

   Matthias Miltenberger

   TU Berlin, Mar 2023

   Abs DOI

   Mixed-integer linear programming (MILP) plays a crucial role in the field of mathematical optimization and is especially relevant for practical applications due to the broad range of problems that can be modeled in that fashion. The vast majority of MILP solvers employ the LP-based branch-and-cut approach. As the name suggests, the linear programming (LP) subproblems that need to be solved therein influence their behavior and performance significantly. This thesis explores the impact of various LP solvers as well as LP solving techniques on the constraint integer programming framework SCIP Optimization Suite. SCIP allows for comparisons between academic and open-source LP solvers like Clp and SoPlex, as well as commercially developed, high-end codes like CPLEX, Gurobi, and Xpress. We investigate how the overall performance and stability of an MILP solver can be improved by new algorithmic enhancements like LP solution polishing and persistent scaling that we have implemented in the LP solver SoPlex. The former decreases the fractionality of LP solutions by selecting another vertex on the optimal hyperplane of the LP relaxation, exploiting degeneracy. The latter provides better numerical properties for the LP solver throughout the MILP solving process by preserving and extending the initial scaling factors, effectively also improving the overall performance of SCIP. Both enhancement techniques are activated by default in the SCIP Optimization Suite. Additionally, we provide an analysis of numerical conditions in SCIP through the lens of the LP solver by comparing different measures and how these evolve during the different stages of the solving process. A side effect of our work on this topic was the development of TreeD: a new and convenient way of presenting the search tree interactively and animated in the three-dimensional space. This visualization technique facilitates a better understanding of the MILP solving process of SCIP. Furthermore, this thesis presents the various algorithmic techniques like the row representation and iterative refinement that are implemented in SoPlex and that distinguish the solver from other simplex-based codes. Although it is often not as performant as its competitors, SoPlex demonstrates the ongoing research efforts in the field of linear programming with the simplex method. Aside from that, we demonstrate the rapid prototyping of algorithmic ideas and modeling approaches via PySCIPOpt, the Python interface to the SCIP Optimization Suite. This tool allows for convenient access to SCIP’s internal data structures from the user-friendly Python programming language to implement custom algorithms and extensions without any prior knowledge of SCIP’s programming language C. TreeD is one such example, demonstrating the use of several Python libraries on top of SCIP. PySCIPOpt also provides an intuitive modeling layer to formulate problems directly in the code without having to utilize another modeling language or framework. All contributions presented in this thesis are readily accessible in source code in SCIP Optimization Suite or as separate projects on the public code-sharing platform GitHub.

2022

1. Mathematical Programming for Stable Control and Safe Operation of Gas Transport Networks

   Kai Hoppmann-Baum

   TU Berlin, Dec 2022

   Dissertationspreis 2023 der Gesellschaft für Operations Research

   Abs DOI

   The fight against climate change makes extreme but inevitable changes in the energy sector necessary. These in turn lead to novel and complex challenges for the transmission system operators (TSOs) of gas transport networks. In this thesis, we consider four different planning problems emerging from real-world operations and present mathematical programming models and solution approaches for all of them. Due to regulatory requirements and side effects of renewable energy production, controlling today’s gas networks with their involved topologies is becoming increasingly difficult. Based on the network station modeling concept for approximating the technical capabilities of complex subnetworks, e.g., compressor stations, we introduce a tri-level MIP model to determine important global control decisions. Its goal is to avoid changes in the network elements’ settings while deviations from future inflow pressures as well as supplies and demands are minimized. A sequential linear programming inspired post-processing routine is run to derive physically accurate solutions w.r.t. the transient gas flow in pipelines. Computational experiments based on real-world data show that meaningful solutions are quickly and reliably determined. Therefore, the algorithmic approach is used within KOMPASS, a decision support system for the transient network control that we developed together with the Open Grid Europe GmbH (OGE), one of Europe’s largest natural gas TSOs. Anticipating future use cases, we adapt the aforementioned algorithmic approach for hydrogen transport. We investigate whether the natural gas infrastructure can be repurposed and how the network control changes when energy-equivalent amounts of hydrogen are transported. Besides proving the need for purpose-built compressors, we observe that, due to the reduced linepack, the network control becomes more dynamic, compression energy increases by 440% on average, and stricter regulatory rules regarding the balancing of supply and demand become necessary. Extreme load flows expose the technical limits of gas networks and are therefore of great importance to the TSOs. In this context, we introduce the Maximum Transportation Problem and the Maximum Potential Transport Moment Problem to determine severe transport scenarios. Both can be modeled as linear bilevel programs where the leader selects supplies and demands, maximizing the follower’s transport effort. To solve them, we identify solution-equivalent instances with acyclic networks, provide variable bounds regarding their KKT reformulations, apply the big-M technique, and solve the resulting MIPs. A case study shows that the obtained scenarios exceed the maximum severity values of a provided test set by at least 23%. OGE’s transmission system is 11,540km long. Monitoring it is crucial for safe operations. To this end, we discuss the idea of using uncrewed aerial vehicles and introduce the Length-Constrained Cycle Partition Problem to optimize their routing. Its goal is to find a smallest cycle partition satisfying vertex-induced length requirements. Besides a greedy-style heuristic, we propose two MIP models. Combining them with symmetry-breaking constraints as well as valid inequalities and lower bounds from conflict hypergraphs yields a highly performant solution algorithm for this class of problems.

2. Computational and Algebraic Aspects of Sums of Nonnegative Circuit Polynomials

   Henning Seidler

   TU Berlin, Dec 2022

   2nd reviewer

   Abs DOI

   In this thesis we introduce a new method how to algorithmically determine lower bounds for multivariate polynomials. It is based on Circuit Polynomials, a class of sparse polynomials, whose nonnegativity is easily checked. The algorithm tries to decompose the given polynomial into a Sum of Nonnegative Circuit Polynomials (SONC) and a constant, therefore providing a lower bound in the majority of cases. Opposed to the established method Sums of Squares (SOS), the complexity of our method does not depend on the degree of the polynomial, but is mainly determined by the number of terms. In fact, our algorithm has a polynomial running time, even when polynomials are given in sparse notation. Hence, our approach is especially suited for sparse polynomials of high degree. Furthermore, we present two extensions of this method. The first one improves the lower bounds by performing a branch-and-bound over the signs of the variables. The running time is FPT in the number of variables, so it remains feasible for a moderate amount of them. In the second extension, we provide a method how, under some additional assumptions, the numerical results of our computations can be transformed into certificates in exact arithmetic. All of our methods are implemented in the free software POEM in Python and extensively tested. We end with a detailed evaluation, in particular comparing running time and quality of the lower bounds with SOS.

2021

1. Infeasibility Analysis for MIP

   Jakob Witzig

   TU Berlin, Dec 2021

   Abs DOI

   Mixed integer programming (MIP) is one of the essential paradigms used in business and industry decision making. In the last decades, it has been successfully applied to many real-world applications. One of the main benefits of using MIP is that it comes with a certificate of optimality. Proving that a given solution is optimal is equivalent to proving that there exists no better solution with respect to costs. In other words, if a solution is optimal, all other solutions are infeasible when considering an additional constraint enforcing better costs. Thus, proving infeasibility is an essential ingredient when solving MIPs. In this thesis, we shed light on infeasibility analysis in MIP. Modern MIP solvers try to “learn” from infeasibilities encountered during the solving process. However, compared to solving satisfiability problems (SAT), where the analysis of infeasibility has its origin, infeasibility analysis for MIP had an subordinate role so far. In this thesis, we show that a general purpose MIP solver such as SCIP can highly benefit when increasing the effort spend in detecting and exploiting infeasibility. This is shown in three different ways. Firstly, we develop a simultaneous approach of combinatorial and analytic infeasibility analysis. In addition, we develop several enhancements that further increase the positive impact on the overall solving process. Secondly, this thesis demonstrates that “learning” from almost infeasible subproblems of the search space is beneficial. Thirdly, we improve an existing method called Rapid Learning and develop new methods that explicitly aim to generate additional information of infeasibility. This newly generated information is used during the remainder of the solving process. In the last part of this thesis we generalize infeasibility analysis as known from solving MIP to general mixed integer nonlinear programs (MINLPs). This generalization is twofold. On the one hand, we present the concept of so-called local dual proofs to improve the performance of an LP-based branch-and-bound for solving nonconvex MINLPs. On the other hand, we develop a concept of nonlinear infeasibility analysis, extend SCIP to a fully-fledged NLP-based branch-and-bound, and construct nonlinear infeasibility proofs from convex NLP relaxations.

2. Adaptive Solver Behavior in Mixed-Integer Programming

   Gregor Hendel

   TU Berlin, Sep 2021

   Abs DOI

   This thesis addresses general-purpose solution techniques for mixed-integer programs (MIPs), a paradigm which captures formulations of countless real-world optimization problems. Most state-of-the-art MIP solvers employ a version of the branch-and-bound (B&B) algorithm to solve a MIP instance to proven optimality, supported by numerous auxiliary components that contribute new solutions or improve the dual convergence. One cannot expect that all such components are equally effective on all possible instances from the tremendous range of MIP applications. Ideally, a solver adapts to a given MIP instance by concentrating the available computational budget on those components that work best. In this thesis, we develop adaptive algorithmic behavior for several such MIP solver components solver as well as the B&B search itself. We develop new notions of pseudo-cost reliability, namely relative-error reliability and hypothesis reliability, by computing confidence intervals and pairwise t-tests on branching candidates to dynamically decide if strong branching is necessary. We develop two heuristic frameworks, adaptive large neighborhood search and adaptive diving that learn the most effective primal heuristics inspired by selection strategies for the multi-armed bandit problem. The presented ideas are transferred to adaptive LP pricing to maximize LP throughout by learning the pricing strategy for the dual simplex algorithms online during the search. Our proposed adaptive algorithmic behavior extends beyond individual solving components to the B&B search as a whole. To this end, we partition the B&B search into a feasibility phase, an improvement phase, and a heuristically detected proof phase. We improve solver performance by emphasizing different components and search strategies in each phase. We propose new estimation techniques for the progress of the B&B search based on forecasting and machine learning techniques. We turn this tree-size estimation into a novel restart strategy of the B&B algorithm called clairvoyant. As a methodological contribution, we describe the selection process of MIPLIB 2017, which is the current state-of-the-art library for benchmarking MIP solver performance. All of the discussed algorithmic approaches are evaluated within the MIP solver SCIP, for which they show clear performance benefits. They are publicly available as part of SCIP and have been adopted by state-of-the-art commercial solvers such as FICO Xpress.

3. Faster algorithms for Steiner tree and related problems: From theory to practice

   Daniel Rehfeld

   TU Berlin, Aug 2021

   Dissertationspreis 2022 der Gesellschaft für Operations Research, EURO Doctoral Dissertation Award (EDDA) 2022, INFORMS 2022 George B. Dantzig Dissertation Award: Honorable Mention

   Abs DOI

   The Steiner tree problem in graphs (SPG) is one of the most studied problems in combinatorial optimization. Part of its theoretical appeal might be attributed to the fact that the SPG generalizes two other classic optimization problems: Shortest paths, and minimum spanning trees. On the practical side, many applications can be modeled as SPG or closely related problems. The SPG has seen impressive theoretical advancements in the last decade. However, the state of the art in (practical) exact SPG solution, set in a series of milestone papers by Polzin and Vahdati Daneshmand, has remained largely unchallenged for almost 20 years. While the DIMACS Challenge 2014 and the PACE Challenge 2018 brought renewed interest into the exact solution of SPGs, even the best new solvers fall far short of reaching the state of the art. This thesis seeks to once again advance exact SPG solution. Since many practical applications are not modeled as pure SPGs, but rather as closely related problems, this thesis also aims to combine SPG advancements with improvement in the exact solution of such related problems. Initially, we establish a broad theoretical basis to guide the subsequent algorithmic developments. In this way, we provide various new theoretical results for SPG and well-known relatives such as the maximum-weight connected subgraph problem. These results include the strength of linear programming relaxations, polyhedral descriptions, and complexity results. We go on to introduce many algorithmic components such as reduction techniques, cutting planes, graph transformations, and heuristics-both for SPG and related problems. Many of these methods and techniques are provably stronger than previous results from the literature. For example, we introduce a new reduction concept that is strictly stronger than the well-known and widely used bottleneck Steiner distance. We also provide theoretical analyses (e.g. concerning complexity) of the new algorithms. The individual components are combined in an exact branch-and-cut algorithm. Notably, all problem classes can be handled by a single branch-and-cut kernel. As a result, we obtain an exact solver for SPG and 14 related problems. The new solver is on each of the 15 problem classes faster than all other (problem-specific) solvers from the literature, often by orders of magnitude. In particular, the solver outperforms the long-reigning state-of-the-art solver for SPG. Finally, many benchmark instances from the literature for several problem classes can be solved for the first time to optimality-some containing millions of edges. These problem classes include the SPG, the prize-collecting Steiner tree problem, the maximum-weight connected subgraph problem, and the Euclidean Steiner tree problem.

4. Optimization of Stationary Expansion Planning and Transient Network Control by Mixed-Integer Nonlinear Programming

   Ralf Lenz

   TU Berlin, May 2021

   Abs DOI

   Nowadays, transmission system operators of energy networks (TSO) have to enable secure energy supply even under challenging transport situations and increasing demand. Hence, they seek a stable network control and regularly expand the capacity of their networks. The challenging questions arise of how to obtain safe network operations for fixed network infrastructure and how to extend the network capacity at minimum cost. In this thesis, we formulate these two questions as mathematical optimization problems and present solution approaches that scale to real-world instances of size and complexity encountered in practice. Model formulations of both problems are located in the field of Mixed-Integer Nonlinear Programming (MINLP). However, global state-of-the-art MINLP solvers are not mature enough to solve or even find primal solutions on large-scale real-world instances since the resulting degree of nonconvexity and nonlinearity pose principal difficulties. For this reason, we develop novel model formulations and optimization algorithms that significantly improve the performance of the solver SCIP. The first part of the thesis focuses on the optimization of stationary network expansions by building new pipelines in parallel to existing ones, so-called looping. Based upon a model reduction approach for multiple loops, we introduce new models for the discrete and split-pipe looping paradigm and compare them with existing models in the literature, both theoretically and empirically. It turns out that our novel split-pipe model performs best in several respects: running time, number of instances solved, and cost savings by up to 7000% over the discrete models. To further improve the performance, we analytically calculate the convex envelope of the nonconvex, nonlinear constraint function f(x,y) = y sgn(x) |x|^a, which models the physical effect of the expansion. In this way, we considerably tighten the convex relaxation of the network expansion problem. The resulting implementation significantly reduces the average solving time by up to 58% on difficult instances. The second part of the thesis deals with the optimization of operations in transient large-scale networks. The problem consists of making day-ahead control decisions that enable feasible energy transport. To this end, we propose a specially-tailored solution approach. First, we aggregate network structures, which TSOs typically consider as of minor importance for the decision-making process. Then, we apply model reformulations that exploit the disjunctive nature of certain network structures and strengthen the linear relaxation. Finally, we present a primal heuristic based on time decomposition. The heuristic solves MINLP sub-models to acquire transport decisions for single time steps. We equip the heuristic with a mechanism that enables moving forward and backward on the time scale to compensate for possibly disadvantageous decisions taken at earlier stages. An extensive computational study shows that our approach reliably generates solutions for 96% to 100% of the instances for three different large-scale real-world networks. Parts of the developed methods are already in use by our industrial cooperation partner Open Grid Europe GmbH to facilitate the respective decision-making processes.

2020

1. On Cutting Planes for Mixed-Integer Nonlinear Programming

   Felipe Serrano Musalem

   TU Berlin, Aug 2020

   Abs DOI

   Mixed-integer nonlinear programming is a powerful technology that allows us to model and solve problems involving nonlinear functions, continuous, and discrete variables. The state-of-the-art solvers of mixed-integer nonlinear programs (MINLPs) use a combination of, among other techniques, branch- and-bound and cutting planes. In the late ’90s, solvers for mixed-integer linear programs saw an increase in performance due to the incorporation of general- purpose cutting planes. In this thesis, we deepen our understanding of a classical cutting planes algorithm, develop a strengthening technique, and two new cutting planes for MINLPs. We first show that Veinott’s supporting hyperplane algorithm is a particular case of Kelley’s cutting plane algorithm. We further extend the applicability of Veinott’s supporting hyperplane algorithm to solve convex problems repre- sented by non-convex functions. We then develop a technique to strengthen cutting planes for non-convex MINLPs. Many cuts for non-convex MINLPs strongly rely on the domain of the variables: tighter bounds produce tighter cuts. Using the point to be separated, we show that we can restrict the feasible region and still ensure the validity of the resulting cutting plane. Finally, we develop two intersection cuts for non-convex MINLP. The first one is a technique to construct S-free sets for any factorable MINLP. For the second one, we show how to build maximal quadratic-free sets, from which we compute intersection cuts. These last cuts reduce the average running time of the solver SCIP by 20% on hard MINLPs.

2. Enhanced Predictions and Structure Exploitation in Branch-and-Bound

   Gerald Gamrath

   TU Berlin, Mar 2020

   Abs DOI

   Mixed-integer linear programming (MIP) is an extremely successful tool to solve real-world optimization problems to optimality. The core algorithm used by state-of-the-art MIP solvers is the branch-and-bound method. It consists of two primary operations: branching splits a problem into smaller subproblems, and bounding uses upper and lower bounds to eliminate subproblems that can be proven not to contain improved solutions. In this thesis, we present methods that improve the branch-and-bound algorithm in both regards. Most branching rules base their decisions on the predicted effect of the split of the subproblems. Since a good prediction can substantially reduce the number of subproblems that need to be processed, the first methods we discuss are focusing on the prediction quality. In order to perform a thorough computational analysis of the newly presented branching rules, we introduce the fair node number, a new measure for the quality of branching decisions. We present strong branching with domain propagation, which improves the dual bound predictions of strong branching by taking implications of the branching decision into account. Additionally, we propose different variants of lookahead branching, which not only consider the effects of the split on the created subproblems, but also regard how those subproblems can be split further. Besides prediction quality, we focus on ways to improve the branch-and-bound method by exploiting structures in MIP instances. We present improvements of common MIP branching rules that exploit dual degeneracy, i.e., the presence of multiple LP optima, to improve prediction quality and reduce branching effort. We introduce cloud diameter branching, a branching rule based solely on degeneracy information, and degeneracy-aware hybrid branching, a rule that adjusts the importance of different measures based on the current degeneracy. Our novel branching on multi-aggregated variables rule splits the problem by branching on a general disjunction corresponding to multi-aggregation structures. To improve the bounding step, we present three structure-driven fix-and-propagate heuristics, which exploit structures present in many MIP instances to predict the impact of variable fixings and construct feasible solutions before the branch-and-bound process starts. Implementations of the methods presented in this thesis are available in source code in the MIP solver SCIP 7.0. We present the results of extensive computational experiments that we conducted to demonstrate their effectiveness.

3. Tighter Relaxations in Mixed-Integer Nonlinear Programming

   Benjamin Müller

   TU Berlin, Mar 2020

   Abs DOI

   Mixed-integer nonlinear programming (MINLP) is one of the most important classes of mathematical optimization problems that combines difficulties from mixed-integer linear programming and nonlinear programming, namely optimizing over a set that is described by integrality, linear, and nonlinear restrictions. This class of optimization problems is essential when constructing accurate models of real-world applications such as energy production and distribution, logistics, engineering design, manufacturing, and fields in chemical and biological sciences. To the best of our knowledge, all state-of-the-art algorithms for solving nonconvex MINLPs to global optimality are based on branch and bound. The performance of these algorithms mainly depends on tight relaxations of a MINLP that are refined throughout a tree search. For this reason, the contribution of this thesis is to present new methods to construct and strengthen relaxations for mixed-integer nonlinear programs. One application of MINLP is the recursive circle packing problem (RCPP), which arises in the tube industry when packing pipes into rectangular containers. Solving a compact formulation for the RCPP is entirely out of reach for state-of-the-art MINLP solvers because relaxations for this problem are known to be weak. To construct significantly tighter relaxations, we present an exact reformulation of the RCPP that is based on a Dantzig-Wolfe decomposition of a nonconvex MINLP formulation. We use column generation techniques to design an algorithm that solves the continuous relaxation of the reformulation to global optimality. This relaxation is substantially tighter than relaxations for a compact MINLP formulation, which enables us to solve 287 out of 800 instances to global optimality that could not be solved so far. The most fundamental ingredient in MINLP solvers is the well-known McCormick relaxation for a product of two variables x and y over a box-constrained domain. This relaxation is far from being tight if the feasible region of a MINLP and its convexification projected in the x-y-space is a strict subset of the box. We develop an algorithm that solves a sequence of linear programs to compute globally valid inequalities on x and y in a similar fashion as optimization-based bound tightening. These valid inequalities enable us to exploit polyhedral results from the literature to tighten the classic McCormick relaxation. Additionally, we present two novel propagation algorithms that compute stronger bounds for x, y, and xy. The resulting implementation reduces the average running time by 36% on difficult MINLPs. Due to both theoretical and practical considerations, relaxations of MINLPs are usually required to be convex. Nonetheless, current optimization solvers improved tremendously during the last decades and are nowadays able to solve problems with a moderate presence of nonconvexities. This progress opens the door for the use of potentially tighter relaxations that contain only a few nonconvexities. Such a nonconvex relaxation can be obtained via the aggregation of constraints: a surrogate relaxation. These relaxations were actively studied for linear integer programs in the 70s and 80s, but they have been scarcely considered since. We revisit these relaxations in a MINLP setting and show the computational benefits and challenges they can have. Additionally, we study a generalization of such relaxation that allows for multiple aggregations simultaneously and present the first algorithm in the literature that is capable of computing the best set of aggregations. We propose a multitude of computational enhancements for improving its practical performance and evaluate the algorithm’s ability to generate tight relaxations through extensive computational experiments. Our results show that we are able to improve the best known bounds for unsolved instances and decrease the average gap by a factor of two on difficult instances. Finally, we present the concept of variable holes for nonconvex MINLPs. Due to the presence of nonconvex nonlinear constraints, the set of feasible assignments of a variable can be disconnected. The resulting forbidden regions are called variable holes and can be viewed as a generalization of integrality restrictions. By exploiting these holes, it is possible to strengthen the relaxation of a MINLP by applying techniques that have been exclusively developed for integer variables to continuous variables. Unfortunately, computing a variable hole is in general NP-hard. Still, for many MINLPs, it is enough to consider relaxations that are described by few constraints to detect variable holes. Based on this observation, we develop three algorithms that are capable of computing variable holes for practical instances. Our computational study shows that integrating variable holes into pseudo cost branching rules decreases the average running time by 62% on affected instances.

2018

1. Presolving techniques and linear relaxations for cumulative scheduling

   Stefan Heinz

   TU Berlin, May 2018

   Dissertationspreis 2019 der Gesellschaft für Operations Research

   Abs DOI

   In the mathematical optimization community the term scheduling usually describes the computation of a sequential plan for a set of jobs w.r.t. a set of side conditions such as precedence constraints and resource restrictions. Thereby, a certain objective should be fulfilled which can be for example to minimize the latest completion time of all jobs. The sequential plan can be an ordering of the jobs or in case of this dissertation a schedule which assigns a start time to each job. Many scheduling problems can be modeled and solved as a constraint program as well as a mixed-integer (linear) program. Both approaches have their advantages and disadvantages which are often complementary. In this dissertation we use a hybrid approach, called constraint integer programming, to solve scheduling problems. We focus on scheduling problems which contain a cumulative resource structure: the available resources are renewable and can be shared between jobs which have to be scheduled non-preemptively. We define the class of energy-based propagation algorithms which are inference algorithms for the cumulative resource structure using volume arguments to infer bounds on the start time and the completion time of a job. Many of the known propagation algorithms for the cumulative resource structure, such as time-tabling, edge-finding, time-tabling edge-finding, and energetic reasoning, belong to this class. For this class we develop explanations for their inferred bound changes. These explanations are used during the analyzes of infeasible sub-problem to retrieve additional (redundant) constraints which help to solve a particular problem more quickly. This concept generalizes known explanations for propagation algorithms for the cumulative resource structure. In addition we show that each energy-based propagation algorithm implies a linear relaxation for the cumulative resource structure with optional jobs. For current state-of-the-art mixed-integer programming solvers presolving is an important feature. During presolving, the original problem is reformulated into a hopefully easier-to-solve problem. One aim is to remove redundant variables and constraints. For the cumulative resource structure we present several presolving techniques generalizing the concept of dual reductions, which is known for mixed-integer programs to shrink a problem formulation, to constraint programs. This techniques allows us to remove feasible or even optimal solutions from the solution space as long as one optimal solution remains in case that the problem is feasible. Using this idea we develop several dual reduction steps for the cumulative resource structure. These reductions enable the removal of jobs from a cumulative resource with the knowledge that this job can be scheduled independently of the schedule for the remaining jobs. In a computational study, we analyze the impact of the presolving techniques for the cumulative constraint and the linear relaxations for the cumulative constraint with optional jobs. Therefore, we use two problem classes which are resource-constrained project scheduling problems and resource allocation and scheduling problem.

2017

1. Exploiting structure in non-convex quadratic optimization and gas network planning under uncertainty

   Jonas Schweiger

   TU Berlin, Feb 2017

   Dissertationspreis 2018 der Gesellschaft für Operations Research

   Abs DOI

   The amazing success of computational mathematical optimization over the last decades has been driven more by insights into mathematical structures than by the advance of computing technology. In this vein, we address applications, where nonconvexity in the model and uncertainty in the data pose principal difficulties. The first part of the thesis deals with non-convex quadratic programs. Branch&Bound methods for this problem class depend on tight relaxations. We contribute in several ways: First, we establish a new way to handle missing linearization variables in the well-known Reformulation-Linearization-Technique (RLT). This is implemented into the commercial software CPLEX. Second, we study the optimization of a quadratic objective over the standard simplex or a knapsack constraint. These basic structures appear as part of many complex models. Exploiting connections to the maximum clique problem and RLT, we derive new valid inequalities. Using exact and heuristic separation methods, we demonstrate the impact of the new inequalities on the relaxation and the global optimization of these problems. Third, we strengthen the state-of-the-art relaxation for the pooling problem, a well-known non-convex quadratic problem, which is, for example, relevant in the petrochemical industry. We propose a novel relaxation that captures the essential non-convex structure of the problem but is small enough for an in-depth study. We provide a complete inner description in terms of the extreme points as well as an outer description in terms of inequalities defining its convex hull (which is not a polyhedron). We show that the resulting valid convex inequalities significantly strengthen the standard relaxation of the pooling problem. The second part of this thesis focusses on a common challenge in real world applications, namely, the uncertainty entailed in the input data. We study the extension of a gas transport network, e.g., from our project partner Open Grid Europe GmbH. For a single scenario this maps to a challenging non-convex MINLP. As the future transport patterns are highly uncertain, we propose a robust model to best prepare the network operator for an array of scenarios. We develop a custom decomposition approach that makes use of the hierarchical structure of network extensions and the loose coupling between the scenarios. The algorithm used the single-scenario problem as black-box subproblem allowing the generalization of our approach to problems with the same structure. The scenario-expanded version of this problem is out of reach for today’s general-purpose MINLP solvers. Yet our approach provides primal and dual bounds for instances with up to 256 scenarios and solves many of them to optimality. Extensive computational studies show the impact of our work.

2015

1. Exact and Fast Algorithms for Mixed-Integer Nonlinear Programming

   Ambros Gleixner

   TU Berlin, Feb 2015

   2nd reviewer

   Abs DOI

   Mixed-integer nonlinear programming (MINLP) comprises the broad class of finite-dimensional mathematical optimization problems from mixed-integer linear programming and global optimization. The combination of the two disciplines allows us to construct more accurate models of real-world systems, while at the same time it increases the algorithmic challenges that come with solving them. This thesis presents new methods that improve the numerical reliability and the computational performance of global MINLP solvers. Since state-of-the-art algorithms for nonconvex MINLP fundamentally rely on solving linear programming (LP) relaxations, we address numerical accuracy directly for LP by means of LP iterative refinement: a new algorithm to solve linear programs to arbitrarily high levels of precision. The thesis is supplemented by an exact extension of the LP solver SoPlex, which proves on average 1.85 to 3 times faster than current state-of-the-art software for solving general linear programs exactly over the rational numbers. These methods can be generalized to quadratic programming. We study their application to numerically difficult multiscale LP models for metabolic networks in systems biology. To improve the computational performance of LP-based MINLP solvers, we show how the expensive, but effective, bound-tightening technique called optimization-based bound tightening can be approximated more efficiently via feasibility-based bound tightening. The resulting implementation increases the number of instances that can be solved and reduces the average running time of the MINLP solver SCIP by 17-19% on hard mixed-integer nonlinear programs. Last, we present branching rules that exploit the presence of nonlinear integer variables, i.e., variables both contained in nonlinear terms and required to be integral. The new branching rules prefer integer variables when performing spatial branching, and favor variables in nonlinear terms when resolving integer infeasibility. They reduce the average running time of SCIP by 17% on affected instances. Most importantly, all of the new methods enable us to solve problems which could not be solved before, either due to their numerical complexity or because of limited computing resources.

2014

1. Heuristic algorithms in global MINLP solvers

   Timo Berthod

   TU Berlin, Feb 2014

   2nd reviewer, Dissertationspreis 2015 der Gesellschaft für Operations Research

   Abs

   n the literature for mixed integer programming, heuristic algorithms (particularly primal heuristics) are often considered as stand-alone procedures; in that context, heuristics are treated as an alternative to solving a problem to proven optimality. This conceals the fact that heuristic algorithms are a fundamental component of state-of-the-art global solvers for mixed integer linear programming (MIP) and mixed integer nonlinear programming (MINLP). In the present thesis, we focus on this latter aspect; we study heuristic algorithms that are tightly integrated within global MINLP solvers and analyze their impact on the overall solution process. Our contributions comprise generalizations of primal heuristics for MIP towards MINLP as well as novel ideas for MINLP primal heuristics and for heuristic algorithms to take branching decisions and to collect global information in MIP. These are: - Shift-and-Propagate, a novel propagation heuristic for MIP that does not require the solution to an LP relaxation, - a generic way to generalize large neighborhood search (LNS) heuristics from MIP to MINLP, - an Objective Feasibility Pump heuristic for nonconvex MINLP that uses second-order information and a dynamic selection of rounding procedures, - RENS, an LNS start heuristic for MINLP that optimizes over the set of feasible roundings of an LP solution, - Undercover, an LNS start heuristic for MINLP that solves a largest sub-MIP of a given MINLP, - Rapid Learning, a heuristic algorithm to generate globally valid conflict constraints for MIPs, - Cloud Branching, a heuristic algorithm that exploits dual degeneracy to reduce the number of candidates for branching variable selection. Additionally, we propose a new performance measure, the primal integral, that captures the benefits of primal heuristics better than traditional methods. In our computational study, we compare the performance of the MIP and MINLP solver SCIP with and without primal heuristics on six test sets with altogether 983 instances from academic and industrial sources, including our project partners ForNe, SAP, and Siemens. We observe that heuristics improve the solver performance regarding all measures that we used - by different orders of magnitude. We further see that the harder a problem is to solve to global optimality, the more important the deployment of primal heuristics becomes. The algorithms presented in this thesis are available in source code as part of the solver SCIP, of which the author has been a main developer for the last years. Methods described in this thesis have also been re-implemented within several commercial and noncommercial MIP and MINLP software packages, including Bonmin, CBC, Cplex, Gams, Sulum, and Xpress.

2. Gas network optimization by MINLP

   Jesco Humpola

   TU Berlin, Feb 2014

   2nd reviewer

   Abs DOI

   One quarter of Europe’s energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euros per kilometer the extension of the European pipeline network is already a multi billion Euro business. The challenging question is how to expand and operate the network in order to facilitate the transportation of specified gas quantities at minimum cost. This task can be formulated as a mathematical optimization problem that reflects to real-world instances of enormous size and complexity. The aim of this thesis is the development of novel theory and optimization algorithms which make it possible to solve these problems. Gas network topology optimization problems can be modeled as nonlinear mixed-integer programs (MINLPs). Such an MINLP gives rise to a so-called active transmission problem (ATP), a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. The key to solving the ATP as well as the overall gas network topology optimization problem and the main contribution of this thesis is a novel domain relaxation of the variable bounds and constraints in combination with a penalization in the objective function. In case the domain relaxation does not yield a primal feasible solution for the ATP we offer novel sufficient conditions for proving the infeasibility of the ATP. These conditions can be expressed in the form of an MILP, i.e., the infeasibility of a non-convex NLP can be certified by solving an MILP. These results provide an efficient bounding procedure in a branch-and-bound algorithm. If the gas network consists only of pipes and valves, the ATP turns into a passive transmission problem (PTP). Although its constraints are non-convex, its domain relaxation can be proven to be convex. Consequently, the feasibility of the PTP can be checked directly in an efficient way. Another advantage of the passive case is that the solution of the domain relaxation gives rise to a cutting plane for the overall topology optimization problem that expresses the infeasibility of the PTP. This cut is obtained by a Benders argument from the Lagrange function of the domain relaxation augmented by a specially tailored pc-regularization. These cuts provide tight lower bounds for the passive gas network topology optimization problem. The domain relaxation does not only provide certificates of infeasibility and cutting planes, it can also be used to construct feasible primal solutions. We make use of parametric sensitivity analysis in order to identify binary variables to be switched based on dual information. This approach allows for the first time to compute directly MINLP solutions for large-scale gas network topology optimization problems. All the research in this thesis has been realized within the collaborative research project "Forschungskooperation Netzoptimierung (ForNe)". The developed software is in use by the cooperation partner Open Grid Europe GmbH. Parts of this thesis have been published in book chapters, journal articles and technical reports. An overview of the topics and solution approaches within the research project is given by Martin et al. (2011) and Fügenschuh et al. (2013). Gas network operation approaches and solution methods are described in detail by Pfetsch et al. (2014) and with a special focus on topology optimization in Fügenschuh et al. (2011). The primal heuristic presented in this thesis is published by Humpola et al. (2014b). The method for pruning nodes of the branch-and-bound tree for an approximation of the original problem is described in Fügenschuh and Humpola (2013) and Humpola et al. (2014a). The Benders like inequality is introduced by Humpola and Fügenschuh (2013).

2013

1. Parallel solution of linear programs

   Edmund Smith

   University of Edinburgh, College of Science & Engineering, Feb 2013

   External reviewer