Geodesic
Solving linear inequalities systems with local search algorithms
Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 136-138.

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

Here, we present a new heuristic on the basis of Balas algorithm for solving systems of linear inequalities with Boolean variables. If a branch in a solution tree leads to a false solution, then a new branch is chosen with the help of simulated annealing technique. The experimental results of fulfilled comparison of new and classical (Balas and simulated annealing) heuristics are listed. Two variants of cost function – sum and maximum – were applied in the new heuristic. The plan of experiments concerned random systems of pseudo-Boolean linear inequalities. According to the results of comparison, the new heuristic is more effective. It was applied to a system of linear inequalities that describes LFSR with a Boolean threshold output function. This system grows exponentially with the length of the output. Some methods for reducing the system size are given. In all cases, the new heuristic allows to find the solution for LFSR sometimes being different from the original.
Keywords: simulated annealing, Balas algorithm, pseudo-Boolean linear inequalities. 
@article{PDMA_2015_8_a52,
     author = {N. V. Anashkina and A. N. Shurupov},
     title = {Solving linear inequalities systems with local search algorithms},
     journal = {Prikladnaya Diskretnaya Matematika. Supplement},
     pages = {136--138},
     publisher = {mathdoc},
     number = {8},
     year = {2015},
     language = {ru},
     url = {http://geodesic.mathdoc.fr/item/PDMA_2015_8_a52/}
}
TY  - JOUR
AU  - N. V. Anashkina
AU  - A. N. Shurupov
TI  - Solving linear inequalities systems with local search algorithms
JO  - Prikladnaya Diskretnaya Matematika. Supplement
PY  - 2015
SP  - 136
EP  - 138
IS  - 8
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/PDMA_2015_8_a52/
LA  - ru
ID  - PDMA_2015_8_a52
ER  - 
%0 Journal Article
%A N. V. Anashkina
%A A. N. Shurupov
%T Solving linear inequalities systems with local search algorithms
%J Prikladnaya Diskretnaya Matematika. Supplement
%D 2015
%P 136-138
%N 8
%I mathdoc
%U http://geodesic.mathdoc.fr/item/PDMA_2015_8_a52/
%G ru
%F PDMA_2015_8_a52
N. V. Anashkina; A. N. Shurupov. Solving linear inequalities systems with local search algorithms. Prikladnaya Diskretnaya Matematika. Supplement, no. 8 (2015), pp. 136-138. http://geodesic.mathdoc.fr/item/PDMA_2015_8_a52/

[1] 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

[2] Anashkina N. V., “Obzor metodov resheniya sistem lineinykh neravenstv”, Vestnik Moskovskogo universiteta lesa. Lesnoi vestnik, 2004, no. 1(32), 144–148

[3] Kochetov Yu. A., “Veroyatnostnye metody lokalnogo poiska dlya zadach diskretnoi optimizatsii”, Diskretnaya matematika i ee prilozheniya, Sb. lektsii molodezhnykh i nauchnykh shkol po diskretnoi matematike i ee prilozheniyam, Izd-vo tsentra prikl. issled. pri mekh.-mat. fak. MGU, M., 2001, 84–117

[4] Khachiyan L. G., “Polinomialnyi algoritm v lineinom programmirovanii”, Dokl. AN SSSR, 244:5 (1979), 1033–1096 | MR

[5] Balakin G. V., Nikonov V. G., “Metody svedeniya bulevykh uravnenii k sistemam porogovykh sootnoshenii”, Obozrenie prikladnoi i promyshlennoi matematiki, 1:3 (1994), 389–401 | Zbl