A global optimization environment

The proposed project aims at the advancement of global optimization both in theoretical and in practical respects by integrating approaches from various mathematical disciplines and providing a modular platform for algorithmic studies. The public domain COCONUT global optimization package developed during the COCONUT EU-project - and now maintained at the Universität Wien - will be enhanced by newly developed and improved strategies, allowing to apply them to many different real-life problems. Moreover, it is planned to increase the speed and efficiency of the COCONUT environment by researching and implementing an automatic strategy selection feature. Global optimization is the task of finding the absolutely best set(s) of admissible conditions to achieve an objective under given constraints, assuming that both are formulated in mathematical terms. A special case is the constraint satisfaction problem, where one just wants to find one or all solutions of a given set of constraints. Both problems are much more difficult than convex programming, finding local minimizers of nonlinear programs, or solving algebraic systems of equations when a good starting point is available, and it is of comparable difficulty as solving hard constraint satisfaction problems. Many scientific and industrial applications (e. g., shape optimization in structural mechanics, robot design and analysis, analysis of phase equilibria, protein folding, traveling salesman) lead to difficult global problems in the range from fewer than ten to many thousands of variables. During the last decade, the interest in global optimization has increased substantially, partly because there are more and more applications, partly because the development of algorithms has already moved the field to the point where many small but already industrial-size applications can be solved reliably. Meeting the challenge of real applications often involves the creation and utilization of new theoretical tools that enable one to exploit the special features of the application. As in many areas with difficult computational problems, success is more often due to theoretical advances rather than to increases in raw computer power or more clever use of existing software packages. There are a number of different approaches to solving global optimization problems and related problems. Those traditional approaches are slowly growing together to a unified whole, making the solution of difficult global optimization problems tractable in dimensions relevant for real-life applications. However, this process is hampered by the fact that the approaches are substantially different and draw their strengths from mathematical traditions which have little common theoretical background (e. g. numerical analysis, convex analysis, optimization theory, combinatorics, logic, algebraic geometry). Cross-fertilization is difficult, however, due to the time needed to get acquainted with the deeper parts of the neighboring disciplines. Until today, global optimization algorithms are mainly based on a single of the possible approaches like constraint programming, interval analysis, local optimization, mixed integer linear programming, relaxations, semidefinite programming,... An important step towards the integration of some traditions was done in the COCONUT project, where six academic institutions and ILOG, the biggest company in the optimization business, joined to create a public domain software environment integrating basic theory and algorithms from the fields of constraint programming, interval analysis, and local optimization. This framework, the COCONUT environment was mainly implemented by the proposer`s research group; its strategy engine was developed at the IRIN (Institute de Recherche en Informatique de Nantes). With the present project, we hope to push the integration further, develop more theory, and include more aspects and algorithms into the solver framework initially written in the COCONUT project and now maintained and extended by the proposer`s research group.

The proposed project aims at the advancement of global optimization both in theoretical and in practical respects by integrating approaches from various mathematical disciplines and providing a modular platform for algorithmic studies. The public domain COCONUT global optimization package developed during the COCONUT EU-project - and now maintained at the Universität Wien - will be enhanced by newly developed and improved strategies, allowing to apply them to many different real-life problems. Moreover, it is planned to increase the speed and efficiency of the COCONUT environment by researching and implementing an automatic strategy selection feature. Global optimization is the task of finding the absolutely best set(s) of admissible conditions to achieve an objective under given constraints, assuming that both are formulated in mathematical terms. A special case is the constraint satisfaction problem, where one just wants to find one or all solutions of a given set of constraints. Both problems are much more difficult than convex programming, finding local minimizers of nonlinear programs, or solving algebraic systems of equations when a good starting point is available, and it is of comparable difficulty as solving hard constraint satisfaction problems. Many scientific and industrial applications (e. g., shape optimization in structural mechanics, robot design and analysis, analysis of phase equilibria, protein folding, traveling salesman) lead to difficult global problems in the range from fewer than ten to many thousands of variables. During the last decade, the interest in global optimization has increased substantially, partly because there are more and more applications, partly because the development of algorithms has already moved the field to the point where many small but already industrial-size applications can be solved reliably. Meeting the challenge of real applications often involves the creation and utilization of new theoretical tools that enable one to exploit the special features of the application. As in many areas with difficult computational problems, success is more often due to theoretical advances rather than to increases in raw computer power or more clever use of existing software packages. There are a number of different approaches to solving global optimization problems and related problems. Those traditional approaches are slowly growing together to a unified whole, making the solution of difficult global optimization problems tractable in dimensions relevant for real-life applications. However, this process is hampered by the fact that the approaches are substantially different and draw their strengths from mathematical traditions which have little common theoretical background (e. g. numerical analysis, convex analysis, optimization theory, combinatorics, logic, algebraic geometry). Cross-fertilization is difficult, however, due to the time needed to get acquainted with the deeper parts of the neighboring disciplines. Until today, global optimization algorithms are mainly based on a single of the possible approaches like constraint programming, interval analysis, local optimization, mixed integer linear programming, relaxations, semidefinite programming,... An important step towards the integration of some traditions was done in the COCONUT project, where six academic institutions and ILOG, the biggest company in the optimization business, joined to create a public domain software environment integrating basic theory and algorithms from the fields of constraint programming, interval analysis, and local optimization. This framework, the COCONUT environment was mainly implemented by the proposer`s research group; its strategy engine was developed at the IRIN (Institute de Recherche en Informatique de Nantes). With the present project, we hope to push the integration further, develop more theory, and include more aspects and algorithms into the solver framework initially written in the COCONUT project and now maintained and extended by the proposer`s research group.