HPC User Report from R. Burlacu (Economics, Discrete Optimization, and Mathematics)

Solving MINLPs using Adaptively Refined MIPS

We propose a method for solving MINLPs to global optimality by discretization of the nonlinearities. The main idea is based on using piecewise linear functions to construct MIP relaxations of the underlying MINLP. We show numerical results in the context of of gas network optimization.

Motivation and problem definition

Many real-world optimization problems can be modeled as an MINLP while both physically and combinatorial aspects are incorporated. Tackling these MINLPs, however, is in general a big challenge. Not only is it hard to find an optimal solution to the problem but also a solution at all. We focus on utilizing fast and robust MIP technology in order to solve these MINLP. Therefore, we develop a framework to solve MINLPs in which any MIP solver can be embedded in a black box fashion.

Methods and codes

We adaptively construct (easier to solve) MIP relaxations of the MINLP by piecewise linear approximations and solve these to global optimality. We procede until the optimal solution of the MIP is an optimal solution of the MINLP within an a priori given tolerance. Moreover, whenever a feasible solution of an MIP relaxation is found, we fix all discrete variables of the underlying MINLP problem according to the MIP solution obtaining an NLP problem, which we solve to local optimality. In this way, we are often able to find feasible solutions for the MINLP very rapidly. Our method is implemented within the C++ software framework LaMaTTO++ [1]. Furthermore, we use CONOPT3 as local NLP solver within GAMS [2].

Results

We obtain promising computational results for compressor energy minimization problems based on the GasLib-582 [3] gas network. We model 200 of these problems as MINLPs and compare our results with state-of-the-art solvers like Baron and SCIP (within GAMS). In most cases the relative optimality gaps obtained by our approach are smaller than 0.10 and differ from the relative gaps computed by Baron and SCIP by a magnitude of almost 10. Moreover, we obtain near-optimal solutions for instationary gas network optimization problems based on the GasLib-11 gas network.

Outreach

The results are part of the preprints [4] and [5] that are funded by the Sonderforschungsbereich/Transregio 154 “Mathematical Modelling, Simulation and Optimization using the Example of Gas Networks”.

References

  1. LaMaTTO++, A Framework for Modeling and Solving Mixed-Integer Nonlinear Programming Problems on Networks (2015). Available at http://www.mso.math.fau.de/edom/projects/lamatto.html.
  2. G.D. Corporation, General Algebraic Modeling System (GAMS) Release 24.8.3, Washington, DC, USA (2017). Available at http://www.gams.com/.
  3. M. Schmidt, D. Aßmann, R. Burlacu, J. Humpola, I. Joormann, N. Kanelakis, T. Koch, D. Oucherif, M.E. Pfetsch, L. Schewe, R. Schwarz, and M. Sirvent, GasLib—A library of Gas Network Instances, Data 2 (2017).
  4. R. Burlacu, H. Egger, M. Groß, A. Martin, M. E. Pfetsch, L. Schewe, M. Sirvent, and M. Skutella. A Global Optimization Approach for Instationary Gas Transport in Pipeline Networks. Preprint, TRR 154, 2017. https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/221.
  5. R. Burlacu, B. Geißler, and L. Schewe. Solving Mixed-Integer Nonlinear Programs using Adaptively Refined Mixed-Integer Linear Programs. Preprint, TRR 154, 2017. https://opus4.kobv.de/opus4-trr154/frontdoor/index/index/docId/151.

Researcher’s Bio and Affiliation

Robert Burlacu studied Mathematics at the Friedrich-Alexander-Universität Erlangen-Nürnberg and received his diploma in 2013. Currently, he is a PhD student in the group of Prof. Dr. Alexander Martin in the field of discrete optimization.