TY - GEN A1 - Achterberg, Tobias A1 - Brinkmann, Raik A1 - Wedler, Markus T1 - Property Checking with Constraint Integer Programming N2 - 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. T3 - ZIB-Report - 07-37 KW - formale Chip Verifikation KW - constraint integer programming KW - scip KW - Eigenschaftsprüfer KW - formal chip verification KW - constraint integer programming KW - scip KW - property checking KW - micro chip Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10376 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Combinatorial Online Optimization: Elevators & Yellow Angels N2 - 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. T3 - ZIB-Report - 07-36 KW - Online-Optimierung KW - Aufzugssteuerung KW - Dispatching von Fahrzeugen KW - online optimization KW - elevator control KW - vehicle dispatching Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10360 SN - 1438-0064 ER - TY - GEN A1 - Schiela, Anton T1 - Optimality Conditions for Convex State Constrained Optimal Control Problems with Discontinuous States N2 - We discuss first order optimality conditions for state constrained optimal control problems. Our concern is the treatment of problems, where the solution of the state equation is not known to be continuous, as in the case of boundary control in three space dimensions or optimal control with parabolic partial differential equations. We show existence of measure valued Lagrangian multipliers, which have just enough additional regularity to be applicable to all possibly discontinuous solutions of the state equation. T3 - ZIB-Report - 07-35 KW - optimal control KW - state constraints KW - optimality conditions Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10342 SN - 1438-0064 ER - TY - GEN A1 - Antoine, Xavier A1 - Arnold, Anton A1 - Besse, Christophe A1 - Ehrhardt, Matthias A1 - Schädle, Achim T1 - A Review of Transparent and Artificial Boundary Conditions Techniques for Linear and Nonlinear Schrödinger Equations N2 - In this review article we discuss different techniques to solve numerically the time-dependent Schrödinger equation on unbounded domains. We present in detail the most recent approaches and describe briefly alternative ideas pointing out the relations between these works. We conclude with several numerical examples from different application areas to compare the presented techniques. We mainly focus on the one-dimensional problem but also touch upon the situation in two space dimensions and the cubic nonlinear case. T3 - ZIB-Report - 07-34 KW - Schrödinger equation KW - transparent boundary condition KW - discrete convolution KW - unbounded domain Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10332 SN - 1438-0064 ER - TY - GEN A1 - Bley, Andreas T1 - Routing and Capacity Optimization for IP networks N2 - 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. T3 - ZIB-Report - 07-33 KW - kombinatorische Optimierung KW - gemischt-ganzzahlige Programmierung KW - kürzeste-Wege Routing KW - Approximationsalgorithmen KW - combinatorial optimization KW - mixed-integer programming KW - shortest path routing KW - approximation algorithms Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10323 SN - 1438-0064 ER - TY - GEN A1 - Schenk, Olaf A1 - Wächter, Andreas A1 - Weiser, Martin T1 - Inertia Revealing Preconditioning For Large-Scale Nonconvex Constrained Optimization N2 - Fast nonlinear programming methods following the all-at-once approach usually employ Newton's method for solving linearized Karush-Kuhn-Tucker (KKT) systems. In nonconvex problems, the Newton direction is only guaranteed to be a descent direction if the Hessian of the Lagrange function is positive definite on the nullspace of the active constraints, otherwise some modifications to Newton's method are necessary. This condition can be verified using the signs of the KKT's eigenvalues (inertia), which are usually available from direct solvers for the arising linear saddle point problems. Iterative solvers are mandatory for very large-scale problems, but in general do not provide the inertia. Here we present a preconditioner based on a multilevel incomplete $LBL^T$ factorization, from which an approximation of the inertia can be obtained. The suitability of the heuristics for application in optimization methods is verified on an interior point method applied to the CUTE and COPS test problems, on large-scale 3D PDE-constrained optimal control problems, as well as 3D PDE-constrained optimization in biomedical cancer hyperthermia treatment planning. The efficiency of the preconditioner is demonstrated on convex and nonconvex problems with $150^3$ state variables and $150^2$ control variables, both subject to bound constraints. T3 - ZIB-Report - 07-32 KW - nonconvex constrained optimization KW - interior-point method KW - inertia KW - multilevel incomplete factorization Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10314 SN - 1438-0064 ER - TY - GEN A1 - Weber, Marcus A1 - Becker, Roland A1 - Köppen, Robert A1 - Durmaz, Vedat T1 - Classical hybrid Monte-Carlo simulations of the interconversion of hexabromocyclododecane N2 - In this paper, we investigate the interconversion processes of the major flame retardant -- 1,2,5,6,9,10-hexabromocyclododecane (HBCD) -- by the means of statistical thermodynamics based on classical force-fields. Three ideas will be presented. First, the application of classical hybrid Monte-Carlo simulations for quantum mechanical processes will be justified. Second, the problem of insufficient convergence properties of hybrid Monte-Carlo methods for the generation of low temperature canonical ensembles will be solved by an interpolation approach. Furthermore, it will be shown how free energy differences can be used for a rate matrix computation. The results of our numerical simulations will be compared to experimental results. T3 - ZIB-Report - 07-31 KW - Markov process KW - molecular dynamics KW - rate matrix Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10308 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo T1 - Heuristics of the Branch-Cut-and-Price-Framework SCIP N2 - 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. T3 - ZIB-Report - 07-30 KW - Primalheuristiken KW - Gemischt-Ganzzahlige Programmierung KW - Branch and Cut KW - SCIP KW - mixed integer programming KW - primal heuristics KW - branch and cut KW - SCIP Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10280 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Liebchen, Christian T1 - When Periodic Timetables are Suboptimal N2 - 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'. T3 - ZIB-Report - 07-29 KW - Taktfahrplan KW - Fahrplan KW - Nahverkehr KW - periodic timetable KW - trip timetable KW - public transport Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9151 SN - 1438-0064 ER - TY - GEN A1 - Berthold, Timo T1 - RENS - Relaxation Enforced Neighborhood Search N2 - 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. T3 - ZIB-Report - 07-28 KW - Primalheuristiken KW - Gemischt-Ganzzahlige Programmierung KW - Nachbarschaftssuche KW - mixed integer programming KW - primal heuristics KW - large neighborhood search Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-4264 SN - 1438-0064 ER - TY - GEN A1 - Rusch, Beate A1 - Block, Barbara A1 - Labner, Josef T1 - Katalogisierung kooperativ gemacht N2 - Bereits seit den siebziger Jahren katalogisieren Bibliotheken arbeitsteilig in Verbünden. Allerdings macht die Kooperation bislang oftmals an den Grenzen traditionell gewachsener Verbundstrukturen halt. Das ist ein Grund dafür, dass in Deutschland und Österreich das gleiche Buch im schlimmsten Fall an zahlreichen Stellen gleichzeitig katalogisiert wird, ohne dass der eine von der Arbeit des anderen profitiert. In dem folgenden Report werden erstmals konkrete Schritte beschrieben, die eine verteilte Katalogisierung über Verbundgrenzen hinweg verbessern. Dazu gehören Vereinbarungen für die Indexierung und die Suche über Z39.50, Regeln für gegenseitige Datenlieferungen und nicht zuletzt die Einführung einer eindeutigen Identifikationsnummer, die die erstkatalogisierende Institution vergibt. Der vorliegende Artikel ist ein vorläufiger Zwischenbericht der von der Arbeitsgemeinschaft der Verbundsysteme eingesetzten Arbeitsgruppe „Kooperative Neukatalogisierung“. T3 - ZIB-Report - 07-27 KW - Verbünde KW - Katalogisierung KW - Datenanreicherung KW - Z39.50 KW - Library KW - Catalog Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10264 SN - 1438-0064 ER - TY - GEN A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas T1 - Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers N2 - 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. T3 - ZIB-Report - 07-26 KW - Aufzugsgruppensteuerung KW - Zielrufsteuerung KW - Echzeitoptimierung KW - Online-Optimierung KW - elevator group control KW - destination call system KW - real time optimation KW - online optimization Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10108 SN - 1438-0064 ER - TY - GEN A1 - Kaibel, Volker A1 - Stephan, Rüdiger T1 - On cardinality constrained cycle and path polytopes N2 - 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. T3 - ZIB-Report - 07-25 KW - path KW - cycles KW - integer characterizations KW - facets Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10093 SN - 1438-0064 ER - TY - GEN A1 - Grötschel, Martin A1 - Lügger, Joachim T1 - Die Wissenschaftsgalaxis: Wie soll die zukünftige wissenschaftliche Informationsversorgung aussehen? N2 - Wissenschaftler sind an qualitativ hochwertiger Information interessiert, selten an Informationsversorgung selbst. Es ist ihnen in Fragen der Organisation meistens egal, von welchem Versorger sie das Material, das sie benötigen, bekommen. Sie wollen einfach nur alles, was sie brauchen, jederzeit, überall, sofort und möglichst kostengünstig oder gar kostenlos haben. Im Prinzip ist das möglich. Seit mindestens zehn Jahren werden so gut wie alle wissenschaftlichen Dokumente (Artikel, Messdaten,…) elektronisch erstellt. Eigentlich bräuchte man diese nur ins Internet zu stellen, und damit wäre alles verfügbar. Irgendwie funktioniert diese einfache Idee nicht so richtig, obwohl viele Anstrengungen von den verschiedensten Einrichtungen und Individuen unternommen werden, z. B. durch Open-Access-Bemühungen. Was sind die Gründe dafür? Die Fortschritte beim schnellen Zugriff auf Information im Internet sind atemberaubend (siehe Google), dennoch ist der zielgerichtete Zugriff auf wissenschaftlich relevante Information weiterhin nur oberflächlich vorhanden. Die Hindernisse sind vielfältiger Natur: Bequemlichkeit und Unwissen der Autoren, Gewohnheiten der Nutzer und Informationsvermittler, Barrieren durch Copyrights und Verlagsstrategien, Eitelkeiten. In diesem Artikel werden einige der Probleme erläutert, die dem Traum des Aufbaus der wissenschaftlichen Universalbibliothek entgegenstehen. Gleichzeitig wird skizziert, wie man auf dem Weg zur Verwirklichung des Traums ein Stück vorankommen und wie die zukünftige wissenschaftliche Informationsversorgung gestaltet werden kann. T3 - ZIB-Report - 07-24 KW - wissenschaftliche Informationsversorgung KW - Open Access KW - digitale Bibliothek KW - Bibliothek der Zukunft KW - World Digital Mathematics Library KW - Open Access Catalog KW - Online Public Access Catalog Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-10032 ER - TY - GEN A1 - Reinefeld, Alexander A1 - Schintke, Florian A1 - Schütt, Thorsten T1 - P2P Routing of Range Queries in Skewed Multidimensional Data Sets N2 - We present a middleware to store multidimensional data sets on Internet-scale distributed systems and to efficiently perform range queries on them. Our structured overlay network \emph{SONAR (Structured Overlay Network with Arbitrary Range queries)} puts keys which are adjacent in the key space on logically adjacent nodes in the overlay and is thereby able to process multidimensional range queries with a single logarithmic data lookup and local forwarding. The specified ranges may have arbitrary shapes like rectangles, circles, spheres or polygons. Empirical results demonstrate the routing performance of SONAR on several data sets, ranging from real-world data to artificially constructed worst case distributions. We study the quality of SONAR's routing information which is based on local knowledge only and measure the indegree of the overlay nodes to find potential hot spots in the routing process. We show that SONAR's routing table is self-adjusting, even under extreme situations, keeping always a maximum of $\lceil \log N \rceil$ routing entries. T3 - ZIB-Report - 07-23 KW - structured overlays KW - range queries KW - routing KW - multidimensional data sets Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9671 SN - 1438-0064 ER - TY - GEN A1 - Harks, Tobias A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vredeveld, Tjark T1 - Online Multicommodity Routing with Time Windows N2 - 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. T3 - ZIB-Report - 07-22 KW - Online Optimization KW - Routing KW - Telecommunications Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9654 SN - 1438-0064 ER - TY - GEN A1 - Koster, Arie M.C.A. A1 - Orlowski, Sebastian A1 - Raack, Christian A1 - Bayer, Georg A1 - Engel, Thomas T1 - Single-layer Cuts for Multi-layer Network Design Problems N2 - 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. T3 - ZIB-Report - 07-21 KW - telecommunication network KW - multi-layer network design KW - mixed-integer programming KW - cutting planes Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9641 SN - 1438-0064 ER - TY - GEN A1 - Borndörfer, Ralf A1 - Schlechte, Thomas T1 - Solving Railway Track Allocation Problems N2 - 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. T3 - ZIB-Report - 07-20 KW - railway track allocation KW - timetabling KW - column generation Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9631 SN - 1438-0064 ER - TY - GEN A1 - Weber, Marcus T1 - Conformation-based transition state theory N2 - For the treatment of equilibrated molecular systems in a heat bath we propose a transition state theory that is based on conformation dynamics. In general, a set-based discretization of a Markov operator ${\cal P}^\tau$ does not preserve the Markov property. In this article, we propose a discretization method which is based on a Galerkin approach. This discretization method preserves the Markov property of the operator and can be interpreted as a decomposition of the state space into (fuzzy) sets. The conformation-based transition state theory presented here can be seen as a first step in conformation dynamics towards the computation of essential dynamical properties of molecular systems without time-consuming molecular dynamics simulations. T3 - ZIB-Report - 07-18 KW - dynamical systems KW - transition state theory KW - rare events Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9612 ER - TY - GEN A1 - Kube, Susanna A1 - Lasser, Caroline A1 - Weber, Marcus T1 - Monte Carlo sampling of Wigner functions and surface hopping quantum dynamics N2 - Wigner transformation provides a one-to-one correspondence between functions on position space (wave functions) and functions on phase space (Wigner functions). Weighted integrals of Wigner functions yield quadratic quantities of wave functions like position and momentum densities or expectation values. For molecular quantum systems, suitably modified classical transport of Wigner functions provides an asymptotic approximation of the dynamics in the high energy regime. The article addresses the computation of Wigner functions by Monte Carlo quadrature. An ad aption of the Metropolis algorithm for the approximation of signed measures with disconnected support is systematically tested in combination with a surface hopping algorithm for non-adiabatic quantum dynamics. The numerical experiments give expectation values and level populations with an error of two to three percent, which agrees with the theoretically expected accuracy. T3 - ZIB-Report - 07-17 KW - Metropolis Monte Carlo KW - approximation KW - quadrature KW - oscillating functions Y1 - 2007 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-9604 ER -