TY - CHAP A1 - Sagnol, Guillaume T1 - Network-related problems in optimal experimental design and second order cone programming T2 - Proceedings of PROBASTAT'2011, Tatra Mountains Mathematical Publications N2 - In the past few years several applications of optimal experimental designs have emerged to optimize the measurements in communication networks. The optimal design problems arising from this kind of applications share three interesting properties: (i) measurements are only available at a small number of locations of the network; (ii) each monitor can simultaneously measure several quantities, which can be modeled by ``multiresponse experiments"; (iii) the observation matrices depend on the topology of the network. In this paper, we give an overview of these experimental design problems and recall recent results for the computation of optimal designs by Second Order Cone Programming (SOCP). New results for the network-monitoring of a discrete time process are presented. In particular, we show that the optimal design problem for the monitoring of an AR1 process can be reduced to the standard form and we give experimental results. Y1 - 2012 U6 - https://doi.org/10.2478/v10127-012-0016-x VL - 51 SP - 161 EP - 171 ER - TY - CHAP A1 - Hildenbrandt, Achim A1 - Reinelt, Gerhard A1 - Heismann, Olga T1 - Integer Programming Models for the Target Visitation Problem T2 - Proceedings of the 16th International Multiconference INFORMATION SOCIETY - IS 2013 N2 - The target visitation problem (TVP) is concerned with finding a route to visit a set of targets starting from and returning to some base. In addition to the distance traveled a tour is evaluated by taking also preferences into account which address the sequence in which the targets are visited. The problem thus is a combination of two well-known combinato- rial optimization problems: the traveling salesman and the linear ordering problem. In this paper we present several possible IP-Models for this problem and compared them to their usability for branch-and-cut approaches. Y1 - 2013 SP - 569 EP - 572 ER - TY - CHAP A1 - Heismann, Olga A1 - Borndörfer, Ralf T1 - Minimum Cost Hyperassignments with Applications to ICE/IC Rotation Planning T2 - Operations Research Proceedings 2011 N2 - Vehicle rotation planning is a fundamental problem in rail transport. It decides how the railcars, locomotives, and carriages are operated in order to implement the trips of the timetable. One important planning requirement is operational regularity, i.e., using the rolling stock in the same way on every day of operation. We propose to take regularity into account by modeling the vehicle rotation planning problem as a minimum cost hyperassignment problem (HAP). Hyperassignments are generalizations of assignments from directed graphs to directed hypergraphs. Finding a minimum cost hyperassignment is NP-hard. Most instances arising from regular vehicle rotation planning, however, can be solved well in practice. We show that, in particular, clique inequalities strengthen the canonical LP relaxation substantially. Y1 - 2012 SP - 59 EP - 64 ER - TY - CHAP A1 - Grötschel, Martin A1 - Lügger, Joachim T1 - E - Learning and the Working Mathematician T2 - Grundfragen Multimedialen Lehrens und Lernens - Tagungsband GML 2009 N2 - Eigentlich war der erste Autor nur zu einem Grußwort zur Tagung „GML 2009 - Grundfragen Multimedialen Lehrens und Lernens“ eingeladen. Aber wie es bei der Vorbereitung zu solchen „Auftritten“ manchmal so kommt, wurde daraus ein E-Learning-bezogener Vortrag, der – basierend auf Erfahrungen im Fach Mathematik – einen kritischen Blick auf die E-Learning-Szene in Deutschland wirft und diese mit entsprechenden Aktivitäten weltweit vergleicht. Dies ist die in seinen mathematischen Teilen gekürzte, in den E-Learning-Anteilen ein wenig erweiterte schriftliche Fassung des Vortrags. Y1 - 2009 SN - ISBN 978 - 3 - 7983 - 2143 - 4 SP - 8 EP - 27 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Hiller, Benjamin A1 - Humpola, Jesco A1 - Koch, Thorsten A1 - Lehmann, Thomas A1 - Schwarz, Robert A1 - Schweiger, Jonas A1 - Szabo, Jacint T1 - Gas Network Topology Optimization for Upcoming Market Requirements T2 - International Conference on the European Energy Market (EEM) N2 - Gas distribution networks are complex structures that consist of passive pipes, and active, controllable elements such as valves and compressors. Controlling such network means to find a suitable setting for all active components such that a nominated amount of gas can be transmitted from entries to exits through the network, without violating physical or operational constraints. The control of a large-scale gas network is a challenging task from a practical point of view. In most companies the actual controlling process is supported by means of computer software that is able to simulate the flow of the gas. However, the active settings have to be set manually within such simulation software. The solution quality thus depends on the experience of a human planner. When the gas network is insufficient for the transport then topology extensions come into play. Here a set of new pipes or active elements is determined such that the extended network admits a feasible control again. The question again is how to select these extensions and where to place them such that the total extension costs are minimal. Industrial practice is again to use the same simulation software, determine extensions by experience, add them to the virtual network, and then try to find a feasible control of the active elements. The validity of this approach now depends even more on the human planner. Another weakness of this manual simulation-based approach is that it cannot establish infeasibility of a certain gas nomination, unless all settings of the active elements are tried. Moreover, it is impossible to find a cost-optimal network extension in this way. In order to overcome these shortcomings of the manual planning approach we present a new approach, rigorously based on mathematical optimization. Hereto we describe a model for finding feasible controls and then extend this model such that topology extensions can additionally and simultaneously be covered. Numerical results for real-world instances are presented and discussed. Y1 - 2011 U6 - https://doi.org/10.1109/EEM.2011.5953035 SP - 346 EP - 351 ER - TY - CHAP A1 - Schlechte, Thomas T1 - Railway Track Allocation BT - Selected Papers of the International Annual Conference of the German Operations Research Society (GOR), Leibniz University of Hannover, Germany, September 5-7, 2012 T2 - Operations Research Proceedings Y1 - 2012 U6 - https://doi.org/10.1007/978-3-319-00795-314 SP - 15 EP - 20 ER - TY - CHAP A1 - Heinz, Stefan A1 - Schulz, Jens T1 - Explanations for the Cumulative Constraint: An Experimental Study T2 - Experimental Algorithms Y1 - 2011 VL - 6630 SP - 400 EP - 409 ER - TY - CHAP A1 - Berthold, Timo A1 - Gleixner, Ambros A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Shinano, Yuji T1 - SCIP Optimization Suite を利用した 混合整数(線形/非線形) 計画問題の解法 T2 - Proceedings of the 24th RAMP symposium. The Operations Society of Japan, RAMP: Research Association of Mathematical Programming N2 - この論文ではソフトウェア・パッケージSCIP Optimization Suite を紹介し,その3つの構成要素:モデリン グ言語Zimpl, 線形計画(LP: linear programming) ソルバSoPlex, そして,制約整数計画(CIP: constraint integer programming) に対するソフトウェア・フレームワークSCIP, について述べる.本論文では,この3つの 構成要素を利用して,どのようにして挑戦的な混合整数線形計画問題(MIP: mixed integer linear optimization problems) や混合整数非線形計画問題(MINLP: mixed integer nonlinear optimization problems) をモデル化 し解くのかを説明する.SCIP は,現在,最も高速なMIP,MINLP ソルバの1つである.いくつかの例により, Zimpl, SCIP, SoPlex の利用方法を示すとともに,利用可能なインタフェースの概要を示す.最後に,将来の開 発計画の概要について述べる. N2 - This paper introduces the SCIP Optimization Suite and discusses the capabilities of its three components: the modeling language Zimpl, the linear programming solver SoPlex, and the constraint integer programming framework SCIP. We explain how in concert these can be used to model and solve challenging mixed integer linear and nonlinear optimization problems. SCIP is currently one of the fastest non-commercial MIP and MINLP solvers. We demonstrate the usage of Zimpl, SCIP, and SoPlex by selected examples, we give an overview over available interfaces, and outline plans for future development. Y1 - 2012 SP - 165 EP - 192 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - van Veldhuizen, Roel A1 - Vierhaus, Ingmar T1 - Production Planning for Non-Cooperating Companies with Nonlinear Optimization T2 - 11th Global Conference on Sustainable Manufacturing : Proceedings N2 - We consider a production planning problem where two competing companies are selling their items on a common market. Moreover, the raw material used in the production is a limited non-renewable resource. The revenue per item sold depends on the total amount of items produced by both players. If they collaborate they could apply a production strategy that leads to the highest combined revenue. Usually the formation of such syndicates is prohibited by law; hence we assume that one company does not know how much the other company will produce. We formulate the problem for company A to find an optimal production plan without information on the strategy of company B as a nonlinear mathematical optimization problem. In its naive formulation the model is too large, making its solution practically impossible. After a reformulation we find a much smaller model, which we solve by spatial branch-and-cut methods and linear programming. We discuss the practical implications of our solutions. Y1 - 2013 SP - 536 EP - 541 PB - Universitätsverlag der TU Berlin CY - Berlin ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Vierhaus, Ingmar T1 - System Dynamic Optimization in the Sustainability Assessment of a World-Model T2 - 11th Global Conference on Sustainable Manufacturing : Proceedings N2 - The System Dynamics (SD) methodology is a framework for modeling and simulating the dynamic behavior of socioeconomic systems. Characteristic for the description of such systems is the occurrence of feedback loops together with stocks and flows. The mathematical equations that describe the system are usually nonlinear. Therefore seemingly simple systems can show a nonintuitive, nonpredictable behavior over time. Controlling a dynamical system means to define a desired final state in which the system should be, and to specify potential interventions from outside that should keep the system on the right track. The central question is how to compute such globally optimal control for a given SD model. We propose a branch-and-bound approach that is based on a bound propagation method, primal heuristics, and spatial branching. We apply our new SD-control method to a small System Dynamics model, that describes the evolution of a social-economic system over time. We examine the problem of steering this system on a sustainable consumption path. Y1 - 2013 SP - 530 EP - 535 PB - Universitätsverlag der TU Berlin CY - Berlin ER - TY - CHAP A1 - Brose, Achim A1 - Fügenschuh, Armin A1 - Gausemeier, Pia A1 - Vierhaus, Ingmar A1 - Seliger, Günther T1 - A System Dynamic Enhancement for the Scenario Technique T2 - Proc. 11th Global Conference on Sustainable Manufacturing N2 - The Scenario Technique is a strategic planning method that aims to describe and analyze potential developments of a considered system in the future. Its application consists of several steps, from an initial problem analysis over an influence analysis to projections of key factors and a definition of the scenarios to a final interpretation of the results. The technique itself combines qualitative and quantitative methods and is an enhancement of the standard Scenario Technique. We use the numerical values gathered during the influence analysis, and embed them in a System Dynamics framework. This yields a mathematically rigorous way to achieve predictions of the system‘s future behavior from an initial impulse and the feedback structure of the factors. The outcome of our new method is a further way of projecting the present into the future, which enables the user of the Scenario Technique to obtain a validation of the results achieved by the standard method. Y1 - 2013 SP - 561 EP - 566 PB - Universitätsverlag der TU Berlin CY - Berlin ER - TY - CHAP A1 - Scheumann, René A1 - Vierhaus, Ingmar A1 - Chang, Ya-Ju A1 - Fügenschuh, Armin A1 - Finkbeiner, Matthias T1 - Identification of trade-offs for sustainable manufacturing of a Bamboo Bike by System Dynamics T2 - Proceedings of the 27. Conference on Environmental Informatics - Informatics for Environmental Protection, Sustainable Development and Risk Management N2 - We develop a generic System Dynamic model to simulate the production, machines, employees, waste, and capital flows of a manufacturing company. In a second step, this model is specialised by defining suit-able input data to represent a bicycle manufacturing company in a developing country. We monitor a set of sustainability indicators to understand the social, environmental and economic impact of the company, and to estimate managerial decisions to be taken in order to improve on these criteria. We show that the social and environmental situation can be improved over time without sacrificing the economic success of the company's business. Y1 - 2013 SP - 523 EP - 531 ER - TY - CHAP A1 - Heinz, Stefan A1 - Beck, J. Christopher T1 - Reconsidering Mixed Integer Programming and MIP-based Hybrids for Scheduling T2 - Integration of AI and OR Techniques in Constraint Programming for Combinatorial Optimization Problems (CPAIOR 2012) Y1 - 2012 VL - 7298 SP - 211 EP - 227 ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Schulz, Jens T1 - An approximative Criterion for the Potential of Energetic Reasoning T2 - Theory and Practice of Algorithms in (Computer) Systems Y1 - 2011 VL - 6595 SP - 229 EP - 239 ER - TY - CHAP A1 - Hendel, Gregor A1 - Berthold, Timo A1 - Achterberg, Tobias T1 - Rounding and Propagation Heuristics for Mixed Integer Programming T2 - Operations Research Proceedings 2011 N2 - Primal heuristics are an important component of state-of-the-art codes for mixed integer programming. In this paper, we focus on primal heuristics that only employ computationally inexpensive procedures such as rounding and logical deductions (propagation). We give an overview of eight different approaches. To assess the impact of these primal heuristics on the ability to find feasible solutions, in particular early during search, we introduce a new performance measure, the primal integral. Computational experiments evaluate this and other measures on MIPLIB~2010 benchmark instances. Y1 - 2011 SP - 71 EP - 76 ER - TY - CHAP A1 - Zakrzewska, Anna A1 - D'Andreagiovanni, Fabio A1 - Ruepp, Sarah A1 - Berger, Michael S. T1 - Biobjective Optimization of Radio Access Technology Selection and Resource Allocation in Heterogeneous Wireless Networks T2 - Proceedings of the 11th International Symposium on Modeling & Optimization in Mobile, Ad Hoc & Wireless Networks (WiOpt 2013) - RAWNET/WNC3’13 Y1 - 2013 SP - 652 EP - 658 ER - TY - CHAP A1 - Scheumann, René A1 - Fügenschuh, Armin A1 - Schenker, Sebastian A1 - Vierhaus, Ingmar A1 - Borndörfer, Ralf A1 - Finkbeiner, Matthias ED - Seliger, Günther T1 - Global Manufacturing: How to Use Mathematical Optimisation Methods to Transform to Sustainable Value Creation BT - (GCSM 2012) T2 - Proceedings of the 10th Global Conference on Sustainable Manufacturing Y1 - 2012 SN - 978-605-63463-1-6 SP - 538 EP - 545 ER - TY - CHAP A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - Scheduling technology migration in WDM Networks T2 - Photonic Networks, 14. 2013 ITG Symposium. Proceedings Y1 - 2013 SP - 1 EP - 5 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A Binary Quadratic Programming Approach to the Vehicle Positioning Problem T2 - Modeling, Simulation and Optimization of Complex Processes -- Proceedings of the Fourth International Conference on High Performance Scientific Computing, March 2-6, 2009 N2 - The Vehicle Positioning Problem (VPP) consists of the assignment of vehicles (buses, trams or trains) of a public transport or railway company to parking positions in a depot and to timetabled trips. Such companies have many different types of vehicles, and each trip can be performed only by vehicles of some of these types. These assignments are non-trivial due to the topology of depots. The parking positions are organized in tracks, which work as one- or two-sided stacks or queues. If a required type of vehicle is not available in the front of any track, shunting movements must be performed in order to change vehicles' positions, which is undesirable and should be avoided. In this text we present integer linear and non-linear programming formulations for some versions of the problem and compare them from a theoretical and a computational point of view. Y1 - 2012 U6 - https://doi.org/10.1007/978-3-642-25707-0 SP - 41 EP - 52 ER - TY - CHAP A1 - Bley, Andreas T1 - On the Hardness of Finding Small Shortest Path Routing Conflicts T2 - Proceedings of 4th International Network Optimization Conference (INOC2009) N2 - Nowadays most data networks use shortest path protocols such as OSPF or IS-IS to route traffic. Given administrative routing lengths for the links of a network, all data packets are sent along shortest paths with respect to these lengths from their source to their destination. One of the most fundamental problems in planning shortest path networks is to decide whether a given set of routing paths forms a valid routing and, if this is not the case, to find a small subset of the given paths that cannot be shortest paths simultaneously for any routing lengths. In this paper we show that it is NP-hard to approximate the size of the smallest shortest path conflict by a factor less than 7/6. Y1 - 2009 ER - TY - CHAP A1 - Menne, Ulrich A1 - Raack, Christian A1 - Wessäly, Roland A1 - Kharitonov, Daniel T1 - Optimal Degree of Optical Circuit Switching in IP-over-WDM Networks T2 - Optical Network Design and Modeling (ONDM), 2012 16th International Conference on N2 - In this paper, we study the influence of technology, traffic properties and price trends on optimized design of a reference IP-over-WDM network with rich underlying fiber topology. In each network node, we investigate the optimal degree of traffic switching in an optical (lambda) domain versus an electrical (packet) domain, also known as measure of \emph{node transparency}. This measure is studied in connection to changes in traffic volume, demand affinity, optical circuit speeds and equipment cost. By applying variable design constraints, we assess the relative roles of the two distinct equipment groups, IP routers and optical cross-connects, with respect to resulting changes in cost-sensitive network architectures. Y1 - 2012 U6 - https://doi.org/10.1109/ONDM.2012.6210206 SP - 1 EP - 6 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Krolikowski, Jonatan A1 - Pulaj, Jonad T1 - A hybrid primal heuristic for Robust Multiperiod Network Design T2 - EvoApplications 2014 Y1 - 2014 ER - TY - CHAP A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio T1 - A New Theoretical Framework for Robust Optimization Under Multi-Band Uncertainty T2 - Operations Research Proceedings 2012 Y1 - 2014 U6 - https://doi.org/10.1007/978-3-319-00795-3_17 SP - 115 EP - 121 ER - TY - CHAP A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - 0-1 Multiband Robust Optimization T2 - Operations Research Proceedings 2013 Y1 - 2013 ER - TY - CHAP A1 - Bley, Andreas A1 - D'Andreagiovanni, Fabio A1 - Karch, Daniel T1 - WDM Fiber Replacement Scheduling T2 - Proceedings of INOC 2013 Y1 - 2013 U6 - https://doi.org/10.1016/j.endm.2013.05.092 VL - 41 SP - 189 EP - 196 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio T1 - A Hybrid Exact-ACO Algorithm for the Joint Scheduling, Power and Cluster Assignment in Cooperative Wireless Networks T2 - BIONETICS 2012 Y1 - 2012 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - Multiband Robust Optimization and its Adoption in Harvest Scheduling T2 - Proc. of FORMATH 2013 Y1 - 2014 ER - TY - CHAP A1 - Büsing, Christina A1 - D'Andreagiovanni, Fabio A1 - Raymond, Annie T1 - Robust optimization under multiband uncertainty T2 - CTW 2013 Y1 - 2013 SP - 35 EP - 38 ER - TY - CHAP A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Pfetsch, Marc A1 - Vigerske, Stefan T1 - Large Neighborhood Search beyond MIP T2 - Proceedings of the 9th Metaheuristics International Conference (MIC 2011) N2 - Large neighborhood search (LNS) heuristics are an important component of modern branch-and-cut algorithms for solving mixed-integer linear programs (MIPs). Most of these LNS heuristics use the LP relaxation as the basis for their search, which is a reasonable choice in case of MIPs. However, for more general problem classes, the LP relaxation alone may not contain enough information about the original problem to find feasible solutions with these heuristics, e.g., if the problem is nonlinear or not all constraints are present in the current relaxation. In this paper, we discuss a generic way to extend LNS heuristics that have been developed for MIP to constraint integer programming (CIP), which is a generalization of MIP in the direction of constraint programming (CP). We present computational results of LNS heuristics for three problem classes: mixed-integer quadratically constrained programs, nonlinear pseudo-Boolean optimization instances, and resource-constrained project scheduling problems. Therefore, we have implemented extended versions of the following LNS heuristics in the constraint integer programming framework SCIP: Local Branching, RINS, RENS, Crossover, and DINS. Our results indicate that a generic generalization of LNS heuristics to CIP considerably improves the success rate of these heuristics. Y1 - 2011 SN - 978-88-900984-3-7 SP - 51 EP - 60 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio T1 - On Improving the Capacity of Solving Large-scale Wireless Network Design Problems by Genetic Algorithms T2 - Applications of Evolutionary Computation - EvoApplications 2011 Y1 - 2011 U6 - https://doi.org/10.1007/978-3-642-20520-0_2 VL - 6625 SP - 11 EP - 20 ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Mannino, Carlo A1 - Sassano, Antonio T1 - Negative Cycle Separation in Wireless Network Design T2 - Network Optimization - INOC 2011 Y1 - 2011 U6 - https://doi.org/10.1007/978-3-642-21527-8_7 VL - 6701 SP - 51 EP - 56 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Neumann, Marika T1 - Linienoptimierung - reif für die Praxis? T2 - Heureka '11 : Optimierung in Verkehr und Transport N2 - Wir stellen in dieser Arbeit ein mathematisches Optimierungsmodell zur Bestimmung eines optimalen Linienplans vor, das sowohl die Fahrzeiten und die Anzahl der Umstiege berücksichtigt als auch die Kosten des Liniennetzes. Dieses Modell deckt wichtige praktische Anforderungen ab, die in einem gemeinsamen Projekt mit den Verkehrsbetrieben in Potsdam (ViP) formuliert wurden. In diesem Projekt wurde der Linienplan 2010 für Potsdam entwickelt. Unsere Berechnungen zeigen, dass die mathematische Optimierung in nichts einer "Handplanung" des Liniennetzes nachsteht. Im Gegenteil, mit Hilfe des Optimierungsprogramms ist es möglich, durch Veränderung der Parameter mehrere verschiedene Szenarien zu berechnen, miteinander zu vergleichen und Aussagen über minimale Kosten und Fahrzeiten zu machen. Y1 - 2011 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika ED - Frigioni, Daniele ED - Stiller, Sebastian T1 - A Configuration Model for the Line Planning Problem T2 - ATMOS 2013 - 13th Workshop on Algorithmic Approaches for Transportation Modeling, Optimization, and Systems Y1 - 2013 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2013.68 VL - 33 SP - 68 EP - 79 PB - Schloss Dagstuhl--Leibniz-Zentrum für Informatik ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Karbstein, Marika ED - Delling, Daniel ED - Liberti, Leo T1 - A Direct Connection Approach to Integrated Line Planning and Passenger Routing T2 - ATMOS 2012 - 12th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems Y1 - 2012 U6 - https://doi.org/http://dx.doi.org/10.4230/OASIcs.ATMOS.2012.47 VL - 25 SP - 47 EP - 57 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Gausemeier, Pia A1 - Seliger, Günther A1 - Severengiz, Semih ED - Dangelmaier, W. T1 - Scenario Technique with Integer Programming for Sustainability in Manufacturing T2 - 8th International Heinz Nixdorf Symposium, Changing Paradigms Y1 - 2010 SP - 320 EP - 331 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Homfeld, Henning A1 - Schülldorf, Hanno A1 - Vigerske, Stefan ED - Rodrigues, H. T1 - Mixed-Integer Nonlinear Problems in Transportation Applications T2 - Proceedings of the 2nd International Conference on Engineering Optimization (+CD-rom) Y1 - 2010 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Defterli, Özlem A1 - Weber, Gehard-Wilhelm T1 - New Discretization and Optimization Techniques with Results in the Dynamics of Gene-Environment Networks T2 - 3rd Global Conference on Power Control and Optimization (PCO 2010) Y1 - 2010 ER - TY - CHAP A1 - Fügenschuh, Armin A1 - Homfeld, Henning A1 - Schülldorf, Hanno ED - Barnhart, Cynthia ED - Clausen, Uwe ED - Lauther, Ulrich ED - Möhring, Rolf T1 - Single Car Routing in Rail Freight Transport T2 - Dagstuhl Seminar Proceedings 09261, Schloss Dagstuhl – Leibniz-Zentrum für Informatik, Deutschland Y1 - 2009 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Cardonha, Carlos T1 - A set partitioning approach to shunting T2 - LAGOS 09 V Latin-American Algorithms, Graphs and Optimization Symposium Y1 - 2009 SP - 359 EP - 364 PB - Elsevier ER - TY - CHAP A1 - Brandt, Andreas A1 - Brandt, Manfred T1 - On the computation of the probability of a system failure T2 - Proc. ESREL’99 10th European Conf. on Safety and Reliability, G.I. Schuëller, P. Kafka (eds.), Balkema Rotterdam Y1 - 1999 SP - 457 EP - 461 CY - München-Garching ER - TY - CHAP A1 - Brandt, Andreas A1 - Brandt, Manfred A1 - Spahl, G. A1 - Weber, D. T1 - Modelling and optimization of call distribution systems T2 - Proc. 15th Int. Teletraffic Cong. (ITC 15) Y1 - 1997 SP - 133 EP - 144 CY - Washington D.C., USA ER - TY - CHAP A1 - D'Andreagiovanni, Fabio A1 - Di Lullo, Michela A1 - Felici, Giovanni A1 - Lacalandra, Fabrizio T1 - A Unified View on Tight Formulations for the Unit Commitment Problem with Optimal Transmission Switching T2 - Gaspard Monge Program for Optimization - Conference on Optimization & Practices in Industry : PGMO-COPI '14 N2 - The classical Unit Commitment Problem (UC) consists in determining the production of a set of thermal and hydro power generation units over a given time horizon, in order to meet a forecast energy demand and minimize a cost function. In the last years, in connection with the UC, increasingly attention has been given to active switching, namely the possibility of changing the topology of the transmission network by tripping some of the lines. Active switching has been indeed recognized as an important way to improve capacity and reliability of the network. Modifying the network topology is also very useful in modern electricity systems, where the penetration of on-programmable renewable energy sources is high and tends to be very concentrated in some zones of the network. As a consequence, the interest for automatic and optimized switching procedures is currently spreading. In this paper, we address the UC when complemented by active switching, thus leading to so-called Unit Commitment with Optimal Transmission Switching (UCOTS). We formulate the UCOTS as a mixed integer linear program, where we unify tight formulations recently proposed in literature for relevant subfamilies of constraints of the problem. Concerning the cost function, in our formulation we approximate the quadratic thermal cost objective function by a piecewise linear function based on perspective cuts and we propose a new simple and effective way to perturb it, with the aim of breaking symmetries induced by optimal transmission switching decision variables. Our original solution approach also exploits specialized branching priorities. Computational experiments on realistic UCOTS instances highlight that our new framework is able to find optimal and near-optimal solutions in reasonable amount of time by direct use of a state-of-the-art commercial MIP solver. Y1 - 2014 ER - TY - CHAP A1 - Karbstein, Marika T1 - Integrated Line Planning and Passenger Routing: Connectivity and Transfers T2 - Operations Research Proceedings 2014 N2 - The integrated line planning and passenger routing problem is an important planning problem in service design of public transport. A major challenge is the treatment of transfers. A main property of a line system is its connectivity. In this paper we show that analysing the connecvitiy aspect of a line plan gives a new idea to handle the transfer aspect of the line planning problem. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-28697-6_37 SP - 263 EP - 269 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Grimm, Boris A1 - Reuther, Markus A1 - Schlechte, Thomas T1 - Template based re-optimization of rolling stock rotations T2 - Proceedings of Conference on Advanced Systems in Public Transport 2015 (CASPT2015) N2 - Rolling stock, i.e., rail vehicles, are among the most expensive and limited assets of a railway company. They must be used efficiently applying optimization techniques. One important aspect is re-optimization, which is the topic that we consider in this paper. We propose a template concept that allows to compute cost minimal rolling stock rotations under a large variety of re-optimization requirements. Two examples, involving a connection template and a rotation template, are discussed. An implementation within the rolling stock rotation optimizer rotor and computational results for scenarios provided by DB Fernverkehr AG, one of the leading railway operators in Europe, are presented. Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57539 ER - TY - CHAP A1 - Borndörfer, Ralf A1 - Reuther, Markus T1 - Regional Search for the Resource Constrained Assignment Problem T2 - 15th Workshop on Algorithmic Approaches for Transportation Modelling, Optimization, and Systems (ATMOS 2015) N2 - The resource constrained assignment problem (RCAP) is to find a minimal cost partition of the nodes of a directed graph into cycles such that a resource constraint is fulfilled. The RCAP has its roots in rolling stock rotation optimization where a railway timetable has to be covered by rotations, i.e., cycles. In that context, the resource constraint corresponds to maintenance constraints for rail vehicles. Moreover, the RCAP generalizes variants of the vehicle routing problem (VRP). The paper contributes an exact branch and bound algorithm for the RCAP and, primarily, a straightforward algorithmic concept that we call regional search (RS). As a symbiosis of a local and a global search algorithm, the result of an RS is a local optimum for a combinatorial optimization problem. In addition, the local optimum must be globally optimal as well if an instance of a problem relaxation is computed. In order to present the idea for a standardized setup we introduce an RS for binary programs. But the proper contribution of the paper is an RS that turns the Hungarian method into a powerful heuristic for the resource constrained assignment problem by utilizing the exact branch and bound. We present computational results for RCAP instances from an industrial cooperation with Deutsche Bahn Fernverkehr AG as well as for VRP instances from the literature. The results show that our RS provides a solution quality of 1.4 % average gap w.r.t. the best known solutions of a large test set. In addition, our branch and bound algorithm can solve many RCAP instances to proven optimality, e.g., almost all asymmetric traveling salesman and capacitated vehicle routing problems that we consider. Y1 - 2015 U6 - https://doi.org/10.4230/OASIcs.ATMOS.2015.111 VL - 48 SP - 111 EP - 129 ER - TY - CHAP A1 - Grötschel, Martin A1 - Borndörfer, Ralf T1 - Mathematik im Verkehr T2 - HEUREKA '14. Vorträge der Tagung am 2./3. April 2014 in Stuttgart N2 - Nach einem kurzen Abriss über die Bedeutung des Verkehrssektors als eine wichtige Schlüsseltechnologie im gesamten Verlauf der Menschheitsgeschichte skizzieren wir die Rolle der Mathematik für Verkehr und Transport. Wir spekulieren dann über zukünftige Entwicklungen, insbesondere im Bereich des öffentlichen Personenverkehrs, und begründen, dass die in diesem Bereich anstehenden Herausforderungen nur mit dem Einsatz mathematischer Methoden angemessen bewältigt werden können. Die demographischen Prozesse, die in verschiedenen Teilen der Welt unterschiedlich verlaufen, wie z.B. Überalterung in Europa oder dynamische Trends zu Megastädten in Entwicklungsländern, sich ändernde Lebens- und Produktionsverhältnisse, stark wachsender Bedarf nach Mobilität und enormes Anwachsen der Komplexität der Verkehrsplanung und -durchführung, machen einen verstärkten Zugriff auf mathematische Modellierung, Simulation und Optimierung notwendig. Diese Entwicklung stellt sowohl große Herausforderungen an die Mathematik, wo vielfach noch keine geeigneten Methoden vorhanden sind, als auch an die Praktiker im Bereich von Verkehr und Transport, die sich mit neuen Planungs- und Steuerungstechnologien befassen und diese effizient einsetzen müssen. Hier wird intensive Kooperation zwischen vielen beteiligten Akteuren gefragt sein. Y1 - 2014 SN - 978-3-86446-074-6 SP - 28 EP - 44 ER - TY - CHAP A1 - Beckenbach, Isabel A1 - Borndörfer, Ralf T1 - An Approximation Result for Matchings in Partitioned Hypergraphs T2 - Operations Research Proceedings 2014 N2 - We investigate the matching and perfect matching polytopes of hypergraphs having a special structure, which we call partitioned hypergraphs. We show that the integrality gap of the standard LP-relaxation is at most $2\sqrt{d}$ for partitioned hypergraphs with parts of size $\leq d$. Furthermore, we show that this bound cannot be improved to $\mathcal{O}(d^{0.5-\epsilon})$. Y1 - 2016 U6 - https://doi.org/10.1007/978-3-319-28697-6_5 SP - 31 EP - 36 PB - Springer International Publishing ER - TY - CHAP A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - Improving the performance of elevator systems using exact reoptimization algorithms T2 - Proceedings of MAPSP Y1 - 2009 UR - http://opus.kobv.de/zib/volltexte/2009/1161/ SP - 224 EP - 226 ER - TY - CHAP A1 - Hiller, Benjamin A1 - Klug, Torsten A1 - Tuchscherer, Andreas T1 - Improved destination call elevator control algorithms for up peak traffic T2 - Operations Research Proceedings 2010 Y1 - 2010 PB - Springer ER - TY - CHAP A1 - Heinz, Stefan A1 - Krumke, Sven A1 - Megow, Nicole A1 - Rambau, Jörg A1 - Tuchscherer, Andreas A1 - Vredeveld, Tjark ED - Erlebach, Thomas ED - Persiano, Giuseppe T1 - The Online Target Date Assignment Problem T2 - Proc. 3rd Workshop on Approximation and Online Algorithms Y1 - 2006 UR - http://opus.kobv.de/zib/volltexte/2005/894/ VL - 3879 SP - 230 EP - 243 PB - Springer ER - TY - CHAP A1 - Hiller, Benjamin A1 - Tuchscherer, Andreas ED - Kalcsics, Jörg ED - Nickel, Stefan T1 - Real-Time Destination-Call Elevator Group Control on Embedded Microcontrollers T2 - Operations Research Proceedings Y1 - 2008 UR - http://opus.kobv.de/zib/volltexte/2007/1025/ SP - 357 EP - 362 PB - Springer ER - TY - CHAP A1 - Hiller, Benjamin A1 - Krumke, Sven A1 - Saliba, Sleman A1 - Tuchscherer, Andreas T1 - Randomized Online Algorithms for Dynamic Multi-Period Routing Problems T2 - Proceedings of MAPSP Y1 - 2009 SP - 71 EP - 73 ER -