Lehrstuhl V Diskrete Optimierung

Permanent URI for this collection

http://hdl.handle.net/2003/38232

Browse

Now showing 1 - 16 of 16

Discrete optimal control with dynamic switches : outer approximation and branch-and-bound
(2024) Grütering, Alexandra; Buchheim, Christoph; Meyer, Christian
Many real life applications lead to optimal control problems whose control is given in form of a finite set of switches. These switches can be operated within a given continuous time horizon and admit only a finite number of states. Examples include gear-switches in automotive engineering or valves and compressors in gas networks. Solving optimal control problems with discrete control variables is challenging, and this thesis aims at developing a branch-and-bound algorithm to globally solve such problems. We here focus on parabolic control problems with binary switches that have only finitely many switching points and possibly need to satisfy further combinatorial constraints. When no restrictions on the binary switches are considered, the straightforward continuous relaxations of the binary problems are closely related to the original problems, since any relaxed control can be approximated arbitrarily well by a sequence of binary switches using an increasing number of switchings. However, solving these relaxed problems and rounding the relaxed solution to produce a binary control, often fails when considering natural combinatorial switching constraints, such as, e.g. a minimum time span between two switchings of the same switch, or an upper bound on the total number of switchings. These constraints are typically treated in a heuristic postprocessing. In contrast, the combinatorial switching constraints are at the heart of our proposed branch-and-bound algorithm to globally solve the problems. The natural branching strategy, which fixes the value of the switches in finitely many points, combined with the bounded variation of the switches, guarantees that the non-fixed part of the switching pattern vanishes. Moreover, tight dual bounds are computed by completely describing the convex hull of feasible controls in function space. This description is built by cutting planes lifted from finite-dimensional projections of the set of feasible switches. The convexified problems can be solved by means of outer approximation. In this way, we compute safe dual bounds for the binary control problems, as long as we do not take the discretization error into account. To solve the problems in function space, we estimate the discretization error contained in the bounds. An adaptive refinement strategy is then specified to handle situations where the discretization-independent bound does not exclude that a solution of desired quality might exist in the current branch. Our branch-and-bound returns an ε -optimal solution in finite time for any given tolerance ε>0. Computational results illustrate the strength of our dual bounds and the potential of the proposed branch-and-bound algorithm.
On the complexity of the bilevel minimum spanning tree problem
(2022-06-08) Buchheim, Christoph; Henke, Dorothee; Hommelsheim, Felix
We consider the bilevel minimum spanning tree (BMST) problem where the leader and the follower choose a spanning tree together, according to different objective functions. We show that this problem is NP-hard, even in the special case where the follower only controls a matching. Moreover, we give some evidence that BMST might even remain hard in case the follower controls only few edges. On the positive side, we present a (|V|-1)-approximation algorithm for BMST, where |V| is the number of vertices. Moreover, we show that 2-approximating BMST is fixed-parameter tractable and that, in case of uniform costs on leader's edges, even solving BMST exactly is fixed-parameter tractable. We finally consider bottleneck variants of BMST and settle the complexity landscape of all combinations of sum or bottleneck objective functions for the leader and follower, for the optimistic as well as the pessimistic setting.
The robust bilevel continuous knapsack problem with uncertain coefficients in the follower’s objective
(2022-01-02) Buchheim, Christoph; Henke, Dorothee
We consider a bilevel continuous knapsack problem where the leader controls the capacity of the knapsack and the follower chooses an optimal packing according to his own profits, which may differ from those of the leader. To this bilevel problem, we add uncertainty in a natural way, assuming that the leader does not have full knowledge about the follower’s problem. More precisely, adopting the robust optimization approach and assuming that the follower’s profits belong to a given uncertainty set, our aim is to compute a solution that optimizes the worst-case follower’s reaction from the leader’s perspective. By investigating the complexity of this problem with respect to different types of uncertainty sets, we make first steps towards better understanding the combination of bilevel optimization and robust combinatorial optimization. We show that the problem can be solved in polynomial time for both discrete and interval uncertainty, but that the same problem becomes NP-hard when each coefficient can independently assume only a finite number of values. In particular, this demonstrates that replacing uncertainty sets by their convex hulls may change the problem significantly, in contrast to the situation in classical single-level robust optimization. For general polytopal uncertainty, the problem again turns out to be NP-hard, and the same is true for ellipsoidal uncertainty even in the uncorrelated case. All presented hardness results already apply to the evaluation of the leader’s objective function.
Complexity of bulk-robust combinatorial optimization problems
(2020) Hommelsheim, Felix; Buchheim, Christoph; Stiller, Sebastian
This thesis studies three robust combinatorial optimization problems on graphs. Most robust combinatorial optimization problems assume that the cost of the resources, e.g. edges in a graph, are uncertain. In this thesis, however, we study the so called bulk-robust approach which models the uncertainty in the underlying combinatorial structure. To be more precise, in the bulk-robust model we are given an explicit list of scenarios comprising a set of resources each, which fail if the corresponding scenario materializes. Additionally, we are given a property that we have to obtain such as 'containing a perfect matching', 's-t-connectivity', or 'being connected', which may arise from a fundamental combinatorial optimization problem. The goal of the bulk-robust optimization problem is to find a minimum weight set of resources such that the desired property is satisfied no matter which scenario materializes, i.e. no matter which set of resources from the list is removed. We study the bulk-robust bipartite matching problem, the bulk-robust k-edge disjoint s-t-paths problem, and the bulk-robust minimum spanning tree problem. We investigate the complexity of the three problems and show that most of them are hard to approximate even if the list of scenarios consists of singletons only. We complement these inapproximability results with polynomial-time approximation algorithms that essentially match the hardness results. Furthermore, we present FPT and XP algorithms and consider special graph classes that allow for a polynomial-time exact algorithm.
K-adaptability in stochastic optimization
(2020) Prünte, Jonas; Buchheim, Christoph; Koster, Arie M.C.A.
In dieser Dissertation untersuchen wir eine neue Strategie, um mit stochastischen Optimierungsproblemen umzugehen. Die stochastische Optimierung beschäftigt sich mit Problemen mit unsicheren Parametern. Unter der Annahme, dass die Verteilung dieser unsicheren Parameter bekannt ist, soll der Erwartungswert der Zielfunktion optimiert werden. Wir führen den Min-E-Min-Ansatz ein, bei dem anstatt einer Lösung K Lösungen berechnet werden. Nachdem die Realisierung der unsicheren Parameter beobachtet worden ist, wird die für die Realisierung beste Lösung ausgewählt. Wir untersuchen die Komplexität des Min-E-Min-Problems, indem wir NP-Schwere, parametrisierte Komplexität und Approximationseigenschaften detailliert analysieren. Wir zeigen, dass das Problem NP-schwer und W[2]-schwer ist, im Fall, dass K Teil des Inputs ist, selbst wenn die Menge der zulässigen Lösungen polynomiell von der Eingabegröße abhängt. Für festes K bleibt das Problem NP-schwer, wenn K größer als zwei ist. Zusätzlich beweisen wir, dass die Existenz eines polynomiellen Algorithmus mit einer konstanten Approximationsgüte für das Min-E-Min-Problem impliziert, dass P und NP gleich sind. Für das Min-E-Min-Problem mit kontinuierlicher Verteilung zeigen wir, dass allein das Evaluieren der Zielfunktion #P-schwer ist. Nichtsdestotrotz beweisen wir, dass man solche Probleme lösen kann, indem man die kontinuierliche Verteilung mit einer ausreichend großen Anzahl an Stichproben, welche derselben Verteilung folgen, diskretisiert. Neben den Komplexitätsresultaten stellen wir auch verschiedene exakte Algorithmen, unter anderem einen Branch-and-price-Algorithmus, zur Lösung des Problems vor. In einer ausführlichen experimentellen Untersuchung können wir belegen, dass je nach Situation jeder der vorgestellten Algorithmen am sinnvollsten sein kann. Darüber hinaus stellen wir verschiedene Varianten einer von uns entwickelten Heuristik vor und demonstrieren, dass diese das Min-E-Min-Problem schnell und genau lösen können. Zu guter Letzt betrachten wir auch verwandte Probleme und untersuchen ihre Komplexität.
Relaxation refinement for mixed-integer nonlinear programs with applications in engineering
(2019) Mertens, Nick; Buchheim, Christoph; Liers, Frauke
Lösungsstrategien für Gemischt-Ganzzahlige Nichtlineare Programme (MINLPs) basieren häufig auf einer konvexen Relaxierung der zulässigen Menge. Diese Relaxierung wird benutzt um untere Schranken zu ermitteln und um die Qualität lokaler Lösungen zu beurteilen. In dieser Thesis diskutieren wir verschiedene Ansätze um geeignete Relaxierungen zu konstruieren und zu verbessern. Außerdem analysieren wir diese in Hinblick auf Strenge und Qualität der resultierenden unteren Schranken. Dabei betrachten wir sowohl allgemeine MINLPs als auch spezifische Probleme, die sich aus der Anwendung ergeben. Wir entwickeln ein Schnittebenenverfahren für die konvexe Hülle der zulässigen Menge von relativ allgemeinen MINLPs. Es basiert auf der simultanen Betrachtung von Nebenbedingungen und auf einem konvexen Optimierungsproblem. Dieses Separationsproblem ist nicht-differenzierbar und benötigt die konvexe Einhüllende von Linearkombinationen der Nebenbedingungen. Wir analysieren seine Struktur und Glätte ausführlich und diskutieren passende Lösungsansätze. Außerdem entwickeln wir Approximationen der konvexen Einhüllenden und ein ensprechendes approximatives Separationsproblem. Dieses führt zu schwächeren Resultaten aber zu einer höheren Anwendbarkeit. Das obige Schnittebenenverfahren wird außerdem auf eine Menge von Nebenbedingungen angewendet, die aus bivariaten quadratischen Absolutwertfunktionen besteht. Wir präsentieren allgemeine analytische Hilfsmittel und Konzepte und bestimmen die konvexe Einhüllende für diese Funktionen unter gewissen Voraussetzungen. Diese Klasse von Funktionen wird auch bei der Modellierung von Gasnetzwerken verwendet, was es uns erlaubt den Einfluss des Schnittebenenverfahrens auf Probleme aus der Anwendung zu untersuchen. Schließlich betrachten wir noch ein Beispiel eines optimalen Designproblems aus dem Bereich des Chemieingenieurwesens. Für das Modell einer Destillationskolonne bieten wir eine Reformulierung an und beweisen monotones Verhalten von bestimmten Folgen relevanter Variablen. Reformulierung und Monotonie werden benutzt um die Formulierung der zugehörigen zulässigen Menge zu verbessern. Insbesondere entwickeln wir eine problemspezifische Bound-Tightening-Strategie. Unsere Ergebnisse werden an einigen Testinstanzen computergestützt evaluiert.
Computational recognition of RNA splice sites by exact algorithms for the quadratic traveling salesman problem
(2015-06-03) Fischer, Anja; Fischer, Frank; Jäger, Gerold; Keilwagen, Jens; Molitor, Paul; Grosse, Ivo
One fundamental problem of bioinformatics is the computational recognition of DNA and RNA binding sites. Given a set of short DNA or RNA sequences of equal length such as transcription factor binding sites or RNA splice sites, the task is to learn a pattern from this set that allows the recognition of similar sites in another set of DNA or RNA sequences. Permuted Markov (PM) models and permuted variable length Markov (PVLM) models are two powerful models for this task, but the problem of finding an optimal PM model or PVLM model is NP-hard. While the problem of finding an optimal PM model or PVLM model of order one is equivalent to the traveling salesman problem (TSP), the problem of finding an optimal PM model or PVLM model of order two is equivalent to the quadratic TSP (QTSP). Several exact algorithms exist for solving the QTSP, but it is unclear if these algorithms are capable of solving QTSP instances resulting from RNA splice sites of at least 150 base pairs in a reasonable time frame. Here, we investigate the performance of three exact algorithms for solving the QTSP for ten datasets of splice acceptor sites and splice donor sites of five different species and find that one of these algorithms is capable of solving QTSP instances of up to 200 base pairs with a running time of less than two days.
Bulk-robust assignment problems: hardness, approximability and algorithms
(2017) Bindewald, Viktor; Michaels, Dennis; Kaibel, Volker
This thesis studies robust assignment problems with focus on computational complexity. Assignment problems are well-studied combinatorial optimization problems with numerous practical applications, for instance in production planning. Classical approaches to optimization expect the input data for a problem to be given precisely. In contrast, real-life optimization problems are modeled using forecasts resulting in uncertain problem parameters. This fact can be taken into account using the framework of robust optimization. An instance of the classical assignment problem is represented using a bipartite graph accompanied by a cost function. The goal is to find a minimum-cost assignment, i.e., a set of resources (edges or nodes in the graph) defining a maximum matching. Most models for robust assignment problems suggested in the literature capture only uncertainty in the costs, i.e., the task is to find an assignment minimizing the cost in a worst-case scenario. The contribution of this thesis is the introduction and investigation of the Robust Assignment Problem (RAP) which models edge and node failures while the costs are deterministic. A scenario is defined by a set of resources that may fail simultaneously. If a scenario emerges, the corresponding resources are deleted from the graph. RAP seeks to find a set of resources of minimal cost which is robust against all possible incidents, i.e., a set of resources containing an assignment for all scenarios. In production planning for example, lack of materials needed to complete an order can be encoded as an edge failure and production line maintenance corresponds to a node failure. The main findings of this thesis are hardness of approximation and NP-hardness results for both versions of RAP, even in case of single edge (or node) failures. These results are complemented by approximation algorithms matching the theoretical lower bounds asymptotically. Additionally, we study a new related problem concerning k-robust matchings. A perfect matching in a graph is $k$-robust if the graph remains perfectly matchable after the deletion of any k matching edges from the graph. We address the following question: How many edges have to be added to a graph to make a fixed perfect matching k-robust? We show that, in general, this problem is as hard as both aforementioned variants of RAP. From an application point of view, this result implies that robustification of an existent infrastructure is not easier than designing a new one from scratch.
Combinatorial optimization under ellipsoidal uncertainty
(2017) Ilyina, Anna; Buchheim, Christoph; Mutzel, Petra
We study combinatorial problems with ellipsoidal uncertainty in the objective function concerning their theoretical and practical solvability. Ellipsoidal uncertainty is a natural model when the coefficients are normally distributed random variables. Robust versions of typical combinatorial problems can be very hard to solve compared to their linear versions. Complexity and approaches differ fundamentally depending on whether uncorrelated or correlated uncertainty occurs. We distinguish between these two cases and consider first the unconstrained binary optimization under uncorrelated ellipsoidal uncertainty. For this we develop an algorithm which computes an optimal solution by merely sorting the variables and, correspondingly, has a running time of O(n log n). The algorithm is based on the diminishing returns-property, which is characteristic for submodular functions. We introduce a new and a more general p-norm-uncertainty and show that with only slight modifications the sorting algorithm can be easily applied. We also extend the algorithm to general integer variables, which in this case only leads to a pseudo-polynomial time. The next step to the general case is investigation of problems with arbitrary combinatorial sets X ⊆ {0, 1}n under uncorrelated ellipsoidal uncertainty. For this case we embed the O(n log n)-algorithm for the unconstrained binary problems into a Lagrangean decomposition approach. The approach separates the objective function from the combinatorial structure applying Lagrangean relaxation to some artificial connecting constraints. This creates two subproblems, one of which is the linear version of the combinatorial problem and the other one is just the unconstrained binary uncorrelated problem, which can be solved using the O(n log n)-algorithm. The solutions of the subproblems are used to obtain primal and dual bounds which are used in a branch and bound-approach. The approach shows an excellent performance in practice. In the correlated case already the unconstrained binary problem turns out to be strongly NP-hard. Here we also define a branch and bound-approach, now with lower bounds determined by underestimation of the given ellipsoid with certainly defined axis-parallel ellipsoids. We use this idea to extend the decomposition approach to general combinatorial problems under correlated uncertainty. In contrast to the uncorrelated case the uncertain subproblem of the decomposition is here strongly NP-hard in itself. We solve it approximately using the developed underestimators which are determined in a preprocessing step. The approach offers room for improvement concerning in the primal extent a faster computation of the underestimators, which is done by solving semidefinite programs.
A coordinate ascent method for solving semidefinite relaxations of non-convex quadratic integer programs
(2017) Montenegro Chingal, Jessica Maribel; Buchheim, Christoph; Wiegele, Angelika
In this thesis we propose a coordinate ascent method for a class of semidefinite programming problems arising in the reformulation of non-convex quadratic optimization problems where the variables are restricted to subsets of the integer numbers. It is known that non-convex quadratic integer problems are NP-hard for two reasons: the non-convexity of the objective function and the restrictions of integrality on the variables. Therefore no polynomial time algorithm is known for solving this class of optimization problems. Standard techniques for addressing these probles are reformulations through linearization or semidefinite programming (SDP), aiming at producing tight convex relaxations of the problem that are then embedded into branch-and-bound schemes. Semidefinite programming has been proved to be a powerful tool for constructing strong convex relaxations for several combinatorial optimization problems, however at increased computational cost. Interior-point based algorithms are the classical solution approaches for semidefinite programming problems, although it turns out that large scale instances are beyond the scope of these algorithms. Buchheim and Wiegele have devised an SDP-based branch-and-bound algorithm (Q-MIST) for a class of mixed-integer quadratic programming problems, that contains the quadratic problems we are considering here. The semidefinite relaxations are solved using the SDP solver CSDP, which based on interior point methods. It has been proved experimentally that this approach outperforms the state-of-the-art non convex mixed-integer programming software COUENNE. Recently, Dong has studied the same class of quadratic problems, and has proposed a semi-infinite convex relaxation. The resulting separation problem is solved by a primal-barrier coordinate minimization algorithm. In this thesis, we have developed an algorithm that on the one hand exploits the structure of the semidefinite relaxations proposed by Buchheim and Wiegele, namely a small total number of active constraints and constraint matrices characterized by a low rank. On the other hand, our algorithm exploits this special structure by solving the dual problem of the semidefinite relaxation, using a barrier method in combination with a coordinate-wise exact line search, motivated by the algorithm presented by Dong. The main ingredient of our algorithm is the computationally cheap update at each iteration and an easy computation of the exact step size. Compared to interior point methods, our approach is much faster in obtaining strong dual bounds. Moreover, no explicit separation and re-optimization is necessary even if the set of primal constraints is large, since in our dual approach this is covered by implicitly considering all primal constraints when selecting the next coordinate. Even more, the structure of the problem allows us to perform a plane search instead of a single line search, this speeds up the convergence of the algorithm. Finally, linear constraints are easily integrated into the algorithmic framework. We have performed experimental comparisons on randomly generated instances, showing that our approach significantly improves the performance of Q-MIST when compared with CSDP and outperforms other specialized global optimization software, such as BARON.
Min-max-min robust combinatorial optimization
(2016) Kurtz, Jannis; Buchheim, Christoph; Schöbel, Anita
In this thesis we introduce a robust optimization approach which is based on a binary min-max-min problem. The so called Min-max-min Robust Optimization extends the classical min-max approach by calculating k different solutions instead of one. Usually in robust optimization we consider problems whose problem parameters can be uncertain. The basic idea is to define an uncertainty set U which contains all relevant problem parameters, called scenarios. The objective is then to calculate a solution which is feasible for every scenario in U and which optimizes the worst objective value over all scenarios in U. As a special case of the K-adaptability approach for robust two-stage problems, the min-max-min robust optimization approach aims to calculate k different solutions for the underlying combinatorial problem, such that, considering the best of these solutions in each scenario, the worst objective value over all scenarios is optimized. This idea can be modeled as a min-max-min problem. In this thesis we analyze the complexity of the afore mentioned problem for convex and for discrete uncertainty sets U. We will show that under further assumptions the problem is as easy as the underlying combinatorial problem for convex uncertainty sets if the number of calculated solutions is greater than the dimension of the problem. Additionally we present a practical exact algorithm to solve the min-max-min problem for any combinatorial problem, given by a deterministic oracle. On the other hand we prove that if we fix the number of solutions k, then the problem is NP-hard even for polyhedral uncertainty sets and the unconstrained binary problem. For the case when the number of calculated solutions is lower or equal to the dimension we present a heuristic algorithm which is based on the exact algorithm above. Both algorithms are tested and analyzed on random instances of the knapsack problem, the vehicle routing problem and the shortest path problem. For discrete uncertainty sets we show that the min-max-min problem is NP-hard for a selection of combinatorial problems. Nevertheless we prove that it can be solved in pseudopolynomial time or admits an FPTAS if the min-max problem can be solved in pseudopolynomial or admits an FPTAS respectively.
Continuous optimization methods for convex mixed-integer nonlinear programming
(2015) Trieu, Long; Buchheim, Christoph; Meyer, Christian
The topic of this dissertation is the design of fast branch-and-bound algorithms that use intelligently adapted approaches from continuous optimization for solving convex mixed-integer nonlinear programming problems. This class of optimization problems is NP-hard and polynomial-time algorithms for these problems are therefore unlikely to exist (unless P=NP). The importance of this class is highlighted by the fact that many real-world applications can be modeled as a (convex) mixed-integer nonlinear programming problem. Currently, there are several standard techniques such as outer approximation that are used within recent state-of-the-art software. Although all these algorithms include sophisticated improvements such as primal heuristics and effective preprocessing, they do not take into account the large gap between the algorithmic performance of NLP and IP solvers. While NLP solvers are well-engineered for large-scale problems, MIP problems of similar sizes are by far harder to solve in practice. Therefore, when using NLP techniques within MIP solvers, these NLP algorithms have to be adjusted to handle small-size instances effectively. Taking this problem into account, we present three branch-and-bound algorithms, based on a former work by Buchheim et al. (2012) on unconstrained convex quadratic integer programming problems. The main strategies used within this branch-andbound framework include extensive preprocessing and fast incremental computations, aiming at a very fast enumeration of the nodes. The first algorithm we present is designed to solve convex quadratic mixed-integer programming problems with linear inequality constraints and is based on a new feasible active set algorithm applied to the dual of the continuous relaxation. This active set algorithm is tailored for the continuous problem and fully exploits its structure. Furthermore, a warmstarting procedure is used to reduce the number of active set iterations per node. The second algorithm we introduce is an approach called quadratic outer approximation for solving box-constrained convex mixed-integer nonlinear programming problems. It extends the classical outer approximation by using quadratic underestimators leading to a faster convergence in practice. Finally, the last algorithm we devise is aimed at a class of mean-risk portfolio optimization problems that can be modeled as convex mixed-integer programming problems with a single linear budget constraint. For this application we propose a branch-and-bound scheme using a modified Frank-Wolfe type algorithm to solve the node relaxations. Similarly to the branch-and-bound algorithms mentionded above we exploit the simplicity of the relaxations to enumerate the nodes as quickly as possible rather than focussing on strong dual bounds. We implemented all three algorithms and compared their performance with several state-of-the art approaches. Our extensive computational studies show that all new approaches presented in this thesis are able to effectively solve large classes of real-world instances.
Combinatorial optimization with one quadratic term
(2014) Klein, Laura; Buchheim, Christoph; Liers, Frauke
Diese Arbeit befasst sich mit einer neuen Herangehensweise für binäre kombinatorische Optimierungsprobleme. Die wesentliche Idee hierbei ist, die Anzahl der quadratischen Terme in der Zielfunktion auf einen einzigen zu beschränken, und das durch eine Linearisierung entstehende Polyeder zu analysieren. Für diesen Ansatz gibt es mehrere Motivationsgründe. Im Allgemeinen ist das ursprüngliche Problem mit beliebig vielen quadratischen Termen NP-schwer. Doch obwohl eine gute polyedrische Beschreibung mit schnellen Separierungsroutinen die Optimierung in einem Branch-and-Cut-Verfahren signifikant beschleunigen könnte, gibt es bislang nur wenige Erkenntnisse zur polyedrischen Struktur des binären quadratischen Optimierungsproblems. Betrachtet man das reduzierte Problem mit einem quadratischen Term, dann ist eine effiziente Optimierung möglich, falls die zugrundeliegende lineare Version effizient lösbar ist. Somit können hier auch die facettendefinierenden Ungleichungen effizient separiert werden. Darüberhinaus bleiben alle zulässigen Ungleichungen des reduzierten Problems zulässig für das ursprüngliche Problem. In Kombination bedeutet dies, dass Erkenntnisse zur Facettenstruktur des Problems mit einem quadratischen Term direkt zu einer verbesserten polyedrische Beschreibung des Ursprungsproblems führen. Für eine praktische Anwendung dieses theoretischen Ansatzes betrachten wir verschiedene konkrete Optimierungsprobleme mit einem quadratischen Term und analysieren deren jeweilige polyedrische Struktur, die sich nach der Linearisierung ergibt. Konkret betrachten wir das Minimale Spannwald- und das Minimale Spannbaumproblem, das Minimale Branching- und das Minimale Arboreszenzproblem, das Minimale Assignmentproblem und das Maximale Matchingproblem. Für jedes dieser Optimierungsprobleme leiten wir neue Klassen von facettendefinierenden Ungleichungen her. Außerdem präsentieren wir für das Minimale Spannwald- und das Minimale Spannbaumproblem eine vollständige Beschreibung der jeweiligen Polytope. Für die verwandten gerichteten Probleme, das Minimale Branching- und das Minimale Arboreszenzproblem, zeigen wir zwar einerseits einige Gemeinsamkeiten mit den ungerichteten Problemen, andererseits aber auch, dass sich die polyedrischen Strukturen im gerichteten Fall durch die zusätzlichen Gradbedingungen deutlich verkomplizieren. Bei der Untersuchung des Minimalen Assignmentproblems mit einem quadratischen Term stellen wir nicht nur die Vermutung über die vollständige polyedrische Beschreibung auf, sondern kommen insbesondere zu der überraschenden Erkenntnis, dass bereits ein einziger quadratischer Term genügen kann, um die Anzahl der Facetten von polynomiell auf exponentiell zu erhöhen. Die größte Vielfalt an Facettenklassen leiten wir für das Polyeder des Maximalen Matchingproblems mit einem quadratischen Term her. Wir zeigen jedoch auch, dass diese noch nicht genügen, um die vollständige Beschreibung des Polyeders zu erhalten. Da die meisten der hergeleiteten Facettenklassen von exponentieller Größe sind, leiten wir verschiedene Routinen für eine polynomielle Separierung her. Unsere exemplarischen Rechenergebnisse für das quadratische Minimale Spannwald- und das quadratische Minimale Spannbaumproblem zeigen die praktische Relevanz unseres Ansatzes.
Exact methods for nonlinear combinatorial optimization
(2014-09-05) Baumann, Frank; Buchheim, Christoph; Mutzel, Petra
We consider combinatorial optimization problems with nonlinear objective functions. Solution approaches for this class of problems proposed so far are either highly problem-specific or they apply generic algorithms for constrained nonlinear optimization, which often does not yield satisfactory results in practice. Our aim is to develop, implement and experimentally evaluate exact algorithms that address the nonlinearity of the objective function and at the same time exploit the underlying combinatorial structure of the problem. To this end we follow two approaches. The first combines good polyhedral descriptions of the objective function and the feasible set in a branch and cut-algorithm. The second approach is based on Lagrangean decomposition. By decomposing the original problem into an unconstrained nonlinear problem and a linear combinatorial problem, we are able to compute strong dual bounds for the optimal value. The computation of lower bounds is then embedded into a branch and bound-algorithm. For many applications there already exist efficient algorithms for the combinatorial subproblem, thus an important aspect of this thesis is the study of the corresponding unconstrained nonlinear subproblems. Both approaches have the advantage that they can easily be adapted to a wide range of nonlinear combinatorial problems.We devise both polyhedral and decomposition- based algorithms for submodular applications from wireless network design and portfolio optimization and evaluate their performance experimentally. Exploiting the equivalence between unconstrained binary quadratic optimization and the maximum cut problem gives rise to a branch and cut-algorithm for quadratic combinatorial problems which we use to compute optimal layouts of tanglegrams, an application from computational biology. Additionally we study the effect of quadratic reformulation of linear constraints, both theoretically and experimentally. The last class of nonlinear combinatorial problems we consider are two-scenario problems. Here we propose a new technique to compute lower bounds in the unconstrained subproblem of the decomposition. Our computational study of the two-scenario minimum spanning tree problem shows that the new Lagrangean decomposition-based algorithm is able to solve significantly larger instances than the standard linearization approach.
path-constrained network flows
(2007-04-25T11:12:16Z) Martens, Maren; Skutella, Martin; Eisenbrand, Friedrich
This thesis focuses on approximation algorithms and complexity assessments concerning network flows. It deals with various network flow problems with path restrictions. These restrictions cover the number of paths that are used to route commodities as well as the amount of flow that is routed along a single path or the path's length. Concerning the first restriction we study the unsplittable flow problem-a generalization of the NP-hard edge-disjoint paths problem. Given a network with commodities that must be routed from their sources to their sinks, the unsplittable flow problem forbids each commodity to use more than one path. For this problem we prove a new lower bound on the performance guarantee of randomized rounding which so far belongs to the best approximation algorithms known for this problem. Further, we present an interesting relation between unsplittable flows and classical (splittable) multicommodity flows in the case that all commodities share a common source: Each single source multicommodity flow can be represented as a convex combination of unsplittable flows of congestion at most 2. Further, we combine different path restrictions from the ones mentioned above. In the k-splittable flow problem with path capacities, we study the NP-hard problem that each commodity may be sent along a limited number of paths while the flow value of each path is bounded. This yields a generalization of the unsplittable flow problem, but we show how one can obtain the same asymptotic approximation ratios. For the length-bounded k-splittable flow problem, we consider the single commodity case and develop a constant factor approximation algorithm. A crucial characteristic of network flows occurring in real-world applications is flow variation over time and the fact that flow does not travel instantaneously through a network but requires a certain amount of time to travel through each arc. Both characteristics are captured by "flows over time" which specify a flow rate for each arc and each point in time. We consider the quickest single commodity k-splittable flow problem and give a constant factor approximation algorithm for it. So far only results for k-splittable flows as well as for length-bounded flows and flows over time have been known, but nothing was known for combinations of them. Bounding the flow value of each path is also interesting in the classical maximum s-t-flow problem. We study the case that each path may carry at most one unit of flow and prove that this restriction makes the maximum s-t-flow problem strongly NP-hard. In contrast to the classical maximum s-t-flow problem, the fractional and the integral problem diverge strongly with the new restriction. For the integral problem, we even prove APX-hardness. We develop an FPTAS for the fractional problem and an O(log m)-approximation algorithm for the integral one. (Here, m is the number of arcs in the network under consideration.) Similar results emerge for the multicommodity case. For the objective to find a maximum integral multicommodity flow our asymptotic approximation ratio of O(m^{0.5}) is proven to be best possible, unless P = NP.
Evacuation by earliest arrival flows
(2007-04-05T11:37:00Z) Baumann, Nadine; Skutella, Martin; Köhler, Ekkehard
Als Evakuierungsprobleme mittels dynamischer Flüsse werden in der Literatur unter Anderem das Quickest Transshipment Problem, das Earliest Arrival Transshipment Problem und das Earliest Arrival Maximalflussproblem betrachtet. In der vorliegenden Arbeit wird sowohl ein exakter polynomialer Algorithmus für das Earliest Arrival Transshipment Problem angegeben als auch das Earliest Arrival Maximalflussproblem für Netzwerke mit flussabhängigen Fahrzeiten untersucht. Dabei wird festgestellt, dass in solchen Netzwerken die Earliest Arrival Eigenschaft verletzt wird. Daher wird ein abgewandeltes Problem untersucht, bei dem die Verspätung minimiert wird. Im Bereich der Datenevakuierung ist zu beachten, dass die Kopierfähigkeit eines Datums die Problemstellung verändert. Für dieses Problem wurden Algorithmen für Datenflüsse auf Pfaden angegeben.

Browse

Recent Submissions