|
ИСТИНА |
Войти в систему Регистрация |
ФНКЦ РР |
||
An Interior Point Heuristic for the Hamiltonian Cycle Problem via Markov Decision Processesстатья
Информация о цитировании статьи получена из
Scopus
Статья опубликована в журнале из списка Web of Science и/или Scopus
Дата последнего поиска статьи во внешних источниках: 16 июня 2023 г.
- Авторы: Ejov Vladimir, Filar Jerzy, Gondzio Jacek
- Журнал: Journal of Global Optimization
- Том: 29
- Номер: 3
- Год издания: 2004
- Издательство: Springer Nature
- Местоположение издательства: Switzerland
- Первая страница: 315
- Последняя страница: 334
- DOI: 10.1023/b:jogo.0000044772.11089.1a
- Аннотация: We consider the Hamiltonian cycle problem embedded in a singularly perturbed Markov decision process (MDP). More specifically, we consider the HCP as an optimization problem over the space of long-run state-action frequencies induced by the MDP's stationary policies. We show that Hamiltonian cycles (if any) correspond to the global minima of a suitably constructed indefinite quadratic programming problem over the frequency space. We show that the above indefinite quadratic can be approximated by quadratic functions that are `nearly convex' and as such suitable for the application of logarithmic barrier methods. We develop an interior-point type algorithm that involves an arc elimination heuristic that appears to perform rather well in moderate size graphs. The approach has the potential for further improvements.
- Добавил в систему: Ежов Владимир Владимирович