论文标题
具有多个重量功能的逆优化问题
Inverse optimization problems with multiple weight functions
论文作者
论文摘要
我们引入了一类新的反优化问题，其中将输入解决方案与$ k $线性权重功能一起提供，目标是通过相同的偏差向量$ p $修改权重，以使输入解决方案相对于每个偏离，而最小化$ \ | | p \ | p \ | _1 $。特别是，我们专注于具有多个重量功能的三个问题：最短的$ s $ - $ t $路径，逆二分之一的完美匹配以及逆动画问题。使用LP二元性，我们为最佳偏差向量的$ \ ell_1 $ norm提供了最低最大特征。此外，我们表明，即使权重功能如此，最佳$ p $也不一定是不可或缺的，因此计算最佳解决方案要比单个加权情况要困难得多。我们还为存在最佳偏差矢量的存在提供了必要的条件，该矢量仅在输入解决方案的元素上更改值，从而对先前的arborescence和unteratives群体有了统一的理解。
We introduce a new class of inverse optimization problems in which an input solution is given together with $k$ linear weight functions, and the goal is to modify the weights by the same deviation vector $p$ so that the input solution becomes optimal with respect to each of them, while minimizing $\|p\|_1$. In particular, we concentrate on three problems with multiple weight functions: the inverse shortest $s$-$t$ path, the inverse bipartite perfect matching, and the inverse arborescence problems. Using LP duality, we give min-max characterizations for the $\ell_1$-norm of an optimal deviation vector. Furthermore, we show that the optimal $p$ is not necessarily integral even when the weight functions are so, therefore computing an optimal solution is significantly more difficult than for the single-weighted case. We also give a necessary and sufficient condition for the existence of an optimal deviation vector that changes the values only on the elements of the input solution, thus giving a unified understanding of previous results on arborescences and matchings.
