Abstract: Three fairly universal and efficient methods of finding near-optimal solutions for NP-hard problems will be discussed in our talk and illustrated by examples of their application to scheduling problems (although, they are surely applicable to a much wider area of Discrete Optimization problems): 1. Methods of “compact” vector summation in a ball (of any norm) of minimum radius, and methods of non-strict summation of vectors in a given area of d-dimensional space. These methods are applicable to problems of finding uniform distributions of multicomponent objects. 2. Application of the maximum flow and the minimum cut algorithms to problems of finding uniform distributions of one-component objects with prescribed constraints on the distribution areas of objects. 3. The method of a gradual reduction of the feasible solutions domain.

Cite: Sevastyanov S.V.
THREE EFFICIENT METHODS OF FINDING NEAR-OPTIMAL SOLUTION FOR NP-HARD DISCRETE OPTIMIZATION PROBLEMS. (ILLUSTRATED BY THEIR APPLICATION TO SCHEDULING PROBLEMS)
International Conference Mathematical Optimization Theory and Operations Research Petrozavodsk, Karelia, Russia, July 2-6, 2022 02-08 Jul 2022