@misc{MaherMiltenbergerPedrosoetal.2016, author = {Maher, Stephen J. and Miltenberger, Matthias and Pedroso, Jo{\~a}o Pedro and Rehfeldt, Daniel and Schwarz, Robert and Serrano, Felipe}, title = {PySCIPOpt: Mathematical Programming in Python with the SCIP Optimization Suite}, issn = {1438-0064}, doi = {10.1007/978-3-319-42432-3_37}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-61348}, year = {2016}, abstract = {SCIP is a solver for a wide variety of mathematical optimization problems. It is written in C and extendable due to its plug-in based design. However, dealing with all C specifics when extending SCIP can be detrimental to development and testing of new ideas. This paper attempts to provide a remedy by introducing PySCIPOpt, a Python interface to SCIP that enables users to write new SCIP code entirely in Python. We demonstrate how to intuitively model mixed-integer linear and quadratic optimization problems and moreover provide examples on how new Python plug-ins can be added to SCIP.}, language = {en} } @article{GleixnerMaherMuelleretal.2020, author = {Gleixner, Ambros and Maher, Stephen and M{\"u}ller, Benjamin and Pedroso, Jo{\~a}o Pedro}, title = {Price-and-verify: a new algorithm for recursive circle packing using Dantzig-Wolfe decomposition}, volume = {284}, journal = {Annals of Operations Research}, number = {2}, publisher = {Springer US}, doi = {10.1007/s10479-018-3115-5}, pages = {527 -- 555}, year = {2020}, abstract = {Packing rings into a minimum number of rectangles is an optimization problem which appears naturally in the logistics operations of the tube industry. It encompasses two major difficulties, namely the positioning of rings in rectangles and the recursive packing of rings into other rings. This problem is known as the Recursive Circle Packing Problem (RCPP). We present the first dedicated method for solving RCPP that provides strong dual bounds based on an exact Dantzig-Wolfe reformulation of a nonconvex mixed-integer nonlinear programming formulation. The key idea of this reformulation is to break symmetry on each recursion level by enumerating one-level packings, i.e., packings of circles into other circles, and by dynamically generating packings of circles into rectangles. We use column generation techniques to design a "price-and-verify" algorithm that solves this reformulation to global optimality. Extensive computational experiments on a large test set show that our method not only computes tight dual bounds, but often produces primal solutions better than those computed by heuristics from the literature.}, language = {en} } @misc{GamrathKochMaheretal.2016, author = {Gamrath, Gerald and Koch, Thorsten and Maher, Stephen J. and Rehfeldt, Daniel and Shinano, Yuji}, title = {SCIP-Jack - A solver for STP and variants with parallelization extensions}, issn = {1438-0064}, doi = {10.1007/s12532-016-0114-x}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-60170}, year = {2016}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. While often a strong relationship between different Steiner tree problem variants can be observed, solution approaches employed so far have been prevalently problem-specific. In contrast, this paper introduces a general-purpose solver that can be used to solve both the classical Steiner tree problem and many of its variants without modification. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances.}, language = {en} } @misc{RehfeldtKoch2016, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {Transformations for the Prize-Collecting Steiner Tree Problem and the Maximum-Weight Connected Subgraph Problem to SAP}, issn = {1438-0064}, doi = {10.4208/jcm.1709-m2017-0002}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59777}, year = {2016}, abstract = {Transformations of Steiner tree problem variants have been frequently discussed in the literature. Besides allowing to easily transfer complexity results, they constitute a central pillar of exact state-of-the-art solvers for well-known variants such as the Steiner tree problem in graphs. In this paper transformations for both the prize-collecting Steiner tree problem and the maximum-weight connected subgraph problem to the Steiner arborescence problem are introduced for the first time. Furthermore, we demonstrate the considerable implications for practical solving approaches, including the computation of strong upper and lower bounds.}, language = {en} } @inproceedings{BorndoerferSchenkerSkutellaetal.2016, author = {Bornd{\"o}rfer, Ralf and Schenker, Sebastian and Skutella, Martin and Strunk, Timo}, title = {PolySCIP}, volume = {9725}, booktitle = {Mathematical Software - ICMS 2016, 5th International Conference, Berlin, Germany, July 11-14, 2016, Proceedings}, editor = {Greuel, G.-M. and Koch, Thorsten and Paule, Peter and Sommese, Andrew}, edition = {Mathematical Software - ICMS 2016}, publisher = {Springer International Publishing}, isbn = {978-3-319-42431-6}, doi = {10.1007/978-3-319-42432-3_32}, pages = {259 -- 264}, year = {2016}, abstract = {PolySCIP is a new solver for multi-criteria integer and multi-criteria linear programs handling an arbitrary number of objectives. It is available as an official part of the non-commercial constraint integer programming framework SCIP. It utilizes a lifted weight space approach to compute the set of supported extreme non-dominated points and unbounded non-dominated rays, respectively. The algorithmic approach can be summarized as follows: At the beginning an arbitrary non-dominated point is computed (or it is determined that there is none) and a weight space polyhedron created. In every next iteration a vertex of the weight space polyhedron is selected whose entries give rise to a single-objective optimization problem via a combination of the original objectives. If the ptimization of this single-objective problem yields a new non-dominated point, the weight space polyhedron is updated. Otherwise another vertex of the weight space polyhedron is investigated. The algorithm finishes when all vertices of the weight space polyhedron have been investigated. The file format of PolySCIP is based on the widely used MPS format and allows a simple generation of multi-criteria models via an algebraic modelling language.}, language = {en} } @article{HumpolaSerrano2017, author = {Humpola, Jesco and Serrano, Felipe}, title = {Sufficient pruning conditions for MINLP in gas network design}, volume = {5}, journal = {EURO Journal on Computational Optimization}, number = {1-2}, publisher = {Springer Berlin Heidelberg}, doi = {10.1007/s13675-016-0077-8}, pages = {239 -- 261}, year = {2017}, 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 Euros per kilometer the extension of the European pipeline network is already a multi-billion Euro business. Therefore, automatic planning tools that support the decision process are desired. We model the topology optimization problem in gas networks by a mixed-integer nonlinear program (MINLP). This gives rise to a so-called active transmission problem, a continuous nonlinear non-convex feasibility problem which emerges from the MINLP model by fixing all integral variables. We offer novel sufficient conditions for proving the infeasibility of this active transmission problem. These conditions can be expressed in the form of a mixed-integer program (MILP), i.e., the infeasibility of a non-convex continuous nonlinear program (NLP) can be certified by solving an MILP. This result provides an efficient pruning procedure in a branch-and-bound algorithm. Our computational results demonstrate a substantial speedup for the necessary computations.}, language = {en} } @misc{BreuerBussieckCaoetal.2017, author = {Breuer, Thomas and Bussieck, Michael and Cao, Karl-Kien and Cebulla, Felix and Fiand, Frederik and Gils, Hans Christian and Gleixner, Ambros and Khabi, Dmitry and Koch, Thorsten and Rehfeldt, Daniel and Wetzel, Manuel}, title = {Optimizing Large-Scale Linear Energy System Problems with Block Diagonal Structure by Using Parallel Interior-Point Methods}, issn = {1438-0064}, doi = {10.1007/978-3-319-89920-6_85}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66183}, year = {2017}, abstract = {Current linear energy system models (ESM) acquiring to provide sufficient detail and reliability frequently bring along problems of both high intricacy and increasing scale. Unfortunately, the size and complexity of these problems often prove to be intractable even for commercial state-of-the-art linear programming solvers. This article describes an interdisciplinary approach to exploit the intrinsic structure of these large-scale linear problems to be able to solve them on massively parallel high-performance computers. A key aspect are extensions to the parallel interior-point solver PIPS-IPM originally developed for stochastic optimization problems. Furthermore, a newly developed GAMS interface to the solver as well as some GAMS language extensions to model block-structured problems will be described.}, language = {en} } @misc{RehfeldtKoch2018, author = {Rehfeldt, Daniel and Koch, Thorsten}, title = {SCIP-Jack—a solver for STP and variants with parallelization extensions: An update}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-66416}, year = {2018}, abstract = {The Steiner tree problem in graphs is a classical problem that commonly arises in practical applications as one of many variants. Although the different Steiner tree problem variants are usually strongly related, solution approaches employed so far have been prevalently problem-specific. Against this backdrop, the solver SCIP-Jack was created as a general-purpose framework that can be used to solve the classical Steiner tree problem and 11 of its variants. This versatility is achieved by transforming various problem variants into a general form and solving them by using a state-of-the-art MIP-framework. Furthermore, SCIP-Jack includes various newly developed algorithmic components such as preprocessing routines and heuristics. The result is a high-performance solver that can be employed in massively parallel environments and is capable of solving previously unsolved instances. After the introduction of SCIP-Jack at the 2014 DIMACS Challenge on Steiner problems, the overall performance of the solver has considerably improved. This article provides an overview on the current state.}, language = {en} } @article{BertholdHendelKoch2017, author = {Berthold, Timo and Hendel, Gregor and Koch, Thorsten}, title = {From feasibility to improvement to proof: three phases of solving mixed-integer programs}, volume = {33}, journal = {Optimization Methods and Software}, number = {3}, publisher = {Taylor \& Francis}, doi = {10.1080/10556788.2017.1392519}, pages = {499 -- 517}, year = {2017}, abstract = {Modern mixed-integer programming (MIP) solvers employ dozens of auxiliary algorithmic components to support the branch-and-bound search in finding and improving primal solutions and in strengthening the dual bound. Typically, all components are tuned to minimize the average running time to prove optimality. In this article, we take a different look at the run of a MIP solver. We argue that the solution process consists of three distinct phases, namely achieving feasibility, improving the incumbent solution, and proving optimality. We first show that the entire solving process can be improved by adapting the search strategy with respect to the phase-specific aims using different control tunings. Afterwards, we provide criteria to predict the transition between the individual phases and evaluate the performance impact of altering the algorithmic behaviour of the non-commercial MIP solver Scip at the predicted phase transition points.}, language = {en} } @article{Koch2017, author = {Koch, Thorsten}, title = {The ZIMPL modeling language}, volume = {103}, journal = {Optima}, pages = {8 -- 9}, year = {2017}, language = {en} }