Suscripción a Biblioteca: Guest
SJR: 0.275 SNIP: 0.59 CiteScore™: 0.8

ISSN Imprimir: 1064-2315
ISSN En Línea: 2163-9337

# Journal of Automation and Information Sciences

DOI: 10.1615/JAutomatInfScien.v51.i7.10
pages 1-23

## Algorithms for Solving the Systems of Linear Constraints with Integer Coefficients in the Set {0, 1}

Sergey L. Kryvyi
Kiev National Taras Shevchenko University, Kiev
Vasiliy T. Antonyuk
Kiev National Taras Shevchenko University, Kiev

### SINOPSIS

The basis concepts of linear homogeneous and inhomogeneous equations and inequalities in the domain {0, 1} are considered, the properties of the TSS-algorithm, which may be applied for solving those systems are described. The procedures for clearing the sets of solutions and determining the linearly dependent equations of the system during the process of the TSS-algorithm are shown. Based on the basis concepts and properties, a modification of the TSS-algorithm for solving systems of linear homogeneous equations and inequalities with integer coefficients in the domain {0, 1}, sufficiently economical relatively to memory, is offered. A description of the proposed algorithm using pseudo-code and an estimate of the time complexity are given. Algorithms for solving a separate class of systems of linear homogeneous equations and inequalities whose coefficients belong to the set {-1, 0, 1} are considered. A series of theorems that prove the correctness of the proposed algorithms are given. It is described their application to the following problems: finding the sets of independent vertices of an undirected graph; finding deadlocks and traps in the Petri net; analysis of multiple disjunctions for contradiction/consistency. For the task of finding sets of independent vertices of an undirected graph, a detailed description of reducing the problem to a system of linear homogeneous inequalities is given, two solution algorithms are proposed, as well as a modification of the second algorithm. Examples with a detailed explanation of the solution via each of the algorithms are given and their time characteristics of work are described. For problems of finding deadlocks and traps in the Petri net, a method for reducing it to systems of linear inequalities with coefficients in the set {-1, 0, 1} and solutions in the set {0, 1} is proposed. An example with the solution explanation and time characteristics of the work of the offered algorithm is described. The algorithm for analyzing the set of disjunctions for inconsistency is presented in a pseudo-code form. In addition to checking for the inconsistency of a given set of disjunctions, it allows one to find the minimal inconsistent subsets of disjunctions if they exist. The operation of the algorithm is illustrated with examples with time characteristics.

### REFERENCIAS

1. Kryvyi S.L., Linear Diophantine restrictions and their application [in Ukrainian], Bukrek, Chernovtsy, Kiev, 2015. .

2. Gross J.L., Yellen J., Handbook of graph theory, CRC Press, 2004, 1, Chap. 5 (Independent Sets and Cliques), 389-402. .

3. Kryvyi S.L., Antonyuk V.T., Implementation of an algorithm for solving a system of linear Diophantine equations in a residue ring, Upravlyayushchiye sistemy i mashiny, 2017, No. 6, 55-64. .

4. Wikipedia. Petersen generalized graph. .

5. Christofides N., Theory of graphs, Algorithmic approach, [Russian translation], Mir, Moscow, 1978. .

6. Murata T., Petri nets: Properties, analysis and applications, Proc. of the IEEE, 1989, 77, No. 4, 541-580. .

7. Ross K., Wright C.R.B., Discrete mathematics, 4-th ed., Upper Saddle River, Prentice-Hall, New York, 1999. .

### Articles with similar content:

Analytical Synthesis of the Probabilistic Characteristics of One Class of Non-Markovian Processes
Journal of Automation and Information Sciences, Vol.31, 1999, issue 4-5
Sergey V. Sokolov
The Concept of Nonlinear Trade-Off Schemes in Multicriteria Problems
Journal of Automation and Information Sciences, Vol.48, 2016, issue 11
Albert N. Voronin
Equations for the Survival Probability of an Insurance Company in the (B, S)-market Taking into Account Advertising
Journal of Automation and Information Sciences, Vol.46, 2014, issue 1
Boris V. Bondarev, Valeria O. Boldyreva
Properties of LSM-Estimator of Correlation Function of Biperiodically Correlated Random Processes
Journal of Automation and Information Sciences, Vol.52, 2020, issue 6
Oxana Yu. Dzeryn , Pavel A. Semenov , Igor N. Javorskyj , Roman M. Yuzefovych
Uniform Approximations by the Poisson Threeharmonic Integrals on the Sobolev Classes
Journal of Automation and Information Sciences, Vol.51, 2019, issue 12
Ulyana Z. Hrabova