maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State Universitymais-1031Research ArticleОригинальные статьиArticlesО нецелочисленных вершинах релаксаций многогранника задачи 3-ВЫПОЛНИМОСТЬOn nonintegral vertices of 3-SAT problem relaxation polytopeНиколаевА. В.NikolaevA. V.Awern@yandex.ruЯрославский государственный университет им. П.Г. ДемидоваRussian Federation20102006201017299111Copyright © Николаев А.В., 20102010Николаев А.В.Nikolaev 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/1031

Устанавливаются новые факты, характеризующие множество вершин релаксационного многогранника задачи 3-ВЫПОЛНИМОСТЬ. В частности, рассмотрен вопрос о сохранении нецелочисленных вершин при переходе к более сильным релаксациям.

New facts characterizing the vertex set of 3-SAT problem relaxation polytope are established. In particular, the question of preservation of nonintegral vertices under additional linear constraints of stronger relaxations is examined.

комбинаторная оптимизациятеория сложностимногогранникиграничные комплексызадача линейного программированияcombinatorial optimizationcomputational complexity theorypolytopesface latticelinear programmingReferencesDantzig G. В., Fulkerson R., Johnson S. M. 'Solution of a large-scale traveling salesman problem // Operations Research. 1954. 2. P. 393-410.Dantzig G. В., Fulkerson R., Johnson S. M. 'Solution of a large-scale traveling salesman problem // Operations Research. 1954. 2. P. 393-410.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982. 416 с.Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.Бондаренко В.А., Максименко А.Н. Геометрические конструкции и сложность в комбинаторной оптимизации. М.: ЛКИ, 2008. 184 с.Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.Деза М., Лоран М. Геометрия разрезов и метрик. М.: МЦНМО, 2001. 736 с.Бондаренко В.А., Урываев Б.В. Об одной задаче целочисленной оптимизации // Автоматика и телемеханика. 2007. №6. С. 18-23.Бондаренко В.А., Урываев Б.В. Об одной задаче целочисленной оптимизации // Автоматика и телемеханика. 2007. №6. С. 18-23.Бондаренко В.А. Об одном комбинаторном многограннике // Моделирование и анализ вычислительных систем: Сб. науч. тр. Ярославль: Яросл. гос. ун-т., 1987. С. 133-134.Бондаренко В.А. Об одном комбинаторном многограннике // Моделирование и анализ вычислительных систем: Сб. науч. тр. Ярославль: Яросл. гос. ун-т., 1987. С. 133-134.Padberg M.V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. 1989. V. 45. P. 139-172.Padberg M.V. The Boolean quadratic polytope: some characteristics, facets and relatives // Mathematical Program. 1989. V. 45. P. 139-172.Дунаева О.А., Николаев А.В. Некоторые свойства релаксационного многогранни¬ка задачи 3-выполнимость // Математическое моделирование и краевые задачи. Труды пятой Всероссийской научной конференции с международным участием. Самара: СамГТУ, 2008. С. 37-43.Дунаева О.А., Николаев А.В. Некоторые свойства релаксационного многогранни¬ка задачи 3-выполнимость // Математическое моделирование и краевые задачи. Труды пятой Всероссийской научной конференции с международным участием. Самара: СамГТУ, 2008. С. 37-43.PORTA: POlyhedron Representation Transformation Algorithm 1.4.0. Thomas Christof, Andreas Loebel. The Konrad-Zuse-Zentrum fur Informationstechnik Berlin, http://www.zib.de/Optimization/Software/Porta/PORTA: POlyhedron Representation Transformation Algorithm 1.4.0. Thomas Christof, Andreas Loebel. The Konrad-Zuse-Zentrum fur Informationstechnik Berlin, http://www.zib.de/Optimization/Software/Porta/

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