@inproceedings{FuegenschuhHomfeldSchuelldorfetal.2010, author = {F{\"u}genschuh, Armin and Homfeld, Henning and Sch{\"u}lldorf, Hanno and Vigerske, Stefan}, title = {Mixed-Integer Nonlinear Problems in Transportation Applications}, series = {Proceedings of the 2nd International Conference on Engineering Optimization (+CD-rom)}, booktitle = {Proceedings of the 2nd International Conference on Engineering Optimization (+CD-rom)}, editor = {Rodrigues, H.}, year = {2010}, language = {en} } @misc{GleixnerHeldHuangetal., author = {Gleixner, Ambros and Held, Harald and Huang, Wei and Vigerske, Stefan}, title = {Towards globally optimal operation of water supply networks}, issn = {1438-0064}, doi = {10.3934/naco.2012.2.695}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-15603}, abstract = {This paper is concerned with optimal operation of pressurized water supply networks at a fixed point in time. We use a mixed-integer nonlinear programming (MINLP) model incorporating both the nonlinear physical laws and the discrete decisions such as switching pumps on and off. We demonstrate that for instances from our industry partner, these stationary models can be solved to ε-global optimality within small running times using problem-specific presolving and state-of-the-art MINLP algorithms. In our modeling, we emphasize the importance of distinguishing between what we call real and imaginary flow, i.e., taking into account that the law of Darcy-Weisbach correlates pressure difference and flow along a pipe if and only if water is available at the high pressure end of a pipe. Our modeling solution extends to the dynamic operative planning problem.}, language = {en} } @misc{VigerskeGleixner, author = {Vigerske, Stefan and Gleixner, Ambros}, title = {SCIP: Global Optimization of Mixed-Integer Nonlinear Programs in a Branch-and-Cut Framework}, issn = {1438-0064}, doi = {10.1080/10556788.2017.1335312}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-59377}, abstract = {This paper describes the extensions that were added to the constraint integer programming framework SCIP in order to enable it to solve convex and nonconvex mixed-integer nonlinear programs (MINLPs) to global optimality. SCIP implements a spatial branch-and-bound algorithm based on a linear outer-approximation, which is computed by convex over- and underestimation of nonconvex functions. An expression graph representation of nonlinear constraints allows for bound tightening, structure analysis, and reformulation. Primal heuristics are employed throughout the solving process to find feasible solutions early. We provide insights into the performance impact of individual MINLP solver components via a detailed computational study over a large and heterogeneous test set.}, language = {en} } @article{BernalVigerskeTrespalaciosetal., author = {Bernal, David E. and Vigerske, Stefan and Trespalacios, Francisco and Grossmann, Ignacio E.}, title = {Improving the performance of DICOPT in convex MINLP problems using a feasibility pump}, series = {Optimization Methods and Software}, journal = {Optimization Methods and Software}, abstract = {The solver DICOPT is based on an outer-approximation algorithm used for solving mixed- integer nonlinear programming (MINLP) problems. This algorithm is very effective for solving some types of convex MINLPs. However, there are certain problems that are diffcult to solve with this algorithm. One of these problems is when the nonlinear constraints are so restrictive that the nonlinear subproblems produced by the algorithm are infeasible. This problem is addressed in this paper with a feasibility pump algorithm, which modifies the objective function in order to efficiently find feasible solutions. It has been implemented as a preprocessing algorithm for DICOPT. Computational comparisons with previous versions of DICOPT and other MINLP solvers on a set of convex MINLPs demonstrate the effectiveness of the proposed algorithm in terms of solution quality and solving time.}, language = {en} } @article{FuriniTraversiBelottietal., author = {Furini, Fabio and Traversi, Emiliano and Belotti, Pietro and Frangioni, Antonio and Gleixner, Ambros and Gould, Nick and Liberti, Leo and Lodi, Andrea and Misener, Ruth and Mittelmann, Hans and Sahinidis, Nikolaos V. and Vigerske, Stefan and Wiegele, Angelika}, title = {QPLIB: A Library of Quadratic Programming Instances}, series = {Mathematical Programming Computation}, volume = {11}, journal = {Mathematical Programming Computation}, number = {2}, doi = {10.1007/s12532-018-0147-4}, pages = {237 -- 265}, abstract = {This paper describes a new instance library for Quadratic Programming (QP), i.e., the family of continuous and (mixed)-integer optimization problems where the objective function, the constrains, or both are quadratic. QP is a very diverse class of problems, comprising sub-classes of problems ranging from trivial to undecidable. This diversity is reflected in the variety of solution methods for QP, ranging from entirely combinatorial ones to completely continuous ones, including many for which both aspects are fundamental. Selecting a set of instances of QP that is at the same time not overwhelmingly onerous but sufficiently challenging for the many different interested communities is therefore important. We propose a simple taxonomy for QP instances that leads to a systematic problem selection mechanism. We then briefly survey the field of QP, giving an overview of theory, methods and solvers. Finally, we describe how the library was put together, and detail its final contents.}, language = {en} } @misc{PfetschFuegenschuhGeissleretal., author = {Pfetsch, Marc and F{\"u}genschuh, Armin and Geißler, Bj{\"o}rn and Geißler, Nina and Gollmer, Ralf and Hiller, Benjamin and Humpola, Jesco and Koch, Thorsten and Lehmann, Thomas and Martin, Alexander and Morsi, Antonio and R{\"o}vekamp, Jessica and Schewe, Lars and Schmidt, Martin and Schultz, R{\"u}diger and Schwarz, Robert and Schweiger, Jonas and Stangl, Claudia and Steinbach, Marc and Vigerske, Stefan and Willert, Bernhard}, title = {Validation of Nominations in Gas Network Optimization: Models, Methods, and Solutions}, issn = {1438-0064}, doi = {10.1080/10556788.2014.888426}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-16531}, abstract = {In this article we investigate methods to solve a fundamental task in gas transportation, namely the validation of nomination problem: Given a gas transmission network consisting of passive pipelines and active, controllable elements and given an amount of gas at every entry and exit point of the network, find operational settings for all active elements such that there exists a network state meeting all physical, technical, and legal constraints. We describe a two-stage approach to solve the resulting complex and numerically difficult mixed-integer non-convex nonlinear feasibility problem. The first phase consists of four distinct algorithms facilitating mixed-integer linear, mixed-integer nonlinear, reduced nonlinear, and complementarity constrained methods to compute possible settings for the discrete decisions. The second phase employs a precise continuous nonlinear programming model of the gas network. Using this setup, we are able to compute high quality solutions to real-world industrial instances whose size is significantly larger than networks that have appeared in the literature previously.}, language = {en} } @misc{BestuzhevaGleixnerVigerske, author = {Bestuzheva, Ksenia and Gleixner, Ambros and Vigerske, Stefan}, title = {A Computational Study of Perspective Cuts}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-81821}, abstract = {The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time.}, language = {en} } @misc{BallersteinMichaelsVigerske, author = {Ballerstein, Martin and Michaels, Dennis and Vigerske, Stefan}, title = {Linear Underestimators for bivariate functions with a fixed convexity behavior}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-17641}, abstract = {This is a technical report for the SCIP constraint handler cons_bivariate. We describe a cut-generation algorithm for a class of bivariate twice continuously differentiable functions with fixed convexity behavior over a box. Computational results comparing our cut-generation algorithms with state-of-the-art global optimization software on a series of randomly generated test instances are reported and discussed.}, language = {en} } @misc{BestuzhevaChmielaMuelleretal., author = {Bestuzheva, Ksenia and Chmiela, Antonia and M{\"u}ller, Benjamin and Serrano, Felipe and Vigerske, Stefan and Wegscheider, Fabian}, title = {Global Optimization of Mixed-Integer Nonlinear Programs with SCIP 8.0}, issn = {1438-0064}, url = {http://nbn-resolving.de/urn:nbn:de:0297-zib-89348}, abstract = {For over ten years, the constraint integer programming framework SCIP has been extended by capabilities for the solution of convex and nonconvex mixed-integer nonlinear programs (MINLPs). With the recently published version~8.0, these capabilities have been largely reworked and extended. This paper discusses the motivations for recent changes and provides an overview of features that are particular to MINLP solving in SCIP. Further, difficulties in benchmarking global MINLP solvers are discussed and a comparison with several state-of-the-art global MINLP solvers is provided.}, language = {en} } @article{BestuzhevaGleixnerVigerske, author = {Bestuzheva, Ksenia and Gleixner, Ambros and Vigerske, Stefan}, title = {A Computational Study of Perspective Cuts}, series = {Mathematical Programming Computation}, volume = {15}, journal = {Mathematical Programming Computation}, doi = {10.1007/s12532-023-00246-4}, pages = {703 -- 731}, abstract = {The benefits of cutting planes based on the perspective function are well known for many specific classes of mixed-integer nonlinear programs with on/off structures. However, we are not aware of any empirical studies that evaluate their applicability and computational impact over large, heterogeneous test sets in general-purpose solvers. This paper provides a detailed computational study of perspective cuts within a linear programming based branch-and-cut solver for general mixed-integer nonlinear programs. Within this study, we extend the applicability of perspective cuts from convex to nonconvex nonlinearities. This generalization is achieved by applying a perspective strengthening to valid linear inequalities which separate solutions of linear relaxations. The resulting method can be applied to any constraint where all variables appearing in nonlinear terms are semi-continuous and depend on at least one common indicator variable. Our computational experiments show that adding perspective cuts for convex constraints yields a consistent improvement of performance, and adding perspective cuts for nonconvex constraints reduces branch-and-bound tree sizes and strengthens the root node relaxation, but has no significant impact on the overall mean time.}, language = {en} }