გიორგი ბოლოთაშვილი

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.

(m,k) ფასეტები აგებული იყო m ის მხოლოდ შემდეგი მნიშვნელობებისთვის m=τk-1,τ≥2,k≥2, ბოლოთაშვილის მიერ 1987 წ. ბუნებრივია ისმის კითხვა, რა სახე ექნება (m,k) ფასეტებს m–ის სხვა მნიშვნელობებისთვის? ამ კითხვას პასუხი გაეცა მოცემულ ნაშრომში ნაწილობრივ. (m,k) ფასეტები აგებულია m ის შემდეგი მნისვნელობებისთვის        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.

 წრფივი გადაადგილებების მრავალწახნაგას ფასეტების აგება ხდება ორი ეტაპი საშუალებით, პირველი ეტაპი, ეს არის ფასეტების აგება გრაფების საშუალებით, მეორე ეტაპი კი გრფი ფასეტებიდან, წრფივი უტოლობების ამოწერა. მოცემულ სტატიაში განხორციელებულია პირველი ეტაპი.

NP-სირთულის ამოცანის მრავალწახნაგას აგება წრფივი უტოლობების გამოყენებით და შემდეგ მათი გამოყენება პრობლემის გადასაჭრელად ჩვენი მთავარი ამოცანაა. ეს ნაშრომი ეძღვნება ამ პრობლემას. წრფივი გადაადგილებების ამოცანის რელაქსაციის მრავალწახნაგას არამთლიანი წვეროსთვის ჩვენ ვპოულობთ მეზობელ მთელ წვეროებს და მათ ვიყენებთ ფასეტების ცალსახად დასადგენად.

წრფივი გადაადგილებების ამოცანისთვის განხილულია რელაქსაციური მრავალწახნაგას არამთელი წვეროების კლასი, რომლების საშუალებითაც ხდება აფსეტების ამოწერა. 

წრფივი გადაადგილებების მრავალწახნაგას ფასეტების აგება ხდება ორი ეტაპი საშუალებით, პირველი ეტაპი, ეს არის ფასეტების აგება გრაფების საშუალებით, მეორე ეტაპი კი გრფი ფასეტებიდან, წრფივი უტოლობების ამოწერა. მოცემულ სტატიაში განხორციელებულია პირველი ეტაპი.

წრფივი გადაადგილებების ამოცანის რელაქსაციური მრავალწახნაგას მარტივი არამთელი წვეროებისთვის ხდება მეზობელი მთელი წვეროების მოძებნა და მათი საშუალებით კი ფასეტების ამოწერა.

წრფივი გადაადგილებების ამოცანის მრავალწახნაგასთვის აგებულია ფასეტების ახალი კლასი

აღწერილი წრფივი გადაადგილების ამოცანის რელაქსაციური მრავალწახნაგას ზოგიერთი არამთელი წვეროების თვისებები.

შესწავლილია წრფივი გადაადგილების ამოცანის რელაქსაციური მრავალწახნაგას ზოგიერთი არამთელი წვეროები და მათი მეზობელი მთელი წვეროები.

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.

დისერტაციის რეცენზირება

სამაგისტრო ნაშრომების ხელმძღვანელობა

სადოქტორო თემის ხელმძღვანელობა/თანახელმძღვანელობა

უცხოურ ენებზე მონოგრაფიის სამეცნიერო რედაქტირება

ქართულ ენაზე მონოგრაფიის სამეცნიერო რედაქტირება

რეფერირებული ან პროფესიული ჟურნალის/ კრებულის მთავარი რედაქტორობა

სამეცნიერო პროფესიული ჟურნალის/ კრებულის რეცენზენტობა

რეფერირებული სამეცნიერო ან პროფესიული ჟურნალის/ კრებულის სარედაქციო კოლეგიის წევრობა

საერთაშორისო ორგანიზაციის მიერ მხარდაჭერილ პროექტში/გრანტში მონაწილეობა

სახელმწიფო ბიუჯეტის სახსრებით მხარდაჭერილ პროექტში/ გრანტში მონაწილეობა

პატენტის ავტორობა

უფლება ქართულ ან უცხოურ სასაქონლო ნიშანზე, სასარგებლო მოდელზე

საქართველოს მეცნიერებათა ეროვნული აკადემიის ან სოფლის მეურნეობის აკადემიის წევრობა

საერთაშორისო პროფესიული ორგანიზაციის წევრობა

კონფერენციის საორგანიზაციო/ საპროგრამო კომიტეტის წევრობა

ჯილდო ეროვნული/ დარგობრივი პრემია, ორდენი, მედალი და სხვ.

საპატიო წოდება

მონოგრაფია

სახელმძღვანელო

სტატია მაღალ რეიტინგულ და ადგილობრივ ჟურნალებში

პუბლიკაცია სამეცნიერო კონფერენციის მასალებში, რომლებიც ინდექსირებულია Web of Science-ში და Scopus-ში