TY - GEN A1 - Rambau, Jörg A1 - Santos, Francisco T1 - The Generalized Baues Problem for Cyclic Polytopes I. N2 - The Generalized Baues Problem asks whether for a given point configuration the order complex of all its proper polyhedral subdivisions, partially ordered by refinement, is homotopy equivalent to a sphere. In this paper, an affirmative answer is given for the vertex sets of cyclic polytopes in all dimensions. This yields the first non-trivial class of point configurations with neither a bound on the dimension, the codimension, nor the number of vertice for which this is known to be true. Moreover, it is shown that all triangulations of cyclic polytopes are lifting triangulations. This contrasts the fact that in general there are many non-regular triangulations of cyclic polytopes. Beyond this, we find triangulations of $C(11,5)$ with flip deficiency. This proves---among other things---that there are triangulations of cyclic polytopes that are non-regular for every choice of points on the moment curve. T3 - ZIB-Report - SC-98-14 KW - Generalized Baues Problem KW - Polyhedral Subdivisions KW - Induced Subdivisions KW - Poset KW - Spherical KW - Cyclic Polytopes KW - Bistellar Operations KW - Flip Defici Y1 - 1998 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-3579 ER - TY - GEN A1 - Rambau, Jörg T1 - Circuit Admissible Triangulations of Oriented Matroids N2 - All triangulations of euclidean oriented matroids are of the same PL-homeomorphism type by a result of Anderson. That means all triangulations of euclidean acyclic oriented matroids are PL-homeomorphic to PL-balls and that all triangulations of totally cyclic oriented matroids are PL-homeomorphic to PL-spheres. For non-euclidean oriented matroids this question is wide open. One key point in the proof of Anderson is the following fact: for every triangulation of a euclidean oriented matroid the adjacency graph of the set of all simplices ``intersecting'' a segment $[p_-p_+]$ is a path. We call this graph the $[p_-p_+]$-adjacency graph of the triangulation. While we cannot solve the problem of the topological type of triangulations of general oriented matroids we show in this note that for every circuit admissible triangulation of an arbitrary oriented matroid the $[p_-p_+]$-adjacency graph is a path. T3 - ZIB-Report - 00-45 KW - triangulations of oriented matroids KW - topological type KW - segment adjacency graph Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6139 ER - TY - GEN A1 - Rambau, Jörg T1 - Triangulierungen von Punktmengen und Polyedern N2 - Dieser Report wurde im Sommersemester 2000 an der TU Berlin in einer Spezialvorlesung über Triangulierungen von Punktmengen und Polyedern als Skriptum verwendet. Nach einem motivierenden Kapitel werden grundlegende Begriffe und Konstruktionen in der Theorie der Triangulierungen von Punktmengen und Polyedern vorgestellt. Danach werden als weiterführende Themen reguläre Triangulierungen, Sekundärpolytope, bistellare Operationen, höhere Stasheff-Tamari-Halbordnungen und Triangulierungen mit wenigen bzw. gar keinen Flips behandelt. Ein Kapitel über Enumeration und Optimierung beschließt die Zusammenstellung. T3 - ZIB-Report - 00-46 KW - point configuration KW - triangulation KW - polytope KW - polyhedron KW - Gale diagram KW - secondary polytope KW - cyclic polytope KW - graph of all triangulations KW - conn Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6145 ER - TY - GEN A1 - Rambau, Jörg T1 - TOPCOM: Triangulations of Point Configurations and Oriented Matroids N2 - TOPCOM is a package for computing triangulations of point configurations and oriented matroids. For example, for a point configuration one can compute the chirotope, components of the flip graph of triangulations, enumerate all triangulations. The core algorithms implemented in TOPCOM are described, and implentation issues are discussed. T3 - ZIB-Report - 02-17 KW - triangulation KW - point configuration KW - oriented matroid KW - software KW - chirotope KW - circuit KW - cocircuit KW - symmetry KW - TOPCOM Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6849 ER - TY - GEN A1 - Pfeifle, Julian A1 - Rambau, Jörg T1 - Computing Triangulations Using Oriented Matroids N2 - Oriented matroids are combinatorial structures that encode the combinatorics of point configurations. The set of all triangulations of a point configuration depends only on its oriented matroid. We survey the most important ingredients necessary to exploit oriented matroids as a data structure for computing all triangulations of a point configuration, and report on experience with an implementation of these concepts in the software package TOPCOM. Next, we briefly overview the construction and an application of the secondary polytope of a point configuration, and calculate some examples illustrating how our tools were integrated into the {\sc polymake} framework. T3 - ZIB-Report - 02-02 KW - triangulation KW - oriented matroid KW - software KW - chirotope KW - circuit KW - cocircuit KW - symmetry KW - regular KW - secondary polytope KW - hypergeometric function Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6692 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Weider, Steffen T1 - An Approximation Algorithm for the Non-Preemptive Capacitated Dial-a-Ride Problem N2 - In the Capacitated Dial-a-Ride Problem (CDARP) we are given a transportation network and a finite set of transportation jobs. Each job specifies the source and target location which are both part of the network. A server which can carry at most $C$~objects at a time can move on the transportation network in order to process the transportation requests. The problem CDARP consists of finding a shortest transportation for the jobs starting and ending at a designated start location. In this paper we are concerned with the restriction of CDARP to graphs which are simple paths. This setting arises for instance when modelling applications in elevator transportation systems. It is known that even for this restricted class of graphs CDARP is NP-hard to solve. We provide a polynomial time approximation algorithm that finds a transportion of length at most thrice the length of the optimal transportation. T3 - ZIB-Report - 00-53 KW - NP-completeness KW - polynomial-time approximation algorithms KW - stacker-crane problem KW - vehicle Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6217 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Torres, Luis Miguel T1 - Real-Time Dispatching of Guided and Unguided Automobile Service Units with Soft Time Windows N2 - Given a set of service requests (events), a set of guided servers (units), and a set of unguided service contractors (conts), the vehicle dispatching problem {\sl vdp} is the task to find an assignment of events to units and conts as well as tours for all units starting at their current positions and ending at their home positions (dispatch) such that the total cost of the dispatch is minimized. The cost of a dispatch is the sum of unit costs, cont costs, and event costs. Unit costs consist of driving costs, service costs and overtime costs; cont costs consist of a fixed cost per service; event costs consist of late costs linear in the late time, which occur whenever the service of the event starts later than its deadline. The program \textsf{ZIBDIP} based on dynamic column generation and set partitioning yields solutions on heavy-load real-world instances (215 events, 95 units) in less than a minute that are no worse than 1\% from optimum on state-of-the-art personal computers. T3 - ZIB-Report - 01-22 KW - vehicle dispatching KW - soft time windows KW - real-time KW - column generation KW - pricing KW - branch and bound KW - real world data KW - ADAC Y1 - 2001 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6484 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg A1 - Torres, Luis Miguel T1 - Online-Dispatching of Automobile Service Units N2 - We present an online algorithm for a real-world vehicle dispatching problem at ADAC, the German Automobile Association. T3 - ZIB-Report - 02-44 KW - vehicle dispatching KW - soft time windows KW - online KW - real-time KW - ADAC Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-7117 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Online Optimierung N2 - Wie soll man einen Aufzug steuern, wenn man keine Informationen über zukünftige Fahraufträge besitzt? Soll man eine Bahncard kaufen, wenn die nächsten Bahnreisen noch unbekannt sind? In der klassischen kombinatorischen Optimierung geht man davon aus, daß die Daten jeder Probleminstanz vollständig gegeben sind. In vielen Fällen modelliert diese \emph{Offline-Optimierung} jedoch die Situationen aus Anwendungen nur ungenügend. Zahlreiche Problemstellungen in der Praxis sind in natürlicher Weise \emph{online}: Sie erfordern Entscheidungen, die unmittelbar und ohne Wissen zukünftiger Ereignisse getroffen werden müssen. Als ein Standardmittel zur Beurteilung von Online-Algorithmen hat sich die \emph{kompetitive Analyse} durchgesetzt. Dabei vergleicht man den Zielfunktionswert einer vom Online-Algorithmus generierten Lösung mit dem Wert einer optimalen Offline-Lösung. Mit Hilfe der kompetitiven Analyse werden im Skript Algorithmen zum Caching, Netzwerk-Routing, Scheduling und zu Transportaufgaben untersucht. Auch die Schwächen der kompetitiven Analyse werden aufgezeigt und alternative Analysekonzepte vorgestellt. Neben der theoretischen Seite werden auch die Anwendungen der Online-Optimierung in der Praxis, vor allem bei Problemen der innerbetrieblichen Logistik, beleuchtet. Bei der Steuerung automatischer Transportsysteme tritt eine Fülle von Online-Problemen auf. Hierbei werden an die Algorithmen oftmals weitere Anforderungen gestellt. So müssen Entscheidungen unter strikten Zeitbeschränkungen gefällt werden (Echtzeit-Anforderungen). Dieses Skript ist aus dem Online-Teil der Vorlesung -Ausgewählte Kapitel aus der ganzzahligen Optimierung- (Wintersemester~1999/2000) und der Vorlesung -Online Optimierung- (Sommersemester~2000) an der Technischen Universität Berlin entstanden. T3 - ZIB-Report - 00-55 KW - Kompetitive Analyse KW - Online Optimierung KW - Online Algorithmen Y1 - 2000 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6238 ER - TY - GEN A1 - Krumke, Sven A1 - Rambau, Jörg T1 - Probieren geht über Studieren? Entscheidungshilfen für kombinatorische Online-Optimierungsprobleme in der innerbetrieblichen Logistik N2 - Die Automatisierung von innerbetrieblicher Logistik erfordert -- über die physikalische Steuerung von Geräten hinaus -- auch eine effiziente Organisation der Transporte: ein Aufgabenfeld der kombinatorischen Optimierung. Dieser Artikel illustriert anhand von konkreten Aufgabenstellungen die Online-Problematik (unvollständiges Wissen) sowie die Echtzeit-Problematik (beschränkte Rechenzeit), auf die man in der innerbetrieblichen Logistik trifft. Der Text gibt einen Überblick über allgemeine Konstruktionsprinzipien für Online-Algorithmen und Bewertungsmethoden, die bei der Entscheidung helfen, welche Algorithmen für eine vorliegende Problemstellung geeignet sind. T3 - ZIB-Report - 02-05 KW - Logistik KW - Hochregallagerbediengeräte KW - Kommissioniermobile KW - Aufzüge KW - Online-Optimierung KW - Echtzeit-Optimierung KW - Simulation KW - kompetitive Analyse Y1 - 2002 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-6723 ER -