Title | ||
---|---|---|
A mixed-integer bilevel programming approach for a competitive prioritized set covering problem. |
Abstract | ||
---|---|---|
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. |
Year | DOI | Venue |
---|---|---|
2016 | 10.1016/j.disopt.2016.04.001 | Discrete Optimization |
Keywords | Field | DocType |
Integer programming,Bilevel programming,Cutting planes,Stackelberg games | Integer,Set cover problem,Mathematical optimization,Bilevel optimization,Binary decision diagram,Convex hull,Facility location problem,Integer programming,Stackelberg competition,Mathematics | Journal |
Volume | Issue | ISSN |
20 | C | 1572-5286 |
Citations | PageRank | References |
5 | 0.44 | 11 |
Authors | ||
2 |
Name | Order | Citations | PageRank |
---|---|---|---|
Mehdi Hemmati | 1 | 9 | 0.90 |
J. Cole Smith | 2 | 610 | 43.34 |