Geodesic
A cut generation algorithm of finding an~optimal~solution in a market competition
Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 2, pp. 5-29.

Voir la notice de l'article provenant de la source Math-Net.Ru

We consider a mathematical model of market competition between two parties. The parties sequentially bring their products to the market while aiming to maximize profit. The model is based on the Stackelberg game and formulated as a bilevel integer mathematical program. The problem can be reduced to the competitive facility location problem (CompFLP) with a prescribed choice of suppliers which belongs to a family of bilevel models generalizing the classical facility location problem. For the CompFLP with a prescribed choice of suppliers, we suggest an algorithm of finding a pessimistic optimal solution. The algorithm is an iterative procedure that successively strengthens an estimating problem with additional constraints. The estimating problem provides an upper bound for the objective function of the CompFLP and is resulted from the bilevel model by excluding the lower-level objective function. To strengthen the estimating problem, we suggest a new family of constraints. Numerical experiments with randomly generated instances of the CompFLP with prescribed choice of suppliers demonstrate the effectiveness of the algorithm. Tab. 2, bibliogr. 17.
Keywords: market competition, Stackelberg game, bilevel programming, estimating problem. 
@article{DA_2019_26_2_a0,
     author = {V. L. Beresnev and A. A. Melnikov},
     title = {A cut generation algorithm of finding an~optimal~solution in a market competition},
     journal = {Diskretnyj analiz i issledovanie operacij},
     pages = {5--29},
     publisher = {mathdoc},
     volume = {26},
     number = {2},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/DA_2019_26_2_a0/}
}
TY  - JOUR
AU  - V. L. Beresnev
AU  - A. A. Melnikov
TI  - A cut generation algorithm of finding an~optimal~solution in a market competition
JO  - Diskretnyj analiz i issledovanie operacij
PY  - 2019
SP  - 5
EP  - 29
VL  - 26
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DA_2019_26_2_a0/
LA  - ru
ID  - DA_2019_26_2_a0
ER  - 
%0 Journal Article
%A V. L. Beresnev
%A A. A. Melnikov
%T A cut generation algorithm of finding an~optimal~solution in a market competition
%J Diskretnyj analiz i issledovanie operacij
%D 2019
%P 5-29
%V 26
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DA_2019_26_2_a0/
%G ru
%F DA_2019_26_2_a0
V. L. Beresnev; A. A. Melnikov. A cut generation algorithm of finding an~optimal~solution in a market competition. Diskretnyj analiz i issledovanie operacij, Tome 26 (2019) no. 2, pp. 5-29. http://geodesic.mathdoc.fr/item/DA_2019_26_2_a0/

[1] V. L. Beresnev, “On the competitive facility location problem with a free choice of suppliers”, Autom. Remote Control, 75:4 (2014), 668–676 | DOI | MR | Zbl

[2] V. L. Beresnev, A. A. Melnikov, “The branch-and-bound algorithm for a competitive facility location problem with the prescribed choice of suppliers”, J. Appl. Ind. Math., 8:2 (2014), 177–189 | DOI | MR | MR | Zbl

[3] V. L. Beresnev, A. A. Melnikov, “Cut generation algorithm for the discrete competitive facility location problem”, Dokl. Math., 97:3 (2018), 254–257 | DOI | DOI | MR | Zbl

[4] V. L. Beresnev, V. I. Suslov, “A mathematical model of market competition”, J. Appl. Ind. Math., 4:2 (2010), 147–157 | DOI | MR | MR | Zbl

[5] Benchmark Library “Discrete Location Problems” (accessed Feb. 11, 2019)

[6] A. A. Melnikov, “Randomized local search for the discrete competitive facility location problem”, Autom. Remote Control, 75:4 (2014), 700–714 | DOI | MR | Zbl

[7] Beresnev V. L., “Branch-and-bound algorithm for a competitive facility location problem”, Comput. Oper. Res., 40:8 (2013), 2062–2070 | DOI | MR | Zbl

[8] Beresnev V. L., Melnikov A. A., “Exact method for the capacitated competitive facility location problem”, Comput. Oper. Res., 95 (2018), 73–82 | DOI | MR | Zbl

[9] Beresnev V. L., Melnikov A. A., “Approximation of the competitive facility location problem with MIPs”, Comput. Oper. Res., 104 (2019), 139–148 | DOI | MR | Zbl

[10] Cánovas L., García S., Labbé M., Marín A., “A strengthened formulation for the simple plant location problem with order”, Oper. Res. Lett., 35:2 (2007), 141–150 | DOI | MR | Zbl

[11] Dempe S., Foundations of bilevel programming, Kluwer Acad. Publ., Dordrecht, 2002, 332 pp. | MR | Zbl

[12] Gurobi optimizer reference manual. Gurobi Optimization, , 2018 (accessed Feb. 11, 2019) http://www.gurobi.com

[13] Hanjoul P., Peeters D., “A facility location problem with clients' preference orderings”, Reg. Sci. Urban Econ., 17:3 (1987), 451–473 | DOI

[14] Hemmati M., Smith J. C., “A mixed-integer bilevel programming approach for a competitive prioritized set covering problem”, Discrete Optim., 20 (2016), 105–134 | DOI | MR | Zbl

[15] Moore J. T., Bard J. F., “The mixed integer linear bilevel programming problem”, Oper. Res., 38:5 (1990), 911–921 | DOI | MR | Zbl

[16] Von Stackelberg H., The theory of the market economy, Oxford Univ. Press, Oxford, 1952, 289 pp.

[17] Vasilyev I., Klimentova X., Boccia M., “Polyhedral study of simple plant location problem with order”, Oper. Res. Lett., 41:2 (2013), 153–158 | DOI | MR | Zbl