C&SA | Contents

Volume 61 >>> № 6 NOVEMBER — DECEMBER 2025

-->

UDC 61.681.3

S.L. Kryvyi
Taras Shevchenko National University of Kyiv, Kyiv, Ukraine,
krivoi@i.com.ua

O.V. Chugaenko
Samsung R&D Institute Ukraine LLC, Kyiv, Ukraine,
firestream_13@yahoo.com

S.M. Krasnitskiy
Kyiv National University of Technologies and Design, Kyiv, Ukraine,
krasnits.sm@ukr.net

ALGORITHMS FOR SOLVING LINEAR CONSTRAINTS IN THE SET {0, 1}

Abstract. Three algorithms for solving linear constraint systems with integer coefficients in the set (0, 1) are presented. The first algorithm has an exponential time complexity estimate, but is parallelizable. The second algorithm finds solutions by reducing the constraint system to a single linear equation. The third algorithm is a parallel combination of the first and second algorithms. Experimental results of the implemented algorithms are presented.

Keywords: linear constraints, 01-solution, algorithms.

full text

REFERENCES

1. Bockmayr A., Weispfenning V. Solving numerical constraints. In: Handbook of Automated Reasoning. Robinson J.A., Voronkov A. (Eds.). Vol. 1. Elsevier Science Publishers B.V., 2001. P. 753–842. https://doi.org/10.1016/B978-044450813-3/50014-X.
2. Kryvyi S.L. Algorithms of solution of systems of linear Diophantine constraints over the set {0, 1}. Cybernetics and Systems Analysis. 2003. Vol. 39, N 5. P. 676–685. https://doi.org/10.1023/B:CASA.0000012088.53339.a7.
3. Kryvyi S.L. Linear Diophantine constraints and their applications. Kyiv: Interservice, 2021. 257 p.
4. Clausen M., Fortenbacher A. Efficient solution of linear diophantine equations. Journal of Symbolic Computation. 1989. Vol. 8, Iss. 1–2. P. 201–216. https://doi.org/10.1016/S0747-7171(89)80025-2.
5. Cohen D., Jeavons P. The complexity of constraint languages. In: Handbook of Constraint Programming. Rossi F., van Beek P., Walsh T. (Eds.). Elsevier, 2006. P. 245–280. https://doi.org/10.1016/S1574-6526(06)80012-X
6. Contenjean E., Devie H. An efficient algorithm for solving systems of Diophantine equations. Information and Computation. 1994. Vol. 113, Iss. 1. P. 143–172. https://doi.org/10.1006/inco.1994.1067.
7. Contejean E., Ajili F. Avoiding slack variables in the solving of linear Diophantine equations and inequations. Theoretical Computer Science. 1997. Vol. 173, Iss. 1. P. 183–208. https://doi.org/10.1016/S0304-3975(96)00195-8
8. Papadimitriou Ch.H. Zlozonosc obliczeniowa. Warszawa: Wydawnictwo Naukowo-Techniczne, 2002. 539 s.