Abstract:
We consider the assignment problem with a special structure with a general form value function and constraints prohibiting certain matchings. In this case, the matching cost may be undefined until some permutation is found. We formulate the problem in terms of graph theory and reduce it to finding a minimal cost path in a graph with nonlocal edge weights. The proposed method for solving the problem is a modification of the Dijkstra’s shortest path algorithm in a weighted directed graph. This research is motivated by well drilling applications. We also show the analysis of our numerical experiments.
Keywords:quadratic assignment problem, invalid matchings, shortest path in a graph, Dijkstra's algorithm.
Presented by the member of Editorial Board:A. A. Lazarev