A Branch, Bound, and Cuts Algorithm for the Dynamic Competitive Facility Location Problem | Sciact - Система учета научной деятельности ИМ СО РАН

A Branch, Bound, and Cuts Algorithm for the Dynamic Competitive Facility Location Problem Научная публикация

Журнал

Journal of Applied and Industrial Mathematics
ISSN: 1990-4789 , E-ISSN: 1990-4797

Вых. Данные

Год: 2024, Том: 18, Номер: 4, Страницы: 643-655 Страниц : 13 DOI: 10.1134/s1990478924040021

Ключевые слова

competitive facility location problem, bilevel mathematical programming, exact method, Stackelberg game

Авторы

Beresnev V.L. ^1,2 , Melnikov A.A. ^1,2

Организации

1	Sobolev Institute of Mathematics
2	Novosibirsk State University

Информация о финансировании (1)

Российский научный фонд

23-21-00082

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

Beresnev V.L. , Melnikov A.A.
A Branch, Bound, and Cuts Algorithm for the Dynamic Competitive Facility Location Problem
Journal of Applied and Industrial Mathematics. 2024. V.18. N4. P.643-655. DOI: 10.1134/s1990478924040021 Scopus РИНЦ OpenAlex

Береснев В.Л. , Мельников А.А.
Алгоритм ветвей, границ и отсечений для неявной динамической задачи конкурентного размещения
Дискретный анализ и исследование операций. 2024. Т.31. №4. С.5–26. DOI: 10.33048/daio.2024.31.814 РИНЦ

Поступила в редакцию:	18 окт. 2024 г.
Принята к публикации:	1 нояб. 2024 г.
Опубликована в печати:	25 дек. 2024 г.
Опубликована online:	11 июл. 2025 г.

Scopus:	2-s2.0-105010543907
РИНЦ:	82621651
OpenAlex:	W4412194792

Пока нет цитирований