Exact Efficient Solution of Mixed Integer Programming Problems with Multiple Objective Functions

数学建模和优化是一项关键技能，在广泛的面向未来的学科，如计算工程或应用自然科学。为了满足这些领域中典型的复杂问题所涉及的需求，适当的建模应该反映出几个不可通约的目标的一致性。因此，我们不能指望一个单一的解决方案同时优化所有目标。相反，在这种多目标设置中，一组所谓的帕累托解被证明是最优的。此外，从结构的角度来看，许多模型必须包含变量的混合，即一些变量被限制为整数，因为它们代表不可分的量，而另一些则不是。关于这一问题的模型和理论的最终实体构成了多目标混合整数规划领域。尽管具有实际意义，但这一领域的研究仍处于起步阶段。考虑到在不那么复杂但相关的数学领域完成一些初步工作的必要性，以及最近适用于解决大型优化问题实例的负担得起的强大计算机的普及，这一观察结果并不像看起来那么令人惊讶。简而言之，本建议的中心思想是开发一种严格的方法，从整体上处理多目标混合整数规划。这项任务包括：a)对发生的结构进行数学分析；b)结合理论发现和快速算法方面的专用计算技能；c)有效地实施这些算法并向学术界传播。为此，一个由法国计算机科学家和德国数学家组成的团队联合起来，将他们的互补技能结合起来。虽然双方在多目标规划方面都有很强的背景，但德国团队在离散优化和多面体理论方面贡献了独特的知识，而法国合作伙伴则负责开发依赖于问题的高效算法和数值求解器的设计。作为这种合作的一个切实的结果，一个名为vOpt的算法工具箱将被创建、实现并提供给学术公众，它允许快速和正确地解决多目标混合整数规划问题。据我们所知，目前还没有其他研究项目致力于这些问题。由于多目标混合整数规划的跨学科相关性，这一两国倡议有望加速可持续和长期需要的发展，最终对实际问题具有重要意义。由于本课题在多目标规划领域的中心地位，以及对结果和软件采用的传播原则，该项目将在科学界产生很高的影响。

Mathematical modeling and optimization is a key skill in a wide range of future-oriented disciplines like computational engineering or applied natural sciences. Meeting the demands implicated by the typically complex problems in these fields, appropriate modeling should reflect adherence of several incommensurable objectives. As a consequence, one cannot hope for a single solution optimizing all objectives simultaneously. Instead, a set of so-called Pareto solutions turns out to be optimal in this multi-objective setting. Moreover, from a structural point of view, many models have to incorporate a mixture of variables, i. e. some variables are restricted to integral numbers since they represent indivisible quantities while others are not. The resulting entity of models and theories concerning this matter constitutes the field of multiple objective mixed integer programming. Despite the practical importance, research in this area is still in its infancy. This observation is not as surprising as it seems considering the necessity of accomplishing some preliminary work in less complex but related mathematical fields as well as the recent spread of affordable powerful computers suitable for solving large instances of optimization problems. In short, the central idea of this proposal is to develop a rigorous methodology treating multiple objective mixed integer programming holistically. This task comprises: a) mathematical analysis of the occurring structures, b) coalescence of the theoretical findings and dedicated computational skills in terms of fast algorithms, c) efficient implementation of these algorithms and the dissemination to the academic community. To this end, a team consisting of French computer scientists and German mathematicians join forces and combine their complementary skills. While both partners have a strong background in multiple objective programming, the German group contributes with a distinctive knowledge in discrete optimization and polyhedral theory while the French partner accounts for the development of problem-dependent, highly efficient algorithms and design of numerical solvers. As a tangible result of this cooperation, a toolbox of algorithms named vOpt, which allows the fast and correct solution of multiple objective mixed integer programming problems, will be created, implemented, and provided to the academic public. According to our knowledge, no other research project is currently devoted to these questions. Due to the cross-disciplinary relevance of multiple objective mixed integer programming, this bi-national initiative is expected to expedite a sustainable and long-needed development with an eventually significant meaning for practical problems. Due to the central position of this topic in the field of multiple objective programming, and the principle of dissemination adopted for the results and the software, the project will enjoy a high impact on the scientific community.