vOPT: Exact Efficient Solution of Mixed Integer Programming Problems with Multiple Objective Functions
The Franco-German research project vOPT is funded by the DFG and the ANR from 01st November 2014 to 31st December 2018.
Mathematical modelling and optimization is a key skill in a wide range of future-oriented disciplines like computational engineering or applied natural sciences. Due to the complexity of real-world problems in these areas, building practical models is a challenging task and often requires that several objectives are optimized simultaneously. Usually, there is not one solution that optimizes all objectives at once but many solutions may be an adequate outcome of the model. Solving these models is the main task of multiple objective mixed integer programming (MOMIP). Despite the practical importance, research in this area is still in its infancy.
In this Franco-German project, partners of computer science and mathematics work together to advance research in the field of MOMIP in both theoretical and practical areas. This includes the analysation of the structure of problems with multiple objectives as well as developing algorithms that solve these problems. Further, these new advances as well as existing results and algorithms will be utilized to develop a toolbox of algorithms, named vOPT, which allows the fast and correct solving of MOMIP problems. This toolbox will be available for the academic public which in turn may also contribute.
The results of the vOPT research group will address different subfields of MOMIP and can be a divided in a theoretical and a practical area. In the former one, the analysation of solution strategies and the structure of the problem is of main interest. This includes the analysis and development of scalarization techniques. Also, methods that are known in optimization but have not been used in the field of MOMIP will be taken under consideration such as relaxation. Additionally, the structure of MOMIP problems will be investigated in terms of polyhedral theory. Based on these theoretical findings, exact and efficient algorithms may be deduced and implemented. These algorithms address both general MOMIP problems as well as specific problems, for example facility location. A special focus will be on Branch and Cut or Branch and Bound algorithms. The new algorithms and existing ones will be made available in the form of the vOPT toolbox together with other features such as an instance library or a visualization toolkit. The vOPT toolbox will be an open source and contributable tool and therefore needs the appropriate architecture as well as performance testing and benchmarking. With the end of the project a ready to use prototype will be published.