Geodesic
Analysis and solution of discrete optimization problems with logical constraints on the base of $L$-partition approach
Prikladnaâ diskretnaâ matematika, no. 4 (2015), pp. 100-108.

Voir la notice de l'article provenant de la source Math-Net.Ru

In the paper, we analize discrete optimization problems with logical constraints based on integer linear programming models and $L$-partition approach. We obtain an upper bound for the power of any $L$-complex of the $2$-SAT polytope. The use of this evaluation allows to solve some applied problems of designing complex products by these approaches much more efficiently.
Keywords: satisfiability problem, logical constraints, integer programming
Mots-clés : $L$-partition. 
@article{PDM_2015_4_a9,
     author = {A. V. Adelshin and A. A. Kolokolov},
     title = {Analysis and solution of discrete optimization problems with logical constraints on the base of $L$-partition approach},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {100--108},
     publisher = {mathdoc},
     number = {4},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2015_4_a9/}
}
TY  - JOUR
AU  - A. V. Adelshin
AU  - A. A. Kolokolov
TI  - Analysis and solution of discrete optimization problems with logical constraints on the base of $L$-partition approach
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2015
SP  - 100
EP  - 108
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2015_4_a9/
LA  - ru
ID  - PDM_2015_4_a9
ER  - 
%0 Journal Article
%A A. V. Adelshin
%A A. A. Kolokolov
%T Analysis and solution of discrete optimization problems with logical constraints on the base of $L$-partition approach
%J Prikladnaâ diskretnaâ matematika
%D 2015
%P 100-108
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2015_4_a9/
%G ru
%F PDM_2015_4_a9
A. V. Adelshin; A. A. Kolokolov. Analysis and solution of discrete optimization problems with logical constraints on the base of $L$-partition approach. Prikladnaâ diskretnaâ matematika, no. 4 (2015), pp. 100-108. http://geodesic.mathdoc.fr/item/PDM_2015_4_a9/

[1] Kolokolov A. A., Adelshin A. V., Yagofarova D. I., “Solving SAT problem using $L$-class enumeration method”, Informatsionnye Tekhnologii, 2009, no. 2, 54–59 (in Russian)

[2] Gu J., Purdom P., Franco J., Wah B., “Algorithms for the satisfiability (SAT) problem: a survey”, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, American Mathematical Society, 1996, 19–152 | MR

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

[4] 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 Conference on Artificial Intelligence, AustAI-2002, Canberra, Australia, 2002, 603–614 | MR | Zbl

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

[6] Adelshin A. V., Kuchin A. K., “Development of algorithms for solving a mixed problem of maximal satisfiability”, Materialy V Vseross. konf. “Problemy optimizatsii i ekonomicheskie prilozheniya”, Omsk, 2012, 99 (in Russian)

[7] Kolokolov A. A., “Regular partitions and truncations in integer programming”, Sibirsk. Zh. Issled. Oper., 1994, no. 2, 18–39 (in Russian) | MR | Zbl

[8] Adelshin A. V., “Investigation of maximum and minimum satisfiability problems using $L$-partition”, Avtomat. i Telemekh., 2004, no. 3, 35–42 (in Russian) | MR | Zbl

[9] Yagofarova D. I., “Analysis of the $L$-structure for 2-SAT problem”, Materialy konf. “Pod znakom ‘Sigma’ ”, Omsk, 1994, 71–77 (in Russian)

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

[11] Cook S. A., “The complexity of theorem-proving procedure”, Proc. 3rd Annual ACM Symp. Theory of Computing, ACM, N.Y., 1971, 151–159

[12] Kolokolov A. A., Yarosh A. V., “Computer-aided design of complex products using discrete optimization and information technologies”, Omskiy nauchnyy vestnik, 2010, no. 2(90), 234–238 (in Russian)

[13] Posypkin M. A., Zaikin O. S., Bespalov D. V., Semenov A. A., “Cryptanalysis of stream ciphers in distributed computing systems”, Trudy ISA, 46, 2009, 119–137 (in Russian)

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