On bilevel minimum and bottleneck spanning tree problems. Issue 3 (2nd April 2019)

• Record Type: Journal Article
• Authors: Shi, Xueyu; Zeng, Bo; Prokopyev, Oleg A.
• Is Part Of: Networks. Volume 74:Issue 3(2019)
• Page Start: 251
• Page End: 273
• Publication Date: 2019-04-02
• Subjects: bilevel programming -- bottleneck spanning tree problem -- computational complexity -- minimum spanning tree problem -- mixed‐integer programming -- spanning tree problem; Network analysis (Planning) -- Periodicals; 658.4032
• DOI: 10.1002/net.21881
• Languages: English
• ISSNs: 0028-3045

Abstract

Abstract: 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.