TY - JOUR
T1 - A mixed-integer bilevel programming approach for a competitive prioritized set covering problem
AU - Hemmati, Mehdi
AU - Smith, J. Cole
N1 - Funding Information:
The authors are grateful for the remarks of three anonymous referees and an Associate Editor, whose remarks led to an improved version of this paper, and in particular led us to present our cutting-plane generation schemes in the context of lifting. The authors also gratefully acknowledge the support of the National Science Foundation under grants CMMI-1100765 , the Defense Threat Reduction Agency under grant HDTRA-10-01-0050 , the Air Force Office of Scientific Research under grant FA9550-12-1-0353 , and the Office of Naval Research under grant N000141310036 . Appendix A
Publisher Copyright:
© 2016 Elsevier B.V. All rights reserved.
PY - 2016/5
Y1 - 2016/5
N2 - The competitive set covering problem is a two-player Stackelberg (leader-follower) game involving a set of items and clauses. The leader acts first to select a set of items, and with knowledge of the leader's action, the follower then selects another subset of items. There exists a set of clauses, where each clause is a prioritized set of items. A clause is satisfied by the selected item having the highest priority, resulting in a reward for the player that introduced the highest-priority selected item. We examine a mixed-integer bilevel programming (MIBLP) formulation for a competitive set covering problem, assuming that both players seek to maximize their profit. This class of problems arises in several fields, including non-cooperative product introduction and facility location games. We develop an MIBLP model for this problem in which binary decision variables appear in both stages of the model. Our contribution regards a cutting-plane algorithm, based on inequalities that support the convex hull of feasible solutions and induce faces of non-zero dimension in many cases. Furthermore, we investigate alternative verification problems to equip the algorithm with cutting planes that induce higher-dimensional faces, and demonstrate that the algorithm significantly improves upon existing general solution method for MIBLPs.
AB - The competitive set covering problem is a two-player Stackelberg (leader-follower) game involving a set of items and clauses. The leader acts first to select a set of items, and with knowledge of the leader's action, the follower then selects another subset of items. There exists a set of clauses, where each clause is a prioritized set of items. A clause is satisfied by the selected item having the highest priority, resulting in a reward for the player that introduced the highest-priority selected item. We examine a mixed-integer bilevel programming (MIBLP) formulation for a competitive set covering problem, assuming that both players seek to maximize their profit. This class of problems arises in several fields, including non-cooperative product introduction and facility location games. We develop an MIBLP model for this problem in which binary decision variables appear in both stages of the model. Our contribution regards a cutting-plane algorithm, based on inequalities that support the convex hull of feasible solutions and induce faces of non-zero dimension in many cases. Furthermore, we investigate alternative verification problems to equip the algorithm with cutting planes that induce higher-dimensional faces, and demonstrate that the algorithm significantly improves upon existing general solution method for MIBLPs.
KW - Bilevel programming
KW - Cutting planes
KW - Integer programming
KW - Stackelberg games
UR - http://www.scopus.com/inward/record.url?scp=84964823836&partnerID=8YFLogxK
UR - http://www.scopus.com/inward/citedby.url?scp=84964823836&partnerID=8YFLogxK
U2 - 10.1016/j.disopt.2016.04.001
DO - 10.1016/j.disopt.2016.04.001
M3 - Article
AN - SCOPUS:84964823836
SN - 1572-5286
VL - 20
SP - 105
EP - 134
JO - Discrete Optimization
JF - Discrete Optimization
ER -