Approach to finding the optimal solution in the assignment problem (Q1364115)

Mathematical models of combinatorial optimization problems are usually represented by one or several sets of an arbitrary nature with interdependent elements. The specifics of each problem are determined by the number of such sets and the nature of interdependence among the elements. Thus, for instance, the traveling salesman problem and the assembly problem are defined by one set with a certain interrelationship among its elements; the assignment problem and the location problem are both defined by two sets, but in the former there are interrelationships among the elements of different sets while in the latter only the elements of the same set are interrelated. The objective function evaluating the solution of the problem is computed using input data that specify the interrelationship among the elements of the given sets and are represented by random variables. These properties are characteristic of combinatorial optimization problems, and they impede the development of general approaches and algorithms for their solution. In the present article, we use the particular case of the assignment problem to construct a mathematical model to which a number of combinatorial problems are reducible. This model permits applying the same algorithm to solve the assignment problem, the traveling salesman problem, and assembly problem, and the location problem.