The purpose of the work is to develop models and algorithms for optimizing matching in dynamically generated graphs of asymmetric relations in coordinated open systems of interacting agents with ...centralized and collective control. The dynamic asymmetric matching optimization problem arises here as a result of a compromise approximation of the mapping of the dynamic programming method onto a stream of known open assignment problems or several traveling salesmen. However, the branching alternatives presented in this way for independent tasks do not take into account the interdependence of real relationships between agents and their tasks, including their relationship to time. Ignoring the dependence of branching alternatives leads to a delay in the moment or to a loss in the quality of assignment of tasks to coordinated agents. The main idea of the proposed implementation of the principle known for effective control is to postpone the moment the final decision is made to the latest moment, taking into account the susceptibility of the system to local changes in state variables. The interdependence of states is revealed on the basis of the analysis of the correspondence of the graph of the current matching with the optimal solution on the subgraph of perfect matching. The transition between states is implemented by the incremental version of the reoptimization algorithm for solving linear problems of assigning the shortest replenishing path using the method. The space of search states is a dynamically generated bipartite sparse graph of alternatives for a combination of agents and tasks, represented by a list of arcs. To highlight the sets of changed arcs, it is proposed to supplement the weight of the arcs with the boundaries of the stability intervals of the solution, optionally formed in the background. By default, the weight of the modified arc matches the boundary of the stability interval. On each correction cycle of the lists of agents, tasks, and their associations, subsets of elements are selected for which reconsideration of matching is required. An enhanced condition for the selection of such elements is to go beyond the boundaries of the stability interval. In this case, the asymmetry of the assignment problem is taken into account by choosing the adjacency structure for the fraction of the graph with a minimum of vertices. As a result, the reaction time of procedures for solving the assignment problem is reduced by an order of magnitude.
An efficient polynomial time algorithm for solving maximum flow problems in directed networks has been proposed in this paper. The algorithm is basically based on successive divisions of capacities ...by multiples of two; it solves the maximum flow problem as a sequence of O(m) shortest path problems on residual networks with n nodes and m arcs. It runs in O(m2 r) time, where r is the smallest integer greater than or equal to log B, and B is the largest arc capacity of the network. A numerical example has been illustrated using this proposed algorithm.
In this paper, the binary representation of arc capacity has been used in developing an efficient polynomial time algorithm for the constrained maximum flow problem in directed networks. The ...algorithm is basically based on solving the maximum flow problem as a sequence of O(n2) shortest path problems on residual directed networks with n nodes generated during iterations. The complexity of the algorithm is estimated to be no more than O(n2mr) arithmetic operations, where m denotes the number of arcs in the network, and r is the smallest integer greater than or equal to log B (B denotes the largest arc capacity in the directed network). Generalization of the algorithm has been also performed in order to solve the maximum flow problem in a directed network subject to non-negative lower bound on the flow vector. A formulation of the simple transportation problem, as a maximal network flow problem has been also performed. Numerical example has been inserted to illustrate the use of the proposed algorithm.
A polynomial time algorithm for solving the minimum-cost network flow problem has been proposed in this paper. This algorithm is mainly based on the binary representation of capacities; it solves the ...minimum-cost flow problem in directed graph of n nodes and m directed arcs as a sequence of O(n2) shortest path problems on residual networks. The algorithm runs in O(n2mr) time, where r is the smallest integer greater than or equal to Log2B, and B is the largest arc capacity of the network. A generalization of this proposed algorithm has been also performed in order to solve the minimum-cost flow problem in a directed network subject to non-negative lower bound on the flow vector. A formulation of both the transportation and the assignment problems, as a minimal cost network flow problem has been also performed. A numerical example has been inserted to illustrate the use of the proposed method.
PDF
