Sprungmarken

Servicenavigation

Hauptnavigation

Sie sind hier:

Hauptinhalt

Kolloquium Optimierung und Operations Research

Logo Kolloquium "Optimierung und Operations Research"Das Kolloquium "Optimierung und Operations Research" wird in Kooperation der Fakultät Wirtschaftswissenschaften, der Fakultät für Informatik sowie der Fakultät Mathematik durchgeführt (Veranstalter: Prof. Dr. Christoph Buchheim, JProf. Dr. Dennis Michaels, Prof. Dr. Petra Mutzel und Prof. Dr. Peter Recht). Interessierte Hörerinnen und Hörer sind herzlich willkommen! Die Vorträge richten sich auch an Studierende der Wirtschaftswissenschaften, Wirtschaftsmathematik, Informatik und Mathematik.

Hier findet sich eine Übersicht der in den vergangenen Semestern und Jahren im Rahmen des Kolloquiums von den jeweiligen Referenten gehaltenen Vorträge (i.d.R. mit einer kurzen Zusammenfassung):

 


2002   2003   2004   2005   2006   2007   2008   2009   2010   2011   2012   2013   2014   2015   2017


2017

Termin Referent Thema
2017-09-18
16:00
M E19
Prof. Dr. Oliver Schaudt
(RWTH Aachen)

A 7/3-Approximation Algorithm for Cluster Vertex Deletion

The cluster vertex deletion problem is to delete a minimum cost set of vertices from a given vertex-weighted graph in such a way that the resulting graph has no induced path on three vertices. In other words, the remaining graph is the disjoint union of complete graphs, so-called clusters. This problem is a special case of the vertex cover problem on a 3-uniform hypergraph, and thus has a straightforward 3-approximation algorithm. Very recently, You, Wang, and Cao described an efficient 5/2-approximation algorithm for the unweighted version of the problem. Our main result is a 7/3-approximation algorithm for arbitrary weights, using the local ratio technique. We further conjecture that the problem admits a 2-approximation algorithm and give some support for the conjecture. This is in sharp constrast with the fact that the similar problem of deleting vertices to eliminate all triangles in a graph is known to be UGC-hard to approximate to within a ratio better than 3, as proved by Guruswami and Lee. Joint work with Samuel Fiorini and Gwenael Joret.

2017-05-30
16:00
SRG I / 1.023
Volker Schmitz
(Axa AG, Köln)
Die Zinszusatzreserve in der Lebensversicherung

 

2015

Termin Referent Thema
2015-11-24
12:15
M 911
Dr. Timm Oertel
(Department Mathematik /
ETH Zürich)

Center-points: Link between Discrete Geometry and Optimization

In this talk, I will consider mixed-integer convex minimization problems. First, I will present optimality conditions for this class of optimization problems. Then, I will introduce the concept of center-points, a generalization of the median from the one dimensional space to vector spaces. Through the theory of center-points I will show how to extend the general cutting plane scheme from the continuous setting to the mixed-integer setting. Further, I will present several properties of center-points and how to compute them approximately.

2015-11-11
11:11
SRG I / 3.031
Matthias Walter
(Fakultät für Mathematik /
Universität Magdeburg)

Investigating Polyhedra by Oracles

The software IPO is presented which investigates a polyhedron P given by means of an optimization oracle, e.g., a mixed-integer hull and a MIP solver. It detects all equations, can check adjacency of vertices, and compute some facets valid for P in exact arithmetic. The facets are produced in such a way that they are helpful in optimizing a given objective function, using target cuts introduced by Buchheim, Liers, and Oswald in 2008. In contrast to usual convex-hull algorithms which produce the entire description, but run out of resources for small dimensions already, IPO can handle much larger dimensions.

2015-11-10
12:15
M 911
Sven Wiese
(Department of Electrical, Electronic
and Information Engineering /
University of Bologna)

Indicator constraints in Mixed Integer Programming

In this talk we present a review and some extensions on how indicator constraints in Mixed Integer Programming (MIP) are handled. In particular, we explore the disjunctive programming paradigm in this context, opposed to the classical big-M method. In the case of Mixed Integer Linear Programming, a clear relation between the two can be derived. We present some computational results that suggest the use of local information in MIP with Indicator constraints and sketch some ideas in this direction.

2015-11-03
12:00
M 614
Dr. Moritz Mühlenthaler
(Department Informatik /
Universität Erlangen-Nürnberg)

Reconfiguration Problems

A reconfiguration problem is the reachability problem on an interesting class of graphs, namely the solution graphs of a combinatorial problem: Given two solutions to some instance, the task is to decide whether one solution can be transformed into the other via “local” changes while maintaining feasibility. For example, given two k-colorings of a graph, the task is to decide whether one can be transformed into the other by changing the color of a single vertex at a time, such that each intermediate coloring is proper. It turns out that the complexity of reconfiguration problems bears some surprises in the sense that a reconfiguration problem can be hard although its underlying combinatorial problem is tractable and vice versa. We give an overview of some recent results and techniques in this area, with a focus on vertex coloring and matchings (and their relation to sliding token puzzles).

2015-06-10
16:15
M E19
Prof. Dr. Hans Mittelmann
(School of Mathematical and
Statistical Sciences /
Arizona State University)

On Solving a Hard Quadratic 3-Dimensional Assignment Problem

We address the exact solution of a very challenging (and previously unsolved) instance of the quadratic 3-dimensional assignment problem, arising in digital wireless communications. When error correction of a transmitted message is not possible, an automatic repeat request (ARQ) may be sent. For the case of PSK coding we describe the techniques developed to solve this instance to proven optimality, from the choice of an appropriate mixed integer programming formulation, to cutting planes and symmetry handling. Combining these approaches we are able to solve this problem with moderate computational effort (2.5 million nodes and the equivalent of one week of computations on a standard PC). This is joint work with Domenico Salvagnin, University of Padova.

2015-06-08
14:15
OH14/E04
Prof. Dr. Matthias Ehrgott
(Management School /
Lancaster University)

Exact Methods for Multi-objective Combinatorial Optimisation

In this talk we consider multi-objective optimisation problems with a combinatorial structure. Such problems have a discrete feasible set and can be formulated as integer (usually binary) optimisation problems with multiple (integer valued) objectives. We focus on a review of exact methods to solve such problems. First, we provide definitions of the most important classes of solutions and explore properties of such problems and their solution sets. Then we discuss the most common approaches to solve multi-objective combinatorial optimisation problems. These approaches include extensions of single objective algorithms, scalarisation methods, the two-phase method and multi-objective branch and bound.

 

2014

Termin Referent Thema
2014-11-05
15:00
M E19
Dr. Francesco Rinaldi
(Università di Padova)

The Frank-Wolfe algorithm: an overview and recent developments

The Frank-Wolfe algorithm is a simple iterative first-order optimization algorithm for constrained convex optimization that allows to efficiently compute sparse approximate solutions to large-scale problems.

Due to its properties, variants of this method have recently been studied in the optimization and machine learning communities. In this talk, we provide a theoretical analysis of the Frank-Wolfe algorithm. We further introduce some variants of the original method devised to improve its performance. Finally, we examine some current challenges and future research perspectives.

2014-07-16
16:15
M E19
Dr. David Adjiashvili
(IFOR, ETH Zürich)

New Models and Methods in Robust Combinatorial Optimization

We survey a number of new models of robust combinatorial optimization. We mainly, but not exclusively, focus on adversarial deletion problems: Given an nominal instance of a combinatorial optimization problem and a set of scenarios, each comprised of a subset of resources (e.g., edges of a graph), the goal is to choose a solution X with the property that X-S (i.e., the solution X without the resources in S) satisfies some feasibility criterion, for every scenario S. Different definitions of the feasibility criterion, and different presentations of the scenario set give rise to a variety of largely-unexplored models.

2014-03-13
16:15
M E19
Prof. Dr. Anita Schöbel
(Universität Göttingen)

New Approaches to Robust Optimization

Many practical problems suffer from inaccurate, missing, or unreliable input data. This is a severe problem, since even small changes can make an optimal solution completely useless for practice. Robust optimization approaches try to hedge against uncertain data. The goal is to find solutions which are good for all scenarios contained in some given uncertainty set. In this talk we will give a short overview on models for robust optimization and present some approaches which do not suffer from the conservatism of the “classical” concepts ([A. Ben-Tal, L. El Ghaoui, and A. Nemirovski. Robust Optimization]).

  • We generalize the recent concept of light robustness originally introduced in [M. Fischetti and M. Monaci: M. Fischetti and M. Monaci] to general optimization problems and analyze its properties. We are able to show that we receive problems of the same type as the original problem in many cases.

  • We furthermore develop a new generic approach to recovery robustness (see, e.g., [C. Liebchen, M. Lübbecke, R. H. Möhring, and S. Stiller. The concept of recoverable robustness, linear programming recovery, and railway applications]) which enables us to generate robust solutions whenever a solution procedure for the certain optimization problem is known. For this approach we derive two variants, recovery to optimality and recovery to feasibility (joint work together with Marc Goerigk, see [GS11, CGKS13, GS13]). We present an analysis of these approaches for different structures of the uncertainty set and experimentally evaluate their performance.

 

2013

 

2012

Termin Referent Thema
2012-07-25
16:00
M 811
Prof. Dr. Peter Zörnig
(University of Brasilia /
Brasilien)

Improved optimization modelling for the closest string and related problems

We present a new integer linear programming model for the closest string problem. This model requires considerably less variables and constraints than the popular binary linear programming model used for this purpose. Due to the reduced size it is easier to handle rounding errors when an LP relaxation technique is used to solve the problem. The proposed model is particularly useful for closest string problems where a small set of long sequences is given. In this case, the optimal string or a good approximate solution can be usually obtained by rounding the optimal solution of the LP relaxation to the nearest integers.

2012-07-16
16:00
M E19
Dr. Dennis Michaels
(ETH Zürich /
Schweiz)

Improved convex relaxations through simultaneous convexification of non-linear functions

A challenging task in global optimization is to construct tight convex relaxations that provide reasonably globally valid bounds on a mixed-integer nonlinear program (MINLP). For a general MINLP, convex relaxations are usually obtained by replacing each non-linearity by convex under- and concave overestimators. The mathematical object studied to derive such estimators is given by the convex hull of the graph of the function over the relevant domain.

To derive improved relaxations, we consider a finite set of given functions as a vector-valued function and study the convex hull of its graph. We establish a link between such a convex hull object and the convex hulls of the graphs of a certain family of real-valued functions. This link can be used to define improved relaxations. We especially focus on small sets of well-structured univariate functions. Moreover, we consider some classes of (real-valued) functions for which a simultaneous convexification with the set of multi-linear monomials leads to an explicit description for the tightest convex underestimating function. The extended formulation is based on the idea of the RLT-approach introduced by Sherali and Adams.

Numerical examples are presented demonstrating the impact of the concepts.

(joint work with Martin Ballerstein and Robert Weismantel)

2012-05-15
16:00
M E19
Tobias Springer
(TU Dortmund)

Optimalitätsbedingungen des Penalized Frame Potentials

2012-04-26
17:00
M E19
Dr. Ivana Ljubić
(Universität Wien)

The Recoverable Robust Two-Level Network Design Problem

We consider a network design application which is modeled as the two level network design problem under uncertainty. In this problem, one of the two available technologies can be installed on each edge and all customers of the network need to be served by at least the lower level (secondary) technology. The decision maker is confronted with uncertainty regarding the set of primary customers, i.e., the set of nodes that need to be served by the higher level (primary) technology. A set of discrete scenarios associated to the possible realizations of primary customers is available. The network is built in two stages. In the first stage the network topology must be determined. One may decide to install the primary technology on some of the edges in the first stage, or one can wait to see which scenario will be realized, in which case, edges with the installed secondary technology may be upgraded to primary technology, but at higher recovery cost. The overall goal is to build a spanning tree in the first stage that serves all customers by at least the lower level technology, and that minimizes the first stage installation cost plus the worst-case cost needed to upgrade the edges of that tree, so that the primary customers of each scenario can be served using the primary technology.

Using the recently introduced concept of recoverable robustness, we address this problem of importance in the design of telecommunication and distribution networks. We study the complexity of the problem on trees and provide mixed integer programming models for solving the problem on trees and on general graphs, respectively. Finally, we provide a qualitative study of the solutions in terms of robustness and recoverability and an assessment of the algorithmic performance of our branch-and-cut approach.

This is a joint work with Eduardo Alvarez-Miranda, S. Raghavan and Paolo Toth.

2012-03-27
14:30
M 511
Dr. Claudia D’Ambrosio
(LIX, École Polytechnique)

Feasibility Pump, Heuristic Methods for Nonconvex Mixed Integer Nonlinear Programming Problems

One of the foremost difficulties in solving Mixed Integer Nonlinear Programs (MINLP), either with exact or heuristic methods, is to find a feasible point. We address this issue with a new feasibility pump algorithm tailored for nonconvex MINLPs. Feasibility pumps are successive projection algorithms that iterate between solving a continuous relaxation and a mixed-integer relaxation of the original problems; such approaches currently exist in the literature for Mixed-Integer Linear Programs and convex MINLPs. Both cases exhibit the distinctive property that the continuous relaxation can be solved in polynomial time. In nonconvex MINLP such a property does not hold and the main innovations in this paper are tailored algorithmic methods to overcome such a difficulty. In this talk, we review the Feasibility Pump evolution from the original one proposed by Fischetti, Glover, and Lodi (2005) to the one addressed to nonconvex Mixed Integer Nonlinear Programming problems, one of the first effective heuristics proposed for general MINLPs.

 

2011

Termin Referent Thema
2011-12-07 PD Dr. Florian Jaehn
(Universität Siegen)

Ein neuer Branch and Bound Algorithmus für das Cliquenpartitionierungsproblem

In einem vollständigen, kantengewichteten Graph sollen die Knoten zu Gruppen zusammengefasst werden, so dass die Summe aller Kantengewichte innerhalb aller Gruppen maximiert wird. Eine Knotengruppe wird auch Clique genannt und das Problem heißt daher Cliquenpartitionierungsproblem. Dieses Problem ist NP-vollständig und hat zahlreiche Anwendungen in der Produktion (insb. in der Gruppentechnologie), in der Biologie, in der Flugzeug-Gate Zuordnung, usw.. In der Literatur finden sich viele heuristische und exakte Verfahren sowie Vergleichstestinstanzen. Die exakten Verfahren nutzen meist Branch and Bound, wobei über die Kanten verzweigt wird. Für solch ein Verfahren stellen wir stärke obere Schranken vor, präsentieren constraint propagation Techniken, die weitere Kanten fixieren, und erarbeiten ein neues Verzweigungsmuster. Die theoretischen Verbesserungen des Verfahrens lassen sich an Hand von Praxisdaten bestätigen. Im Vergleich zu anderen Verfahren wird die Laufzeit deutlich verringert.

2011-11-16 Prof. Dr. Anita Schöbel
(Universität Göttingen)

A geometric solution algorithm for mixed continuous and combinatorial optimization problems

Geometric branch-and-bound techniques like the „big-square-small-square method“are popular solution algorithms for continuous and non-convex global optimization problems. The idea is to partition the continuous solution space into boxes and to approximate the problem on any of them. By calculating bounds some of the boxes can be discarded, while the remaining ones are split into sub-boxes. This is repeated until a certain accuracy is obtained. The most important task throughout this branch-and-bound algorithm is the calculation of good lower bounds on the objective function. Several techniques to do so exist.

This geometric branch & bound approach has been applied so far for pure continuous objective functions. The aim of this paper is to extend geometric branch-and-bound methods to mixed continuous and combinatorial optimization problems, i.e. to objective functions containing continuous and integer variables. The idea is to do a geometric branching for the continuous variables and to approximate the remaining discrete problem in order to obtain the required bounds on the boxes. This is in contrast to the classical integer branch-and-bound in which branching is done on the discrete variables.

We formulate this new approach and extend known bounding operations from the continuous case to mixedinteger problems. We are able to derive theoretical results about their rate of convergence. Moreover, we discuss an extension of the method which leads to exact optimal solutions under certain conditions. We also implemented our approach and applied it to some facility location problems with combinatorial decisions. Our numerical results show that we succeeded in finding exact optimal solutions in relatively low computational time.

  Dipl.-Math. Ruth Hübner
(Universität Göttingen)

When is rounding allowed?
A level set approach to integer nonlinear optimization.

We consider nonlinear integer optimization problems. In order to solve such a problem, we use the fact, that continuous nonlinear optimization problems are often easier to solve than their integer counterparts. Assume that we can solve a continuous nonlinear problem in polynomial time and we know that an optimal integer point can be found by just rounding (up or down) the components of an optimal solution of the continuous problem, then we can (in fixed dimension) also solve the IP in polynomial time. To check whether we get an optimal soluTion to the IP by rounding a continuous solution (we call this the rounding property) we use a geometric approach: we investigate the geometric shape of the level sets. E.g. if the level sets are balls around the continuous solution the problem has the rounding property. We extend this by identifying geometric properties of the level sets that also lead to the rounding property: First, the rounding property is still true, if we don’t take the standard Euclidean-norm-ball, but an arbitrary p-norm ball. Second, we will show that the rounding property holds if the level set is included between two p-norm-balls if the difference of their radii is small enough. We call this type of sets p-quasiround. Four our third generalization we investigate rectangular-distance-star-shaped sets and show that the rounding property also holds in this case. Furthermore, we will discuss a sharper property which makes sure that we can round the continuous optimum to the closest integer point. If it holds then we can solve the integer version of a continuous optimization problem in the same time as the continuous problem (in any dimension).

2011-05-09 Prof. Dr. Marco Luebbecke
(RWTH Aachen)

Automatische Dekomposition ganzzahliger Programme

Viele praktische Optimierungsprobleme lassen sich als ganzzahliges Programm formulieren. Diese Technik ist nicht zuletzt deswegen auch in der Praxis so erfolgreich, weil leistungsfähige Lösungsalgorithmen (Branch-and-Bound, Branch-and-Cut) gut implementiert zur Verfugung stehen. Viele Probleme (z.B. Vehicle Routing, Bin Packing, p-Median, Graphenfärbung) führen allerdings auf speziell strukturierte Modelle, die immer öfter mit Branch-and-Price-Algorithmen gelöst werden können. Hierbei wird das originale Modell mit Hilfe einer Dekomposition in ein so genanntes Master- und ein Subproblem umformuliert, so dass die Struktur des Problems ausgenutzt wird und im Allgemeinen z.B. wesentlich verbesserte duale Schranken an das Optimum erzielt werden können (Stichwort: Column Generation). Der Pferdefuss: Alle diese Ansätze erfordern eine eigene Implementation und immer noch ein solides Wissen einer Vielzahl von Details der Algorithmen und Dekompositionen. Wünschenswert wäre also ein „generischer“ Ansatz, der die notwendige Dekomposition automatisch ausführt, falls sie sich anbietet, und einen Branch-and-Price-Algorithmus ohne weiteres Zutun des Benutzers anstösst. In diesem Vortrag berichten wir über jüngste Fortschritte in dieser Richtung.

2011-01-19 Prof. Dr. Erwin Pesch
(Universität Siegen)

Gate-Management an Verkehrsflughäfen

Seit Mitte der achtziger Jahre haben sich Passagier- und Frachtzahlen im internationalen Luftverkehr mehr als verdoppelt. Mit dem Verkehrsaufkommen haben auch die Flugverspätungen überproportional zugenommen. Die beobachtete Dauer der Verspätungen ist insbesondere an hoch frequentierten Flughäfen sowohl absolut als auch in Relation zur Bodenzeit der Flugzeuge erheblich. Ein großer Teil der Verspätungen wird durch die Abfertigung am Flughafen verursacht. Aktuellen Studien zufolge betragen die jährlichen gesamtwirtschaftlichen Kosten der Verspätungen im europäischen Luftverkehr mehrere Milliarden Euro. Im Rahmen des so genannten Gate-Managements werden ankommende und abgehende Flüge bzw. Flugzeuge geeigneten Terminal-Gates oder Vorfeldabfertigungspositionen zugeordnet, und die exakte Verweildauer am Gate wird bestimmt. Ein Flug kann in Abhängigkeit von Eigenschaften wie dem zugehörigen Flugzeugtyp, Herkunfts- und/oder Zielort oder Fluglinie etc. an bestimmten Gates bearbeitet werden und erfordert zur Abfertigung eine gewisse Mindestanstelldauer am Gate. Die Güte eines Plans hängt von zahlreichen Kriterien ab. Vorrangiges Ziel ist die Zuordnung einer möglichst großen Zahl von Flügen zu Gates, denn häufig existiert insbesondere in Spitzenzeiten keine Lösung, bei der alle Flüge geeigneten Gates zugeordnet werden können; eine solche Situation erfordert dann manuelle Intervention, z.B. durch die Verkürzung von Mindestbearbeitungsdauern. Weitere wichtige Zielkriterien sind unter anderem die Maximierung der erzielten Flug-Gate-Präferenzwerte, die Minimierung der erforderlichen Schleppvorgänge und die Minimierung der Abweichungen von einem infolge von Flugplanänderungen nicht mehr länger realisierbaren Vorgabeplan. Die Gatezuordnung hat auch entscheidenden Einfluss auf den Service einer Fluggesellschaft, derart, dass sie durch blockierte Gates verursachte Wartezeiten eines ankommenden Fluges auf dem Vorfeld minimiert. Das im Vortrag zu beschreibende komplexe Entscheidungsproblem wird in unterschiedlicher Weise als kombinatorisches Optimierungsproblem modelliert. Lösungsansätze werden skizziert und Rechenergebnisse für reale Flugdaten zeigen eine beeindruckende Überlegenheit der Verfahren gegenüber der vorhandenen Planung.

 

2010

Termin Referent Thema
2010-07-16 Dr. Lutz Schade
(Dr. Schade GmbH)
Versicherungsmathematische Motivation für zeitgemässebetriebliche Altersversorgung

Mit der sog. Altersvermögensreform hat sich der Gesetzgeber seit dem Jahre 2001 sukzessive von einer staatlich finanzierbaren Altersvorsorge als selbständige Form einer Altersabsicherung verabschiedet. In diesem Zuge mussten notwendigerweise sowohl die betriebliche Altersversorgung (bAV) als auch die private Altersversorgung gestärkt werden. Die gesetzliche Rentenversicherung wird damit unter Berücksichtigung der demographischen Entwicklung in Deutschland insbesondere für die jungen Generationen in Zukunft nur noch eine Existenzgrundabsicherung darstellen können. Im Verständnis der Pensionsversicherungsmathematik als Spezialform der allgemeinen Lebensversicherungsmathematik (zusammengesetzte Ausscheideordnung mit den Ausscheideursachen Erreichen des Pensionsalters, Berufsunfähigkeit und Tod) beleuchtet der Vortrag die betriebliche Altersversorgung allgemein und tiefer gehend am Beispiel der sog. Direktzusage. Aktuarisch interessieren dabei Themenschwerpunkte wie (echte und unechte) beitragsorientierte Leistungszusagen, Entgeltumwandlung und verschiedene versicherungsmathematische Bewertungsverfahren (sog. Teilwertverfahren und Projected-Unit-Credit-Methode) mit deren Wirkungen auf die Steuer- und Handelsbilanz (bei gleichzeitiger Berücksichtigung der neuen handelsrechtlichen Bilanzierungsvorschriften nach dem BilMoG). Im betriebswirtschaftlich „gesunden“ Verständnis eines „klugen Kaufmanns“ wird ein Vorschlag für eine zeitgemässe Gestaltung der betrieblichen Altersversorgung für Unternehmen erarbeitet. Dabei steht das Ziel der Einrichtung attraktiver Mitarbeiterversorgungswerke und der Steigerung des personal- und betriebswirtschaftlichen Nutzens im Vordergrund. Die bisherige übliche Gestaltung der Versorgungszusagen und vorherrschende „Glaubenssätze“ werden gleichermassen kritisch analysiert.

 

2009

Termin Referent Thema
2009-06-17 Prof. Dr. Ingo Schiermeyer
(TU Bergakademie Freiberg)
Regenbogenfärbungen in Graphen

In diesem Vortrag betrachten wir Graphen, deren Kanten gefärbt sind. Ein Teilgraph H G eines Graphen G heißt regenbogengefärbt, wenn alle seine Kanten verschiedene Farben besitzen. Im ersten Teil des Vortrages werden für eine Reihe von Teilgraphen H die Regenbogenzahlen rb(G;H) bestimmt. Dies ist die minimale Anzahl von Farben, die eine regenbogengefärbte Kopie von H in einem Graphen G garantiert. Diese Extremalresultate stehen in engem Zusammenhang mit den Turanzahlen. Im zweiten Teil des Vortrags behandeln wir das Minimum Rainbow Subgraph Problem (MRS): In einem Graphen G; dessen Kanten mit p Farben gefärbt sind, wird ein Teilgraph F G von G mit minimaler Ordnung und p Kanten gesucht, so dass jede Farbe genau einmal vorkommt. Dieses Problem liefert einen Lösungsalgorithmus für ein Genomerzeugungsproblem aus der Bioinformatik.

2009-05-20 Prof. Dr. Dieter Rautenbach
(TU Ilmenau)
Kreise, Wege, Zusammenhang und Durchmesser von Distanzgraphen

Circulant graphs form an important and very well-studied class of graph. They are Cayley graphs of cyclic groups and have been proposed for numerous applications such as local area computer networks, large area communication networks, parallel processing architectures, distributed computing, and VLSI design. Their connectivity and diameter, cycle and path structure, and further graph-theoretical properties have been studied in great detail. Polynomial time algorithms for isomorphism testing and recognition of circulant graphs have been long-standing open problems which were completely solved only recently.

Our goal here is to extend some of the fundamental results concerning circulant graphs to the similarly defined yet more general class of distance graphs. We prove that the class of circulant graphs coincides with the class of regular distance graphs. We study the existence of long cycles and paths in distance graphs and analyse the computational complexity of problems related to their connectivity and diameter.

(joint work with L. Draque Penso und J.L. Szwarcfiter)

 

2008

Termin Referent Thema
2008-07-11 Prof. Dr. Jörg Fliege
(University of Southampton
United Kingdom)
Issues in Computational Optimization of Wireless Telecommunication Networks

More and more in a global economy, businesses require access to high speed voice, data and video communications. A region that achieves broadband technology assures itself a place on the high side of the digital divide that separates areas of economic vitality from those left behind. Thus, there is a strong demand for the communication industry on delivering broadband access for all. Wireless mesh networks are ranked as promising technique for broadband coverage and capacity extension. The data between nodes constructing a wireless mesh network is transmitted on wireless links by means of wireless transmission technologies. These wireless links suffer from time-variant influences caused by the timely changing environment and, as a result, the capacity (maximum amount of data that can be transmitted) of a wireless link is not fixed. Instead, this capacity has to be adjusted by resource allocation. As a consequence, efficiently transmitting data in wireless mesh networks requires integrated routing and resource optimization.

A mathematical analysis of the underlying model leads to a method that solves the corresponding joint routing and power control optimization problem by decomposing the problem into sub-problems while still meeting main requirements such as distributed implementation, multiple path routing, and per-hop error performance. Scheduling is managed separately by including the corresponding requirements in the constraints of the problem. We show that the resulting Routing and Power Control Decomposition (RPCD) algorithm produces a sequence of points converging to a KKT-point of the optimization problem. This convergence holds even if the links suffer multiple access interference, as it is the case for TDMA/CDMA networks. Numerical results show the applicability of the algorithm in practice.

2008-05-27 Prof. Dr. Jochen Harant
(Technische Universität Ilmenau)
Graph Parameters and Multilinear Functions

Die Bestimmung einer Vielzahl von wichtigen Graphenparametern ist schwierig in dem Sinne, dass die zugehörigen Entscheidungsprobleme NP-vollständig sind. Es werden Sätze aufgelistet und teilweise bewiesen, die zeigen, dass man das kombinatorische Optimierungsproblem, einen solchen Parameter zu bestimmen, durch ein stetiges Optimierungsproblem über einem hochdimensionalen Einheitswürfel, wobei dort eine geeignete multilineare Funktion zu optimieren ist, ersetzen kann. Ausgehend davon werden Schranken und realisierende Algorithmen.

 

2007

Termin Referent Thema
2007-12-12 Prof. Dr. Stefan Scholtes
(University of Cambridge
United Kingdom)
Double or Quits: Co-development Contracts with Opt-out-Options

WIn 2004, the UK biotech company Cambridge Antibody Technology and the pharma major Astra Zeneca entered a $175M co-development alliance for biotechnology drugs. The contract won an industry award for innovative business development. The novel element was the use of opt-out options for the partners to deal with uncertainty. In this paper we show that, in contrast to traditional royalty-milestone arrangements, co-development with optout is an efficient contract, i.e., the development of commercially viable drugs is not unduly delayed in certain scenarios.

We then investigate contracts with opt-out options for both parties. If both parties have the same opt-out terms, then they would opt out in the same scenarios, which would lead to inefficiency. To avoid this, the opt-out terms for both parties have to be asymmetric. It turns out that contract terms that seem, at first glance, more favourable for one partner than for the other, can share the value, ex ante, in a fair way. We characterise asymmetric contract terms that (a) make the contract efficient, (b) result in fair value sharing and (c) align options exercise with the different strategic goals of both partners

2007-11-14 Prof. Dr. Mathias Stolpe
(Technical University of Denmark /
Lyngby / Copenhagen /
Denmark)
Global Optimization of Discrete Topology Design Problems

A classical problem within the field of structural topology optimization is to find the stiffest structure subject to multiple loads and a bound on the volume (or weight) of the structure. We minimize a weighted average of the compliances, i.e. the inverse of the stiffness. The design variables describe the cross sectional areas of the bars in a truss or fiber directions in a structure made of laminated composites. This class of problems is well-studied for continuous variables. We consider here the situation that the variables are discrete.

Our goal is to compute guaranteed globally optimal structures. We present a method for the computation of a global optimizer of the underlying non-convex discrete problem. The method is a finitely convergent nonlinear branch and cut method tailored to solve large-scale instances of the original discrete problem. The branch and cut algorithm is based on solving a sequence of continuous relaxations, which are obtained by relaxing the discreteness requirements. The main effect of this approach lies in the fact that these relaxed problems can be equivalently reformulated as all-quadratic convex problems and thus can be efficiently solved to global optimality.

2007-02-07 Dr. Angelika Wiegele
(Universität Köln)
Ein exakter Lösungsalgorithmus des Max-Cut Problems

Dieser Vortrag handelt von einer exakten Lösungsmethode des Max-Cut Problems, ein NP-schweres kombinatorisches Optimierungsproblem. Grundlage dieses neuen Algorithmus ist ein Semidefinites Optimierungsproblem (SDO), dessen Lösung als obere Schranke an den maximalen cut verwendet wird. Da das Lösen dieses Semidefiniten Optimierungsproblems auf Grund der vielen Nebenbedingungen mit herkömmlichen Methoden nicht möglich ist, verwenden wir die sogenannte Bundle Methode, um das Problem ’fast’ optimal zu lösen. Diese Schrankenberechnung wird in einem Branch and Bound Verfahren eingebaut und all das zusammen nennen wir Biq Mac - a solver for BInary Quadratic and MAx-Cut problems.

Im Vortrag wird das Max-Cut Problem erklärt und das SDO hergeleitet. Weiters wird die Bundle Methode, mit der das SDO gelöst wird, erläutert. Es werden viele numerische Resultate präsentiert und wir geben eine grobe U¨ bersicht, wie sich die Rechenzeiten von Biq Mac mit jenen anderer exakter Lo¨sungsmethoden vergleichen lassen.

2007-01-25 Dr. Marco Lübbecke
(Technische Universität Berlin)
Intelligentes Stapeln: Transportoptimierung in einem Brammenlager

In der Stahlproduktion gegossene Brammen, Barren von bis zu zwölf Meter Länge und zwanzig Tonnen Gewicht, müssen innerhalb gegebener Zeitfenster an der Strangussanlage entsorgt und meist vor der Weiterverarbeitung zwischengelagert werden. Um Lagerplatz effizient zu nutzen, werden sie auf Stapeln gelagert. Die Brammen sind nicht austauschbar und parallel zur Einlagerung müssen vorgegebene Stapel am Ausgang des Lagers zur Verfügung gestellt werden.

Um den Durchsatz des Lagers zu erhöhen, soll die Gesamtanzahl notwendiger Krantransporte innerhalb des Lagers minimiert werden; insbesondere ist also häufiges Umstapeln von Brammen zu vermeiden. Wir stellen einen praxistauglichen Algorithmus aus dem Bereich der kombinatorischen Optimierung vor, welcher beweisbar sehr gute Lösungen für das beschriebene Problem liefert und auch leicht auf andere Logistikanwendungen übertragbar ist, in denen Güter gestapelt werden.

 

2006

Termin Referent Thema
2006-11-29 JProf. Dr. Mirjam Dür
(Technische Universität Darmstadt)
Kontinuierliche Ansätze zur diskreten Optimierung mittels konvexer Kegel

Relaxierungen spielen eine entscheidende Rolle, wenn ein diskretes Optimierungsproblem (etwa mit Branch-and-Bound) gelöst werden soll. Neben der bekannten LP-Relaxierung sind in den letzten Jahren vermehrt so genannte semidefinite Relaxierungen betrachtet worden. Das ursprüngliche Problem wird dabei in einen höherdimensionalen Raum von Matrixvariablen transformiert, wobei die Ganzzahligkeitsbedingungen mittels spezieller Matrixbedingungen relaxiert werden: es wird verlangt, dass die Matrixvariable im Kegel der positiv semidefiniten Matrizen enthalten sei. Für solche semidefinite Programme gibt es sehr effiziente Algorithmen. Die Lösung erfordert zwar einen etwas höheren Rechenaufwand als die Berechnung der LP-Relaxierung, qualitativ ist die semidefinite Relaxierung der LP-Relaxierung aber oft deutlich überlegen. Noch bessere Schranken (in manchen Fällen sogar die Optimallösung) lassen sich berechnen, indem man statt des Kegels der semidefiniten Matrizen andere konvexe Kegel, zum Beispiel den Kegel der so genannten copositiven Matrizen betrachtet.

Im Vortrag sollen Vor- und Nachteile dieser Relaxierungstechniken diskutiert werden. Insbesondere wird ein neues Approximationsschema vorgestellt, mit Hilfe dessen copositive Programme bis auf eine vorgegebene Genauigkeit gel öst werden können. Der Ansatz beruht auf polyedrischen Approximationen des copositiven Kegels sowohl von innen als auch von außen. Ersetzt man den copositiven Kegel durch diese approximierenden Kegel, so erhält man ein lineares Problem, das effizient gel öst werden kann. Durch geschickte Verfeinerung der Approximation erzeugt man eine Folge von LPs, die das vorgegebene copositive Programm beliebig genau approximieren. Dabei kann die Verfeinerung so gesteuert werden, dass nur in dem für die Optimierung relevanten Bereich verfeinert wird und der numerische Aufwand begrenzt bleibt.

Die Resultate zur Copositiven Optimierung sind in Zusammenarbeit mit Stefan Bundfuss entstanden.

2006-09-07 Prof. Dr. Jochen Könemann
(University of Waterloo /
Canada)
A Fresh Look at Steiner Trees: Greedy vs Primal-Dual Algorithms

The Steiner tree problem is a classical NP-hard optimization problem with a wide range of practical applications. In an instance of this problem, we are given an undirected graph G = (V;E), a subset R of V of terminals, and non-negative costs ce for all edges e in E. The goal is to find a minimum-cost tree T in G that spans all terminals in R.

The best known approximation algorithm known for the Steiner tree problem is due to Robins and Zelikovsky (SIAM J. Discrete Math, 2005) and achieves a performance ration of 1.55. Robins and Zelikovsky’s algorithm is a greedy algorithm. The best known LP-based algorithm for general graphs is a 2-approximation due to Agrawal, Klein and Ravi (SIAM J. Computing, 1995). The analysis of this algorithm is tight as the underlying undirected cut relaxation for the Steiner tree problem has an integrality gap of nearly 2. Rajagopalan and Vazirani (SODA, 2000) have recently proposed a new primal-dual (1.5+²)-approximation algorithm for the Steiner tree problem in quasi-bipartite graphs; these are graphs in which no two Steiner vertices are connected by an edge. Their algorithm is based on the so called bidirected cut relaxation for the Steiner tree problem.

Motivated by the result of Rajagopalan and Vazirani, most recent efforts on finding better LP-based approximation algorithms have focused on the bidirected cut relaxation. In this talk, we propose a new undirected formulation, and we first show that Khang and Robins’ well-known 1-Steiner heuristic for quasi-bipartite graphs returns a 1.5-approximate Steiner tree with respect to our relaxation. Furthermore, we can show that the above analysis for the quasi-bipartite special case extends to general graphs; Robins’ and Zelikovsky’s 1.55-approximation can be interpreted as a primal-dual algorithm using our relaxation.

This is joint work with Kunlun Tan.

2006-02-15 Alexander Offtermatt Souza
(ETH Zürich /
Schweiz)
On Adequate Performance Measures for Paging

Memory management is a fundamental problem in computer architecture and operating systems. We consider a two-level memory system with fast, but small cache and slow, but large main memory. The underlying theoretical problem is known as the paging problem. A sequence of requests to pages has to be served by making each requested page available in the cache. A paging strategy replaces pages in the cache with requested ones. The aim is to minimize the number of page faults that occur whenever a requested page is not in the cache.

Experience shows that the Least-Recently-Used (LRU) paging strategy usually achieves a factor around 2 to 3 compared to the optimum number of faults. This contrasts the theoretical worst case, in which this factor can be as large as the cache size k.

One difficulty in analyzing the paging problem was the lack of an appropriate lower bound for the minimum number of page faults. We address this issue and propose a general lower bound which provides insight into the global structure of a given request sequence. In addition, we derive a characterization for the number of faults incurred by LRU.

We give a theoretical explanation why LRU performs well in practice. We classify the set of all request sequences according to certain parameters and prove a bound on the competitive ratio of LRU, which depends on them. This bound varies between 2 and k, i.e., it includes the worst-case, but explains for which sequences LRU achieves constant competitive ratio. The classification is motivated from the structure of request sequences of practical applications: locality of reference and characteristic data access patterns. We argue that this structure yields values around 2 for our bound. Indeed, it is between 2 and 5 in extensive practical experiments.

Moreover, we show that the alternative approach of variable cache size, which was also studied previously, is not appropriate to explain this phenomenon. Further, our analysis provides evidence that the approach of the expected competitive ratio in the diffuse adversary model can be misleading. We propose the use of the expected performance ratio instead, and prove tight bounds for both measures.

2006-01-26 Prof. Dr. Bernhard Fleischmann
(Universität Augsburg)
Dynamische Pickup-and-Delivery-Probleme

Wir betrachten das folgende Dynamische Pickup-and-Delivery-Problem (DPDP): Ein Logistik-Dienstleister erfüllt mit seinem Fuhrpark in einem städtischen Gebiet Transportaufträge, die jeweils an einem Standort abzuholen und an einem Zielort auszuliefern sind. Für die Abholung und Auslieferung sind jeweils Zeitfenster zu beachten. Ein Teil der Aufträge ist schon zu Beginn des Tages bekannt, die übrigen Aufträge kommen während des Tages zufällig an. Aufgabe der zentralen Disposition ist es, den Einsatz der Fahrzeuge in Echtzeit so zu steuern, dass die Verspätungen und die Summe der Fahrstrecke minimiert werden. Dabei sind zwei Fälle zu unterscheiden: Im ersten Fall kann ein Fahrzeug nur einen Auftrag zugleich ausführen, im zweiten Fall können mehrere Aufträge unter Beachtung der Fahrzeugkapazität kombiniert werden.

Wir stellen verschiedene Methoden für beide Fälle vor und berichten über Rechentests.

2006-01-04 Prof. Dr. Marc Uetz
(Universität Maastricht /
Niederlande)
Scheduling Parallel Jobs with Linear Speedup

We consider a scheduling problem where a set of jobs is a- priori distributed over a set of parallel machines. The processing time of any job is dependent on the usage of a scarce renewable resource, e.g. personnel. An amount of k units of that resource can be allocated to the jobs at any time, and the more of that resource is allocated to a job, the smaller its processing time. The dependence of processing times on the amount of resources is linear for any job. The objective is to find a resource allocation and a schedule that minimizes the makespan. Utilizing an integer quadratic programming relaxation, we show how to obtain a (3 + ")- approximation algorithm for that problem, for any " > 0. This generalizes and improves previous results, respectively. Apart from this result for the scheduling problem, however, the main contribution rather lies on the methodology side: We derive a fully polynomial time approximation scheme to solve the quadratic programming relaxation. This result is interesting in itself, because the underlying quadratic program is a concave quadratic minimization problem, which is NP-hard to solve. We also discuss some further generalizations of the results.

 

2005

Termin Referent Thema
2005-12-15 Dr. Tatiana Starostina
(Technische Universität Freiberg)
Transportation Problems With Fuzzy Data

In general case a transportation problem is concerned with distributing any commodity from any group of supply centers, called sources, to any group of receiving centers, called destinations, in such a way as to minimize the total distribution cost. Each source has a fixed supply of units, where this entire supply must be distributed to the destinations. Similarly, each destination has a fixed demand for units, where this entire demand must be received from the sources. This assumption that there is no leeway in the amounts to be sent or received means that there needs to be a balance between the total supply from all sources and the total demand at all destinations.

Usually it is assumed that parameters of transportation problem are crisp values. But in many real situations transportation costs or also demand and supply values can not be exactly defined because they are variable, unreliable and imprecise. In this situation a suitable way to model these imprecise data is to use fuzzy sets. Moreover some criteria may be considered, for example transportation cost, transportation time etc.

Two formulations of the transportation problem with fuzzy data will be discussed. The first formulation is with fuzzy cost coefficients and the second is with fuzzy demand and supply values. Some algorithms for solution of appropriated transportation problems with fuzzy data will be considered.

2005-11-23 Prof. Dr. Horst Sachs
(Technische Universität Ilmenau)
Berge's Lemma on Maximum Matchings and the Maximum Charge Problem

This is joint work with Ramesh Krishnamurti and his co-workers at Simon Frazer University, Vancouver. Let G = (V;E) denote a finite undirected graph every element (edge or vertex) of which has a positive capacity; the capacities may be assumed to be reals or integers.

A charge on G is a collection of non-negative numbers (reals or integers) assigned to the edges of G. The charge of a vertex is the sum of the charges of the edges incident upon this vertex; the total charge of G is the sum of the charges taken over all edges of G.

Maximum Charge Problem:

Maximize the total charge subject to the restriction that for no element of G the charge of this element exceeds its capacity. A well-known (simple but) fundamental lemma of Claude Berge says that a matchingM in a graph G is maximum if and only if there is in G no augmenting path with respect to M. This lemma can, in an elementary way, be extended to the following characterization of a maximum charge. A charge C on a capacitated graph G is maximum if and only if there is in G no ”augmenting lasso” with respect to C.

According to a very recent letter of Ramesh, an O(|V| * |E|) algorithm that finds (or approximates) a maximum charge, based on the above proposition, is under way.

2005-11-22 Prof. Dr. Jan-J. Rückmann
(Universidad de las Américas /
Puebla / México)
Über verallgemeinerte semi-infinite Optimierungsprobleme

The lecture deals with nonconvex optimization problems in a finite-dimensional space whose feasible sets are defined by infinitely many inequality constraints. These so-called (generalized) semi-infinite optimization problems can be used for the modelling of several practical tasks, e.g. in robotics, design problems, waveletes, approximation problems and others. Several properties of the topological structure of the corresponding feasible sets are discussed and, moreover, necessary and sufficient optimality conditions are analyzed under different assumptions: under appropriate constraint qualifications or by using the directional differentiability of the corresponding optimal value function. Finally, some examples provide a geometrical impression of the results presented.

2005-11-16 Prof. Dr. Ulrich Pferschy
(Universität Graz /
Österreich)
Optimierter Ausbau von Netzwerken

Bei der Planung von Fernwärmenetzen muss entschieden werden, welche Gebäude an das Heiznetzwerk angeschlossen werden sollen und durch welche Rohrleitungen diese Anschlüsse erfolgen sollen. Für jeden möglichen Kunden ist bekannt, welcher Profit sich durch einen Anschluss an das Netzwerk ergeben würde.Weiter sind für alle möglichen Verbindungen die Herstellungskosten gegeben. Es ist nun eine Teilmenge der Kunden auszuwählen, sodass die Summe der Profite der gewählten Kunden abzüglich der Kosten ihrer Netzanbindung maximal ist.

Dieses Problem kann als Prize-Collecting Steiner Tree Problem (PCST) formuliert werden. Dafür geben wir eine Formulierung als lineares ganzzahliges Programm (ILP) an, das auf Zusammenhangsbedingungen in einem gerichteten Graphen beruht. Zur Lösung dieses ILP-Modells entwickeln wir einen Branch-and-Cut Algorithmus mit mehreren Verbesserungen der Separierung. In Verbindung mit geeignetem Preprozessing werden damit alle bisher veröffentlichten Resultate für PCST klar übertroffen und auch optimale Lösungen für neue, größere Probleminstanzen gefunden.

Eine ähnliche Planungsaufgabe ergibt sich beim Ausbau von Glasfasernetzen bis zum Einzelkunden (”last mile“); ein hochaktuelles Thema für Anbieter von Telekommunikation. Um die entstehenden, komplexeren Instanzen in kurzer Rechenzeit behandeln zu können, wird auf einen evolutionären Algorithmus zurückgegriffen, der mit Elementen des exakten Branch-and-Cut Algorithmus verbunden werden kann. Ein aktuelles Forschungsprojekt mit mehreren universitären und industriellen Partnern beschäftigt sich mit der Entwicklung eines leistungsfähigen Planungstools unter Berücksichtigung der technischen Besonderheiten von Glasfasernetzen.

2005-05-18 Prof. Dr. Frits Spieksma
(Katholieke Universiteit Leuven /
Belgien)
Approximation of Geometric Packing and Stabbing Problems

Given a set of intervals on the line, one can be interested in i) the maximum number of pairwise disjoint intervals, and ii) the minimum number of vertical lines needed to stab each interval at least once. It is well-known that each of these problems can be solved easily, i.e., in polynomial time; in fact, their optimal values coincide. In this talk, we consider generalizations of this setting that include the problem of stabbing rectangles using a minimum number of horizontal and vertical lines, we describe applications, and we give approximation algorithms. In particular, we show that the rectangle stabbing problem admits a 2-approximation algorithm using a rounding argument, and we show that in some special cases this ratio can be improved to e/(e-1).

2005-05-12 Prof. Dr. Ryszard Urbanski,
(Adam-Mickiewicz-University of Poznan /
Polen)
On Minkowski Addition and Subtraction

I would like to present some properties of the well-known Minkovski sum. Moreover, some applications of the ordered cancellation law in the cone of convex compact sets to the short proof of the classical Riesz lemma on compactness of the ball, will be shown. We also will discuss the problem of the existence of the substraction if convex sets in connection with the so called fractions of sets. The theory will be illustrated by computer presentation.

2005-05-11 Prof. Dr. Rüdiger Schultz
(Universität Duisburg-Essen)
Algorithms for Stochastic Integer Programs with Risk Aversion

Stochastic programs are deterministic equivalents to random optimization problems. The way this equivalence has to be understood depends on how risk aversion is included into the model. We will start out from basic paradigms of model building in stochastic programming and highlight the role of risk aversion. This leads to discussing risk measures together with their structural and algorithmic implications in stochastic programming. Special attention is paid to models including integer variables. If the underlying probability distribution is discrete, then stochastic integer programs turn into large-scale block-structured (mixed-integer linear) models. The decomposition structure of these models is essentially determined by the risk measure employed. We will discuss relevant cases, together with appropriate decomposition and approximation algorithms.

2005-05-04 Prof. Dr. Rolf H. Möhring
(Technische Universität Berlin)
Optimierte Routenplanung in Verkehr und Logistik

Verkehrslenkung und Routenführung in der Logistik sind Optimierungsaufgaben von hoher Anwendungsrelevanz. Man möchte z. B. das vorhandene Straßennetz oder logistische System so nutzen, dass die Netzbelastung minimiert oder der Durchsatz maximiert wird. Der Vortrag behandelt diese Optimierungsprobleme vom Standpunkt der Netzwerkfluss-Theorie und berichtet neben den mathematischen Grundlagen über zwei konkrete Praxisanwendungen: die Lenkung von Verkehr zur Rushhour (Projekt mit DaimlerChrysler AG, Berlin) und die Steuerung eines führerlosen Transportsystems in einem Containerterminal (Projekt mit HHLA AG, Hamburg).

2005-02-16 Prof. Dr. Jose Correa
(Universidad Adolfo Ibanez /
Chile)
An Approximate König's Theorem for Edge-Coloring Weighted Bipartite Graphs

We consider a generalization of edge coloring bipartite graphs in which every edge has a weight in [0; 1] and the coloring of the edges must satisfy that the sum of the weights of the edges incident to a vertex v of any color must be at most 1. For unit weights, König’s theorem says that the number of colors needed is exactly the maximum degree. For this generalization, we show that 2:557n + o(n) colors are sufficient where n is the maximum total weight adjacent to any vertex, improving the previously best bound of 2:833n+O(1) due to Du et al. This question is motivated by the question of the rearrangeability of 3-stage Clos networks. In that context, the corresponding parameter n of interest in the edge coloring problem is the maximum over all vertices of the number of unitsized bins needed to pack the weights of the incident edges. In that setting, we are able to improve the bound to 2:5480n+o(n), also improving a bound of 2:5625n+O(1) of Du et al. Additionally, we look at the online variant of the problem, in which edges are revealed over time. Using heuristics borrowed from online bin packing we obtain, among other results, a bound of 5n for the online coloring problem, improving upon the 5:75n of Gao and Hwang. The latter result leads to a simple O(n log n) algorithm for the offline problem that is guaranteed to use no more than 8n=3 colors.

Our analysis is interesting in its own and involves a novel decomposition result for bipartite graphs and the introduction of an associated continuous one-dimensional bin packing instance which we can prove allows perfect packing.

This is joint work with Michel Goemans

2005-02-02 Prof. Dr. Jens Vygen
(Universität Bonn)
Kombinatorische Optimierung im Chip-Design

Das Chip-Design (häufig auch VLSI-Design genannt, was für very large-scale integrated steht und höchstintegrierte Schaltkreise meint) ist vielleicht das vielseitigste, ergiebigste und interessanteste Anwendungsgebiet der kombinatorischen Optimierung. Mehrere Millionen Bauteile, die ihrerseits jeweils aus einigen Transistoren bestehen, müssen auf einer möglichst kleinen Chipfläche so platziert werden, dass ihre Anschlüsse korrekt miteinander verbunden werden können, Abstandsregeln eingehalten werden, und alle Signale rechtzeitig ankommen.

Auch wenn das Gesamtproblem nicht optimal l ösbar und wohl auch nicht approximierbar ist, l ässt es sich auf natürliche Weise in Teilprobleme zerlegen, die oft nichttriviale Verallgemeinerungen klassischer kombinatorischer Optimierungsprobleme sind und sich effizient lösen lassen. Hierfür zeigen wir einige Beispiele. Die enorme und st ändig wachsende Größenordnung der Probleme (das Verdrahtungsproblem aktueller Chips kann man z.B. als Packen von einigen Millionen Steinerbäumen in einem Graphen mit rund 20 Milliarden Knoten auffassen) stellt dabei stets eine besondere Herausforderung dar.

Die vorgestellten Algorithmen sind Kern der sogenannten Bonn-Tools, die laufend zum Design der komplexesten Chips nahezu aller großen Technologiefirmen benutzt werden.

 

2004

Termin Referent Thema
2004-11-17 Dr. Marco Lübbecke
(Technische Universität Berlin)
Einschränken der Ladebedingungen beim Pickup and Delivery Problem: Gut für Theorie und Praxis
2004-07-19 Dr. Petra Johann
(Siemens AG / München)
Optimierung von Bestückautomaten

Der Vortrag stellt die Modellierung und Lösung von Problemen zur Optimierung von Bestückautomaten durch konvexe Optimierungsprobleme vor.

Darüber hinaus berichtet die Vortragende auch von Erfahrungen beim Berufseinstieg.

2004-07-07 Dr. Michal Kocvara
(Academy of Sciences /
Prague / Czech Republic)
Towards the Solution of Large-Scale Nonlinear SDP Problems

Memory requirements and complexity of Hessian assembling are limiting factors when solving large-scale linear SDPs by second-order methods. The situation becomes dramatic when trying to solve nonlinear SDPs. We propose a first order method that is based on the Augmented Lagrangian algorithm whereas the linear systems are solved by the preconditioned conjugate gradient method. The new algorithm is implemented in the code PENNON. We will refer on computational experience for linear and nonlinear SDPs.

This is a joint work with Michael Stingl, University of Erlangen.

2004-05-19 Dr. Jens Starke
(Universität Heidelberg)
Robust Control of Flexible Manufacturing Systems

Time-dependent robot-target assignment problems with several autonomous robots and several targets are considered as model of flexible manufacturing systems. Each manufacturing target has to be served in a given time interval by one and only one robot and the total working costs have to be minimized (or total winnings maximized). A specifically constructed dynamical system approach (coupled selection equations) is used which guarantees feasiblitiy of the assignment solutions. This type of control is based on pattern formation principles known in physics, chemistry and biology and results in fault resistant and robust behaviour. The performance of the suggested control is demonstrated and visualized with a computer simulation of autonomous space robots building a space station by distributed transporting several parts from a space shuttle to defined positions at the space station

This is in parts joint work with C. Ellsässer.

2004-05-12 Dr. Mathias Stolpe
(Technical University of Denmark /
Lyngby / Copenhagen /
Denmark)
A Branch-and-Cut Method for Topology Optimization of Truss Structures

The talk begins with an introduction to topology optimization of truss structures. It is shown how the nonconvex problem of minimizing the compliance (maximizing stiffness) of a truss structure subject to elastic equilibrium conditions may equivalently be cast as a linear semidefinite program. Thereafter, we present three equivalent ways of representing the nonconvex problem of minimizing the weight of a truss structure subject to stress constraints. Finally, a convergent continuous branch-and-cut method for global optimization of minimum weight problems with stress and displacement constraints is presented. The valid inequalities (cuts) which strengthen the problem formulation are generated by solving well-defined convex optimization problems. The problem formulation is also strengthened using feasibility- and optimality-based range reductions as well as probing. Computational results on a large set of problems taken from the literature are presented. Most of these problems are solved with a proof of global optimality for the first time.

2004-01-14 Oliver Schütze
(Universität Paderborn)
Unterteilungstechniken zur globalen Mehrzieloptimierung

In technischen Anwendungen ist es oft erforderlich, mehrere Zielfunktionen gleichzeitig zu optimieren. Stellvertretend sei hier die Minimierung der Kosten und der Ausfallrate bei einem Produktionsprozess genannt. In dem Vortrag wird ein neuer Ansatz zur Berechnung dieser sogenannten Mehrzieloptimierungsprobleme präsentiert. Dabei werden Unterteilungstechniken verwendet, die es erlauben, die gesamte Menge der globalen Lösungen — die Pareto-Menge — zu approximieren. Neben den Grundalgorithmen werden Erweiterungen für glatte und nichtglatte Modelle vorgestellt. Der Vortrag schließt mit einigen Anwendungen, die hauptsächlich aus der Mechatronik stammen.

 

2003

Termin Referent Thema
2003-11-19 Dr. Cornelia Schön
(Universität Karlsruhe)
Entscheidungsunterstützung für das Preismanagement von Telekommunikationsdienstleistungen

Im liberalisierten Telekommunikationsmarkt stellt das Preismanagement eines der wichtigsten Instrumente dar, um den langfristigen Markterfolg der Diensteanbieter zu sichern. Gleichzeitig gestaltet sich die Aufgabe der Tarifgestaltung im Wettbewerbsmarkt zunehmend komplex und erfordert eine systematische Entscheidungsunterstützung. Der Beitrag stellt Modelle und Methoden zur praxisorientierten Entscheidungsunterstützung des Preismanagements im Telekommunikationsmarkt vor, die im Rahmen eines gemeinsamen Forschungsprojekts mit der Deutschen Telekom AG entwickelt wurden. Im Mittelpunkt der Betrachtung steht zunächst die Analyse und Modellierung aller wesentlichen EinflussgröSSen gewinnorientierter Preisentscheidungen. Hierzu zählen z.B. die Reaktion der Nachfrage auf das Tarifangebot, die Aktivitäten des Wettbewerbs, regulatorische Rahmenbedingungen sowie von Preisentscheidungen verursachte Kosten und beschränkte Kapazitäten, deren Auslastung unmittelbar über die Nachfrage und damit den Preis gesteuert werden. Die Ergebnisse für die einzelnen EinflussgröSSen bilden die Bausteine für zwei Optimierungsmodelle zur Gestaltung zweiteiliger und multiattributiver Tarife, die zusammen mit geeigneten Lösungsverfahren vorgestellt werden. Eine Fallstudie zeigt die Leistungsfähigkeit und Praxistauglichkeit der entwickelten Ansätze, die als Modell- und Methodenkomponente wesentliche Teile eines Decision-Support-Systems für die Praxis darstellen.

2003-02-12 Dr. Lutz Schade
(Provinzial Versicherung / Düsseldorf)
Anforderungen an Mathematik und Tarifierung von Lebensversicherungen aufgrund der Altersvermögensreform und andere aktueller Entwicklungen

Ausgehend von den Perspektiven, welche die gesetzlichen Vorsorgesysteme in der Zukunft noch haben werden, beschäftigt sich der Vortrag mit den Anforderungen, die die Altersvermögensreform, die betriebliche Altersversorgung und die Entgeltumwandlung an die Kalkulationsmethodik von geeigneten Lebensversicherungsprodukten stellt.

Es wird dabei die Frage aufgeworfen, in wie weit etwa die ”klassische” Versicherungstechnik (noch) in der Lage ist die geänderten Leistungserwartungen der ”neuen, mündigen Versicherungskunden”, die rechtlichen Normen internationaler Bewertungsmethoden (IAS, US-GAAP) und die Veränderung in den biometrischen Bedingungen adäquat abzubilden. Entsprechende Konsequenzen für die Versicherungsmathematik und die Tarife bzw. die Produkte eines Lebensversicheres werden gezogen.

2003-01-22 Dr. Ekaterina Kostina
(Universität Heidelberg)
Primal-Dual Active-Set Method for Quadratic Programming

The talk deals with a method for solving general convex quadratic programming problems with equality and inequality constraints. The interest in such problems comes from at least two facts. First, quadratic models are widely used in real-life applications. Second, in many algorithms for nonlinear programming a search direction is determined at each iteration as a solution of a quadratic problem. The method method uses information about dual and primal variables to effectively manage active sets. At each iteration the duality gap is decreasing, and the process can be stopped earlier on a suboptimal solution. Numerical experiments show that the method is very effective on problems with many box constraints and range inequalities.

 

2002

Termin Referent Thema
2002-12-11 Dr. Ralf Werner
(RiskLab GmbH /
München)
Indextracking: Anwendung Konvexer Optimierung und offene Probleme

Obwohl die mathematische Seite der Finanzindustrie in den letzten Jahren stärkere Bekanntheit durch Anwendungen der stochastischen Analysis – hierunter fallen z.B. Preisbestimmung von Derivaten und Black-Scholes-Theorie – gewonnen hat, verdient auch eine andere Facette Beachtung durch Mathematiker, nämlich die der Optimierungstheorie. Im ersten Teil des Vortrags werden zur Illustration einige wichtige Beispiele für konvexe, nicht-konvexe und gemischt-ganzzahlige Probleme aus unterschiedlichen Anwendungsfeldern der Finanzwirtschaft gegeben, wie z.B. Bestimmung risikoneutraler Dichten, Parameterschätzung, Portfolio-Optimierung oder ALM. Im zweiten Teil wird anhand des Beispiels Indextracking – genauer Aktienindex- sowie Rentenindexreplikation – ein konkretes Modell und existierende Lösungsansätze vorgestellt. Der Vortrag schließt mit einer Reihe offener Probleme (z.B. robuste Optimierung, hoch-dimensionale Optimierung, etc.) und aktuellen Fragestellungen.

2002-11-07 PD Dr. Christian Zillober
(Universität Bayreuth)
Verfahren zur Lösung extrem großer nichtlinearer Optimierungsprobleme
2002-06-12 Tag der Optimierung
Prof. Dr. Robert Weismantel
(Universität Magdeburg)
Ganzzahlige Basen in der Optimierung

Der Vortrag ist in dem Gebiet der algorithmischen diskreten Mathematik angesiedelt. Behandelt wird eine neue Methode zur Lösung linearer ganzzahliger Probleme, welche darauf basiert, iterativ Vektoren der Nebenbedingungsmatrix durch ganzzahlige Erzeugendensysteme zu ersetzen. Wir diskutieren die algorithmischen Konsequenzen dieser Methode und stellen dar, welche mathematischen Fragestellungen für diesen Ansatz von besonderer Relevanz sind

Prof. Dr. Diethard Pallaschke
(Universität Karlsruhe)
Morse-Theorie für stückweise differenzierbare Funktionen

Ausgangspunkt einer Morse-Theorie für stückweise differenzierbare Funktionen ist die folgende Verallgemeinerung des zweiten Morse-Lemmas von H. Th. Jongen. Danach sind stückweise differenzierbare Funktionen in einer Umgebung eines regulären Punktes linearisierbar, und nach Einführung neuer Koordinaten können die Variablen so zerlegt werden, daß eine stückweise differenzierbare Funktion f in einer Umgebung eines nichtdegenerierten kritischen Punktes

topologisch äquivalent zu einer Funktion der Form

ist. Dabei ist l eine stetige, stückweise lineare Funktion, die sich als max-min Kombination aus den Koordinaten-Funktionen

und

zusammensetzt. In dieser Darstellung entspricht der zweite Summand dem differenzierbaren Anteil der Funktion, während der erste Summand den nicht-differenzierbaren Anteil der Funktion wiederspiegelt.

Aus dem zweiten Morse-Lemma folgt nun, daß die Niveaumengen von stückweise differenzierbaren Funktionen auf differenzierbaren Mannigfaltigkeiten homotopie-äquivalent zum Join zwischen dem differenzierbaren und nicht-differenzierbaren Anteil der Niveaumengen sind. Mit Hilfe der Künneth-Formel läßt sich dann der Morse-Index über die relativen Homotopiegruppen der Niveaumengen bestimmen, so daß insgesamt die klassische Morse-Theorie bis zu den Morse-Ungleichungen vollständig für stückweise differenzierbare Funktionen auf differenzierbaren Mannigfaltigkeiten übertragen werden kann.

Dr. Oliver Stein
(Technische Universität Chemnitz)
Bilevel-Strategien in der semi-infiniten Optimierung

Optimierungsprobleme mit endlich-dimensionalen Variablen, die unendlich vielen Ungleichungsrestriktionen unterworfen sind, nennt man semi-infinit. Die Behandlung dieser Probleme nimmt ihren Ursprung in der Approximationstheorie, und bis heute ist eine ganze Reihe weiterer Anwendungen aus Ingenieurs- und Wirtschaftswissenschaften in einer semi-infiniten Formulierung bearbeitet worden, etwa robuste Optimierungsaufgaben, Minimax-Probleme, Design Centering und Defektminimierungsaufgaben für Operatorgleichungen. Dabei ist es häufig unvermeidlich, dass die Indexmenge, durch die die Ungleichungsrestriktionen parametrisiert sind, von der Entscheidungsvariable abhängt.

Die generische Struktur der Restriktionsmenge von Problemen letzteren Typs hat sich als sehr ungewöhnlich erwiesen. Wir motivieren diese Generizitätsergebnisse geometrisch und zeigen, welche Arten von Stationaritätsbedingungen die optimalen Punkte unter verschiedenen Strukturvoraussetzungen erfüllen. Die Herleitung dieser Ergebnisse basiert entscheidend auf der Bilevel-Struktur semi-infiniter Optimierungsprobleme. Eine geschickte Ausnutzung dieser Bilevel-Struktur erlaubt es unter einer Konvexitätsannahme außerdem, einen leicht implementierbaren Lösungsalgorithmus für semi-infinite Probleme anzugeben. Wir diskutieren die Konvergenzergebnisse für diesen Algorithmus und illustrieren sie mit numerischen Beispielen.

Prof. Dr. Stephan  Dempe
(Technische Universität Freiberg)
Optimalitätsbedingungen für Zwei-Ebenen-Optimierungsaufgaben

Zwei-Ebenen-Optimierungsaufgaben sind hierarchische Optimierungsprobleme, bei denen die Menge zulässiger Punkte des sogenannten Problems der oberen Ebene von der Menge der optimalen Lösungen des Problems der unteren Ebene abhängt. Zu seiner Definition sei das folgende parametrische Optimierungsproblem betrachtet:


(Problem der unteren Ebene)

Die Optimalmenge dieses Problems sei mit

bezeichnet. Dann besteht die Zwei-Ebenen-Optimierungsaufgabe in


(Problem der oberen Ebene)

Zwei-Ebenen-Optimierungsaufgaben haben viele Anwendungen wie zum Beispiel die Prinzipal-Agenten-Theorie in der Ökonomie und die Suche nach besten chemischen Gleichgewichten.

Die Anführungszeichen in der obigen Definition sind verwendet worden, um die Unbestimmtheit in dieser Definition auszudrücken im Falle, dass das Problem der unteren Ebene keine eindeutige optimale Lösung besitzt. Die sich daraus ergebenden Konsequenzen und möglichen Modifikationen des Problems (der optimistische und der pessimistische Zugang) werden gemeinsam mit den entsprechenden Optimalitätsdefinitionen Gegenstand des Vortrags sein.

Das Hauptziel des Vortrags besteht in der Formulierung von notwendigen und hinreichenden Optimalitätsbedingungen in beiden Zugägen. Unter Verwendung bestimmter Voraussetzungen wird es sich zum Beispiel erweisen, dass es eine notwendige Voraussetzung für ein lokales Optimum ist, dass eine gewisse Anzahl von Ungleichungssystemen keine Lösung besitzt. Das ist ein wesentlicher Unterschied zu Ein-Ebenen-Optimierungsaufgaben, wo die Unlösbarkeit lediglich eines Ungleichungssystems aus der lokalen Optimalität eines Punktes folgt.



Nebeninhalt

Kontakt

Operations Research und Wirtschaftsinformatik Sekretariat
Tel.: 0231 755-5943
 

Links