Analysis of $L$-structure of polyhedron in the partial MAX SAT problem

A. V. Adelshin ; A. K. Kuchin

Prikladnaâ diskretnaâ matematika, no. 4 (2017), pp. 110-118.

Résumé

In many decision-making problems, related to design, planning, management etc., the logical constraints are used. These constraints are often described in the terms of mathematical logic and lead to the satisfiability problem (SAT) and its generalizations. Most known problems are the maximum satisfiability problem (MAX SAT) and the partial maximum satisfiability problem. The latter problem includes two types of constraints that are used: the “hard” constraints (that should be satisfied anyway) and the “soft” constraints (that can be violated under certain conditions). In this paper, we analyze the partial maximum satisfiability problem as discrete optimization problem based on integer linear programming models and $L$-partition approach. In previous papers, estimates of the cardinality of $L$-complexes of polyhedrons of the SAT and the MAX SAT problems were obtained. In this paper, we prove a new property of the polyhedron of the partial MAX SAT problem, namely a relation of cardinality of the $L$-complexes of the indicated problem and the corresponding SAT problem is obtained. Using this result, it is possible to obtain theoretical estimates of the cardinality of the $L$-complex of the polyhedron of the partial MAX SAT problem on the basis of similar estimates for the SAT and the MAX SAT problems. In particular, it is established that if hard constraints form an instance of $2$-SAT problem, then the cardinality of any $L$-complex of the partial MAX SAT problem does not exceed $n-1$. In addition, we can construct families of logical formulas for which the cardinality of $L$-complex of the polyhedron of partial MAX SAT problem grows exponentially with increasing number of variables in the formulas.

Détail

Keywords: logical constraints, partial maximum satisfiability problem, integer programming
Mots-clés : $L$-partition.

Bibliographie

[1] Kolokolov A. A., Yarosh A. V., “Automation of designing complex products using discrete optimization and information technology”, Omsk Scientific Bulletin, 2010, no. 2(90), 234–238 (in Russian)

[2] Posypkin M. A., Zaikin O. S., Bespalov D. V., Semenov A. A., “Solving the problems of cryptanalysis of stream ciphers in distributed computing environments”, Proc. ISA RAS, 46, 2009, 119–137 (in Russian)

[3] Massacci F., Marraro L., “Logical cryptanalysis as a SAT problem”, J. Automated Reasoning, 24 (2000), 165–203 | DOI | MR | Zbl

[4] Marathe M. V., Ravi S. S., “On approximation algorithms for the minimum satisfiability problem”, Inform. Proc. Lett., 58 (1996), 23–29 | DOI | MR | Zbl

[5] Zaikin O. S., Otpushchennikov I. V., Semenov A. A., “Application of the SAT approach to the solution of the quadratic assignment problem”, 15th Baikal Intern. School-Seminar on Optimization Methods and their Applications, Irkutsk, 2011, 111–116 (in Russian)

[6] Kolokolov A. A., Adelshin A. V., Yagofarova D. I., “Solving the SAT problem using the $L$-partition approach”, Information Technologies, 2009, no. 2, 54–59 (in Russian)

[7] Gu J., Purdom P., Franco J., Wah B., “Algorithms for the satisfiability (SAT) problem: a survey”, DIMACS Series in Discr. Math. and Theor. Comput. Sci., 35 (1996), 19–152 | MR

[8] Hamadi Y., Jabbour S., Sais L., “ManySAT: a parallel SAT solver”, J. Satisfiability, Boolean Modeling and Computation, 6 (2009), 245–262 | Zbl

[9] Thornton J., Bain S., Sattar A., Pham D. N., “A two level local search for MAX-SAT problems with hard and soft constraints”, Proc. 15th Australian Joint Conf. on Artificial Intelligence, AustAI-2002, Canberra, Australia, 2002, 603–614 | MR | Zbl

[10] Kolokolov A. A., Adelshin A. V., Yagofarova D. I., “Study of dicrete optimization problems with logical constraints based on regular partitions”, Prikladnaya Diskretnaya Matematika, 2013, no. 1(19), 99–109 (in Russian)

[11] Adelshin A. V., Kuchin A. K., “Development of algorithms for solving the partial MAX SAT problem”, V Russian Conf. “Optimization Problems and their Economical Applications”, Omsk, 2012, 99 (in Russian)

[12] Kolokolov A. A., “Regular partitions and cuts in integer programming”, Siberian J. Operations Research, 1:2 (1994), 18–39 (in Russian) | MR | Zbl

[13] Adel'shin A. V., “Investigation of maximum and minimum satisfiability problems using $L$-partition”, Automation and Remote Control, 65:3 (2004), 388–395 | DOI | MR | Zbl

[14] Kolokolov A., Adelshin A., Yagofarova D., “Analysis and solving SAT and MAX-SAT problems using an $L$-partition approach”, J. Math. Modeling. Algorithms, 12:2 (2013), 201–212 | MR | Zbl

[15] Kolokolov A. A., Adelshin A. V., “Analysis and solving discrete optimization problems with logical constraints on the basis of the $L$-partition approach”, Prikladnaya Diskretnaya Matematika, 2015, no. 4(30), 100–108 (in Russian) | DOI