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

多目标函数混合整数规划问题的精确高效解

• 批准号: 258775501
• 负责人: Professor Dr. Stefan Ruzika
• 金额: --
• 依托单位: LINA - Laboratoire dInformatique de Nantes Atlantique
• 依托单位国家: 德国
• 项目类别: Research Grants
• 财政年份: 2014
• 资助国家: 德国
• 起止时间: 2013-12-31 至 2019-12-31
• 项目状态: 已结题
• 来源: https://gepris.dfg.de/gepris/projekt/258775501?language=en
• 关键词: Exact; Efficient; Solution; Mixed; Integer

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.

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

项目成果

On branching heuristics for the bi-objective 0/1 unidimensional knapsack problem

双目标0/1一维背包问题的分支启发法

• DOI: 10.1007/s10732-017-9346-9
• 发表时间: 2017
• 期刊: Journal of Heuristics
• 影响因子: 2.7
• 作者: Audrey Cerqueus;Xavier Gandibleux;Anthony Przybylski;Frédéric Saubion
• 通讯作者: Frédéric Saubion

Multiobjective optimization for interwoven systems

• DOI: 10.1002/mcda.1598
• 发表时间: 2017
• 期刊: Journal of Multi-criteria Decision Analysis
• 影响因子: 2
• 作者: K. Klamroth;Sanaz Mostaghim;B. Naujoks;S. Poles;R. Purshouse;G. Rudolph;Stefan Ruzika;Serpil Sayın;M. Wiecek;Xin Yao

A General Approximation Method for Bicriteria Minimization Problems

双准则最小化问题的通用逼近方法

• DOI: 10.1016/j.tcs.2017.07.003
• 发表时间: 2017
• 期刊: ArXiv
• 作者: Pascal Halffmann;Stefan Ruzika;Clemens Thielen;David Willems
• 通讯作者: David Willems

Easy to say they are Hard, but Hard to see they are Easy— Towards a Categorization of Tractable Multiobjective Combinatorial Optimization Problems

说它们很困难很容易，但很难看出它们很简单â 可处理的多目标组合优化问题的分类

• DOI: 10.1002/mcda.1574
• 发表时间: 2017
• 期刊: Journal of Multi-criteria Decision Analysis
• 影响因子: 2
• 作者: José Rui Figueira;Carlos M. Fonseca;Pascal Halffmann;Kathrin Klamroth;Luís Paquete;Stefan Ruzika;Britta Schulze;Michael Stiglmayr;David Willems
• 通讯作者: David Willems

Introducing multiobjective complex systems

• DOI: 10.1016/j.ejor.2019.07.027
• 发表时间: 2020-01-16
• 期刊: EUROPEAN JOURNAL OF OPERATIONAL RESEARCH
• 影响因子: 6.4
• 作者: Dietz, Tobias;Klamroth, Kathrin;Wiecek, Margaret M.
• 通讯作者: Wiecek, Margaret M.