TY - CHAP A1 - Vierhaus, Ingmar A1 - Fügenschuh, Armin T1 - Global and Local Optimal Control of a Resource Utilization Problem T2 - Proceedings of the 33rd International Conference of the System Dynamics Society N2 - System Dynamic models describe physical, technical, economical, or social systems using differential and algebraic equations. In their purest form, these models are intended to describe the evolution of a system from a given initial state. In many applications, it is possible to intervene with the system in order to obtain a desired dynamic or a certain outcome in the end. On the mathematical side, this leads to control problems, where aside from the simulation one has to find optimal intervention functions over time that maximize a specific objective function. Using a dynamical model for the utilization of a natural nonrenewable resource of Behrens as a demonstrator example, we present two main mathematical solution strategies. They are distinguished by the quality certificate on their respective solution: one leads to proven local optimal solution, and the other technique yields proven global optimal solutions. We present implementational and numerical issues, and a comparison of both methods. Y1 - 2015 ER - TY - CHAP A1 - Hiller, Benjamin A1 - Saitenmacher, René A1 - Walther, Tom T1 - Analysis of operating modes of complex compressor stations T2 - Proceedings of Operations Research 2016 N2 - We consider the modeling of operation modes for complex compressor stations (i.e., ones with several in- or outlets) in gas networks. In particular, we propose a refined model that allows to precompute tighter relaxations for each operation mode. These relaxations may be used to strengthen the compressor station submodels in gas network optimization problems. We provide a procedure to obtain the refined model from the input data for the original model. Y1 - 2017 U6 - https://doi.org/10.1007/978-3-319-55702-1_34 SP - 251 EP - 257 ER - TY - THES A1 - Viernickel, Jan Merlin T1 - Abschätzung der Suchbaumgröße und Laufzeit für Branch-and-Bound Algorithmen Y1 - 2016 ER - TY - THES A1 - Gottwald, Robert Lion T1 - Experiments with Concurrency and Heuristics in SCIP Y1 - 2016 ER - TY - THES A1 - Roessig, Ansgar T1 - Formulations and algorithms for the USCCSP Y1 - 2016 ER - TY - THES A1 - Teuchert, Andreas T1 - Degeneriertheit im Simplexverfahren Y1 - 2017 ER - TY - THES A1 - Brückner, Michael T1 - On the Shortest Path Problem with Pair Constraints N2 - This thesis investigates the shortest path problem with pair constraints or the pair constraint problem (PCP) for short. We consider two types of pair constraints, namely forbidden pairs and binding pairs consisting of two distinct vertices each. A path respects a forbidden pair if it uses at most one of the two vertices and it respects a binding pair (x,y) if it uses also y, if x is used. Within this thesis, we bring together and compare several formulations and variants of the pair constraint problem and their complexities. We also collect existing recursive algorithms and present their running times. Most of the presented contributions only consider forbidden pairs. We introduce a new recursive algorithm also handling binding pairs and prove its theoretical complexity of O(n^4). We implemented the algorithm and tested it on real-world instances provided by Lufthansa Systems AG. Therefore we needed to develop a heuristic translating the real-world data into an instance of the shortest path problem with pair constraints. This heuristic is presented as well as all computational results. In Chapter 4, we start investigating the associated polytope of an integer program formulation of the shortest path problem with pair constraints. For the case of one forbidden or binding pair, we find a complete linear description of the associated polytope. We prove that the number of facets grows exponentially in |V| even in these simple cases. However, separation is still possible in polynomial time. The complete linear description can be extended to the case of contiguously disjoint pairs. Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57265 ER - TY - GEN A1 - D'Andreagiovanni, Fabio A1 - Felici, Giovanni A1 - Lacalandra, Fabrizio T1 - Revisiting the use of Robust Optimization for optimal energy offering under price uncertainty N2 - We propose a new Robust Optimization method for the energy offering problem of a price-taker generating company that wants to build offering curves for its generation units, in order to maximize its profit while taking into account the uncertainty of market price. Our investigations have been motivated by a critique to another Robust Optimization method, which entails the solution of a sequence of robust optimization problems imposing full protection and defined over a sequence of nested subintervals of market prices: this method presents a number of issues that may severely limit its application and computational efficiency in practice and that may expose a company to the risk of presenting offering curves resulting into suboptimal or even infeasible accepted offers. To tackle all such issues, our method provides for solving one single robust counterpart, considering an intermediate level of protection between null and full protection, and to make energy offers at zero price, practically eliminating the risk of non-acceptance. Computational results on instances provided by our industrial partners show that our new method is able to grant a great improvement in profit. T3 - ZIB-Report - 15-61 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57128 SN - 1438-0064 N1 - Fabio D'Andreagiovanni is First Author ER - TY - GEN A1 - Borndörfer, Ralf A1 - Hoppmann, Heide A1 - Karbstein, Marika T1 - Passenger Routing for Periodic Timetable Optimization N2 - The task of periodic timetabling is to schedule the trips in a public transport system by determining arrival and departure times at every station such that travel and transfer times are minimized. To date, the optimization literature generally assumes that passengers do not respond to changes in the timetable, i.e., the passenger routes are fixed. This is unrealistic and ignores potentially valuable degrees of freedom. We investigate in this paper periodic timetabling models with integrated passenger routing. We show that different routing models have a huge influence on the quality of the entire system: Whatever metric is applied, the performance ratios of timetables w.r.t. to different routing models can be arbitrarily large. Computations on a real-world instance for the city of Wuppertal substantiate the theoretical findings. These results indicate the existence of untapped optimization potentials that can be used to improve the efficiency of public transport systems. T3 - ZIB-Report - 15-55 KW - Passenger routing KW - Periodic timetabling KW - Public transport Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56739 SN - 1438-0064 ER - TY - GEN A1 - Pulaj, Jonad A1 - Raymond, Annie A1 - Theis, Dirk T1 - New Conjectures For Union-Closed Families N2 - The Frankl conjecture, also known as the union-closed sets conjecture, states that there exists an element in at least half of the sets of any (non-empty) union-closed family. From an optimization point of view, one could instead prove that 2a is an upper bound to the number of sets in a union-closed family with n elements where each element is in at most a sets, where a and n are non-negative integers. Formulating these problems as integer programs we observe that computed optimal values do not vary with n. We formalize these observations as conjectures, and show that they are not equivalent to the Frankl conjecture while still having wide-reaching implications if proven true. Finally, we partially prove the new conjectures and discuss possible approaches to solve them completely. T3 - ZIB-Report - 15-57 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-56804 SN - 1438-0064 ER - TY - GEN A1 - Hendel, Gregor T1 - Exploiting Solving Phases for Mixed-Integer Programs N2 - Modern MIP solving software incorporates dozens of auxiliary algorithmic components for supporting the branch-and-bound search in finding and improving solutions and in strengthening the relaxation. Intuitively, a dynamic solving strategy with an appropriate emphasis on different solving components and strategies is desirable during the search process. We propose an adaptive solver behavior that dynamically reacts on transitions between the three typical phases of a MIP solving process: The first phase objective is to find a feasible solution. During the second phase, a sequence of incumbent solutions gets constructed until the incumbent is eventually optimal. Proving optimality is the central objective of the remaining third phase. Based on the MIP-solver SCIP, we demonstrate the usefulness of the phase concept both with an exact recognition of the optimality of a solution, and provide heuristic alternatives to make use of the concept in practice. T3 - ZIB-Report - 15-64 KW - Branch-and-Bound, Mixed-Integer Programming Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-57098 SN - 1438-0064 ER - TY - JOUR A1 - Borndörfer, Ralf A1 - Reuther, Markus A1 - Schlechte, Thomas A1 - Waas, Kerstin A1 - Weider, Steffen T1 - Integrated Optimization of Rolling Stock Rotations for Intercity Railways JF - Transportation Science N2 - This paper proposes a highly integrated solution approach for rolling stock planning problems in the context of long distance passenger traffic between cities. The main contributions are a generic hypergraph-based mixed-integer programming model for the considered rolling stock rotation problem and an integrated algorithm for its solution. The newly developed algorithm is able to handle a large spectrum of industrial railway requirements, such as vehicle composition, maintenance constraints, infrastructure capacities, and regularity aspects. We show that our approach has the power to produce rolling stock rotations that can be implemented in practice. In this way, the rolling stock rotations at the largest German long distance operator Deutsche Bahn Fernverkehr AG could be optimized by an automated system utilizing advanced mathematical programming techniques. Y1 - 2016 U6 - https://doi.org/10.1287/trsc.2015.0633 VL - 50 IS - 3 SP - 863 EP - 877 ER - TY - JOUR A1 - Blanco, Marco A1 - Borndörfer, Ralf A1 - Brückner, Michael A1 - Hoang, Nam-Dung A1 - Schlechte, Thomas T1 - On the Path Avoiding Forbidden Pairs Polytope JF - Electronic Notes in Discrete Mathematics N2 - Given a directed, acyclic graph, a source and a sink node, and a set of forbidden pairs of arcs, the path avoiding forbidden pairs (PAFP) problem is to find a path that connects the source and sink nodes and contains at most one arc from each forbidden pair. The general version of the problem is NP-hard, but it becomes polynomially solvable for certain topological configurations of the pairs. We present the first polyhedral study of the PAFP problem. We introduce a new family of valid inequalities for the PAFP polytope and show that they are sufficient to provide a complete linear description in the special case where the forbidden pairs satisfy a disjointness property. Furthermore, we show that the number of facets of the PAFP polytope is exponential in the size of the graph, even for the case of a single forbidden pair. Y1 - 2015 U6 - https://doi.org/10.1016/j.endm.2015.07.057 VL - 50 SP - 343 EP - 348 ER - TY - CHAP A1 - Shinano, Yuji A1 - Achterberg, Tobias A1 - Berthold, Timo A1 - Heinz, Stefan A1 - Koch, Thorsten A1 - Winkler, Michael ED - IEEE, T1 - Solving Hard MIPLIP2003 Problems with ParaSCIP on Supercomputers: An Update T2 - IPDPSW'14 Proceedings of the 2014 IEEE, International Parallel & Distributed Processing Symposium Workshops Y1 - 2014 SN - 978-1-4799-4117-9 U6 - https://doi.org/10.1109/IPDPSW.2014.174 SP - 1552 EP - 1561 PB - IEEE Computer Society CY - Washington, DC, USA ER - TY - JOUR A1 - Grötschel, Martin T1 - Die IMU und ihr Sekretariat JF - Mitteilungen der DMV N2 - Was macht die International Mathematical Union (IMU) eigentlich, und wozu ist das IMU-Sekretariat da? ... Y1 - 2015 U6 - https://doi.org/10.1515/dmvm-2015-0012 VL - 23 IS - 1 SP - 24 EP - 29 ER - TY - GEN A1 - Yokoyama, Ryohei A1 - Shinano, Yuji A1 - Taniguchi, Syusuke A1 - Ohkura, Masashi A1 - Wakui, Tetsuya T1 - Optimization of energy supply systems by MILP branch and bound method in consideration of hierarchical relationship between design and operation N2 - To attain the highest performance of energy supply systems, it is necessary to rationally determine types, capacities, and numbers of equipment in consideration of their operational strategies corresponding to seasonal and hourly variations in energy demands. In the combinatorial optimization method based on the mixed-integer linear programming (MILP), integer variables are used to express the selection, numbers, and on/off status of operation of equipment, and the number of these variables increases with those of equipment and periods for variations in energy demands, and affects the computation efficiency significantly. In this paper, a MILP method utilizing the hierarchical relationship between design and operation variables is proposed to solve the optimal design problem of energy supply systems efficiently: At the upper level, the optimal values of design variables are searched by the branch and bound method; At the lower level, the values of operation variables are optimized independently at each period by the branch and bound method under the values of design variables given tentatively during the search at the upper level; Lower bounds for the optimal value of the objective function are evaluated, and are utilized for the bounding operations at both the levels. This method is implemented into open and commercial MILP solvers. Illustrative and practical case studies on the optimal design of cogeneration systems are conducted, and the validity and effectiveness of the proposed method are clarified. T3 - ZIB-Report - 14-09 KW - Energy supply systems KW - Optimal design KW - Optimal operation KW - Mixed-integer linear programming KW - Branch and bound method KW - Hierarchical approach Y1 - 2014 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-49413 SN - 1438-0064 ER - TY - JOUR A1 - Shinano, Yuji A1 - Inui, Nobuo A1 - Fukagawa, Youzou A1 - Takakura, Noburu T1 - Optimizing Movement Sequences for Step-and-Scan Lithography Equipment JF - Journal of Advanced Mechanical Design, Systems, and Manufacturing N2 - The purpose of this work is to improve the throughput of step-and-scan lithography equipment to shorten the production time of a wafer. For this purpose, we propose a method for solving the MSOP (Movement Sequence Optimization Problem), which is the problem of computing the fastest schedule for visiting all shots on a wafer. It is well-known that the MSOP on step-and-repeat lithography equipment can be modeled as a traveling salesman problem. In contrast to step-and-repeat lithography equipment, a schedule for step-and-scan lithography equipment must also indicate the scanning direction of each shot, in addition to the sequence of the shots. For this reason, the traveling salesman problem formulation for step-and-repeat lithography equipment cannot be applied to solve the MSOP on step-and-scan lithography equipment directly. We overcame this difficulty by introducing auxiliary vertices to model the scanning directions in the traveling salesman problem formulation. By this method, we were able to compute exact optimal sequences considering the scanning directions of shots for several MSOP instances. Our numerical experiments demonstrated that our proposed method was capable of computing exact optimal solutions for real-world MSOP instances having up to 232 shots on a wafer. These optimal solutions gave a 0.25% to 4.66% improvement in productivity over solutions computed by previously known methods. Y1 - 2013 U6 - https://doi.org/10.1299/jamdsm.7.608 VL - 7 IS - 4 SP - 608 EP - 618 ER - TY - THES A1 - Fügenschuh, Armin T1 - Computational aspects of time in scheduling and dynamic flow problems Y1 - 2011 ER - TY - THES A1 - Winter, Bianca T1 - Mathematische Optimierungsverfahren für die Konferenzplanung Y1 - 2011 ER - TY - THES A1 - Laaser, A. T1 - Gröbnerbasen und das Resource-Constrained-Shortest-Path Problem Y1 - 2013 ER - TY - THES A1 - Radke, A. T1 - Das Travelling Salesman Problem als Modell für Kapazitätsanalysen im Schienenverkehr Y1 - 2013 ER - TY - THES A1 - Jung, S. T1 - Optimierung der Bahnplanung für eine Pick-and-Place-Maschine Y1 - 2012 ER - TY - THES A1 - Roos, Stephanie T1 - Analysis of Routing on Sparse Small-World Topologies Y1 - 2011 ER - TY - GEN A1 - Gleixner, Ambros A1 - Steffy, Daniel A1 - Wolter, Kati T1 - Iterative Refinement for Linear Programming N2 - We describe an iterative refinement procedure for computing extended precision or exact solutions to linear programming problems (LPs). Arbitrarily precise solutions can be computed by solving a sequence of closely related LPs with limited precision arithmetic. The LPs solved share the same constraint matrix as the original problem instance and are transformed only by modification of the objective function, right-hand side, and variable bounds. Exact computation is used to compute and store the exact representation of the transformed problems, while numeric computation is used for solving LPs. At all steps of the algorithm the LP bases encountered in the transformed problems correspond directly to LP bases in the original problem description. We show that this algorithm is effective in practice for computing extended precision solutions and that it leads to a direct improvement of the best known methods for solving LPs exactly over the rational numbers. Our implementation is publically available as an extension of the academic LP solver SoPlex. T3 - ZIB-Report - 15-15 Y1 - 2015 U6 - http://nbn-resolving.de/urn/resolver.pl?urn:nbn:de:0297-zib-55118 SN - 1438-0064 ER -