Preview

Моделирование и анализ информационных систем

Расширенный поиск

Замечания о расположениях точек на квадриках

https://doi.org/10.18255/1818-1015-2012-4-72-77

Аннотация

Рассмотрена задача минимизации квадратичного многочлена на множестве всех точек многомерного вещественного пространства, координаты которых равны нулю или единице. Получены некоторые ограничения на взаимное расположение точек минимума, когда их достаточно много.

Об авторе

Александр Владиславович Селиверстов
Институт проблем передачи информации им. А. А. Харкевича РАН
Россия
старший научный сотрудник, кандидат физико-математических наук


Список литературы

1. Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Издательство Института математики, 2005. 408 с.

2. Billionnet A., Elloumi S. Using a mixed integer quadratic programming solver for the unconstrained quadratic 0-1 problem // Mathematical programming. Ser. A. 2007. V. 109. №1. P. 55–68.

3. Ahlat¸cio˘glu A., Bussieck M., Esen M., Guignard M., Jagla J.-H., Meeraus A. Combining QCR and CHR for convex quadratic pure 0-1 programming problems with linear constraints // Annals of operations research. 2012. V. 199. №1. P. 33–49.

4. Емеличев В. А., Коротков В. В. Об устойчивости лексикографического решения векторной минимаксной квадратичной булевой задачи // Тр. Института матем. НАН Беларуси. 2011. Т. 19. №2. С. 26–36.

5. Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.

6. Padberg M. The boolean quadric polytope: some characteristics, facets and relatives // Mathematical programming. 1989. V. 45. №1–3. P. 139–172.

7. Максименко А. Н. О числе фасет 2-смежностного многогранника // Модел. и анализ информ. систем. 2010. Т. 17. №1. С. 76–82.

8. Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.

9. Zhao W., Posner M. E. A large class of facets for the K-median polytope // Mathematical programming. Ser. A. 2011. V. 128. №1–2. P. 171–203.

10. Galli L., Kaparis K., Letchford A. N. Gap inequalities for non-convex mixed-integer quadratic programs // Operations research letters. 2011. V. 39. №5. P. 297–300.

11. Николаев А. В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника // Модел. и анализ информ. систем. 2011. Т. 18. №3. С. 82–100.

12. Делоне Б. Н. Геометрия положительных квадратичных форм // УМН. 1937. №3. С. 16–62.

13. Селиверстов А. В., Любецкий В. А. О симметричных матрицах с неопределенной главной диагональю // Пробл. передачи информ. 2009. Т. 45. №3. C. 73–78.

14. Селиверстов А. В., Любецкий В. А. О формах, равных нулю в каждой вершине куба // Информационные процессы. 2011. Т. 11. №3. С. 330–335. Электронный научный журнал http://www.jip.ru

15. Costello K. P., Vu V. H. The rank of random graphs // Random structures and algorithms. 2008. V. 33. №3. P. 269–285.


Рецензия

Для цитирования:


Селиверстов А.В. Замечания о расположениях точек на квадриках. Моделирование и анализ информационных систем. 2012;19(4):72-77. https://doi.org/10.18255/1818-1015-2012-4-72-77

For citation:


Seliverstov A.V. Some Notes about Arrangements of Points on Quadrics. Modeling and Analysis of Information Systems. 2012;19(4):72-77. (In Russ.) https://doi.org/10.18255/1818-1015-2012-4-72-77

Просмотров: 805


Creative Commons License
Контент доступен под лицензией Creative Commons Attribution 4.0 License.


ISSN 1818-1015 (Print)
ISSN 2313-5417 (Online)