Geodesic
Study of discrete optimization problems with logical constraints based on regular partitions
Prikladnaâ diskretnaâ matematika, no. 1 (2013), pp. 99-109.

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

Some discrete optimization problems with logical constraints are considered, and the possibility of applying these problems in complex products design is investigated. The results of the studying these problems with the use of the integer programming models and regular partitions approach are reviewed. The structure and the complexity of the problems are analysed, and the algorithms for SAT and MAX-SAT problems based on this approach are proposed.
Keywords: satisfiability problem, logical constraints, integer programming, $L$-class enumeration. 
@article{PDM_2013_1_a8,
     author = {A. A. Kolokolov and A. V. Adelshin and D. I. Yagofarova},
     title = {Study of discrete optimization problems with logical constraints based on regular partitions},
     journal = {Prikladna\^a diskretna\^a matematika},
     pages = {99--109},
     publisher = {mathdoc},
     number = {1},
     year = {2013},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDM_2013_1_a8/}
}
TY  - JOUR
AU  - A. A. Kolokolov
AU  - A. V. Adelshin
AU  - D. I. Yagofarova
TI  - Study of discrete optimization problems with logical constraints based on regular partitions
JO  - Prikladnaâ diskretnaâ matematika
PY  - 2013
SP  - 99
EP  - 109
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDM_2013_1_a8/
LA  - ru
ID  - PDM_2013_1_a8
ER  - 
%0 Journal Article
%A A. A. Kolokolov
%A A. V. Adelshin
%A D. I. Yagofarova
%T Study of discrete optimization problems with logical constraints based on regular partitions
%J Prikladnaâ diskretnaâ matematika
%D 2013
%P 99-109
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDM_2013_1_a8/
%G ru
%F PDM_2013_1_a8
A. A. Kolokolov; A. V. Adelshin; D. I. Yagofarova. Study of discrete optimization problems with logical constraints based on regular partitions. Prikladnaâ diskretnaâ matematika, no. 1 (2013), pp. 99-109. http://geodesic.mathdoc.fr/item/PDM_2013_1_a8/

[1] Kolokolov A. A., Adelshin A. V., Yagofarova D. I., “Reshenie zadachi vypolnimosti s ispolzovaniem metoda perebora $L$-klassov”, Informatsionnye tekhnologii, 2009, no. 2, 54–59 | MR

[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, AMS, Princeton, 1996, 19–152 | MR

[3] Hansen P., Jaumard B., “Algorithms for the maximum satisfiability problem”, Computing, 1990, no. 4, 279–303 | DOI | MR | 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”, AustAI-2002, Proc. 15th Australian Joint Conference on Artificial Intelligence (Canberra, Australia, 2002), 603–614 | MR | Zbl

[5] Kolokolov A. A., “Regulyarnye razbieniya i otsecheniya v tselochislennom programmirovanii”, Sib. zhurnal issledovaniya operatsii, 1994, no. 2, 18–39 | MR | Zbl

[6] Adelshin A. V., “Issledovanie zadach maksimalnoi i minimalnoi vypolnimosti s ispolzovaniem $L$-razbieniya”, Avtomatika i telemekhanika, 2004, no. 1, 35–42 | MR

[7] Kolokolov A. A., Adelshin A. V., Cheredova Yu. N., “Primenenie $L$-razbieniya k issledovaniyu nekotorykh zadach vypolnimosti”, Metody optimizatsii i ikh prilozheniya, Trudy XII Baikalskoi mezhdunar. konf. (Irkutsk, 2001), v. 1, 166–172

[8] Cook S. A., “The complexity of theorem-proving procedure”, Proc. 3rd Annual ACM Symposium on the Theory of Computing, ACM, New York, 1971, 151–159 | DOI

[9] Kolokolov A. A., Yarosh A. V., “Avtomatizatsiya proektirovaniya slozhnykh izdelii s ispolzovaniem diskretnoi optimizatsii i informatsionnykh tekhnologii”, Omskii nauchnyi vestnik, 2010, no. 2(90), 234–238 | MR

[10] Adelshin A. V., Zhovner E. N., “Primenenie zadach vypolnimosti logicheskoi formuly dlya proektirovaniya khimicheskogo sostava rezin”, Vestnik Omskogo universiteta, 2011, no. 2, 14–18

[11] Guseletova O. N., Kolokolov A. A., “Reshenie zadach diskretnoi optimizatsii s logicheskimi ogranicheniyami pri proektirovanii slozhnykh izdelii”, Avtomatika i telemekhanika, 2008, no. 10, 176–182 | MR | Zbl

[12] Kolokolov A. A., Serysheva Yu. S., Shulepova L. D., “Reshenie zadach formirovaniya malykh grupp s uchetom mezhlichnostnykh otnoshenii”, Metody optimizatsii i ikh prilozheniya, Trudy XV Baikalskoi mezhdunar. shkoly-seminara (Irkutsk, 2011), v. 5, 61–66

[13] Posypkin M. A., Zaikin O. S., Bespalov D. V., Semenov A. A., “Reshenie zadach kriptoanaliza potochnykh shifrov v raspredelennykh vychislitelnykh sredakh”, Trudy ISA, 46, 2009, 119–137

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

[15] Kolokolov A. A., Cheredova Yu. N., “Issledovanie i reshenie zadachi o vypolnimosti s ispolzovaniem $L$-razbieniya”, Diskretnyi analiz i issledovanie operatsii, Materialy mezhdunar. konf. (Novosibirsk, 2000), 150

[16] Kolokolov A. A., Adelshin A. V., Yagofarova D. I., “Algoritmy leksikograficheskogo perebora dlya resheniya zadachi vypolnimosti i nekotorykh eë obobschenii”, Metody optimizatsii i ikh prilozheniya, Trudy XIII Baikalskoi mezhdunar. shkoly-seminara (Irkutsk, 2005), v. 1, 503–508

[17] Adelshin A. V., Kuchin A. K., “Algoritmy tochnogo i priblizhennogo resheniya zadachi maksimalnoi vypolnimosti”, Omskii nauchnyi vestnik, 2011, no. 1(97), 5–9