Exact solution approaches for bilevel assignment problems
Exact solution approaches for bilevel assignment problems
复制标题
双层分配问题的精确求解方法
DOI：
10.1007/s10589-015-9799-4
复制
发表时间：
2016
影响因子：
2.2
通讯作者：
E. Pasiliao
中科院分区：
文献类型：
--
作者：
B. Beheshti;O. Prokopyev;E. Pasiliao
我们考虑双层分配问题，其中每个决策者（即，领导者和跟随者）具有其自己的目标函数并且控制给定二分图中的不同的边集合。领导者首先选择它的一些边。随后，跟随者完成分配过程。领导者和追随者所选择的边需要构成完美的匹配。在本文中，我们提出了一个精确的解决方案的方法，这是基于一个分支和界限的框架，并利用分配问题的结构特性。大量的计算实验与线性和线性瓶颈目标函数进行证明所开发的方法的性能。虽然所考虑的问题是已知的NP-困难的一般情况下，我们还描述了一些限制的情况下，可以在多项式时间内解决。
We consider the bilevel assignment problem in which each decision maker (i.e., the leader and the follower) has its own objective function and controls a distinct set of edges in a given bipartite graph. The leader acts first by choosing some of its edges. Subsequently, the follower completes the assignment process. The edges selected by the leader and the follower are required to constitute a perfect matching. In this paper we propose an exact solution approach, which is based on a branch-and-bound framework and exploits structural properties of the assignment problem. Extensive computational experiments with linear sum and linear bottleneck objective functions are conducted to demonstrate the performance of the developed methods. While the considered problem is known to be NP-hard in general, we also describe some restricted cases that can be solved in polynomial time.