maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2012-4-72-77mais-43Research ArticleОригинальные статьиArticlesЗамечания о расположениях точек на квадрикахSome Notes about Arrangements of Points on QuadricsСеливерстовАлександр ВладиславовичSeliverstovA. V.

старший научный сотрудник, кандидат физико-математических наук

старший научный сотрудник, кандидат физико-математических наук

slvstv@iitp.ruИнститут проблем передачи информации им. А. А. Харкевича РАНРоссияИнститут проблем передачи информации им. А. А. Харкевича РАНRussian Federation2012280220151947277Copyright © Селиверстов А.В., 20152015Селиверстов А.В.Seliverstov A.V.Данная работа распространяется под лицензией Creative Commons Attribution 4.0.This work is licensed under a Creative Commons Attribution 4.0 License.https://www.mais-journal.ru/jour/article/view/43

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

It is considered the minimization of a quadratic polynomial on the set of all points of a multidimensional space, coordinates of which are either zero or one. Some restrictions are imposed on the arrangement of the minimum points when there are many such points.

combinatorial optimization, quadratic programming, empty quadric, polytope, facet

комбинаторная оптимизацияквадратичное программированиепустая квадрикамногогранникфасетаcombinatorial optimizationquadratic programmingempty quadricpolytopefacetReferencesБереснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Издательство Института математики, 2005. 408 с.Береснев В. Л. Дискретные задачи размещения и полиномы от булевых переменных. Новосибирск: Издательство Института математики, 2005. 408 с.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.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.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.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.Емеличев В. А., Коротков В. В. Об устойчивости лексикографического решения векторной минимаксной квадратичной булевой задачи // Тр. Института матем. НАН Беларуси. 2011. Т. 19. №2. С. 26–36.Емеличев В. А., Коротков В. В. Об устойчивости лексикографического решения векторной минимаксной квадратичной булевой задачи // Тр. Института матем. НАН Беларуси. 2011. Т. 19. №2. С. 26–36.Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.Емеличев В. А., Ковалев М. М., Кравцов М. К. Многогранники, графы, оптимизация. М.: Наука, 1981. 344 с.Padberg M. The boolean quadric polytope: some characteristics, facets and relatives // Mathematical programming. 1989. V. 45. №1–3. P. 139–172.Padberg M. The boolean quadric polytope: some characteristics, facets and relatives // Mathematical programming. 1989. V. 45. №1–3. P. 139–172.Максименко А. Н. О числе фасет 2-смежностного многогранника // Модел. и анализ информ. систем. 2010. Т. 17. №1. С. 76–82.Максименко А. Н. О числе фасет 2-смежностного многогранника // Модел. и анализ информ. систем. 2010. Т. 17. №1. С. 76–82.Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.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.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.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.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.Николаев А. В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника // Модел. и анализ информ. систем. 2011. Т. 18. №3. С. 82–100.Николаев А. В. Гиперграфы специального вида и анализ свойств релаксаций разрезного многогранника // Модел. и анализ информ. систем. 2011. Т. 18. №3. С. 82–100.Делоне Б. Н. Геометрия положительных квадратичных форм // УМН. 1937. №3. С. 16–62.Делоне Б. Н. Геометрия положительных квадратичных форм // УМН. 1937. №3. С. 16–62.Селиверстов А. В., Любецкий В. А. О симметричных матрицах с неопределенной главной диагональю // Пробл. передачи информ. 2009. Т. 45. №3. C. 73–78.Селиверстов А. В., Любецкий В. А. О симметричных матрицах с неопределенной главной диагональю // Пробл. передачи информ. 2009. Т. 45. №3. C. 73–78.Селиверстов А. В., Любецкий В. А. О формах, равных нулю в каждой вершине куба // Информационные процессы. 2011. Т. 11. №3. С. 330–335. Электронный научный журнал http://www.jip.ruСеливерстов А. В., Любецкий В. А. О формах, равных нулю в каждой вершине куба // Информационные процессы. 2011. Т. 11. №3. С. 330–335. Электронный научный журнал http://www.jip.ruCostello K. P., Vu V. H. The rank of random graphs // Random structures and algorithms. 2008. V. 33. №3. P. 269–285.Costello K. P., Vu V. H. The rank of random graphs // Random structures and algorithms. 2008. V. 33. №3. P. 269–285.

The authors declare that there are no conflicts of interest present.