ON A SUCCESS RATE OF INTERNAL POINT ALGORITHM FOR SOLVING SYSTEMS OF LINEAR INEQUALITIES WITH BOOLEAN VARIABLES
( Pp. 48-56)
More about authors
Manyaev Gleb Olegovich
sotrudnik
FEMA (Federal Educational Methodical Association) in the system of higher education on Information security Shurupov Andrei Nikolaevich sotrudnik
FEMA (Federal Educational Methodical Association) in the system of higher education on Information security
FEMA (Federal Educational Methodical Association) in the system of higher education on Information security Shurupov Andrei Nikolaevich sotrudnik
FEMA (Federal Educational Methodical Association) in the system of higher education on Information security
Abstract:
The interior point method (Karmarkar’s method [1]) is well known for its solution of the continuous problem of linear programming. 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 following return to Boolean solution. In our algorithm a system’s coefficients linear function was chosen instead of the system discrepancy, which is traditionally used as an objective function. Experimental analysis showed that reliability of the algorithm is about 86 %. This value is higher than the reliability (77 & 85%) of other heuristic algorithms, applied to the same problem [2; 3]. As the result of experimental research, we found some classes of systems of inequalities, which are solved by different algorithms with significantly different reliabilities. These results allow of recommending the developed algorithm for addition to the class of heuristics, oriented on the researched problem. The drawback of the developed algorithm is relatively long working time.
How to Cite:
Manyaev G.O., Shurupov A.N., (2018), ON A SUCCESS RATE OF INTERNAL POINT ALGORITHM FOR SOLVING SYSTEMS OF LINEAR INEQUALITIES WITH BOOLEAN VARIABLES. Computational Nanotechnology, 4 => 48-56.
Reference list:
Karmarkar N. A new polynomial-time algorithm for linear programming // Combinatorica. 1984. № 4. Rp. 373-395.
Anashkina N.V., SHurupov A.N. Eksperimental noe sravnenie algoritmov Balasha i imitatsii otzhiga v zadache resheniya sistem lineynykh neravenstv // Prikladnaya diskretnaya matematika. Prilozhenie. Trudy Vserossiyskoy konferentsii SIBECRYPT 14. № 7. Tomskiy gosudarstvennyy universitet, 2014. S. 151-153.
Anashkina N.V., SHurupov A.N. Primenenie algoritmov lokal nogo poiska k resheniyu sistem psevdobulevykh lineynykh neravenstv. // Prikladnaya diskretnaya matematika. Prilozhenie. 2015. № 8. S. 136-138.
Balakin G.V., Nikonov V.G. Metody svedeniya bulevykh uravneniy k sistemam porogovykh sootnosheniy // Obozrenie prikl. promyshl. matem. Ser.: Diskret, matem. . 1994. T. 1. № 3. S. 389-401.
Nikonov V.G. Porogovye predstavleniya bulevykh funktsiy // Obozrenie prikl. promyshl. matem. Ser.: Diskret. matem. . 1994. T. 1. № 3. S. 402-457.
CHernikova N.V. Algoritm dlya nakhozhdeniya obshchey formuly neotritsatel nykh resheniy sistemy lineynykh neravenstv // ZH. vychisl. matem. i matem. fiziki. 1965. 5. № 2. S. 334-337.
KHachiyan L.G. Izbrannye trudy. M.: MTSNMO, 2009.
Burdelev A.V., Nikonov V.G., Lapikov I.I. Raspoznavanie parametrov uzla zashchity informatsii, realizovannogo porogovoy k-znachnoy funktsiey // Trudy SPIIRAN. 2016. Vyp. 46. C. 108-127.
Anashkina N.V., SHurupov A.N. Eksperimental noe sravnenie algoritmov Balasha i imitatsii otzhiga v zadache resheniya sistem lineynykh neravenstv // Prikladnaya diskretnaya matematika. Prilozhenie. Trudy Vserossiyskoy konferentsii SIBECRYPT 14. № 7. Tomskiy gosudarstvennyy universitet, 2014. S. 151-153.
Anashkina N.V., SHurupov A.N. Primenenie algoritmov lokal nogo poiska k resheniyu sistem psevdobulevykh lineynykh neravenstv. // Prikladnaya diskretnaya matematika. Prilozhenie. 2015. № 8. S. 136-138.
Balakin G.V., Nikonov V.G. Metody svedeniya bulevykh uravneniy k sistemam porogovykh sootnosheniy // Obozrenie prikl. promyshl. matem. Ser.: Diskret, matem. . 1994. T. 1. № 3. S. 389-401.
Nikonov V.G. Porogovye predstavleniya bulevykh funktsiy // Obozrenie prikl. promyshl. matem. Ser.: Diskret. matem. . 1994. T. 1. № 3. S. 402-457.
CHernikova N.V. Algoritm dlya nakhozhdeniya obshchey formuly neotritsatel nykh resheniy sistemy lineynykh neravenstv // ZH. vychisl. matem. i matem. fiziki. 1965. 5. № 2. S. 334-337.
KHachiyan L.G. Izbrannye trudy. M.: MTSNMO, 2009.
Burdelev A.V., Nikonov V.G., Lapikov I.I. Raspoznavanie parametrov uzla zashchity informatsii, realizovannogo porogovoy k-znachnoy funktsiey // Trudy SPIIRAN. 2016. Vyp. 46. C. 108-127.
