Giorgi Bolotashvili

In this paper, a survey of the results is given, giving a polynomial algorithm for the NP hard of linear ordering problem. We consider the linear ordering problem as an integer linear programming problem. Solving the linear programming problem and obtaining a non-integer solution, we find all the necessary cutting facets using a polynomial algorithm and with the obtained facets we again solve the linear programming problem. This approach to solving the problem continues until now until we get an integer solution. Every time we can find all the necessary facets using a polynomial algorithm. Therefore we obtain a polynomial algorithm for solving the linear ordering problem.

The program of admission of applicants to universities at passing state exams has been partially studied. It has been proven that the recruitment of applicants to higher education institutions and the distribution of grants occurs with significant errors. A way to solve this problem is also given.

The (m,k) facts were constructed only for the following values m=τk-1,τ≥2,k≥2, by Bolotashvili in 1987. Naturally, the question arises, how will the faces (m,k) look like for other values of m? A partial answer to this question is given in this article, (m,k) facts are constructed for the following values m=τk,τ≥2,k≥2.

Is it possible to construct a polyhedron, using linear equalities and inequalities, corresponding to some NP-hard problem? This question is relevant to the author. In this paper, for the NP-hard linear order polytope, a new class of facets is built. In 1987 we built the so-called (m, k) facets, where m = tk − 1. When these facets are expanded, below certain values of T and k, we obtain fundamentally different facets from each other. Therefore, given the difference and the complexity of individual classes of cells, they are studied separately. When k ≥ 3, k is odd, t = 3, Bolotashvili G., Demidenko V., Pisaruk N. built the facet in 2014; when k ≥ 3, k is odd, t ≥ 4, Kovalev M., Bolotashvili G. built the facet in 2012; when k ≥ 4, k is even, t = 3, the facet is built in this work. Also facets are built separately: when k ≥ 5, k is odd, t = 3; when k ≥ 5, k is odd, T ≥ 4; and when k ≥ 4, k is even, T ≥ 4.

The construction of facets for a polyhedron of linear orders is built in two stages, the first stage is the construction of facets using graphs, and the second stage is to write facets in the form of linear inequalities. In this article, the first stage has been implemented.

The construction of a polytope of an NP-hard problem using linear inequalities, and then using them to solve the problem is our main task. This work is devoted to this problem. For a non-integer vertex of the relaxation polytope of the problem of linear orders, we find adjacent integer vertices and use them to uniquely determine the facets.

For the of linear ordering problem a class of non-integer vertices is studied, with the help of which facets are written out.

The construction of facets for a polyhedron of linear orders is built in two stages, the first stage is the construction of facets using graphs, and the second stage is to write facets in the form of linear inequalities. In this article, the first stage has been implemented.

For simple non-integer vertices of the relaxation polytope of the linear ordering problem, we find neighboring integer vertices and to build facets.

For the polytope of the linear ordering problem constructed new class of facets

Described properties of some non-integer vertices of the relaxation polytope for the linear ordering problem

Studied some non-integer vertices of the relaxation polytope for the linear ordering problem and their integer vertices.

For the the NP-hard linear ordering problem construct about 10 classes of facets [1,...,6], where each class contains exponential number facets. Therefore our aim can be formulated as follows: by solving linear ordering problem step-by-step we construct needed facets by a polynomial algorithm. Consequently, is studied in this article the examples of non-integer vertices of the relaxation polytope of the linear ordering problem.

Doctoral Thesis Referee

Master Theses Supervisor

Doctoral Thesis Supervisor/Co-supervisor

Scientific editor of monographs in foreign languages

Scientific editor of a monograph in Georgian

Editor-in-Chief of a peer-reviewed or professional journal / proceedings

Review of a scientific professional journal / proceedings

Member of the editorial board of a peer-reviewed scientific or professional journal / proceedings

Participation in a project / grant funded by an international organization

Participation in a project / grant funded from the state budget

Patent authorship

Membership of the Georgian National Academy of Science or Georgian Academy of Agricultural Sciences

Membership of an international professional organization

Membership of the Conference Organizing / Program Committee

National Award / Sectoral Award, Order, Medal, etc.

Honorary title

Monograph

Handbook

Research articles in high impact factor and local Scientific Journals

Publication in Scientific Conference Proceedings Indexed in Web of Science and Scopus