TY - JOUR

T1 - A Branch, Bound, and Cuts Algorithm for the Dynamic Competitive Facility Location Problem

AU - Береснев, Владимир Леонидович

AU - Мельников, Андрей Андреевич

N1 - This work was supported by the Russian Science Foundation, project no. 23–21–00082.

PY - 2024/12

Y1 - 2024/12

N2 - We consider a dynamic competitive facility location problem modeling an interaction of two competing parties (Leader and Follower) who place their facilities within a planning horizon split into several time periods. The Leader is assumed to open his/her facilities at the beginning of the planning horizon and does not change his/her decision later, while the Follower can modify his/her choice within each time period. We propose an algorithm that computes the best Leader’s decision and is built on the base of the branch-and-bound computational scheme. To compute upper bounds, a special relaxation of the initial bilevel problem strengthened with additional constraints (cuts) is used. The paper describes the construction of these constraints while utilizing auxiliary optimization problems; this provides the strongest cuts. On an instance of a dynamic competitive facility location on a network with three vertices, we demonstrate that the model is capable to take into account information regarding the changes of problem’s parameters along the time period. An implementation of the branch-and-bound algorithm shows a significant benefit from using the cuts specially designed for dynamic competitive models: it improves the upper bound’s quality and reduces the number of nodes in the branching tree.

AB - We consider a dynamic competitive facility location problem modeling an interaction of two competing parties (Leader and Follower) who place their facilities within a planning horizon split into several time periods. The Leader is assumed to open his/her facilities at the beginning of the planning horizon and does not change his/her decision later, while the Follower can modify his/her choice within each time period. We propose an algorithm that computes the best Leader’s decision and is built on the base of the branch-and-bound computational scheme. To compute upper bounds, a special relaxation of the initial bilevel problem strengthened with additional constraints (cuts) is used. The paper describes the construction of these constraints while utilizing auxiliary optimization problems; this provides the strongest cuts. On an instance of a dynamic competitive facility location on a network with three vertices, we demonstrate that the model is capable to take into account information regarding the changes of problem’s parameters along the time period. An implementation of the branch-and-bound algorithm shows a significant benefit from using the cuts specially designed for dynamic competitive models: it improves the upper bound’s quality and reduces the number of nodes in the branching tree.

KW - COMPETITIVE FACILITY LOCATION PROBLEM

KW - BILEVEL MATHEMATICAL PROGRAMMING

KW - EXACT METHOD

KW - STACKELBERG GAME

UR - https://www.scopus.com/pages/publications/105010543907

UR - https://www.elibrary.ru/item.asp?id=82621651

UR - https://www.elibrary.ru/item.asp?id=82606991

U2 - 10.1134/S1990478924040021

DO - 10.1134/S1990478924040021

M3 - Article

VL - 18

SP - 643

EP - 655

JO - Journal of Applied and Industrial Mathematics

JF - Journal of Applied and Industrial Mathematics

SN - 1990-4789

IS - 4

M1 - 2

ER -