一类极大加和逆优化问题的研究

项目名称： 一类极大加和逆优化问题的研究

项目编号： No.11471073

项目类型： 面上项目

立项/批准年度： 2015

项目学科： 数理科学和化学

项目作者： 关秀翠

作者单位： 东南大学

项目金额： 68万元

中文摘要： 本项目提出一类新的逆优化问题- - 极大加和逆优化问题：通过调整sum-权向量或max-权向量，使得某个给定可行解成为新权值下的极大加和优化问题的最优解，目标是使得调整量在某种模意义下尽可能小。本项目首先从研究三个具体问题- - 极大加和逆支撑树问题、极大加和逆最短路问题和极大加和逆线性规划问题入手，再延伸到研究一般的极大加和逆优化问题，旨在找出这类问题的结构特点和算法共性，并设计通用算法。针对具体问题，根据组合结构特点和度量模特性，分析不同模下的时间复杂性，设计相应的多项式时间算法或近似算法，分析近似算法的近似比，进行数值试验验证算法性能。该研究问题比单目标逆优化问题更具挑战性，需要设计新方法。本项目开创了研究双准则逆优化问题的先河，对多目标逆优化问题的研究有重要推动作用。因此,本项目的研究将深化组合优化逆问题的理论，同时这种逆优化思想的延伸及与应用领域的交叉融合将有助于产生新的优化问题。

中文关键词： 组合优化；算法设计与分析；网络优化；计算复杂性；近似算法

英文摘要： A new class of inverse optimization problems is proposed.In the inverse max+sum optimization problems, the sum-weight vector or max-weight vector is modified to make a given feasible solution optimal in the max+sum optimization problem with the new weight vector. The objective is to minimize the modification of vector under some norm. We first consider three concrete problems including the inverse max+sum spanning tree problems, the inverse max+sum shortest path problems and the inverse max+sum linear programming problems. Then consider the general inverse max+sum optimization problems. We aim to devise a general algorithm for this class of problems based on their structure characteristic and common properties of algorithms. For these three concrete problems, we first analyze time complexities and devise the corresponding algorithms based on the properties of combinatorial structures and different norms; then analyze approximation ratios and verify algorithm performance by numerical experiments.This class of problems is more challenging than the inverse single-objective optimization problems. And we need to devise new algorithms to solve them. As far as we know, this project is the first one on the inverse bicriteria optimization problems, which will promote the development of inverse multi-criteria optimization problems.Therefore, this project will strengthen the theories on inverse combinatorial optimization problems. Meanwhile, extension of ideas in inverse optimization problems and integration of cross-curricular interests in application fields will help produce new optimization problems.

英文关键词： Combinatorial Optimization;Algorithm design and analasys;network optimization;computation complexity;approximation algorithm