@misc{Stephan, author = {Stephan, R{\"u}diger}, title = {Cardinality Constrained Combinatorial Optimization: Complexity and Polyhedra}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-11026}, number = {08-48}, abstract = {Given a combinatorial optimization problem and a subset \$N\$ of natural numbers, we obtain a cardinality constrained version of this problem by permitting only those feasible solutions whose cardinalities are elements of \$N\$. In this paper we briefly touch on questions that addresses common grounds and differences of the complexity of a combinatorial optimization problem and its cardinality constrained version. Afterwards we focus on polytopes associated with cardinality constrained combinatorial optimization problems. Given an integer programming formulation for a combinatorial optimization problem, by essentially adding Gr{\"o}tschel's cardinality forcing inequalities, we obtain an integer programming formulation for its cardinality restricted version. Since the cardinality forcing inequalities in their original form are mostly not facet defining for the associated polyhedra, we discuss possibilities to strengthen them.}, language = {en} } @misc{BorndoerferHoang, author = {Bornd{\"o}rfer, Ralf and Hoang, Nam-Dung}, title = {Fair Ticket Prices in Public Transport}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10999}, number = {08-46}, abstract = {Ticket pricing in public transport usually takes a welfare or mnemonics maximization point of view. These approaches do not consider fairness in the sense that users of a shared infrastructure should pay for the costs that they generate. We propose an ansatz to determine fair ticket prices that combines concepts from cooperative game theory and integer programming. An application to pricing railway tickets for the intercity network of the Netherlands demonstrates that, in this sense, prices that are much fairer than standard ones can be computed in this way.}, language = {en} } @misc{AchterbergBertholdHeinzetal., author = {Achterberg, Tobias and Berthold, Timo and Heinz, Stefan and Koch, Thorsten and Wolter, Kati}, title = {Constraint Integer Programming: Techniques and Applications}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10950}, number = {08-43}, abstract = {This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques for solving satisfiability problems. SCIP is available in source code and free for noncommercial use. We demonstrate the usefulness of CIP on three tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we demonstrate how to use CIP techniques to compute the number of optimal solutions of integer programs. Third, we employ the CIP framework to solve chip design verification problems, which involve some highly nonlinear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the nonlinear constraints by employing constraint programming techniques.}, language = {en} } @misc{HillerVredeveld, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {On the optimality of Least Recently Used}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10928}, number = {08-39}, abstract = {It is well known that competitive analysis yields too pessimistic results when applied to the paging problem and it also cannot make a distinction between many paging strategies. Many deterministic paging algorithms achieve the same competitive ratio, ranging from inefficient strategies as flush-when-full to the good performing least-recently-used (LRU). In this paper, we study this fundamental online problem from the viewpoint of stochastic dominance. We show that when sequences are drawn from distributions modelling locality of reference, LRU is stochastically better than any other online paging algorithm.}, language = {en} } @misc{TorresTorresBorndoerferetal., author = {Torres, Luis Miguel and Torres, Ramiro and Bornd{\"o}rfer, Ralf and Pfetsch, Marc}, title = {Line Planning on Paths and Tree Networks with Applications to the Quito Trolebus System}, organization = {ZIB}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10869}, number = {08-35}, abstract = {Line planning is an important step in the strategic planning process of a public transportation system. In this paper, we discuss an optimization model for this problem in order to minimize operation costs while guaranteeing a certain level of quality of service, in terms of available transport capacity. We analyze the problem for path and tree network topologies as well as several categories of line operation that are important for the Quito Trolebus system. It turns out that, from a computational complexity worst case point of view, the problem is hard in all but the most simple variants. In practice, however, instances based on real data from the Trolebus System in Quito can be solved quite well, and significant optimization potentials can be demonstrated.}, language = {en} } @misc{BorndoerferMuraSchlechte, author = {Bornd{\"o}rfer, Ralf and Mura, Annette and Schlechte, Thomas}, title = {Vickrey Auctions for Railway Tracks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10855}, number = {08-34}, abstract = {We consider an auction of slots to run trains through a railway network. In contrast to the classical setting for combinatorial auctions, there is not only competition for slots, but slots can mutually exclude each other, such that general conflict constraints on bids arise. This turns the winner determination problem associated with such an auction into a complex combinatorial optimization problem. It also raises a number of auction design questions, in particular, on incentive compatibilty. We propose a single-shot second price auction for railway slots, the Vickrey Track Auction (VTA). We show that this auction is incentive compatible, i.e., rational bidders are always motivated to bid their true valuation, and that it produces efficient allocations, even in the presence of constraints on allocations. These properties are, however, lost when rules on the submission of bids such as, e.g., lowest bids, are imposed. Our results carry over to generalized" Vickrey auctions with combinatorial constraints.}, language = {en} } @misc{BertholdPfetsch, author = {Berthold, Timo and Pfetsch, Marc}, title = {Detecting Orbitopal Symmetries}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10842}, number = {08-33}, abstract = {Orbitopes can be used to handle symmetries which arise in integer programming formulations with an inherent assignment structure. We investigate the detection of symmetries appearing in this approach. We show that detecting so-called orbitopal symmetries is graph-isomorphism hard in general, but can be performed in linear time if the assignment structure is known.}, language = {en} } @misc{HeinzSachenbacher, author = {Heinz, Stefan and Sachenbacher, Martin}, title = {Using Model Counting to Find Optimal Distinguishing Tests}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10832}, number = {08-32}, abstract = {Testing is the process of stimulating a system with inputs in order to reveal hidden parts of the system state. In the case of non-deterministic systems, the difficulty arises that an input pattern can generate several possible outcomes. Some of these outcomes allow to distinguish between different hypotheses about the system state, while others do~not. In this paper, we present a novel approach to find, for non-deterministic systems modeled as constraints over variables, tests that allow to distinguish among the hypotheses as good as possible. The idea is to assess the quality of a test by determining the ratio of distinguishing (good) and not distinguishing (bad) outcomes. This measure refines previous notions proposed in the literature on model-based testing and can be computed using model counting techniques. We propose and analyze a greedy-type algorithm to solve this test optimization problem, using existing model counters as a building block. We give preliminary experimental results of our method, and discuss possible improvements.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {The Line Connectivity Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10820}, number = {08-31}, abstract = {This paper introduces the "line connectivity problem", a generalization of the Steiner tree problem and a special case of the line planning problem. We study its complexity and give an IP formulation in terms of an exponential number of constraints associated with "line cut constraints". These inequalities can be separated in polynomial time. We also generalize the Steiner partition inequalities.}, language = {en} } @misc{Bley, author = {Bley, Andreas}, title = {An Integer Programming Algorithm for Routing Optimization in IP Networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10814}, number = {08-30}, abstract = {Most data networks nowadays use shortest path protocols to route the traffic. Given administrative routing lengths for the links of the network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. In this paper, we present an integer programming algorithm for the minimum congestion unsplittable shortest path routing problem, which arises in the operational planning of such networks. Given a capacitated directed graph and a set of communication demands, the goal is to find routing lengths that define a unique shortest path for each demand and minimize the maximum congestion over all links in the resulting routing. We illustrate the general decomposition approach our algorithm is based on, present the integer and linear programming models used to solve the master and the client problem, and discuss the most important implementational aspects. Finally, we report computational results for various benchmark problems, which demonstrate the efficiency of our algorithm.}, language = {en} } @misc{AchterbergKochTuchscherer, author = {Achterberg, Tobias and Koch, Thorsten and Tuchscherer, Andreas}, title = {On the Effects of Minor Changes in Model Formulations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10808}, number = {08-29}, abstract = {Starting with the description of the Traveling Salesmen Problem formulation as given by van Vyve and Wolsey in the article Approximate extended formulations'', we investigate the effects of small variations onto the performance of contemporary mixed integer programming solvers. We will show that even minor changes in the formulation of the model can result in performance difference of more than a factor of 1000. As the results show it is not obvious which changes will result in performance improvements and which not.}, language = {en} } @misc{BleyKochNiu, author = {Bley, Andreas and Koch, Thorsten and Niu, Lingfeng}, title = {Experiments with nonlinear extensions to SCIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8300}, number = {08-28}, abstract = {This paper describes several experiments to explore the options for solving a class of mixed integer nonlinear programming problems that stem from a real-world mine production planning project. The only type of nonlinear constraints in these problems are bilinear equalities involving continuous variables, which enforce the ratios between elements in mixed material streams. A branch-and-bound algorithm to handle the integer variables has been tried in another project. However, this branch-and-bound algorithm is not effective for handling the nonlinear constraints. Therefore state-of-the-art nonlinear solvers are utilized to solve the resulting nonlinear subproblems in this work. The experiments were carried out using the NEOS server for optimization. After finding that current nonlinear programming solvers seem to lack suitable preprocessing capabilities, we preprocess the instances beforehand and use an heuristic approach to solve the nonlinear subproblems. In the appendix, we explain how to add a polynomial constraint handler that uses IPOPT as embedded nonlinear programming solver for the constraint programming framework SCIP. This is one of the crucial steps for implementing our algorithm in SCIP. We briefly described our approach and give an idea of the work involved.}, language = {en} } @misc{Ridder, author = {Ridder, Johanna}, title = {Wegeprobleme der Graphentheorie}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10782}, number = {08-26}, abstract = {Den k{\"u}rzesten Weg in einem Graphen zu finden ist ein klassisches Problem der Graphentheorie. {\"U}ber einen Vortrag zu diesem Thema beim Tag der Mathematik 2007 von R. Bornd{\"o}rfer kam ich in Kontakt mit dem Konrad-Zuse-Zentrum (ZIB), das sich u.a. mit Wegeoptimierung besch{\"a}ftigt. Ein Forschungsschwerpunkt dort ist im Rahmen eines Projekts zur Chipverifikation das Z{\"a}hlen von L{\"o}sungen, das, wie wir sehen werden, eng mit dem Z{\"a}hlen von Wegen zusammenh{\"a}ngt. Anhand von zwei Fragen aus der Graphentheorie soll diese Facharbeit unterschiedliche L{\"o}sungsmethoden untersuchen. Wie bestimmt man den k{\"u}rzesten Weg zwischen zwei Knoten in einem Graphen und wie findet man alle m{\"o}glichen Wege? Nach einer Einf{\"u}hrung in die Graphentheorie und einer Konkretisierung der Probleme wird zun{\"a}chst f{\"u}r beide eine L{\"o}sung mit auf Graphen basierenden Algorithmen vorgestellt. W{\"a}hrend der Algorithmus von Dijkstra sehr bekannt ist, habe ich f{\"u}r das Z{\"a}hlen von Wegen einen eigenen Algorithmus auf der Basis der Tiefensuche entwickelt. Im zweiten Teil der Arbeit wird das Konzept der ganzzahligen Programmierung vorgestellt und die L{\"o}sungsm{\"o}glichkeiten f{\"u}r Wegeprobleme, die sich dar{\"u}ber ergeben. Schließlich wurden die vorgestellten Algorithmen am Beispiel des S- und U-Bahnnetzes von Berlin implementiert und mit Programmen, die die gleichen Fragen {\"u}ber ganzzahlige Programmierung l{\"o}sen, verglichen.}, language = {de} } @misc{Groetschel, author = {Gr{\"o}tschel, Martin}, title = {Tiefensuche: Bemerkungen zur Algorithmengeschichte}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9628}, number = {08-23}, abstract = {Dieser kurze Aufsatz zur Algorithmengeschichte ist Eberhard Knobloch, meinem Lieblings-Mathematikhistoriker, zum 65. Geburtstag gewidmet. Eberhard Knobloch hat immer, wenn ich ihm eine historische Frage zur Mathematik stellte, eine Antwort gewusst - fast immer auch sofort. Erst als ich mich selbst ein wenig und dazu amateurhaft mit Mathematikgeschichte besch{\"a}ftigte, wurde mir bewusst, wie schwierig dieses „Gesch{\"a}ft" ist. Man muss nicht nur mehrere (alte) Sprachen beherrschen, sondern auch die wissenschaftliche Bedeutung von Begriffen und Symbolen in fr{\"u}heren Zeiten kennen. Man muss zus{\"a}tzlich herausfinden, was zur Zeit der Entstehung der Texte „allgemeines Wissen" war, insbesondere, was seinerzeit g{\"u}ltige Beweisideen und -schritte waren, und daher damals keiner pr{\"a}zisen Definition oder Einf{\"u}hrung bedurfte. Es gibt aber noch eine Steigerung des historischen Schwierigkeitsgrades: Algorithmengeschichte. Dies m{\"o}chte ich in diesem Artikel kurz darlegen in der Hoffnung, dass sich Wissenschaftshistoriker dieses Themas noch intensiver annehmen, als sie das bisher tun. Der Grund ist, dass heute Algorithmen viele Bereiche unserer Alltagswelt steuern und unser t{\"a}gliches Leben oft von funktionierenden Algorithmen abh{\"a}ngt. Daher w{\"a}re eine bessere Kenntnis der Algorithmengeschichte von großem Interesse.}, language = {de} } @misc{SchlechteBorndoerfer, author = {Schlechte, Thomas and Bornd{\"o}rfer, Ralf}, title = {Balancing Efficiency and Robustness - A Bi-criteria Optimization Approach to Railway Track Allocation}, organization = {ZIB}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10763}, number = {08-22}, abstract = {Technical restrictions and challenging details let railway traffic become one of the most complex transportation systems. Routing trains in a conflict-free way through a track network is one of the basic scheduling problems for any railway company. This article focuses on a robust extension of this problem, also known as train timetabling problem (TTP), which consists in finding a schedule, a conflict free set of train routes, of maximum value for a given railway network. However, timetables are not only required to be profitable. Railway companies are also interested in reliable and robust solutions. Intuitively, we expect a more robust track allocation to be one where disruptions arising from delays are less likely to be propagated causing delays of subsequent trains. This trade-off between an efficient use of railway infrastructure and the prospects of recovery leads us to a bi-criteria optimization approach. On the one hand we want to maximize the profit of a schedule, that is more or less to maximize the number of feasible routed trains. On the other hand if two trains are scheduled as tight as possible after each other it is clear that a delay of the first one always affects the subsequent train. We present extensions of the integer programming formulation in [BorndoerferSchlechte2007] for solving (TTP). These models can incorporate both aspects, because of the additional track configuration variables. We discuss how these variables can directly be used to measure a certain type of robustness of a timetable. For these models which can be solved by column generation techniques, we propose so-called scalarization techniques, see [Ehrgott2005], to determine efficient solutions. Here, an efficient solution is one which does not allow any improvement in profit and robustness at the same time. We prove that the LP-relaxation of the (TTP) including an additional \$\epsilon\$-constraint remains solvable in polynomial time. Finally, we present some preliminary results on macroscopic real-world data of a part of the German long distance railway network.}, language = {en} } @misc{GroetschelLutzWestphal, author = {Gr{\"o}tschel, Martin and Lutz-Westphal, Brigitte}, title = {Diskrete Mathematik und ihre Anwendungen: Auf dem Weg zu authentischem Mathematikunterricht}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10758}, number = {08-21}, abstract = {Das heutige Leben ist durchdrungen von komplexen Technologien. Ohne Kommunikationsnetze, Internet, Mobilfunk, Logistik, Verkehrstechnik, medizinische Apparate, etc. k{\"o}nnte die moderne Gesellschaft nicht funktionieren. Fast alle dieser Technologien haben einen hohen Mathematikanteil. Der "normale B{\"u}rger"' weiss davon nichts, der Schulunterricht k{\"o}nnte dem ein wenig abhelfen. Einige mathematische Aspekte dieser Technologien sind einfach und sogar spielerisch intuitiv zug{\"a}nglich. Solche Anwendungen, die zus{\"a}tzlich noch der Lebensumwelt der Sch{\"u}ler zugeh{\"o}ren, k{\"o}nnen dazu genutzt werden, die mathematische Modellierung, also die mathematische Herangehensweise an die L{\"o}sung praktischer Fragen, anschaulich zu erl{\"a}utern. Gerade in der diskreten Mathematik k{\"o}nnen hier, quasi "nebenbei" mathematische Theorien erarbeitet und Teilaspekte (Definitionen, Fragestellungen, einfache Sachverhalte) durch eigenst{\"a}ndiges Entdecken der Sch{\"u}ler entwickelt werden. Wir beginnen mit einigen Beispielen.}, language = {de} } @misc{BorndoerferGroetschelJaeger, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Jaeger, Ulrich}, title = {Planung von {\"o}ffentlichem Personenverkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10744}, number = {08-20}, abstract = {Millionen von Menschen werden allein in Deutschland t{\"a}glich von Bussen, Bahnen und Flugzeugen transportiert. Der {\"o}ffentliche Personenverkehr ({\"O}V) ist von großer Bedeutung f{\"u}r die Lebensqualit{\"a}t einzelner aber auch f{\"u}r die Leistungsf{\"a}higkeit ganzer Regionen. Qualit{\"a}t und Effizienz von {\"O}V-Systemen h{\"a}ngen ab von politischen Rahmenbedingungen (staatlich geplant, wettbewerblich organisiert) und der Eignung der Infrastruktur (Schienensysteme, Flughafenstandorte), vom vorhandenen Verkehrsangebot (Fahr- und Flugplan), von der Verwendung angemessener Technologien (Informations-, Kontroll- und Buchungssysteme) und dem bestm{\"o}glichen Einsatz der Betriebsmittel (Energie, Fahrzeuge und Personal). Die hierbei auftretenden Entscheidungs-, Planungs- und Optimierungsprobleme sind z.T. gigantisch und "schreien" aufgrund ihrer hohen Komplexit{\"a}t nach Unterst{\"u}tzung durch Mathematik. Dieser Artikel skizziert den Stand und die Bedeutung des Einsatzes von Mathematik bei der Planung und Durchf{\"u}hrung von {\"o}ffentlichem Personenverkehr, beschreibt die bestehenden Herausforderungen und regt zukunftsweisende Maßnahmen an.}, language = {de} } @misc{ErolKlemenzSchlechteetal., author = {Erol, Berkan and Klemenz, Marc and Schlechte, Thomas and Schultz, S{\"o}ren and Tanner, Andreas}, title = {TTPLIB 2008 - A Library for Train Timetabling Problems}, organization = {ZIB,}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10732}, number = {08-19}, abstract = {We introduce (TTPlib), a data library for train timetabling problems that can be accessed at http://ttplib.zib.de. In version 1.0, the library contains data related to 50 scenarios. Most instances result from the combination of macroscopic railway networks and several train request sets for the German long distance area containing Hannover, Kassel and Fulda, short denoted by Ha-Ka-Fu. In this paper, we introduce the data concepts of TTPlib, describe the scenarios included in the library and provide a free visualization tool TraVis.}, language = {en} } @misc{HillerVredeveld, author = {Hiller, Benjamin and Vredeveld, Tjark}, title = {Probabilistic analysis of Online Bin Coloring algorithms via Stochastic Comparison}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10726}, number = {08-18}, abstract = {This paper proposes a new method for probabilistic analysis of online algorithms that is based on the notion of stochastic dominance. We develop the method for the Online Bin Coloring problem introduced by Krumke et al. Using methods for the stochastic comparison of Markov chains we establish the strong result that the performance of the online algorithm GreedyFit is stochastically dominated by the performance of the algorithm OneBin for any number of items processed. This result gives a more realistic picture than competitive analysis and explains the behavior observed in simulations.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Models for Fare Planning in Public Transport}, issn = {1438-0064}, doi = {10.1016/j.dam.2012.02.027}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10708}, number = {08-16}, abstract = {The optimization of fare systems in public transit allows to pursue objectives such as the maximization of demand, revenue, profit, or social welfare. We propose a non-linear optimization approach to fare planning that is based on a detailed discrete choice model of user behavior. The approach allows to analyze different fare structures, optimization objectives, and operational scenarios involving, e.g., subsidies. We use the resulting models to compute optimized fare systems for the city of Potsdam, Germany.}, language = {en} } @misc{Wolf, author = {Wolf, Thomas}, title = {The Parametric Solution of Underdetermined linear ODEs}, issn = {1438-0064}, doi = {10.1134/S0361768811020113}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10693}, number = {08-15}, abstract = {The purpose of this paper is twofold. An immediate practical use of the presented algorithm is its applicability to the parametric solution of underdetermined linear ordinary differential equations (ODEs) with coefficients that are arbitrary analytic functions in the independent variable. A second conceptual aim is to present an algorithm that is in some sense dual to the fundamental Euclids algorithm, and thus an alternative to the special case of a Gr\"{o}bner basis algorithm as it is used for solving linear ODE-systems. In the paper Euclids algorithm and the new dual version' are compared and their complementary strengths are analysed on the task of solving underdetermined ODEs. An implementation of the described algorithm is interactively accessible at http://lie.math.brocku.ca/crack/uode.}, language = {en} } @misc{TsarevWolf, author = {Tsarev, Sergey and Wolf, Thomas}, title = {Classification of 3-dimensional integrable scalar discrete equations}, issn = {1438-0064}, doi = {10.1007/s11005-008-0230-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10667}, number = {08-13}, abstract = {We classify all integrable 3-dimensional scalar discrete affine linear equations \$Q_3=0\$ on an elementary cubic cell of the lattice \${\mathbb Z}^3\$. An equation \$Q_3=0\$ \%of such form is called integrable if it may be consistently imposed on all \$3\$-dimensional elementary faces of the lattice \${\mathbb Z}^4\$. Under the natural requirement of invariance of the equation under the action of the complete group of symmetries of the cube we prove that the only ontrivial(non-linearizable) integrable equation from this class is the well-known dBKP-system.}, language = {en} } @misc{BertholdHeinzPfetsch, author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc}, title = {Solving Pseudo-Boolean Problems with SCIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10671}, number = {08-12}, abstract = {Pseudo-Boolean problems generalize SAT problems by allowing linear constraints and a linear objective function. Different solvers, mainly having their roots in the SAT domain, have been proposed and compared,for instance, in Pseudo-Boolean evaluations. One can also formulate Pseudo-Boolean models as integer programming models. That is,Pseudo-Boolean problems lie on the border between the SAT domain and the integer programming field. In this paper, we approach Pseudo-Boolean problems from the integer programming side. We introduce the framework SCIP that implements constraint integer programming techniques. It integrates methods from constraint programming, integer programming, and SAT-solving: the solution of linear programming relaxations, propagation of linear as well as nonlinear constraints, and conflict analysis. We argue that this approach is suitable for Pseudo-Boolean instances containing general linear constraints, while it is less efficient for pure SAT problems. We present extensive computational experiments on the test set used for the Pseudo-Boolean evaluation 2007. We show that our approach is very efficient for optimization instances and competitive for feasibility problems. For the nonlinear parts, we also investigate the influence of linear programming relaxations and propagation methods on the performance. It turns out that both techniques are helpful for obtaining an efficient solution method.}, language = {en} } @misc{AncoBlumanWolf, author = {Anco, Stephen and Bluman, George and Wolf, Thomas}, title = {Invertible Mappings of Nonlinear PDEs to Linear PDEs Through Admitted Conservation Laws}, organization = {Department of Mathematics, Brock University, St. Catharines, ON Canada L2S 3A1}, issn = {1438-0064}, doi = {10.1007/s10440-008-9205-7}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10652}, number = {08-11}, abstract = {An algorithmic method using conservation law multipliers is introduced that yields necessary and sufficient conditions to find invertible mappings of a given nonlinear PDE to some linear PDE and to construct such a mapping when it exists. Previous methods yielded such conditions from admitted point or contact symmetries of the nonlinear PDE. Through examples, these two linearization approaches are contrasted.}, language = {en} } @misc{Wolf, author = {Wolf, Thomas}, title = {On solving large systems of polynomial equations appearing in Discrete Differential Geometry}, issn = {1438-0064}, doi = {10.1134/S0361768808020047}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10646}, number = {08-10}, abstract = {The paper describes a method for solution of very large overdetermined algebraic polynomial systems on an example that appears from a classification of all integrable 3-dimensional scalar discrete quasilinear equations \$Q_3=0\$ on an elementary cubic cell of the lattice \${\mathbb Z}^3\$. The overdetermined polynomial algebraic system that has to be solved is far too large to be formulated. A probing' technique which replaces independent variables by random integers or zero allows to formulate subsets of this system. An automatic alteration of equation formulating steps and equation solving steps leads to an iteration process that solves the computational problem.}, language = {en} } @misc{AchterbergHeinzKoch, author = {Achterberg, Tobias and Heinz, Stefan and Koch, Thorsten}, title = {Counting solutions of integer programs using unrestricted subtree detection}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10632}, number = {08-09}, abstract = {In the recent years there has been tremendous progress in the development of algorithms to find optimal solutions for integer programs. In many applications it is, however, desirable (or even necessary) to generate all feasible solutions. Examples arise in the areas of hardware and software verification and discrete geometry. In this paper, we investigate how to extend branch-and-cut integer programming frameworks to support the generation of all solutions. We propose a method to detect so-called unrestricted subtrees, which allows us to prune the integer program search tree and to collect several solutions simultaneously. We present computational results of this branch-and-count paradigm which show the potential of the unrestricted subtree detection.}, language = {en} } @misc{Stephan, author = {Stephan, R{\"u}diger}, title = {On the cardinality constrained matroid polytope}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10614}, number = {08-08}, abstract = {Edmonds showed that the so-called rank inequalities and the nonnegativity constraints provide a complete linear description of the matroid polytope. By essentially adding Gr{\"o}tschel's cardinality forcing inequalities, we obtain a complete linear description of the cardinality constrained matroid polytope which is the convex hull of the incidence vectors of those independent sets that have a feasible cardinality. Moreover, we show how the separation problem for the cardinality forcing inequalities can be reduced to that for the rank inequalities. We also give necessary and sufficient conditions for a cardinality forcing inequality to be facet defining.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Angebotsplanung im {\"o}ffentlichen Nahverkehr}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10555}, number = {08-04}, abstract = {Die Angebotsplanung im {\"o}ffentlichen Nahverkehr umfasst die Aufgaben der Netz-, Linien-,Fahr- und Preisplanung. Wir stellen zwei mathematische Optimierungsmodelle zur Linien- und Preisplanung vor. Wir zeigen anhand von Berechnungen f{\"u}r die Verkehrsbetriebe in Potsdam(ViP), dass sich damit komplexe Zusammenh{\"a}nge quantitativ analysieren lassen. Auf diese Weise untersuchen wir die Auswirkungen von Freiheitsgraden auf die Konstruktion von Linien und die Wahl von Reisewegen der Passagiere, Abh{\"a}ngigkeiten zwischen Kosten und Reisezeiten sowie den Einfluss verschiedener Preissysteme auf Nachfrage und Kostendeckung.}, language = {de} } @misc{AchterbergBertholdKochetal., author = {Achterberg, Tobias and Berthold, Timo and Koch, Thorsten and Wolter, Kati}, title = {Constraint Integer Programming: a New Approach to Integrate CP and MIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10520}, number = {08-01}, abstract = {This article introduces constraint integer programming (CIP), which is a novel way to combine constraint programming (CP) and mixed integer programming (MIP) methodologies. CIP is a generalization of MIP that supports the notion of general constraints as in CP. This approach is supported by the CIP framework SCIP, which also integrates techniques from SAT solving. SCIP is available in source code and free for non-commercial use. We demonstrate the usefulness of CIP on two tasks. First, we apply the constraint integer programming approach to pure mixed integer programs. Computational experiments show that SCIP is almost competitive to current state-of-the-art commercial MIP solvers. Second, we employ the CIP framework to solve chip design verification problems, which involve some highly non-linear constraint types that are very hard to handle by pure MIP solvers. The CIP approach is very effective here: it can apply the full sophisticated MIP machinery to the linear part of the problem, while dealing with the non-linear constraints by employing constraint programming techniques.}, language = {en} } @misc{GroetschelNemhauser, author = {Gr{\"o}tschel, Martin and Nemhauser, George}, title = {George Dantzig's contributions to integer programming}, issn = {1438-0064}, doi = {10.1016/j.disopt.2007.08.003}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10393}, number = {07-39}, abstract = {This paper reviews George Dantzig's contribution to integer programming, especially his seminal work with Fulkerson and Johnson on the traveling salesman problem}, language = {en} } @misc{AchterbergBrinkmannWedler, author = {Achterberg, Tobias and Brinkmann, Raik and Wedler, Markus}, title = {Property Checking with Constraint Integer Programming}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10376}, number = {07-37}, abstract = {We address the property checking problem for SoC design verification at the register transfer level (RTL) by integrating techniques from integer programming, constraint programming, and SAT solving. Specialized domain propagation and preprocessing algorithms for individual RTL operations extend a general constraint integer programming framework. Conflict clauses are learned by analyzing infeasible LPs and deductions, and by employing reverse propagation. Experimental results show that our approach outperforms SAT techniques for proving the validity of properties on circuits containing arithmetics.}, language = {en} } @misc{GroetschelHillerTuchscherer, author = {Gr{\"o}tschel, Martin and Hiller, Benjamin and Tuchscherer, Andreas}, title = {Combinatorial Online Optimization: Elevators \& Yellow Angels}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10360}, number = {07-36}, abstract = {In \emph{classical optimization} it is assumed that full information about the problem to be solved is given. This, in particular, includes that all data are at hand. The real world may not be so nice'' to optimizers. Some problem constraints may not be known, the data may be corrupted, or some data may not be available at the moments when decisions have to be made. The last issue is the subject of \emph{online optimization} which will be addressed here. We explain some theory that has been developed to cope with such situations and provide examples from practice where unavailable information is not the result of bad data handling but an inevitable phenomenon.}, language = {en} } @misc{Bley, author = {Bley, Andreas}, title = {Routing and Capacity Optimization for IP networks}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10323}, number = {07-33}, abstract = {This article describes the main concepts and techniques that have been developed during the last year at ZIB to solve dimensioning and routing optimization problems for IP networks. We discuss the problem of deciding if a given path set corresponds to an unsplittable shortest path routing, the fundamental properties of such path sets, and the computational complexity of some basic network planning problems for this routing type. Then we describe an integer-linear programming approach to solve such problems in practice. This approach has been used successfully in the planning of the German national education and research network for several years.}, language = {en} } @misc{Berthold, author = {Berthold, Timo}, title = {Heuristics of the Branch-Cut-and-Price-Framework SCIP}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10280}, number = {07-30}, abstract = {In this paper we give an overview of the heuristics which are integrated into the open source branch-cut-and-price-framework SCIP. We briefly describe the fundamental ideas of different categories of heuristics and present some computational results which demonstrate the impact of heuristics on the overall solving process of SCIP.}, language = {en} } @misc{BorndoerferLiebchen, author = {Bornd{\"o}rfer, Ralf and Liebchen, Christian}, title = {When Periodic Timetables are Suboptimal}, organization = {DFG Reseach Center Matheon "Mathematics for Key Technologies"}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9151}, number = {07-29}, abstract = {The timetable is the essence of the service offered by any provider of public transport'' (Jonathan Tyler, CASPT 2006). Indeed, the timetable has a major impact on both operating costs and on passenger comfort. Most European agglomerations and railways use periodic timetables in which operation repeats in regular intervals. In contrast, many North and South American municipalities use trip timetables in which the vehicle trips are scheduled individually subject to frequency constraints. We compare these two strategies with respect to vehicle operation costs. It turns out that for short time horizons, periodic timetabling can be suboptimal; for sufficiently long time horizons, however, periodic timetabling can always be done in an optimal way'.}, language = {en} } @misc{Berthold, author = {Berthold, Timo}, title = {RENS - Relaxation Enforced Neighborhood Search}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-4264}, number = {07-28}, abstract = {In the recent years, a couple of quite successful large neighborhood search heuristics for mixed integer programs has been published. Up to our knowledge, all of them are improvement heuristics. We present a new start heuristic for general MIPs working in the spirit of large neighborhood search. It constructs a sub-MIP which represents the space of all feasible roundings of some fractional point - normally the optimum of the LP-relaxation of the original MIP. Thereby, one is able to determine whether a point can be rounded to a feasible solution and which is the best possible rounding. Furthermore, a slightly modified version of RENS proves to be a well-performing heuristic inside the branch-cut-and-price-framework SCIP.}, language = {en} } @misc{HillerTuchscherer, author = {Hiller, Benjamin and Tuchscherer, Andreas}, title = {Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10108}, number = {07-26}, abstract = {Algorithmic control of elevator systems has been studied for a long time. More recently, a new paradigm for elevator control has emerged. In destination call systems, the passenger specifies not only the direction of his ride, but the destination floor. Such a destination call system is very interesting from an optimization point of view, since more information is available earlier, which should allow improved planning. However, the real-world destination call system envisioned by our industry partner requires that each destination call (i.e. passenger) is assigned to a serving elevator immediately. This early assignment restricts the potential gained from the destination information. Another aspect is that there is no way to specify the destination floor in the cabin. Therefore, the elevator has to stop on every destination floor of an assigned call, although the passenger may not have boarded the cabin, e.g. due to insufficient capacity. In this paper we introduce a new destination call control algorithm suited to this setting. Since the control algorithm for an entire elevator group has to run on embedded microprocessors, computing resources are very scarce. Since exact optimization is not feasible on such hardware, the algorithm is an insertion heuristic using a non-trivial data structure to maintain a set of tours. To assess the performance of our algorithm, we compare it to similar and more powerful algorithms by simulation. We also compare to algorithms for a conventional system and with a more idealized destination call system. This gives an indication of the relative potentials of these systems. In particular, we assess how the above real-world restrictions influence performance. The algorithm introduced has been implemented by our industry partner for real-world use.}, language = {en} } @misc{KaibelStephan, author = {Kaibel, Volker and Stephan, R{\"u}diger}, title = {On cardinality constrained cycle and path polytopes}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-10093}, number = {07-25}, abstract = {We consider polytopes associated with cardinality constrained path and cycle problems defined on a directed or undirected graph. We present integer characterizations of these polytopes by facet defining linear inequalities for which the separation problem can be solved in polynomial time. Moreover, we give further facet defining inequalities, in particular those that are specific to odd/even paths and cycles.}, language = {en} } @misc{HarksHeinzPfetschetal., author = {Harks, Tobias and Heinz, Stefan and Pfetsch, Marc and Vredeveld, Tjark}, title = {Online Multicommodity Routing with Time Windows}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9654}, number = {07-22}, abstract = {We consider a multicommodity routing problem, where demands are released \emph{online} and have to be routed in a network during specified time windows. The objective is to minimize a time and load dependent convex cost function of the aggregate arc flow. First, we study the fractional routing variant. We present two online algorithms, called Seq and Seq\$^2\$. Our first main result states that, for cost functions defined by polynomial price functions with nonnegative coefficients and maximum degree~\$d\$, the competitive ratio of Seq and Seq\$^2\$ is at most \$(d+1)^{d+1}\$, which is tight. We also present lower bounds of \$(0.265\,(d+1))^{d+1}\$ for any online algorithm. In the case of a network with two nodes and parallel arcs, we prove a lower bound of \$(2-\frac{1}{2} \sqrt{3})\$ on the competitive ratio for Seq and Seq\$^2\$, even for affine linear price functions. Furthermore, we study resource augmentation, where the online algorithm has to route less demand than the offline adversary. Second, we consider unsplittable routings. For this setting, we present two online algorithms, called U-Seq and U-Seq\$^2\$. We prove that for polynomial price functions with nonnegative coefficients and maximum degree~\$d\$, the competitive ratio of U-Seq and U-Seq\$^2\$ is bounded by \$O{1.77^d\,d^{d+1}}\$. We present lower bounds of \$(0.5307\,(d+1))^{d+1}\$ for any online algorithm and \$(d+1)^{d+1}\$ for our algorithms. Third, we consider a special case of our framework: online load balancing in the \$\ell_p\$-norm. For the fractional and unsplittable variant of this problem, we show that our online algorithms are \$p\$ and \$O{p}\$ competitive, respectively. Such results where previously known only for scheduling jobs on restricted (un)related parallel machines.}, language = {en} } @misc{KosterOrlowskiRaacketal., author = {Koster, Arie M.C.A. and Orlowski, Sebastian and Raack, Christian and Bayer, Georg and Engel, Thomas}, title = {Single-layer Cuts for Multi-layer Network Design Problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9641}, number = {07-21}, abstract = {We study a planning problem arising in SDH/WDM multi-layer telecommunication network design. The goal is to find a minimum cost installation of link and node hardware of both network layers such that traffic demands can be realized via grooming and a survivable routing. We present a mixed-integer programming formulation that takes many practical side constraints into account, including node hardware, several bitrates, and survivability against single physical node or link failures. This model is solved using a branch-and-cut approach with problem-specific preprocessing and cutting planes based on either of the two layers. On several realistic two-layer planning scenarios, we show that these cutting planes are still useful in the multi-layer context, helping to increase the dual bound and to reduce the optimality gaps.}, language = {en} } @misc{BorndoerferSchlechte, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Solving Railway Track Allocation Problems}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9631}, number = {07-20}, abstract = {The \emph{optimal track allocation problem} (\textsc{OPTRA}), also known as the train routing problem or the train timetabling problem, is to find, in a given railway network, a conflict-free set of train routes of maximum value. We propose a novel integer programming formulation for this problem that is based on additional configuration' variables. Its LP-relaxation can be solved in polynomial time. These results are the theoretical basis for a column generation algorithm to solve large-scale track allocation problems. Computational results for the Hanover-Kassel-Fulda area of the German long distance railway network involving up to 570 trains are reported.}, language = {en} } @misc{OrlowskiPioroTomaszewskietal., author = {Orlowski, Sebastian and Pioro, Michal and Tomaszewski, Artur and Wess{\"a}ly, Roland}, title = {SNDlib 1.0--Survivable Network Design Library}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9582}, number = {07-15}, abstract = {We provide information on the Survivable Network Design Library (SNDlib), a data library for fixed telecommunication network design that can be accessed at http://sndlib.zib.de. In version 1.0, the library contains data related to 22 networks which, combined with a set of selected planning parameters, leads to 830 network planning problem instances. In this paper, we provide a mathematical model for each planning problem considered in the library and describe the data concepts of the SNDlib. Furthermore, we provide statistical information and details about the origin of the data sets.}, language = {en} } @misc{BorndoerferSchlechte, author = {Bornd{\"o}rfer, Ralf and Schlechte, Thomas}, title = {Models for Railway Track Allocation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-9451}, number = {07-02}, abstract = {This article is about the optimal track allocation problem (OPTRA) to find, in a given railway network, a conflict free set of train routes of maximum value. We study two types of integer programming formulations: a standard formulation that models block conflicts in terms of packing constraints, and a new extended formulation that is based on additional configuration' variables. We show that the packing constraints in the standard formulation stem from an interval graph, and that they can be separated in polynomial time. It follows that the LP relaxation of a strong version of this model, including all clique inequalities from block conflicts, can be solved in polynomial time. We prove that the extended formulation produces the same LP bound, and that it can also be computed with this model in polynomial time. Albeit the two formulations are in this sense equivalent, the extended formulation has advantages from a computational point of view, because it features a constant number of rows and is therefore amenable to standard column generation techniques. Results of an empirical model comparison on mesoscopic data for the Hannover-Fulda-Kassel region of the German long distance railway network are reported.}, language = {en} } @misc{BorndoerferGroetschelLukacetal.2005, author = {Bornd{\"o}rfer, Ralf and Gr{\"o}tschel, Martin and Lukac, Sascha and Mitusch, Kay and Schlechte, Thomas and Schultz, S{\"o}ren and Tanner, Andreas}, title = {An Auctioning Approach to Railway Slot Allocation}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8786}, number = {05-45}, year = {2005}, abstract = {We present an approach to implement an auction of railway slots. Railway network, train driving characteristics, and safety requirements are described by a simplified, but still complex macroscopic model. In this environment, slots are modelled as combinations of scheduled track segments. The auction design builds on the iterative combinatorial auction. However, combinatorial bids are restricted to some types of slot bundles that realize positive synergies between slots. We present a bidding language that allows bidding for these slot bundles. An integer programming approach is proposed to solve the winner determination problem of our auction. Computational results for auction simulations in the Hannover-Fulda-Kassel area of the German railway network give evidence that auction approaches can induce a more efficient use of railway capacity.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Optimal Fares for Public Transport}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8698}, number = {05-35}, abstract = {The \emph{fare planning problem} for public transport is to design a system of fares that maximize the revenue. We introduce a nonlinear optimization model to approach this problem. It is based on a d iscrete choice logit model that expresses demand as a function of the fares. We illustrate our approach by computing and comparing two different fare systems for the intercity network of the Netherlands.}, language = {en} } @misc{BorndoerferNeumannPfetsch, author = {Bornd{\"o}rfer, Ralf and Neumann, Marika and Pfetsch, Marc}, title = {Fare Planning for Public Transport}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-8541}, number = {05-20}, abstract = {In this paper we introduce the fare planning problem for public transport which consists in designing a system of fares maximizing revenue. We propose a new simple general model for this problem. It i s based on a demand function and constraints for the different fares. The constraints define the structure of the fare system, e.g., distance dependent fares or zone fares. We discuss a simple example with a quadratic demand function and distance dependent fares. Then we introduce a more realistic discrete choice model in which passengers choose between different alternatives depending on the numb er of trips per month. We demonstrate the examples by computational experiments.}, language = {en} } @misc{MarencoWagler, author = {Marenco, Javier and Wagler, Annegret}, title = {Chromatic Scheduling Polytopes coming from the Bandwidth Allocation Problem in Point-to-Multipoint Radio AccessSystems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7614}, number = {03-39}, abstract = {Point-to-Multipoint systems are one kind of radio systems supplying wireless access to voice/data communication networks. Such systems have to be run using a certain frequency spectrum, which typically causes capacity problems. Hence it is, on the one hand, necessary to reuse frequencies but, on the other hand, no interference must be caused thereby. This leads to the bandwidth allocation problem, a special case of so-called chromatic scheduling problems. Both problems are NP-hard, and there exist no polynomial time approximation algorithms with a guaranteed quality. One kind of algorithms which turned out to be successful for many other combinatorial optimization problems uses cutting plane methods. In order to apply such methods, knowledge on the associated polytopes is required. The present paper contributes to this issue, exploring basic properties of chromatic scheduling polytopes and several classes of facet-defining inequalities.}, language = {en} } @misc{Borndoerfer, author = {Bornd{\"o}rfer, Ralf}, title = {Combinatorial Packing Problems}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-7255}, number = {03-03}, abstract = {This article investigates a certain class of combinatorial packing problems and some polyhedral relations between such problems and the set packing problem.}, language = {en} } @phdthesis{Krumke, author = {Krumke, Sven}, title = {Online Optimization: Competitive Analysis and Beyond}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6925}, number = {02-25}, abstract = {Traditional optimization techniques assume, in general, knowledge of all data of a problem instance. There are many cases in practice, however, where decisions have to be made before complete information about the data is available. In fact, it may be necessary to produce a part of the problem solution as soon as a new piece of information becomes known. This is called an \emph{online situation}, and an algorithm is termed \emph{online}, if it makes a decision (computes a partial solution) whenever a new piece of data requests an action. \emph{Competitive analysis} has become a standard yardstick to measure the quality of online algorithms. One compares the solution produced by an online algorithm to that of an optimal (clairvoyant) offline algorithm. An online algorithm is called \$c\$-competitive if on every input the solution it produces has cost'' at most \$c\$~times that of the optimal offline algorithm. This situation can be imagined as a game between an online player and a malicious adversary. Although competitive analysis is a worst-case analysis and henceforth pessimistic, it often allows important insights into the problem structure. One can obtain an idea about what kind of strategies are promising for real-world systems and why. On the other hand there are also cases where the offline adversary is simply too powerful and allows only trivial competitiveness results. This phenomenon is called hitting the triviality barrier''. We investigate several online problems by means of competitive analysis. We also introduce new concepts to overcome the weaknesses of the standard approach and to go beyond the triviality barrier.}, language = {en} } @phdthesis{Helmberg, author = {Helmberg, Christoph}, title = {Semidefinite Programming for Combinatorial Optimization}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-6022}, number = {00-34}, abstract = {This book offers a self-contained introduction to the field of semidefinite programming, its applications in combinatorial optimization, and its computational methods. We equip the reader with the basic results from linear algebra on positive semidefinite matrices and the cone spanned by them. Starting from linear programming, we introduce semidefinite programs and discuss the associated duality theory. We then turn to semidefinite relaxations of combinatorial optimization and illustrate their interrelation. In the second half we deal with computational methods for solving semidefinite programs. First, the interior point approach, its iteration complexity, and implementational issues are discussed. Next, we explain in great detail the spectral bundle method, which is particularly suited for large scale semidefinite programming. One of the most successful techniques in integer linear programming is the cutting plane approach which improves an initial relaxation by adding violated inequalities. We explore possibilities to combine the two solution methods with the cutting plane approach in order to strengthen semidefinite relaxations of combinatorial optimization problems.}, language = {en} }