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/