Geodesic
On effectiveness of solving pseudo-Boolean systems of linear inequalities by simulated annealing, Balas algorithm and interior point algorithm
Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 218-227.

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

The aim of this paper is the development and reliability research of the algorithm for solving systems of linear inequalities with Boolean variables, based on variables relaxation, application of the internal point method and the consequent return to Boolean solution. Experimental analysis shows that reliability of the algorithm is about 86 %. This value is higher than the reliability of other heuristic algorithms, applied to the same problem. As the result of experimental research, we have found some classes of systems of inequalities, which are solved by different algorithms with the significantly different reliabilities.
Keywords: pseudo Boolean linear inequalities, interior point method, relaxation, linear programming. 
@article{PDMA_2019_12_a60,
     author = {G. O. Manyaev and A. N. Shurupov},
     title = {On effectiveness of solving {pseudo-Boolean} systems of linear inequalities by simulated annealing, {Balas} algorithm and interior point algorithm},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {218--227},
     publisher = {mathdoc},
     number = {12},
     year = {2019},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2019_12_a60/}
}
TY  - JOUR
AU  - G. O. Manyaev
AU  - A. N. Shurupov
TI  - On effectiveness of solving pseudo-Boolean systems of linear inequalities by simulated annealing, Balas algorithm and interior point algorithm
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2019
SP  - 218
EP  - 227
IS  - 12
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2019_12_a60/
LA  - ru
ID  - PDMA_2019_12_a60
ER  - 
%0 Journal Article
%A G. O. Manyaev
%A A. N. Shurupov
%T On effectiveness of solving pseudo-Boolean systems of linear inequalities by simulated annealing, Balas algorithm and interior point algorithm
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2019
%P 218-227
%N 12
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2019_12_a60/
%G ru
%F PDMA_2019_12_a60
G. O. Manyaev; A. N. Shurupov. On effectiveness of solving pseudo-Boolean systems of linear inequalities by simulated annealing, Balas algorithm and interior point algorithm. Prikladnaya Diskretnaya Matematika. Supplement, no. 12 (2019), pp. 218-227. http://geodesic.mathdoc.fr/item/PDMA_2019_12_a60/

[1] Balakin G. V., Nikonov V. G., “Metody svedeniya bulevykh uravnenii k sistemam porogovykh sootnoshenii”, Obozrenie prikl. promyshl. matem. Ser. diskret. matem., 1:3 (1994), 389–401 | Zbl

[2] Nikonov V. G., “Porogovye predstavleniya bulevykh funktsii”, Obozrenie prikl. promyshl. matem. Ser. diskret. matem., 1:3 (1994), 402–457 | MR | Zbl

[3] Chernikova N. V., “Algoritm dlya nakhozhdeniya obschei formuly neotritsatelnykh reshenii sistemy lineinykh neravenstv”, Zhurn. vychisl. matem. i matem. fiziki, 5:2 (1965), 334–337

[4] Khachiyan L. G., Izbrannye trudy, MTsNMO, M., 2009

[5] Karmarkar N., “A new polynomial-time algorithm for linear programming”, Combinatorica, 1984, no. 4, 373–395 | DOI | MR | Zbl

[6] Burdelev A. V., Nikonov V. G., Lapikov I. I., “Raspoznavanie parametrov uzla zaschity informatsii, realizovannogo porogovoi k-znachnoi funktsiei”, Trudy SPIIRAN, 46 (2016), 108–127

[7] Anashkina N. V., Shurupov A. N., “Eksperimentalnoe sravnenie algoritmov Balasha i imitatsii otzhiga v zadache resheniya sistem lineinykh neravenstv”, Prikladnaya diskretnaya matematika. Prilozhenie, 2014, no. 7, 151–153

[8] Anashkina N. V., Shurupov A. N., “Primenenie algoritmov lokalnogo poiska k resheniyu sistem psevdobulevykh lineinykh neravenstv”, Prikladnaya diskretnaya matematika. Prilozhenie, 2015, no. 8, 136–138