Geodesic
Parallel algorithms for solving SAT-problems in application to
Numerical methods and programming, Tome 12 (2011) no. 1, pp. 205-212

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

A parallel technology that can be used to solve various problems of discrete optimization is proposed. This technology is based on a number of efficient procedures of reducing combinatorial optimization problems to SAT problems. A process of solving an optimization problem is implemented as an iterative scheme such that a SAT problem is solved at each step using various techniques of parallelization. In order to take into account the information accumulated during previous iterations, a special technique called “Incremental SAT” is used. This technique is usually applied to solve the verification problems for discrete systems. The technology proposed was tested using various combinatorial problems, in particular, the quadratic assignment problem.
Keywords: inversion of discrete functions; satisfiability problem (SAT-problem); Boolean equations; problems of combinatorial optimization. 
@article{VMP_2011_12_1_a24,
     author = {O. S. Zaikin and I. V. Otpushchennikov and A. A. Semenov},
     title = {Parallel algorithms for solving {SAT-problems} in application to},
     journal = {Numerical methods and programming},
     pages = {205--212},
     publisher = {mathdoc},
     volume = {12},
     number = {1},
     year = {2011},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/VMP_2011_12_1_a24/}
}
TY  - JOUR
AU  - O. S. Zaikin
AU  - I. V. Otpushchennikov
AU  - A. A. Semenov
TI  - Parallel algorithms for solving SAT-problems in application to
JO  - Numerical methods and programming
PY  - 2011
SP  - 205
EP  - 212
VL  - 12
IS  - 1
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/VMP_2011_12_1_a24/
LA  - ru
ID  - VMP_2011_12_1_a24
ER  - 
%0 Journal Article
%A O. S. Zaikin
%A I. V. Otpushchennikov
%A A. A. Semenov
%T Parallel algorithms for solving SAT-problems in application to
%J Numerical methods and programming
%D 2011
%P 205-212
%V 12
%N 1
%I mathdoc
%U http://geodesic.mathdoc.fr/item/VMP_2011_12_1_a24/
%G ru
%F VMP_2011_12_1_a24
O. S. Zaikin; I. V. Otpushchennikov; A. A. Semenov. Parallel algorithms for solving SAT-problems in application to. Numerical methods and programming, Tome 12 (2011) no. 1, pp. 205-212. http://geodesic.mathdoc.fr/item/VMP_2011_12_1_a24/