Analysis of L-structure of polyhedron in the partial MAX SAT problem | Prikladnaya Diskretnaya Matematika - Applied Discrete Mathematics. 2017. № 38. DOI: 10.17223/20710410/38/9

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.