Developing a rigorous global optimization solver for MINLPs

The target of this project is the research of special optimization methods and the development of an optimization software. We optimize problems that model nonlinear relations between the decision variables; such nonlinear problems occur in many areas of science, engineering, economics, etc. Furthermore, we are dealing with problems for which some variables can attain any values in a given range (called continuous variables), while some others are allowed to have only integer values. The latter type of variables occur very frequently in applications, e.g., when one wants to model quantities that can have integer values only, to represent yes/no decisions (with, e.g., variables that can be either one or zero), or to model various assignments. Our optimization methods aim at finding those values of the decision variables that result in the absolutely best, globally optimal solution of the problem. Furthermore, we design computer algorithms that can cope with the phenomenon that not all numbers can be exactly represented on a computer, thus, the results of ordinary computer calculations may contain numerical errors. With our methods, the solutions are computed in the forms of intervals that always contain the mathematically exact result. During the last decade, we have been working on an optimization framework called the `COCONUT Environment`, that already contains many methods for calculating with intervals, and plenty of tools that support the development of optimization software using this methodology. With these tools we have recently created a software, called coco_gop_ex, that was found to be competitive with the best available solvers on more simple types of problems. The main goal of the project is to research and implement new methods with which coco_gop_ex can be further developed, in order to solve the above mentioned nonlinear problems with continuous and integer variables. To the best of our knowledge, this software would be the first that is able to solve such problems to global optimality and with mathematical exactness. Additionally, we plan to work on the further improvement of the backbone of the COCONUT Environment, so that others can use our interval methods for the development of their own software. We also hope that we can attract scientists from other fields who find our methods and software useful for solving their special applications.

Developing a rigorous global optimization solver for mixed integer nonlinear programming Dr. Mihly Csaba Markt, University of Vienna The project aimed at the development of novel methods for solving nonlinear and mixed integer nonlinear programming problems. We targeted problems where a so-called complete global search was necessary. Such methods are to find all global optimizers of a problem and to prove that they are indeed global, or to verify an optimization-related mathematical statement on a computer. We also developed new computer algorithms that will be part of general purpose solvers. We delivered new interval algorithms for 'generalized disjunctive programming' (GDP), that is an alternative formulation for many mixed-integer nonlinear programming problems. We addressed this by introducing interval extensions for logical operators. We derived functions for the interval evaluation of disjunctions, conjunctions, exclusive disjunctions, negation, and conditionals. The new operators extend the capabilities of rigorous global optimization solvers. Based on these results, we also proposed a specialized procedure for solving GDPs with mathematical rigor. We illustrated the capabilities of the new approach by solving small-sized examples from the literature. In another study we developed methods for computer-assisted proofs for finding optimal arrangements of points on the sphere. In this research a new interval representation of the subsets of the search space was introduced. The power of the new methodology was demonstrated by solving the famous 3-dimensional kissing number problem (also known as the 13 spheres problem) on a computer. A further important part of the research was about 'process network synthesis' (PNS). This is the research field of designing a system that produces a given set and amount of products from a given set and amount of raw materials, by applying a network of various operation units. The goal is to find that of the network structure, as well as the parameters of the involved operation units, that is optimal with respect to some cost function. In the project the design problem of a 'wastewater treatment network' was considered. In a collaborative work with chemical engineers, our task was to propose suitable modeling and optimization methods that cope with the model nonlinearities and various other computational difficulties.