@unpublished{GruebelKrugSchmidtetal.2022, author = {Gr{\"u}bel, Julia and Krug, Richard and Schmidt, Martin and Wollner, Winnifried}, title = {A Successive Linear Relaxation Method for MINLPs with Multivariate Lipschitz Continuous Nonlinearities}, pages = {34}, year = {2022}, abstract = {We present a novel method for mixed-integer optimization problems with multivariate and Lipschitz continuous nonlinearities. In particular, we do not assume that the nonlinear constraints are explicitly given but that we can only evaluate them and that we know their global Lipschitz constants. The algorithm is a successive linear relaxation method in which we alternate between solving a master problem, which is a mixed-integer linear relaxation of the original problem, and a subproblem, which is designed to tighten the linear relaxation of the next master problem by using the Lipschitz information about the respective functions. By doing so, we follow the ideas of Schmidt et al. (2018, 2021) and improve the tackling of multivariate constraints. Although multivariate nonlinearities obviously increase modeling capabilities, their incorporation also significantly increases the computational burden of the proposed algorithm. We prove the correctness of our method and also derive a worst-case iteration bound. Finally, we show the generality of the addressed problem class and the proposed method by illustrating that both bilevel optimization problems with nonconvex and quadratic lower levels as well as nonlinear and mixed-integer models of gas transport can be tackled by our method. We provide the necessary theory for both applications and briefly illustrate the outcomes of the new method when applied to these two problems.}, language = {en} } @article{SchmidtAssmannBurlacuetal.2017, author = {Schmidt, Martin and Aßmann, Denis and Burlacu, Robert and Humpola, Jesco and Joormann, Imke and Kanelakis, Nikolaos and Koch, Thorsten and Oucherif, Djamal and Pfetsch, Marc E. and Schewe, Lars and Schwarz, Robert and Sirvent, Mathias}, title = {GasLib - A Library of Gas Network Instances}, series = {Data}, volume = {4}, journal = {Data}, number = {2}, doi = {10.3390/data2040040}, pages = {18}, year = {2017}, abstract = {The development of mathematical simulation and optimization models and algorithms for solving gas transport problems is an active field of research. In order to test and compare these models and algorithms, gas network instances together with demand data are needed. The goal of GasLib is to provide a set of publicly available gas network instances that can be used by researchers in the field of gas transport. The advantages are that researchers save time by using these instances and that different models and algorithms can be compared on the same specified test sets. The library instances are encoded in an XML format. In this paper, we explain this format and present the instances that are available in the library.}, language = {en} } @article{GrimmKleinertLiersetal.2017, author = {Grimm, Veronika and Kleinert, Thomas and Liers, Frauke and Schmidt, Martin and Z{\"o}ttl, Gregor}, title = {Optimal Price Zones of Electricity Markets: A Mixed-Integer Multilevel Model and Global Solution Approaches}, series = {Optimization Methods and Software}, journal = {Optimization Methods and Software}, number = {34(2)}, pages = {406 -- 436}, year = {2017}, abstract = {Mathematical modeling of market design issues in liberalized electricity markets often leads to mixed-integer nonlinear multilevel optimization problems for which no general-purpose solvers exist and which are intractable in general. In this work, we consider the problem of splitting a market area into a given number of price zones such that the resulting market design yields welfare-optimal outcomes. This problem leads to a challenging multilevel model that contains a graph-partitioning problem with multi-commodity flow connectivity constraints and nonlinearities due to proper economic modeling. Furthermore, it has highly symmetric solutions. We develop different problem-tailored solution approaches. In particular, we present an extended KKT transformation approach as well as a generalized Benders approach that both yield globally optimal solutions. These methods, enhanced with techniques such as symmetry breaking and primal heuristics, are evaluated in detail on academic as well as on realistic instances. It turns out that our approaches lead to effective solution methods for the difficult optimization tasks presented here, where the problem-specific generalized Benders approach performs considerably better than the methods based on KKT transformation.}, language = {en} } @article{ScheweSchmidt2016, author = {Schewe, Lars and Schmidt, Martin}, title = {Computing Feasible Points for Binary MINLPs with MPECs}, series = {Mathematical Programming Computation}, journal = {Mathematical Programming Computation}, number = {11(1)}, pages = {95 -- 118}, year = {2016}, abstract = {Nonconvex mixed-binary nonlinear optimization problems frequently appear in practice and are typically extremely hard to solve. In this paper we discuss a class of primal heuristics that are based on a reformulation of the problem as a mathematical program with equilibrium constraints. We then use different regularization schemes for this class of problems and use an iterative solution procedure for solving series of regularized problems. In the case of success, these procedures result in a feasible solution of the original mixed-binary nonlinear problem. Since we rely on local nonlinear programming solvers the resulting method is fast and we further improve its reliability by additional algorithmic techniques. We show the strength of our method by an extensive computational study on 662 MINLPLib2 instances, where our methods are able to produce feasible solutions for 60\% of all instances in at most 10s.}, language = {en} }