Refine
Year of publication
Document Type
- Article (119)
- ZIB-Report (110)
- In Proceedings (38)
- Book chapter (34)
- Book (4)
- In Collection (4)
- Report (2)
- Master's Thesis (1)
Is part of the Bibliography
- no (312)
Keywords
- combinatorial optimization (4)
- integer programming (4)
- polyhedral combinatorics (4)
- BBAW (3)
- Dublin Core (3)
- Heuristics (3)
- Kooperativer Bibliotheksverbund Berlin-Brandenburg (3)
- Math-Net (3)
- column generation (3)
- polyhedra and polytopes (3)
- polynomial inequalities (3)
- Bibliotheksverbund (2)
- Harvest (2)
- Information System (2)
- Integer Programming (2)
- Internet services (2)
- KOBV (2)
- KOBV-Suchmaschine (2)
- Math-Net-Links (2)
- Online Optimization (2)
- Online-Optimierung (2)
- Open Access (2)
- Operations Research (2)
- RDF (2)
- Steiner tree (2)
- TSP (2)
- XML (2)
- distributed systems (2)
- elektronisches Publizieren (2)
- frequency assignment (2)
- line planning (2)
- online optimization (2)
- real-world problems (2)
- semi-algebraic sets (2)
- stability index (2)
- vehicle dispatching (2)
- öffentlicher Verkehr (2)
- ADAC (1)
- Algebraic Modelling Languages (1)
- Algorithmengeschichte (1)
- Algorithmus (1)
- Architektur der Suchmaschine (1)
- Asymmetric Travelling Salesman Problem (1)
- Aufzugssteuerung (1)
- Aufzugsteuerung (1)
- Automatic Storage System (1)
- Bibliothek der Zukunft (1)
- Branch&Cut-Algorithm (1)
- CEIC (1)
- Cellular Radio Telephone Systems (1)
- Column Generation (1)
- Combinatorial Auctions (1)
- Competitive Analysis (1)
- Constraint Shortest Paths Problem (1)
- Control of Stacker Cranes (1)
- Copyright (1)
- Cycles in Matroids (1)
- Discrete Mathematics (1)
- Diskrete Mathematik (1)
- Diskrete Optimierung (1)
- Dispatching von Fahrzeugen (1)
- Duty Scheduling (1)
- E-Learning (1)
- Echtzeit-Optimierung (1)
- Energy (1)
- FTTx, FTTH, FTTB, FTTC, FTTN, telecommunications, access networks, passive optical networks, network design, routing, energy efficiency (1)
- Facets (1)
- Frequency Assignment Problem (1)
- Frequenzplanung (1)
- GSM-Funknetze (1)
- Gemeinsamer Index (1)
- Gemischt-ganzzahlige Optimierung (1)
- George Dantzig (1)
- Hochschulbibliotheken (1)
- IMU (1)
- Integer Programs (1)
- KOBV-Projekt (1)
- Klassifikation (1)
- Kombinatorische Optimierung (1)
- Komplexität (1)
- Komplexitätstheorie (1)
- Kostenaufteilungsprobleme (1)
- Kürzeste Wege (1)
- Laserschweißen (1)
- MIP-Solver (1)
- Mathematics in Industry (1)
- Mathematik als Entscheidungshilfe (1)
- Mathematikunterricht in Schulen (1)
- Metadaten (1)
- Minimum-Cost Flow Problems (1)
- Mobilfunk (1)
- Modelling (1)
- Network Capacity Planning (1)
- OSPF Routing (1)
- Online Public Access Catalog (1)
- Online optimization (1)
- Online-Algorithm (1)
- Open Access Catalog (1)
- Optimierung (1)
- Optimization (1)
- P=NP (1)
- PCB Design (1)
- Packing (1)
- Produktionsfaktor Mathematik (1)
- Public transport (1)
- Publikations- und Kommunikationstechniken (1)
- Railway Slot Allocation (1)
- Realtime Optimization (1)
- Rundreisen (1)
- Shortest Path Routing (1)
- Spieltheorie (1)
- Steiner tree packing (1)
- Suchmaschine (1)
- Survey (1)
- Survivable Networks (1)
- Teaching (1)
- Telecommunication (1)
- Telecommunication Network Design (1)
- Telekommunikation (1)
- Telota (1)
- Telota-Projekt (1)
- Time Windows (1)
- Train Dispatching (1)
- Transportation (1)
- Transportation Systems (1)
- Traveling Salesman Problem (1)
- Travelling-Salesman-Problem (1)
- Verteilte Suche (1)
- Wahlverfahren und Mathematik (1)
- Wissenschaftsrat (1)
- World Digital Mathematics Library (1)
- applications in industry (1)
- applications of integer programming (1)
- applications to manufacturing (1)
- authentischer Mathematikunterricht (1)
- branch and bound (1)
- cardinality homogeneous set systems (1)
- chains (1)
- coloring (1)
- competitive analysis (1)
- competitiveness (1)
- computational complexity (1)
- cutting plane algorithm (1)
- cutting planes (1)
- digitale Bibliothek (1)
- digitale Information (1)
- digitale Informationstechnologie (1)
- digitale Informationsversorgung (1)
- discrete mathematics (1)
- discrete optimization (1)
- diskrete Mathematik (1)
- diskrete Optimierung (1)
- duty scheduling (1)
- dynamic programming (1)
- e-learning (1)
- electronic learning (1)
- elektronische Publikation (1)
- elektronisches Lehren und Lernen (1)
- elevator (1)
- elevator control (1)
- facets (1)
- ganzzahlige Programmierung (1)
- gas transport optimization (1)
- graph coloring (1)
- graph theory (1)
- greedy algorithm (1)
- hop constraints (1)
- industrial mathematics (1)
- kompetitive Analyse (1)
- mixed integer nonlinear programming (1)
- mixed-integer programs (1)
- mobile phone (1)
- operations research (1)
- optimale Tour (1)
- perfect graphs (1)
- placement (1)
- polyhedron (1)
- polytopes (1)
- pricing (1)
- public transit (1)
- public transportation (1)
- real world data (1)
- real-time (1)
- routing (1)
- routing in VLSI-design (1)
- semialgebraic sets (1)
- shortest paths (1)
- simulation studies (1)
- soft time windows (1)
- techniques of publishing and communication (1)
- telecommunication (1)
- transportation planning (1)
- traveling salesman problem (1)
- vehicle scheduling (1)
- wissenschaftliche Informationsversorgung (1)
- Öffentlicher Personenverkehr (1)
10 Jahre TELOTA
(2012)
Das TELOTA-Projekt - zunächst nur für zwei Jahre gestartet - feierte am 15. Juni 2011 sein 10-jähriges Bestehen im Rahmen eines Workshops mit einem abschließenden Festvortrag von Richard Stallmann zum Thema „Copyright versus community in the age of computer networks“. Diese Veranstaltung zeigte, wie aktuell die TELOTA-Themen weiterhin sind und dass diese eine große Resonanz in der allgemeinen Öffentlichkeit finden. Die TELOTA-Aktivitäten haben sich als wichtiger Bestandteil der IT-Infrastruktur der BBAW erwiesen, gehen aber weit über reinen Service hinaus. Sie beeinflussen die Forschung selbst und führen zu neuen interessanten wissenschaftlichen Fragestellungen. Der Rückblick auf die ersten zehn Jahre der TELOTA-Initiative in diesem Artikel soll einen kleinen Eindruck von dem geben, was bisher geleistet wurde.
10 Jahre TELOTA
(2012)
Das TELOTA-Projekt - zunächst nur für zwei Jahre gestartet - feierte am 15. Juni 2011 sein
10-jähriges Bestehen im Rahmen eines Workshops mit einem abschließenden Festvortrag von
Richard Stallmann zum Thema „Copyright versus community in the age of computer
networks“. Diese Veranstaltung zeigte, wie aktuell die TELOTA-Themen weiterhin sind und
dass diese eine große Resonanz in der allgemeinen Öffentlichkeit finden. Die TELOTA-Aktivitäten
haben sich als wichtiger Bestandteil der IT-Infrastruktur der BBAW erwiesen,
gehen aber weit über reinen Service hinaus. Sie beeinflussen die Forschung selbst und führen
zu neuen interessanten wissenschaftlichen Fragestellungen. Der Rückblick auf die ersten zehn
Jahre der TELOTA-Initiative in diesem Artikel soll einen kleinen Eindruck von dem geben,
was bisher geleistet wurde.
The line planning problem is one of the fundamental problems in strategic planning of public and rail transport. It consists in finding lines and corresponding frequencies in a transport network such that a given travel demand can be satisfied. There are (at least) two objectives. The transport company wishes to minimize operating costs, the passengers want to minimize travel times. We propose a n ew multi-commodity flow model for line planning. Its main features, in comparison to existing models, are that the passenger paths can be freely routed and that the lines are generated dynamically. We discuss properties of this model and investigate its complexity. Results with data for the city of Potsdam, Germany, are reported.
Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate. Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems. The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de
Natural gas is one of the most important energy sources in Germany and Europe. In recent years, political regulations have led to a strict separation of gas trading and gas transport, thereby assigning a central role in energy politics to the transportation and distribution of gas. These newly imposed political requirements influenced the technical processes of gas transport in such a way that the complex task of planning and operating gas networks has become even more intricate.
Mathematically, the combination of discrete decisions on the configuration of a gas transport network, the nonlinear equations describing the physics of gas, and the uncertainty in demand and supply yield large-scale and highly complex stochastic mixed-integer nonlinear optimization problems.
The Matheon project "Optimization of Gas Transport" takes the key role of making available the necessary core technology to solve the mathematical optimization problems which model the topology planning and the operation of gas networks. An important aspect of the academic impact is the free availability of our framework. As a result of several years of research and development, it is now possible to download a complete state-of-the-art framework for mixed-integer linear and nonlinear programming in source code at http://scip.zib.de
A Network Dimensioning Tool
(1996)
Designing low cost networks that survive certain failure situations belongs to one of the prime tasks in the telecommunications industry. In this paper we describe a mathematical model combining several aspects of survivability that are elsewhere treated in a hierarchical fashion. We present mathematical investigations of this integrated model, a cutting plane algorithm, as well as several heuristics for its solution. Moreover, we report computational results with real world data. The problem we address is the following. Suppose, between each pair of nodes in a region, a communication demand is given. We want to determine the topology of a telecommunication network connecting the given nodes and to dimension all potential physical links. For each link, the possible capacities are restricted to a given finite set. The capacities must be chosen such that the communication demands are satisfied, even if certain network components fail, and such that the network building costs are as small as possible. Moreover, for each pair of nodes and each failure situation, we want to determine the paths on which the demand between the nodes is routed.
The asymmetric travelling salesman problem with time windows (ATSP-TW) is a basic model for scheduling and routing applications. In this paper we present a formulation of the problem involving only 0/1-variables associated with the arcs of the underlying digraph. This has the advantage of avoiding additional variables as well as the associated (typically very ineffective) linking constraints. In the formulation, time window restrictions are modelled by means of ``infeasible path elimination'' constraints. We present the basic form of these constraints along with some possible strengthenings. Several other classes of valid inequalities derived from related asymmetric travelling salesman problems are also described, along with a lifting theorem. We also study the ATSP-TW polytope, $P_{TW}$, defined as the convex hull of the integer solutions of our model. We show that determining the dimension of $P_{TW}$ is strongly {\em NP}--complete problem, even if only one time window is present. In this latter case, we provide a minimal equation system for $P_{TW}$. Computational experiments on the new formulation are reported in a companion paper [1997] where we show that it outperforms alternative formulations on some classes of problem instances.
The need to solve {\it transportation problems\/} was and still is one of the driving forces behind the development of the mathematical disciplines of graph theory, optimization, and operations research. Transportation problems seem to occur for the first time in the literature in the form of the four ''River Crossing Problems'' in the book Propositiones ad acuendos iuvenes. The {\it Propositiones\/} ---the oldest collection of mathematical problems written in Latin--- date back to the $8$th century A.D. and are attributed to Alcuin of York, one of the leading scholars of his time, a royal advisor to Charlemagne at his Frankish court. Alcuin's river crossing problems had no impact on the development of mathematics. However, they already display all the characteristics of today's large-scale real transportation problems. From our point of view, they could have been the starting point of combinatorics, optimization, and operations research. We show the potential of Alcuin's problems in this respect by investigating his problem~18 about a wolf, a goat and a bunch of cabbages with current mathematical methods. This way, we also provide the reader with a leisurely introduction into the modern theory of integer programming.
An application of combinatorial optimization to statistical physics and circuit layout design
(1988)
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.
Die vorliegende Arbeit ist die (z.T.~wesentlich) erweiterte Fassung eines Vortrages auf dem Deutschen Dokumentartag im September 1995 an der Fachhochschule Potsdam. Unser Ziel ist eine Bestandsaufnahme der gegenwärtigen Entwicklungen auf dem Gebiet der elektronischen Information und Kommunikation. Wir diskutieren Chancen und Risiken, beleuchten gesellschaftliche Rahmenbedingungen - vor allem im Vergleich mit den Vereinigten Staaten von Amerika - und skizzieren Aufgaben im Bereich von Forschung, Staat und Wirtschaft, die unserer Meinung nach noch zu bewältigen sind. Wir führen insbesondere in Gebiete ein, die vermutlich in naher Zukunft die Landschaft des Dokumentierens und Archivierens wesentlich verändern werden. Wir benutzen dabei häufig Beispiele und Modellvorstellungen aus der Mathematik, unserem eigenen Fachgebiet, die u.a. zeigen, wie Elemente des Informierens, Dokumentierens und Archivierens durch die neuen Technologien der elektronischen Datenverarbeitung und Kommunikation ineinander flie\"sen. Mehr Leistung kann mit geringeren Kosten erzielt werden. Wir schliessen mit einer Auflistung von neuen Perspektiven und Möglichkeiten zum Handeln in diesem Bereich.
Designing low-cost networks that survive certain failure situations is one of the prime tasks in the telecommunication industry. In this paper we survey the development of models for network survivability used in practice in the last ten years. We show how algorithms integrating polyhedral combinatorics, linear programming, and various heuristic ideas can help solve real-world network dimensioning instances to optimality or within reasonable quality guarantees in acceptable running times. The most general problem type we address is the following. Let a communication demand between each pair of nodes of a telecommunication network be given. We consider the problem of choosing, among a discrete set of possible capacities, which capacity to install on each of the possible edges of the network in order to (i) satisfy all demands, (ii) minimize the building cost of the network. \noindent In addition to determining the network topology and the edge capacities we have to provide, for each demand, a routing such that (iii) no path can carry more than a given percentage of the demand, (iv) no path in the routing exceeds a given length. \noindent We also have to make sure that (v) for every single node or edge failure, a certain percentage of the demand is reroutable. \noindent Moreover, for all failure situations feasible routings must be computed. The model described above has been developed in cooperation with a German mobile phone provider. We present a mixed-integer programming formulation of this model and computational results with data from practice.
A subset ${\cal C}$ of the power set of a finite set $E$ is called cardinality homogeneous if, whenever ${\cal C}$ contains some set $F$, ${\cal C}$ contains all subsets of $E$ of cardinality $|F|$. Examples of such set systems ${\cal C}$ are the sets of circuits and the sets of cycles of uniform matroids and the sets of all even or of all odd cardinality subsets of $E$. With each cardinality homogeneous set system ${\cal C}$, we associate the polytope $P({\cal C})$, the convex hull of the incidence vectors of all sets in ${\cal C}$, and provide a complete and nonredundant linear description of $P({\cal C})$. We show that a greedy algorithm optimizes any linear function over $P({\cal C})$, give an explicit optimum solution of the dual linear program, and provide a polynomial time separation algorithm for the class of polytopes of type $P({\cal C})$.
In this paper, we study the hop constrained chain polytope, that is, the convex hull of the incidence vectors of (s,t)-chains using at most k arcs of a given digraph, and its dominant. We use extended formulations (implied by the inherent structure of the Moore-Bellman-Ford algorithm) to derive facet defining inequalities for these polyhedra via projection. Our findings result into characterizations of all facet defining {0,+1,-1}-inequalities for the hop constrained chain polytope and all facet defining {0,1}-inequalities
for its dominant. Although the derived inequalities are already known, such classifications were not previously given to the best of our knowledge. Moreover, we use this approach to generalize so called jump inequalities, which have been introduced in a paper of Dahl and Gouveia in 2004.
In ``classical'' optimization, all data of a problem instance are considered given. The standard theory and the usual algorithmic techniques apply to such cases only. Online optimization is different. Many decisions have to be made before all data are available. In addition, decisions once made cannot be changed. How should one act ``best'' in such an environment? In this paper we survey online problems coming up in combinatorial optimization. We first outline theoretical concepts, such as competitiveness against various adversaries, to analyze online problems and algorithms. The focus, however, lies on real-world applications. We report, in particular, on theoretical investigations and our practical experience with problems arising in transportation and the automatic handling of material.
This paper gives a short introduction into combinatorial online optimization. It explains a few evaluation concepts of online algorithms, such as competitiveness, and discusses limitations in their application to real--world problems. The main focus, however, is a survey of combinatorial online problems coming up in practice, in particular, in large scale material flow and flexible manufacturing systems.
Optimization is the task of finding an optimum solution to a given problem. When the decision variables are discrete we speak of a combinatorial optimization problem. Such a problem is online when decisions have to be made before all data of the problem are known. And we speak of a real-time online problem when online decisions have to be computed within very tight time bounds. This paper surveys the are of combinatorial online and real-time optimization, it discusses, in particular, the concepts with which online and real-time algorithms can be analyzed.
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.
Combinatorial Optimization
(1995)
Combinatorial Optimization.
(1993)