Top

Published in:

2018 | OriginalPaper | Chapter

On Vertices of the Simple Boolean Quadric Polytope Extension

Author : Andrei V. Nikolaev

Published in: Optimization Problems and Their Applications

Publisher: Springer International Publishing

Activate our intelligent search to find suitable subject content or patents.

search-config

AI-assisted search

Off

Abstract

Following the seminal work of Padberg on the Boolean quadric polytope BQP and its LP relaxation \(BQP_{LP}\), we consider a natural extension: the polytopes SATP and \(SATP_{LP}\), with \(BQP_{LP}\) being a projection of \(SATP_{LP}\) face (and BQP – projection of SATP face). Various special instances of 3-SAT problem like NAE-3-SAT, 1-in-3-SAT, weighted MAX-3-SAT, and others can be solved by integer programming over \(SATP_{LP}\). We consider the properties of SATP 1-skeleton and \(SATP_{LP}\) fractional vertices. Like \(BQP_{LP}\), the polytope \(SATP_{LP}\) has the Trubin-property being quasi-integral (1-skeleton of SATP is a subset of 1-skeleton of \(SATP_{LP}\)). However, unlike BQP, not all vertices of SATP are pairwise adjacent, the diameter of SATP equals 2, and the clique number of 1-skeleton is superpolynomial in dimension. It is known that the fractional vertices of \(BQP_{LP}\) are half-integral (0, 1 or 1/2 valued). We establish that the denominators of \(SATP_{LP}\) fractional vertices can take any integer values.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

über 102.000 Bücher
über 537 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Finance + Banking
Management + Führung
Marketing + Vertrieb
Maschinenbau + Werkstoffe
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 390 Zeitschriften

aus folgenden Fachgebieten:

Automobil + Motoren
Bauwesen + Immobilien
Business IT + Informatik
Elektrotechnik + Elektronik
Energie + Nachhaltigkeit
Maschinenbau + Werkstoffe

Jetzt Wissensvorsprung sichern!

inform now

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

über 67.000 Bücher
über 340 Zeitschriften

aus folgenden Fachgebieten:

Bauwesen + Immobilien
Business IT + Informatik
Finance + Banking
Management + Führung
Marketing + Vertrieb
Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

inform now

previous chapter Fast Numerical Evaluation of Periodic Solutions for a Class of Nonlinear Systems and Its Applications for Parameter Estimation Problems

next chapter On Accuracy Estimates for One Regularization Method in Linear Programming

Aguilera, N.E., Katz, R.D., Tolomei, P.B.: Vertex adjacencies in the set covering polyhedron. Discrete Appl. Math. 218, 40–56 (2017). https://doi.org/10.1016/j.dam.2016.10.024MathSciNetCrossRefMATH

Avis, D.: On the extreme rays of the metric cone. Can. J. Math. 32, 126–144 (1980)MathSciNetCrossRef

Barahona, F.: On cuts and matchings in planar graphs. Math. Program. 60(1–3), 53–68 (1993). https://doi.org/10.1007/BF01580600MathSciNetCrossRefMATH

Bondarenko, V.A., Uryvaev, B.V.: On one problem of integer optimization. Automat. Rem. Contr. 68(6), 948–953 (2007). https://doi.org/10.1134/S0005117907060021CrossRefMATH

Bondarenko, V.A., Maksimenko, A.N.: Geometricheskie konstruktsii i slozhnost’ v kombinatornoy optimizatsii (Geometric constructions and complexity in combinatorial optimization), LKI (2008). (Russian)

Bondarenko, V., Nikolaev, A.: On graphs of the cone decompositions for the min-cut and max-cut problems. Int. J. Math. Sci. 2016, article ID 7863650 (2016). https://doi.org/10.1155/2016/7863650

Bondarenko, V.A., Nikolaev, A.V.: On the skeleton of the polytope of pyramidal tours. J. Appl. Ind. Math. 12(1), 9–18 (2018). https://doi.org/10.1134/S1990478918010027CrossRefMATH

Bondarenko, V.A., Nikolaev, A.V., Symanovich, M.E., Shemyakin, R.O.: On a recognition problem on cut polytope relaxations. Automat. Rem. Contr. 75(9), 1626–1636 (2014). https://doi.org/10.1134/S0005117914090082MathSciNetCrossRefMATH

Chegireddy, C.R., Hamacher, H.W.: Algorithms for finding K-best perfect matchings. Discrete Appl. Math. 18(2), 155–165 (1987). https://doi.org/10.1016/0166-218X(87)90017-5MathSciNetCrossRefMATH

10.

De Simone, C.: The cut polytope and the Boolean quadric polytope. Discrete Math. 79(1), 71–75 (1990). https://doi.org/10.1016/0012-365X(90)90056-NMathSciNetCrossRefMATH

11.

Deza, A., Fukuda, K., Pasechnik, D., Sato, M.: On the Skeleton of the metric polytope. In: Akiyama, J., Kano, M., Urabe, M. (eds.) JCDCG 2000. LNCS, vol. 2098, pp. 125–136. Springer, Heidelberg (2001). https://doi.org/10.1007/3-540-47738-1_10CrossRef

12.

Deza, M.M., Laurent, M.: Geometry of Cuts and Metrics. AC, vol. 15. Springer, Heidelberg (1997). https://doi.org/10.1007/978-3-642-04295-9CrossRefMATH

13.

Fiorini, S., Massar, S., Pokutta, S., Tiwary, H.R., De Wolf, R.: Exponential lower bounds for polytopes in combinatorial optimization. J. ACM. 62(2), 1–17 (2015). https://doi.org/10.1145/2716307MathSciNetCrossRefMATH

14.

Grishukhin, V.P.: Computing extreme rays of the metric cone for seven points. Eur. J. Combin. 13(3), 153–165 (1992). https://doi.org/10.1016/0195-6698(92)90021-QMathSciNetCrossRefMATH

15.

Kaibel, V., Weltge, S.: A short proof that the extension complexity of the correlation polytope grows exponentially. Discrete Comput. Geom. 53(2), 397–401 (2015). https://doi.org/10.1007/s00454-014-9655-9MathSciNetCrossRefMATH

16.

Laurent, M.: Graphic vertices of the metric polytope. Discrete Math. 151(1–3), 131–153 (1996). https://doi.org/10.1016/0012-365X(94)00091-VMathSciNetCrossRefMATH

17.

Matsui, T., Tamura, S.: Adjacency on combinatorial polyhedra. Discrete Appl. Math. 56(2–3), 311–321 (1995). https://doi.org/10.1016/0166-218X(94)00092-RMathSciNetCrossRefMATH

18.

Maksimenko, A.N.: A special role of Boolean quadratic polytopes among other combinatorial polytopes. Model. Anal. Inform. Sist. 23(1), 23–40 (2016). https://doi.org/10.18255/1818-1015-2016-1-23-40MathSciNetCrossRef

19.

Nikolaev, A.: On integer recognition over some boolean quadric polytope extension. In: Kochetov, Y., Khachay, M., Beresnev, V., Nurminski, E., Pardalos, P. (eds.) DOOR 2016. LNCS, vol. 9869, pp. 206–219. Springer, Cham (2016). https://doi.org/10.1007/978-3-319-44914-2_17CrossRef

20.

Padberg, M.: The Boolean quadric polytope: some characteristics, facets and relatives. Math. Program. 45(1–3), 139–172 (1989). https://doi.org/10.1007/BF01589101MathSciNetCrossRefMATH

21.

Papadimitriou, C.H., Steiglitz, K.: Combinatorial Optimization: Algorithms and Complexity. Dover Publications, Mineola (1998)MATH

22.

Trubin, V.: On a method of solution of integer linear programming problems of a special kind. Sov. Math. Dokl. 10, 1544–1546 (1969)MATH

23.

Veselov, S.I., Chirkov, A.J.: Integer program with bimodular matrix. Discrete Optim. 6(2), 220–222 (2009). https://doi.org/10.1016/j.disopt.2008.12.002MathSciNetCrossRefMATH

24.

Zolotykh, N.Y.: New modification of the double description method for constructing the skeleton of a polyhedral cone. Comp. Math. Math. Phys. 52(1), 146–156 (2012). https://doi.org/10.1134/S0965542512010162MathSciNetCrossRefMATH

Title: On Vertices of the Simple Boolean Quadric Polytope Extension
Author: Andrei V. Nikolaev
Publisher: Springer International Publishing
Book: Optimization Problems and Their Applications
Print ISBN: 978-3-319-93799-1

Electronic ISBN: 978-3-319-93800-4

Copyright Year: 2018
DOI: https://doi.org/10.1007/978-3-319-93800-4_13

Springer Professional

Abstract

Please log in to get access to your license.

Dont have a licence yet? Then find out more about our products and how to get one now:

Springer Professional "Wirtschaft+Technik"

Springer Professional "Technik"

Springer Professional "Wirtschaft"

Premium Partner