@misc{Tesch2016, author = {Tesch, Alexander}, title = {Improved Compact Models for the Resource-Constrained Project Scheduling Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-62891}, year = {2016}, abstract = {In this article, we study compact Mixed-Integer Programming (MIP) models for the Resource-Constrained Project Scheduling Problem (RCPSP). Compared to the classical time-indexed formulation, the size of compact models is strongly polynomial in the number of jobs. In addition to two compact models from the literature, we propose a new compact model. We can show that all three compact models are equivalent by successive linear transformations. For their LP-relaxations, however, we state a full inclusion hierarchy where our new model dominates the previous models in terms of polyhedral strength. Moreover, we reveal a polyhedral relationship to the common time-indexed model. Furthermore, a general class of valid cutting planes for the compact models is introduced and finally all models are evaluated by computational experiments.}, language = {en} } @inproceedings{Tesch2016, author = {Tesch, Alexander}, title = {A Nearly Exact Propagation Algorithm for Energetic Reasoning in O(n^2 log n)}, volume = {22}, booktitle = {Principles and Practice of Constraint Programming (CP 2016)}, doi = {10.1007/978-3-319-44953-1_32}, pages = {493 -- 519}, year = {2016}, abstract = {In constraint programming, energetic reasoning constitutes a powerful start time propagation rule for cumulative scheduling problems (CuSP). In this paper, we first present an improved time interval checking algorithm that is derived from a polyhedral model. In a second step, we extend this algorithm to an energetic reasoning propagation algorithm with complexity O(n^2 log n) where n denotes the number of jobs. The key idea is based on a new sweep line subroutine that efficiently evaluates the relevant time intervals for all jobs. In particular, our algorithm yields at least one possible energetic reasoning propagation for each job. Finally, we show that on the vast number of relevant time intervals our approach yields the maximum possible propagation according to the energetic reasoning rule.}, language = {en} } @inproceedings{BorndoerferKarbsteinMehrgahrdtetal.2016, author = {Bornd{\"o}rfer, Ralf and Karbstein, Marika and Mehrgahrdt, Julika and Reuther, Markus and Schlechte, Thomas}, title = {The Cycle Embedding Problem}, booktitle = {Operations Research Proceedings 2014}, doi = {10.1007/978-3-319-28697-6_65}, pages = {465 -- 472}, year = {2016}, abstract = {Given two hypergraphs, representing a fine and a coarse "layer", and a cycle cover of the nodes of the coarse layer, the cycle embedding problem (CEP) asks for an embedding of the coarse cycles into the fine layer. The CEP is NP-hard for general hypergraphs, but it can be solved in polynomial time for graphs. We propose an integer rogramming formulation for the CEP that provides a complete escription of the CEP polytope for the graphical case. The CEP comes up in railway vehicle rotation scheduling. We present computational results for problem instances of DB Fernverkehr AG that justify a sequential coarse-first-fine-second planning approach.}, language = {en} } @article{PeitzGraelerHenkeetal.2016, author = {Peitz, Sebastian and Gr{\"a}ler, Manuel and Henke, Christian and Hessel-von Molo, Mirko and Dellnitz, Michael and Tr{\"a}chtler, Ansgar}, title = {Multiobjective Model Predictive Control of an Industrial Laundry}, journal = {Procedia Technology}, number = {26}, pages = {483 -- 490}, year = {2016}, abstract = {In a wide range of applications, it is desirable to optimally control a system with respect to concurrent, potentially competing goals. This gives rise to a multiobjective optimal control problem where, instead of computing a single optimal solution, the set of optimal compromises, the so-called Pareto set, has to be approximated. When it is not possible to compute the entire control trajectory in advance, for instance due to uncertainties or unforeseeable events, model predictive control methods can be applied to control the system during operation in real time. In this article, we present an algorithm for the solution of multiobjective model predictive control problems. In an offline scenario, it can be used to compute the entire set of optimal compromises whereas in a real time scenario, one optimal compromise is computed according to an operator's preference. The results are illustrated using the example of an industrial laundry. A logistics model of the laundry is developed and then utilized in the optimization routine. Results are presented for an offline as well as an online scenario}, language = {en} } @article{HumpolaFuegenschuhKoch2016, author = {Humpola, Jesco and F{\"u}genschuh, Armin and Koch, Thorsten}, title = {Valid inequalities for the topology optimization problem in gas network design}, volume = {38}, journal = {OR Spectrum}, number = {3}, publisher = {Springer}, address = {Berlin Heidelberg}, doi = {https://doi.org/10.1007/s00291-015-0390-2}, pages = {597 -- 631}, year = {2016}, abstract = {One quarter of Europe's energy demand is provided by natural gas distributed through a vast pipeline network covering the whole of Europe. At a cost of 1 million Euro per km extending the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. Unfortunately, current mathematical methods are not capable of solving the arising network design problems due to their size and complexity. In this article, we will show how to apply optimization methods that can converge to a proven global optimal solution. By introducing a new class of valid inequalities that improve the relaxation of our mixed-integer nonlinear programming model, we are able to speed up the necessary computations substantially.}, language = {en} } @misc{SagnolBarnerBorndoerferetal.2016, author = {Sagnol, Guillaume and Barner, Christoph and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Matthes and Spies, Claudia and Wernecke, Klaus}, title = {Robust Allocation of Operating Rooms: a Cutting Plane Approach to handle Lognormal Case Durations}, issn = {1438-0064}, doi = {10.1016/j.ejor.2018.05.022}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-58502}, year = {2016}, abstract = {The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. We formulate this problem as a parallel machines scheduling problem, in which job durations follow a lognormal distribution, and a fixed assignment of jobs to machines must be computed. We propose a cutting-plane approach to solve the robust counterpart of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations that identifies worst-case scenarios and generates cut inequalities. The main result of this article uses Hilbert's projective geometry to prove the convergence of this procedure under mild conditions. We also propose two exact solution methods for a similar problem, but with a polyhedral uncertainty set, for which only approximation approaches were known. Our model can be extended to balance the load over several planning periods in a rolling horizon. We present extensive numerical experiments for instances based on real data from a major hospital in Berlin. In particular, we find that: (i) our approach performs well compared to a previous model that ignored the distribution of case durations; (ii) compared to an alternative stochastic programming approach, robust optimization yields solutions that are more robust against uncertainty, at a small price in terms of average cost; (iii) the \emph{longest expected processing time first} (LEPT) heuristic performs well and efficiently protects against extreme scenarios, but only if a good prediction model for the durations is available. Finally, we draw a number of managerial implications from these observations.}, language = {en} } @misc{SagnolBorndoerferGrimaetal.2016, author = {Sagnol, Guillaume and Bornd{\"o}rfer, Ralf and Grima, Micka{\"e}l and Seeling, Matthes and Spies, Claudia}, title = {Robust Allocation of Operating Rooms with Lognormal case Durations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-58497}, year = {2016}, abstract = {The problem of allocating operating rooms (OR) to surgical cases is a challenging task, involving both combinatorial aspects and uncertainty handling. In this article, we formulate this problem as a job shop scheduling problem, in which the job durations follow a lognormal distribution. We propose to use a cutting-plane approach to solve a robust version of this optimization problem. To this end, we develop an algorithm based on fixed-point iterations to solve the subproblems that identify worst-case scenarios and generate cut inequalities. The procedure is illustrated with numerical experiments based on real data from a major hospital in Berlin.}, language = {en} } @article{BorndoerferFuegenschuhKlugetal.2016, author = {Bornd{\"o}rfer, Ralf and F{\"u}genschuh, Armin and Klug, Torsten and Schang, Thilo and Schlechte, Thomas and Sch{\"u}lldorf, Hanno}, title = {The Freight Train Routing Problem for Congested Railway Networks with Mixed Traffic}, volume = {50}, journal = {Transportation Science}, number = {2}, doi = {10.1287/trsc.2015.0656}, pages = {408 -- 423}, year = {2016}, abstract = {We consider the following freight train routing problem (FTRP). Given is a transportation network with fixed routes for passenger trains and a set of freight trains (requests), each defined by an origin and destination station pair. The objective is to calculate a feasible route for each freight train such that the sum of all expected delays and all running times is minimal. Previous research concentrated on microscopic train routings for junctions or inside major stations. Only recently approaches were developed to tackle larger corridors or even networks. We investigate the routing problem from a strategic perspective, calculating the routes in a macroscopic transportation network of Deutsche Bahn AG. In this context, macroscopic refers to an aggregation of complex and large real-world structures into fewer network elements. Moreover, the departure and arrival times of freight trains are approximated. The problem has a strategic character since it asks only for a coarse routing through the network without the precise timings. We provide a mixed-integer nonlinear programming (MINLP) formulation for the FTRP, which is a multicommodity flow model on a time-expanded graph with additional routing constraints. The model's nonlinearities originate from an algebraic approximation of the delays of the trains on the arcs of the network by capacity restraint functions. The MINLP is reduced to a mixed-integer linear model (MILP) by piecewise linear approximation. The latter is solved by a state-of-the art MILP solver for various real-world test instances.}, language = {en} } @inproceedings{Karbstein2016, author = {Karbstein, Marika}, title = {Integrated Line Planning and Passenger Routing: Connectivity and Transfers}, booktitle = {Operations Research Proceedings 2014}, doi = {10.1007/978-3-319-28697-6_37}, pages = {263 -- 269}, year = {2016}, abstract = {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.}, language = {en} } @masterthesis{Wyczisk2016, type = {Bachelor Thesis}, author = {Wyczisk, Christopher}, title = {Portfoliooptimierung mittels mathematischer Optimierung}, year = {2016}, language = {de} } @misc{GamrathFischerGallyetal.2016, author = {Gamrath, Gerald and Fischer, Tobias and Gally, Tristan and Gleixner, Ambros and Hendel, Gregor and Koch, Thorsten and Maher, Stephen J. and Miltenberger, Matthias and M{\"u}ller, Benjamin and Pfetsch, Marc and Puchert, Christian and Rehfeldt, Daniel and Schenker, Sebastian and Schwarz, Robert and Serrano, Felipe and Shinano, Yuji and Vigerske, Stefan and Weninger, Dieter and Winkler, Michael and Witt, Jonas T. and Witzig, Jakob}, title = {The SCIP Optimization Suite 3.2}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57675}, year = {2016}, abstract = {The SCIP Optimization Suite is a software toolbox for generating and solving various classes of mathematical optimization problems. Its major components are the modeling language ZIMPL, the linear programming solver SoPlex, the constraint integer programming framework and mixed-integer linear and nonlinear programming solver SCIP, the UG framework for parallelization of branch-and-bound-based solvers, and the generic branch-cut-and-price solver GCG. It has been used in many applications from both academia and industry and is one of the leading non-commercial solvers. This paper highlights the new features of version 3.2 of the SCIP Optimization Suite. Version 3.2 was released in July 2015. This release comes with new presolving steps, primal heuristics, and branching rules within SCIP. In addition, version 3.2 includes a reoptimization feature and improved handling of quadratic constraints and special ordered sets. SoPlex can now solve LPs exactly over the rational number and performance improvements have been achieved by exploiting sparsity in more situations. UG has been tested successfully on 80,000 cores. A major new feature of UG is the functionality to parallelize a customized SCIP solver. GCG has been enhanced with a new separator, new primal heuristics, and improved column management. Finally, new and improved extensions of SCIP are presented, namely solvers for multi-criteria optimization, Steiner tree problems, and mixed-integer semidefinite programs.}, language = {en} } @misc{D'Andreagiovanni2016, author = {D'Andreagiovanni, Fabio}, title = {Revisiting wireless network jamming by SIR-based considerations and Multiband Robust Optimization}, issn = {1438-0064}, doi = {10.1007/s11590-014-0839-2}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-57728}, year = {2016}, abstract = {We revisit the mathematical models for wireless network jamming introduced by Commander et al. (2007,2008): we first point out the strong connections with classical wireless network design and then we propose a new model based on the explicit use of signal-to-interference quantities. Moreover, to ad- dress the uncertain nature of the jamming problem and tackle the peculiar right-hand-side (RHS) uncertainty of the corresponding model, we propose an original robust cutting-plane algorithm drawing inspiration from Multiband Robust Optimization. Finally, we assess the performance of the proposed cutting plane algorithm by experiments on realistic network instances.}, language = {en} } @inproceedings{BeckenbachBorndoerfer2016, author = {Beckenbach, Isabel and Bornd{\"o}rfer, Ralf}, title = {An Approximation Result for Matchings in Partitioned Hypergraphs}, booktitle = {Operations Research Proceedings 2014}, publisher = {Springer International Publishing}, doi = {10.1007/978-3-319-28697-6_5}, pages = {31 -- 36}, year = {2016}, abstract = {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})\$.}, language = {en} } @misc{HillerSaitenmacherWalther2016, author = {Hiller, Benjamin and Saitenmacher, Ren{\´e} and Walther, Tom}, title = {Analysis of operating modes of complex compressor stations}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61092}, year = {2016}, abstract = {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.}, language = {en} } @misc{SchwartzBorndoerferBartz2016, author = {Schwartz, Stephan and Bornd{\"o}rfer, Ralf and Bartz, Gerald}, title = {The Graph Segmentation Problem}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60750}, year = {2016}, abstract = {We investigate a graph theoretical problem arising in the automatic billing of a network toll. Given a network and a family of user paths, we study the graph segmentation problem (GSP) to cover parts of the user paths by a set of disjoint segments. The GSP is shown to be NP-hard but for special cases it can be solved in polynomial time. We also show that the marginal utility of a segment is bounded. Computational results for real-world instances show that in practice the problem is more amenable than the theoretic bounds suggest.}, language = {en} } @inproceedings{BorndoerferHoppmannKarbsteinetal.2016, author = {Bornd{\"o}rfer, Ralf and Hoppmann, Heide and Karbstein, Marika and L{\"o}bel, Fabian}, title = {The Modulo Network Simplex with Integrated Passenger Routing}, booktitle = {Operations Research Proceedings 2016}, year = {2016}, abstract = {Periodic timetabling is an important strategic planning problem in public transport. The task is to determine periodic arrival and departure times of the lines in a given network, minimizing the travel time of the passengers. We extend the modulo network simplex method, a well-established heuristic for the periodic timetabling problem, by integrating a passenger (re)routing step into the pivot operations. Computations on real-world networks show that we can indeed find timetables with much shorter total travel time, when we take the passengers' travel paths into consideration.}, language = {en} } @inproceedings{ShinanoBertholdHeinz2016, author = {Shinano, Yuji and Berthold, Timo and Heinz, Stefan}, title = {A First Implementation of ParaXpress: Combining Internal and External Parallelization to Solve MIPs on Supercomputers}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_38}, pages = {308 -- 316}, year = {2016}, language = {en} } @book{GreuelKochPauleetal.2016, author = {Greuel, Martin and Koch, Thorsten and Paule, Peter and Sommese, Andrew}, title = {Mathematical Software - ICMS 2016, 5th Int. Conf. Berlin, Germany, July 11-14, 2016, Proceedings}, volume = {9725}, journal = {Lecture Notes in Computer Science (LNCS)}, publisher = {Springer}, isbn = {978-3-319-42431-6}, doi = {10.1007/978-3-319-42432-3}, pages = {XXIV, 532}, year = {2016}, language = {en} } @inproceedings{BertholdFarmerHeinzetal.2016, author = {Berthold, Timo and Farmer, James and Heinz, Stefan and Perregaard, Michael}, title = {Parallelization of the FICO Xpress-Optimizer}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_31}, pages = {251 -- 258}, year = {2016}, language = {en} } @inproceedings{ChraparyRen2016, author = {Chrapary, Hagen and Ren, Yue}, title = {The Software Portal swMATH: A State of the Art Report and Next Steps}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference Berlin, Germany, July 11-14, 2016 Proceedings}, doi = {10.1007/978-3-319-42432-3_49}, pages = {397 -- 402}, year = {2016}, language = {en} }