Subclasses of solvable problems from classes of combinatorial optimization problems
- PDF / 127,564 Bytes
- 8 Pages / 595.276 x 793.701 pts Page_size
- 79 Downloads / 193 Views
SUBCLASSES OF SOLVABLE PROBLEMS FROM CLASSES OF COMBINATORIAL OPTIMIZATION PROBLEMS
UDC 519.11.176
N. K. Timofeeva
Well-known subclasses of solvable problems from classes of combinatorial optimization are reviewed. For solvable problems such as the traveling salesman problem, location problem, assignment problem, and clustering problem, the changes in the objective function on a given ordering of combinatorial configurations are analyzed. Keywords: solvable problems, combinatorial optimization, combinatorial configuration, objective and combinatorial functions. INTRODUCTION The paper reviews well-known and new (obtained by the author) subclasses of solvable problems from classes of combinatorial optimization problems. Solvable problems are meant a certain subclass of problems for which there is an analytic method to find the optimal solution without enumeration of alternatives. Subclasses of solvable problems from combinatorial optimization classes are considered; they are mathematical models of such applied problems as the traveling salesman problem, assignment problem, location of objects on a given surface, and clustering. Applied problems pertaining to classes of combinatorial optimization problems are often high-dimensional. For example, designing very large-scale integrated circuits requires arrangement of tens of thousands of modules. As dimensions of these problems increases, it becomes hardly possible to find optimal solutions using methods that employ enumeration of alternatives; therefore, approximate polynomial algorithms should be developed to solve them. There are two approaches to solving combinatorial optimization problems: (a) methods and algorithms based on a partial enumeration of alternatives [1–8]; (b) methods and algorithms that involve recognition of the structure of input information. The second approach involves finding subclasses of solvable problems and developing recognition algorithms for the structure of input information corresponding to this subclasses [9–37]. An analysis of these cases stimulated research efforts to find optimal solutions without enumeration of alternatives. An analysis of classes of combinatorial optimization problems allows revealing their characteristic properties and generalizing and developing this subject area. FORMULATION OF A COMBINATORIAL OPTIMIZATION PROBLEM Combinatorial optimization problems are as a rule defined on one or several sets, for example, A = {a1 , K , a n } and B = {b1 , K , bn~ }, whose elements are of any nature. Suppose n = n~. We will call these sets base ones. There are two types of problems. In the first type, each of these sets, A and B, can be represented as a graph whose nodes are elements of a given set and each edge is associated with a number (edge weight) c st Î R ( R is the set of real numbers), i.e., there are constraints among elements a s , a t Î A (or a s Î A , bt Î B ), and their numerical values are called weights. We will call c st the input data International Research and Training Center for Information Technologies a
Data Loading...
