广义组合优化逆问题的算法设计与分析

在近十几年来，组合优化逆问题得到国内外广大专家学者的关注，成为运筹学研究的一个重要领域，它不仅具有丰富的理论意义，而且同时具有较大的实际意义和应用价值. 组合优化问题是在给定参数的情况下寻找最优解，而实际当中，往往先有一个问题的可行解，在当前的参数下，它并不是一个最优解，从而要求我们尽可能少的修改现有的参数，使得已有的可行解成为一个最优解，这就是组合优化逆问题. 本项目将着重研究三类广义层面上的组合优化逆问题：给出部分解的组合优化逆问题；不同范数相结合的组合优化逆问题；广义网络上的组合优化逆问题. 对于以上这些问题，我们将探讨它们的计算复杂性、多项式时间算法、快速近似算法或难近似性. 通过本项目的研究，在理论上进一步丰富和完善组合优化的算法设计与分析的技巧，在实际中进一步拓展组合优化理论的应用领域，可为实际中的城市规划、网络建设等提供理论依据和技术支持.

在近十几年来，组合优化逆问题得到国内外广大专家学者的关注，成为运筹学研究的一个重要领域，它不仅具有丰富的理论意义，而且同时具有较大的实际意义和应用价值. 组合优化问题是在给定参数的情况下寻找最优解，而实际当中，往往先有一个问题的可行解，在当前的参数下，它并不是一个最优解，从而要求我们尽可能少的修改现有的参数，使得已有的可行解成为一个最优解，这就是组合优化逆问题. 本项目将着重研究三类广义层面上的组合优化逆问题：给出部分解的组合优化逆问题；不同范数相结合的组合优化逆问题；广义网络上的组合优化逆问题. 对于以上这些问题，我们将探讨它们的计算复杂性、多项式时间算法、快速近似算法或难近似性. 通过本项目的研究，在理论上进一步丰富和完善组合优化的算法设计与分析的技巧，在实际中进一步拓展组合优化理论的应用领域，可为实际中的城市规划、网络建设等提供理论依据和技术支持。经过三年的研究，到目前为止已经在发表6篇学术论文，还有多篇在审稿中，在项目研究进行中，协助培养了博士一名（已毕业），硕士两名（已毕业），正在培养的硕士三名。