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

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.

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

本项目以极大加和支撑树的逆问题的研究为切入点，开展了对于双准则优化逆问题的研究。完成了在调整“和”权值向量时分别基于赋权l 模、l1 模和哈明距离下的逆问题，以及在调整“极大”权值向量时基于赋权l 模的逆问题的研究。证明了单位和型哈明距离下的逆问题是NP-困难的，分析了其不可近似性，其他情况下的逆问题都得到了多项式时间的算法。接着，研究了和型哈明距离下的最短路的改进问题和阻塞问题，分别从改进和阻塞两个截然相反的角度研究网络的可塑性和脆弱性；分析了有根树上改进问题的时间复杂性，设计了一般图上的启发式算法和有根树上的动态规划算法；针对更新关键边的树上最短路阻塞问题，从极大化最短路长和最短路之和两个不同角度衡量树上的最短路，证明了一般哈明距离下问题的NP-难性，分别给出了单位哈明距离下的动态规划方法和贪心算法。再次，提出了以剩余图的连通指数与度为优化目标的关键节点问题，设计了其在树上的多项式时间的动态规划算法和一般图上的贪心算法；并且增加了以剩余图的分支数和最大分支基数有界的两个约束条件，设计了树上的多项式时间的动态规划算法。这种关于删除关键点后剩余网络的分裂程度的刻画，能更加均衡地反映其分裂程度。最后，研究了一般线性规划的有界逆问题和约束逆问题，这是研究极大加和线性规划逆问题的前提基础。运用对偶理论和互补松弛性条件将逆问题进行转化，提出求解该问题的一般方法；在某些特殊情况下，给出了有界逆问题的最优解的具体形式；将上述方法和结果推广到指派问题的有界逆问题上。同时，将添加瓶颈哈明距离和无穷摸的约束逆问题分别转化为线性规划的限制逆问题和有界逆问题。.本项目共完成和发表论文12 篇，其中5 篇发表在优化领域高水平的SCI检索刊物上，另还有6篇论文在整理准备阶段，待投稿。本项目共培养硕士研究生8名，其中5人已经毕业获得硕士学位，1人将于2019年1月完成硕士论文答辩，并在2019年3月继续攻读项目负责人的博士学位。