The computational complexity of bilevel assignment problems
The computational complexity of bilevel assignment problems
复制标题
双层分配问题的计算复杂度
DOI：
--
复制
发表时间：
2009
期刊：
影响因子：
--
通讯作者：
Bettina Klinz
中科院分区：
文献类型：
--
作者：
Elisabeth Gassner;Bettina Klinz
在两层优化问题中，有两个决策者，领导者和跟随者，他们按等级行事。每个决策者都有自己的目标函数，但也有共同的约束。本文研究了两层指派问题，其中每个决策者控制一个边子集，每个边都有一个领导者和一个跟随者的权重。引导者和跟随者选择的边需要形成完美的匹配。任务是确定领导者应该选择哪些边，以使其目标值最大化，该目标值取决于跟随者的最佳反应。我们考虑领导者和追随者的总和和瓶颈目标函数。此外，如果追随者的所有最优反应并不都导致相同的领导者的目标值，那么追随者要么选择对领导者最好的(乐观规则)，要么选择对领导者最差的(悲观规则)。我们证明了当领导者和追随者的目标函数是和函数或瓶颈函数时，如果应用悲观规则，所产生的所有变量都是NP-难的。在乐观规则的情况下，如果至少有一个决策者有一个和目标函数，则该问题被证明是NP难的。
In bilevel optimization problems there are two decision makers, the leader and the follower, who act in a hierarchy. Each decision maker has his own objective function, but there are common constraints. This paper deals with bilevel assignment problems where each decision maker controls a subset of edges and each edge has a leader’s and a follower’s weight. The edges selected by the leader and by the follower need to form a perfect matching. The task is to determine which edges the leader should choose such that his objective value which depends on the follower’s optimal reaction is maximized. We consider sum- and bottleneck objective functions for the leader and follower. Moreover, if not all optimal reactions of the follower lead to the same leader’s objective value, then the follower either chooses an optimal reaction which is best (optimistic rule) or worst (pessimistic rule) for the leader. We show that all the variants arising if the leader’s and follower’s objective functions are sum or bottleneck functions are NP-hard if the pessimistic rule is applied. In case of the optimistic rule the problem is shown to be NP-hard if at least one of the decision makers has a sum objective function.