@masterthesis{Hendel2011, type = {Bachelor Thesis}, author = {Hendel, Gregor}, title = {New Rounding and Propagation Heuristics for Mixed Integer Programming}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-13322}, school = {Zuse Institute Berlin (ZIB)}, pages = {95}, year = {2011}, abstract = {Die vorliegende Arbeit befasst sich mit Primalheuristiken f{\"u}r gemischt-ganzzahlige, lineare Optimierungsprobleme (engl.: mixed integer program MIP). Zahlreiche Optimierungsprobleme aus der Praxis lassen sich als MIP modellieren, Beispiele hierf{\"u}r sind u. a. Optimierungsprobleme im {\"o}ffentlichen Nah- und Fernverkehr, bei logistischen Fragestellungen oder im Bereich der Chip-Verifikation. Das L{\"o}sen von MIP ist NP-schwer und wird heutzutage meistens mit Hilfe von Branch-and-Bound-basierenden Algorithmen versucht. Das Branch-and-Bound-Ver\-fah\-ren profitiert unter Umst{\"a}nden von bereits fr{\"u}hzeitig zur Verf{\"u}gung stehenden L{\"o}sungen, daher sind wir sehr an heuristischen Verfahren interessiert, die in der Praxis schnell eine gute L{\"o}sung f{\"u}r eine große Zahl an MIPs liefern und somit die L{\"o}sezeit des Branch-and-Bound-Verfahrens erheblich beschleunigen k{\"o}nnen. Primalheuristiken sind Suchverfahren zum Auffinden zul{\"a}ssiger L{\"o}sungen eines MIP. Verschiedene Typen von Primalheuristiken sollen dabei den jeweiligen Bedarf des Anwenders zu unterschiedlichen Zeiten w{\"a}hrend der Branch-and-Bound-Suche decken. W{\"a}hrend Start- und Rundeheuristiken zu Beginn des L{\"o}seprozesses eine große Rolle bei der Suche nach der ersten zul{\"a}ssigen L{\"o}sung haben, arbeiten Verbesserungs-heuristiken auf schon bekannten L{\"o}sungen, um neue, bessere L{\"o}sungen zu produzieren. Diese Arbeit besch{\"a}ftigt sich mit Primalheuristiken, welche Teil des MIP-L{\"o}sers SCIP sind. Im ersten Kapitel werden nach der Erarbeitung grundlegender Definitionen viele der durch Tobias Achterberg und Timo Berthold in SCIP integrierten heuristischen Verfahren vorgestellt und kategorisiert. Auf dieser Grundlage bauen dann die Kapitel 2-4 der Arbeit auf. In diesen werden drei zus{\"a}tzliche Heuristiken vorgestellt, im Einzelnen sind dies ZI Round, eine Rundeheuristik, welche zuerst von Wallace beschrieben wurde, außerdem eine 2-Opt-Heuristik f{\"u}r MIP und eine neue Startheuristik, Shift-And-Propagate. Großer Wert wird in jedem Kapitel auf die algorithmische Beschreibung der Heuristiken gelegt, die stets anhand von motivierenden Beispielen eingef{\"u}hrt und anhand von Pseudocode-Algorithmen begleitet werden. Zus{\"a}tzlich enth{\"a}lt jedes Kapitel Auswertungen der mit den neuen Heuristiken gemessenen Ergebnisse von SCIP. Eine kurze Zusammenfassung in Kapitel 5 schließt diese Arbeit ab.}, language = {en} } @misc{BertholdHeinzPfetschetal.2011, author = {Berthold, Timo and Heinz, Stefan and Pfetsch, Marc and Vigerske, Stefan}, title = {Large Neighborhood Search beyond MIP}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-12989}, number = {11-21}, year = {2011}, abstract = {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.}, language = {en} } @misc{FuegenschuhHumpola2013, author = {F{\"u}genschuh, Armin and Humpola, Jesco}, title = {A Unified View on Relaxations for a Nonlinear Network Flow Problem}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18857}, year = {2013}, abstract = {We consider a nonlinear nonconvex network flow problem that arises, for example, in natural gas or water transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. The problem is how to numerically compute this flow and pressures. We review an existing approach of Maugis (1977) and extend it to the case of networks with active elements (for example, compressors). We further examine different ways of relaxations for the nonlinear network flow model. We compare different approaches based on nonlinear optimization numerically on a set of test instances.}, language = {en} } @misc{FuegenschuhVierhaus2013, author = {F{\"u}genschuh, Armin and Vierhaus, Ingmar}, title = {A Global Approach to the Optimal Control of System Dynamics Models}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18600}, year = {2013}, abstract = {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 ordinary differential equations and nonlinear algebraic constraints. Therefore seemingly simple systems can show a nonintuitive, unpredictable behavior over time. Controlling a dynamical system means to specify potential interventions from outside that should keep the system on the desired track, and to define an evaluation schema to compare different controls among each other, so that a "best" control can be defined in a meaningful way. The central question is how to compute such globally optimal control for a given SD model, that allows the transition of the system into a desired state with minimum effort. We propose a mixed-integer nonlinear programming (MINLP) reformulation of the System Dynamics Optimization (SDO) problem. MINLP problems can be solved by linear programming based branch-and-bound approach. We demonstrate that standard MINLP solvers are not able to solve SDO problem. To overcome this obstacle, we introduce a special-tailored bound propagation method. We apply our new method to a predator-prey model with additional hunting activity as control, and to a mini-world model with the consumption level as control. Numerical results for these test cases are presented.}, language = {en} } @misc{LindnerLiebchen2021, author = {Lindner, Niels and Liebchen, Christian}, title = {Timetable Merging for the Periodic Event Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81587}, year = {2021}, abstract = {We propose a new mixed integer programming based heuristic for computing new benchmark primal solutions for instances of the PESPlib. The PESPlib is a collection of instances for the Periodic Event Scheduling Problem (PESP), comprising periodic timetabling problems inspired by real-world railway timetabling settings, and attracting several international research teams during the last years. We describe two strategies to merge a set of good periodic timetables. These make use of the instance structure and minimum weight cycle bases, finally leading to restricted mixed integer programming formulations with tighter variable bounds. Implementing this timetable merging approach in a concurrent solver, we improve the objective values of the best known solutions for the smallest and largest PESPlib instances by 1.7 and 4.3 percent, respectively.}, language = {en} } @misc{LeitnerLjubicSinnletal.2013, author = {Leitner, Markus and Ljubic, Ivana and Sinnl, Markus and Werner, Axel}, title = {On the Two-Architecture Connected Facility Location Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18610}, year = {2013}, abstract = {We introduce a new variant of the connected facility location problem that allows for modeling mixed deployment strategies (FTTC/FTTB/FTTH) in the design of local access telecommunication networks. Several mixed integer programming models and valid inequalities are presented. Computational studies on realistic instances from three towns in Germany are provided.}, language = {en} } @misc{HumpolaFuegenschuh2013, author = {Humpola, Jesco and F{\"u}genschuh, Armin}, title = {A New Class of Valid Inequalities for Nonlinear Network Design Problems}, issn = {1438-0064}, doi = {10.1007/s00291-015-0390-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17771}, year = {2013}, abstract = {We consider a nonlinear nonconvex network design problem that arises in the extension of natural gas transmission networks. Given is such network with active and passive components, that is, valves, compressors, pressure regulators (active) and pipelines (passive), and a desired amount of flow at certain specified entry and exit nodes of the network. Besides flow conservation constraints in the nodes the flow must fulfill nonlinear nonconvex pressure loss constraints on the arcs subject to potential values (i.e., pressure levels) in both end nodes of each arc. Assume that there does not exist a feasible flow that fulfills all physical constraints and meets the desired entry and exit amounts. Then a natural question is where to extend the network by adding pipes in the most economic way such that this flow becomes feasible. Answering this question is computationally demanding because of the difficult problem structure. We use mixed-integer nonlinear programming techniques that rely on an outer approximation of the overall problem, and a branching on decision variables. We formulate a new class of valid inequalities (or cutting planes) which reduce the overall solution time when added to the formulation. We demonstrate the computational merits of our approach on test instances.}, language = {en} } @misc{LindnerLiebchenMasing2021, author = {Lindner, Niels and Liebchen, Christian and Masing, Berenike}, title = {Forward Cycle Bases and Periodic Timetabling}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2021.2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82756}, year = {2021}, abstract = {Periodic timetable optimization problems in public transport can be modeled as mixed-integer linear programs by means of the Periodic Event Scheduling Problem (PESP). In order to keep the branch-and-bound tree small, minimum integral cycle bases have been proven successful. We examine forward cycle bases, where no cycle is allowed to contain a backward arc. After reviewing the theory of these bases, we describe the construction of an integral forward cycle basis on a line-based event-activity network. Adding turnarounds to the instance \texttt{R1L1} of the benchmark library PESPlib, we computationally evaluate three types of forward cycle bases in the Pareto sense, and come up with significant improvements concerning dual bounds.}, language = {en} } @misc{LindnerMaristanydelasCasasSchiewe2021, author = {Lindner, Niels and Maristany de las Casas, Pedro and Schiewe, Philine}, title = {Optimal Forks: Preprocessing Single-Source Shortest Path Instances with Interval Data}, issn = {1438-0064}, doi = {10.4230/OASIcs.ATMOS.2021.7}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-82716}, year = {2021}, abstract = {We investigate preprocessing for single-source shortest path queries in digraphs, where arc costs are only known to lie in an interval. More precisely, we want to decide for each arc whether it is part of some shortest path tree for some realization of costs. We show that this problem is solvable in polynomial time by giving a combinatorial algorithm, using optimal structures that we call forks. Our algorithm turns out to be very efficient in practice, and is sometimes even superior in quality to a heuristic developed for the one-to-one shortest path problem in the context of passenger routing in public transport.}, language = {en} } @misc{LindnervanLieshout2021, author = {Lindner, Niels and van Lieshout, Rolf}, title = {Benders Decomposition for the Periodic Event Scheduling Problem}, issn = {1438-0064}, doi = {10.1007/978-3-031-08623-6_43}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-83338}, year = {2021}, abstract = {The Periodic Event Scheduling Problem (PESP) is the central mathematical model behind the optimization of periodic timetables in public transport. We apply Benders decomposition to the incidence-based MIP formulation of PESP. The resulting formulation exhibits particularly nice features: The subproblem is a minimum cost network flow problem, and feasibility cuts are equivalent to the well-known cycle inequalities by Odijk. We integrate the Benders approach into a branch-and-cut framework, and assess the performance of this method on instances derived from the benchmarking library PESPlib.}, language = {en} } @misc{FuegenschuhVierhaus2013, author = {F{\"u}genschuh, Armin and Vierhaus, Ingmar}, title = {System Dynamic Optimization in the Sustainability Assessment of a World-Model}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-18148}, year = {2013}, abstract = {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.}, language = {en} }