On bilevel minimum and bottleneck spanning tree problems
On bilevel minimum and bottleneck spanning tree problems
复制标题
关于双层最小生成树和瓶颈生成树问题
DOI：
10.1002/net.21881
复制
发表时间：
2019
期刊：
影响因子：
2.1
通讯作者：
Prokopyev, Oleg A.
中科院分区：
文献类型：
--
作者：
Shi, Xueyu;Zeng, Bo;Prokopyev, Oleg A.
本文研究了一类两层生成树（BST）问题，这类问题涉及两个独立的决策者，即具有不同目标的领导者和追随者，他们共同在图中构造一棵生成树。领导者首先采取行动，从她控制的集合中选择一个不包含循环的初始边子集。follower选择剩余的边来完成生成树的构造，同时对自己的目标函数进行优化。如果跟随者存在多个最优解，导致领导者的目标函数值不同，那么跟随者可以选择对领导者最有利的（乐观版本）或最不利的（悲观版本）。我们研究了乐观和悲观两种情况下dm的和型和瓶颈型目标函数的BST问题。对于至少有一个dm具有瓶颈型目标函数的BST问题，分别在乐观和悲观两种情况下提出了多项式时间算法。对于具有和型目标函数的BST问题，我们给出了一个等价的单级线性混合整数规划公式。然后提出了一个计算研究来探索我们的重新表述的有效性。
We study a class of bilevel spanning tree (BST) problems that involve two independent decision‐makers (DMs), the leader and the follower with different objectives, who jointly construct a spanning tree in a graph. The leader, who acts first, selects an initial subset of edges that do not contain a cycle, from the set under her control. The follower then selects the remaining edges to complete the construction of a spanning tree, but optimizes his own objective function. If there exist multiple optimal solutions for the follower that result in different objective function values for the leader, then the follower may choose either the one that is the most (optimistic version) or least (pessimistic version) favorable to the leader. We study BST problems with the sum‐ and bottleneck‐type objective functions for the DMs under both the optimistic and pessimistic settings. The polynomial‐time algorithms are then proposed in both optimistic and pessimistic settings for BST problems in which at least one of the DMs has the bottleneck‐type objective function. For BST problem with the sum‐type objective functions for both the leader and the follower, we provide an equivalent single‐level linear mixed‐integer programming formulation. A computational study is then presented to explore the efficacy of our reformulation.
登录
查看更多内容
影响因子：
2.2
作者：
B. Beheshti;O. Prokopyev;E. Pasiliao
通讯作者：
E. Pasiliao
DOI：
10.1109/infcom.2003.1209193
发表时间：
2003-07
期刊：
IEEE INFOCOM 2003. Twenty-second Annual Joint Conference of the IEEE Computer and Communications Societies (IEEE Cat. No.03CH37428)
影响因子：
--
作者：
Ning Li;J. Hou;L. Sha
通讯作者：
Ning Li;J. Hou;L. Sha
DOI：
--
发表时间：
1996
期刊：
ACM-SIAM Symposium on Discrete Algorithms
影响因子：
--
作者：
G. Frederickson;Roberto Solis
通讯作者：
Roberto Solis
DOI：
--
发表时间：
2009
期刊：
4OR
影响因子：
--
作者：
Elisabeth Gassner;Bettina Klinz
通讯作者：
Bettina Klinz
DOI：
--
发表时间：
2011
期刊：
影响因子：
--
作者：
Oleksii Ursulenko
通讯作者：
Oleksii Ursulenko