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

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

VL - 20

SP - 105

EP - 134

JO - Discrete Optimization

JF - Discrete Optimization

SN - 1572-5286

ER -