maisМоделирование и анализ информационных системModeling and Analysis of Information Systems1818-10152313-5417Yaroslavl State University10.18255/1818-1015-2016-1-23-40mais-304Research ArticleОригинальные статьиArticlesA Special Role of Boolean Quadratic Polytopes among Other Combinatorial PolytopesA Special Role of Boolean Quadratic Polytopes among Other Combinatorial PolytopesМаксименкоАлександр НиколаевичMaksimenkoA. N.

канд. физ.-мат. наук, доцент

PhD

maximenko.a.n@gmail.comЯрославский государственный университет им. П.Г. ДемидоваРоссияP.G. Demidov Yaroslavl State University, Sovetskaya str., 14, Yaroslavl, 150000, RussiaRussian Federation2016200220162312340Copyright © Максименко А.Н., 20162016Максименко А.Н.Maksimenko A.N.Данная работа распространяется под лицензией 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/304

Рассматриваются несколько семейств комбинаторных многогранников, ассоциированных со следующими NP-полными задачами: максимальный разрез, булево квадратичное программирование, квадратичная задача линейного упорядочения, квадратичные назначения, разбиение и упаковка множества, независимое множество, 3-назначения. Для сравнения двух семейств многогранников используется следующий способ. Будем говорить, что семейство

We consider several families of combinatorial polytopes associated with the following NP-complete problems: maximum cut, Boolean quadratic programming, quadratic linear ordering, quadratic assignment, set partition, set packing, stable set, 3-assignment. For comparing two families of polytopes we use the following method. We say that a family

NP-трудные задачиаффинная сводимостьграни многогранниковNP-hard problemsaffine reductionfaces of polytopesReferencesD. Avis and H. R. Tiwary, “On the Extension Complexity of Combinatorial Polytopes”, Automata, Languages, and Programming, Lecture Notes in Computer Science, 7965, Springer, 2013, 57–68.D. Avis and H. R. Tiwary, “On the Extension Complexity of Combinatorial Polytopes”, Automata, Languages, and Programming, Lecture Notes in Computer Science, 7965, Springer, 2013, 57–68.E. Balas and M. J. Saltzman, “Facets of the three-index assignment polytope”, Discrete Applied Mathematics, 23:3 (1989), 201–229.E. Balas and M. J. Saltzman, “Facets of the three-index assignment polytope”, Discrete Applied Mathematics, 23:3 (1989), 201–229.L. J. Billera, A. Sarangarajan, “All 0-1 polytopes are travelling salesman polytopes”, Combinatorica, 16:2 (1996), 175–188.L. J. Billera, A. Sarangarajan, “All 0-1 polytopes are travelling salesman polytopes”, Combinatorica, 16:2 (1996), 175–188.V. A. Bondarenko, A. N. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii, LKI, Moscow, 2008, 184 pp.V. A. Bondarenko, A. N. Maksimenko, Geometricheskie konstruktsii i slozhnost v kombinatornoy optimizatsii, LKI, Moscow, 2008, 184 pp.C. Buchheim, A. Wiegele, and L. Zheng, “Exact Algorithms for the Quadratic Linear Ordering Problem”, INFORMS J. on Computing, 22:1 (2010), 168–177.C. Buchheim, A. Wiegele, and L. Zheng, “Exact Algorithms for the Quadratic Linear Ordering Problem”, INFORMS J. on Computing, 22:1 (2010), 168–177.V. Chvatal, “On certain polytopes associated with graphs”, J. Combin. Theory, Ser. B, 18 (1975), 138–154.V. Chvatal, “On certain polytopes associated with graphs”, J. Combin. Theory, Ser. B, 18 (1975), 138–154.M. Conforti, G. Cornu´ejols, and G. Zambelli, “Extended formulations in combinatorial optimization”, A Quarterly Journal of Operations Research, 8:1 (2010), 1–48.M. Conforti, G. Cornu´ejols, and G. Zambelli, “Extended formulations in combinatorial optimization”, A Quarterly Journal of Operations Research, 8:1 (2010), 1–48.G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson, “Solution of a large-scale traveling salesman problem”, Operation Research, 2:4 (1954), 393–410.G. B. Dantzig, D. R. Fulkerson, and S. M. Johnson, “Solution of a large-scale traveling salesman problem”, Operation Research, 2:4 (1954), 393–410.C. De Simone, “The cut polytope and the Boolean quadric polytope”, Discrete Math, 79 (1990), 71–75.C. De Simone, “The cut polytope and the Boolean quadric polytope”, Discrete Math, 79 (1990), 71–75.M. M. Deza, M. Laurent, Geometry of cuts and metrics, Springer, 1997, 588 pp.M. M. Deza, M. Laurent, Geometry of cuts and metrics, Springer, 1997, 588 pp.R. Euler, “Odd cycles and a class of facets of the axial 3-index assignment polytope”, Applicationes Mathematicae (Zastosowania Matematyki), 19 (1987), 375–386.R. Euler, “Odd cycles and a class of facets of the axial 3-index assignment polytope”, Applicationes Mathematicae (Zastosowania Matematyki), 19 (1987), 375–386.S. Fiorini, “A combinatorial study of partial order polytopes”, Eur. J. Comb., 24:2 (2003), 149–159.S. Fiorini, “A combinatorial study of partial order polytopes”, Eur. J. Comb., 24:2 (2003), 149–159.S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, “Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds”, Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC ’12, ACM, New York, 2012, 95–106.S. Fiorini, S. Massar, S. Pokutta, H. R. Tiwary, R. de Wolf, “Linear vs. Semidefinite Extended Formulations: Exponential Separation and Strong Lower Bounds”, Proceedings of the Forty-fourth Annual ACM Symposium on Theory of Computing, STOC ’12, ACM, New York, 2012, 95–106.M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, 1979, 340 pp.M. R. Garey and D. S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, 1979, 340 pp.M. Gr¨otschel, M. J¨unger, and G. Reinelt, “Facets of the linear ordering polytope”, Math. Program., 33 (1985), 43–60.M. Gr¨otschel, M. J¨unger, and G. Reinelt, “Facets of the linear ordering polytope”, Math. Program., 33 (1985), 43–60.V. Kaibel, Polyhedral combinatorics of the quadratic assignment problem, Ph.D. Thesis, Universit¨at zu K¨oln, 1997, 281 pp.V. Kaibel, Polyhedral combinatorics of the quadratic assignment problem, Ph.D. Thesis, Universit¨at zu K¨oln, 1997, 281 pp.V. Kaibel, Extended Formulations in Combinatorial Optimization, Optima, 85, 2011, 2–7.V. Kaibel, Extended Formulations in Combinatorial Optimization, Optima, 85, 2011, 2–7.V. Kaibel, S. Weltge, “A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially”, Discrete & Computational Geometry, 53:2 (2015), 396– 401.V. Kaibel, S. Weltge, “A Short Proof that the Extension Complexity of the Correlation Polytope Grows Exponentially”, Discrete & Computational Geometry, 53:2 (2015), 396– 401.V. M. Kravtsov, “A characterization of the types of maximal noninteger vertices of a polyhedron in the three-index axial assignment problem”, Russian Mathematics, 50:12 (2006), 63–66.V. M. Kravtsov, “A characterization of the types of maximal noninteger vertices of a polyhedron in the three-index axial assignment problem”, Russian Mathematics, 50:12 (2006), 63–66.A. N. Maksimenko, “Mnogogranniki zadachi o vypolnimosti yavlyayutsya granyami mnogogrannika zadachi kommivoyazhera”, Diskretn. analiz i issled. oper., 18:3 (2011), 76–83.A. N. Maksimenko, “Mnogogranniki zadachi o vypolnimosti yavlyayutsya granyami mnogogrannika zadachi kommivoyazhera”, Diskretn. analiz i issled. oper., 18:3 (2011), 76–83.A. N. Maksimenko, “On affine reducibility of combinatorial polytopes”, Doklady Mathematics, 85:2 (2012), 283–285.A. N. Maksimenko, “On affine reducibility of combinatorial polytopes”, Doklady Mathematics, 85:2 (2012), 283–285.A. N. Maksimenko, “An analog of the Cook theorem for polytopes”, Russian Mathematics, 56:8 (2012), 28–34.A. N. Maksimenko, “An analog of the Cook theorem for polytopes”, Russian Mathematics, 56:8 (2012), 28–34.A. N. Maksimenko, “k-Neighborly Faces of the Boolean Quadric Polytopes”, Journal of Mathematical Sciences, 203:6 (2014), 816–822.A. N. Maksimenko, “k-Neighborly Faces of the Boolean Quadric Polytopes”, Journal of Mathematical Sciences, 203:6 (2014), 816–822.A. N. Maksimenko, “The Common Face of some 0/1-Polytopes with NP-Complete Nonadjacency Relation”, Journal of Mathematical Sciences, 203:6 (2014), 823–832.A. N. Maksimenko, “The Common Face of some 0/1-Polytopes with NP-Complete Nonadjacency Relation”, Journal of Mathematical Sciences, 203:6 (2014), 823–832.T. Matsui, “NP-completeness of non-adjacency relations on some 0-1-polytopes”, Lecture Notes in Operations Research, 1, 1995, 249–258.T. Matsui, “NP-completeness of non-adjacency relations on some 0-1-polytopes”, Lecture Notes in Operations Research, 1, 1995, 249–258.M. W. Padberg and M. R. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”, Math. Program., 7 (1974), 32–45.M. W. Padberg and M. R. Rao, “The travelling salesman problem and a class of polyhedra of diameter two”, Math. Program., 7 (1974), 32–45.M. W. Padberg, “The boolean quadric polytope: some characteristics, facets and relatives”, Math. Program., 45 (1989), 139–172.M. W. Padberg, “The boolean quadric polytope: some characteristics, facets and relatives”, Math. Program., 45 (1989), 139–172.C. H. Papadimitriou, “The adjacency relation on the traveling salesman polytope is NPcomplete”, Math. Program., 14:1 (1978), 312–324.C. H. Papadimitriou, “The adjacency relation on the traveling salesman polytope is NPcomplete”, Math. Program., 14:1 (1978), 312–324.L. Qi and D. Sun, “Polyhedral Methods for Solving Three Index Assignment Problems”, Nonlinear Assignment Problems, Combinatorial Optimization, 7, eds. P. M. Pardalos and L. S. Pitsoulis, Springer, 2000, 91–107.L. Qi and D. Sun, “Polyhedral Methods for Solving Three Index Assignment Problems”, Nonlinear Assignment Problems, Combinatorial Optimization, 7, eds. P. M. Pardalos and L. S. Pitsoulis, Springer, 2000, 91–107.M.P. Rijal, Scheduling, design and assignment problems with quadratic costs, Ph.D. Thesis, New York University, 1995, 281 pp.M.P. Rijal, Scheduling, design and assignment problems with quadratic costs, Ph.D. Thesis, New York University, 1995, 281 pp.H. Saito, T. Fujie, T. Matsui, Sh. Matuura, “A study of the quadratic semi-assignment polytope”, Discrete Optimization, 6:1 (2009), 37–50.H. Saito, T. Fujie, T. Matsui, Sh. Matuura, “A study of the quadratic semi-assignment polytope”, Discrete Optimization, 6:1 (2009), 37–50.M. Yannakakis., “Expressing combinatorial optimization problems by linear programs”, J. Comput. Syst. Sci., 43:3 (1991), 441–466.M. Yannakakis., “Expressing combinatorial optimization problems by linear programs”, J. Comput. Syst. Sci., 43:3 (1991), 441–466.H.P. Young, “On permutations and permutation polytopes”, Mathematical Programming Study, 8 (1978), 128–140.H.P. Young, “On permutations and permutation polytopes”, Mathematical Programming Study, 8 (1978), 128–140.G. M. Ziegler, “Lectures on 0/1-Polytopes”, Polytopes — Combinatorics and Computation, DMV Seminar, 29, eds. G. Kalai and G. M. Ziegler, Birkh¨auser Basel, 2000, 1–41.G. M. Ziegler, “Lectures on 0/1-Polytopes”, Polytopes — Combinatorics and Computation, DMV Seminar, 29, eds. G. Kalai and G. M. Ziegler, Birkh¨auser Basel, 2000, 1–41.

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