Semenov V. Bilevel and vector problems of optimization on discrete sets

Semenov V.V. Bilevel and vector problems of optimization on discrete sets. – Qualified scientific work as manuscript. Thesis for candidate degree in Physics and Mathematics; speciality 01.05.02 – mathematical modeling and computational methods. V.M. Glushkov Institute of Cybernetics of National Academy of Sciences of Ukraine, Kyiv, 2021. The problem of solvability of vector problems of lexicographic optimization is investigated, necessary and sufficient conditions of existence of solutions of the specified problems with an unbounded convex closed feasible set are established. The research is based on applying of properties of recessive cones of feasible set and cones of perspective lexicographic directions of optimization problems. The conditions for the optimality for different types of solutions of lexicographic optimization problems are established. Algorithms for solving lexicographic problems of discrete optimization by the method of cutting planes are developed and theoretically proved. A meaningful and mathematical model of the optimal distribution of transfers under given budget constraints in the form of a bilevel problem of discrete optimization is formulated. An approach to solving the optimistic formulation of a bilevel discrete optimization problem is developed, which allows to obtain approximate solutions of bilevel discrete problems using efficient local search algorithms. An algorithm for finding local solutions of a lower-level parametric problem in a bilevel problem, built based on using the method of directional neighborhood, is developed. Parallel algorithms for solving vector problems of discrete optimization based on a combination of reference point and local search methods have been developed. New models and algorithms for solving applied problems are constructed, which are described by vector problems with fuzzy given data on a combinatorial set. Models and methods of bilevel and vector discrete optimization find application in different areas from business to the modern high technologies. Key words: discrete optimization, bilevel problems, vector problems, combinatorial sets, vector criteria, conditions of solvability, conditions of optimality, integer variables, algorithms of local search, approximate algorithms.