A New Algorithm for Solving a Special Matching Problem with a General Form Value Function under Constraints
- Authors: Uzhegov D.V.1, Anan’ev A.A.1, Lomovitskii P.V.1, Khlyupin A.N.1
-
Affiliations:
- MIPhT Engineering Center for Hard to Recover Minerals
- Issue: Vol 80, No 1 (2019)
- Pages: 81-92
- Section: Control in Technical Systems
- URL: https://journals.rcsi.science/0005-1179/article/view/151261
- DOI: https://doi.org/10.1134/S0005117919010077
- ID: 151261
Cite item
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.
About the authors
D. V. Uzhegov
MIPhT Engineering Center for Hard to Recover Minerals
Author for correspondence.
Email: denis.uzhegov@phystech.edu
Russian Federation, Moscow
A. A. Anan’ev
MIPhT Engineering Center for Hard to Recover Minerals
Email: denis.uzhegov@phystech.edu
Russian Federation, Moscow
P. V. Lomovitskii
MIPhT Engineering Center for Hard to Recover Minerals
Email: denis.uzhegov@phystech.edu
Russian Federation, Moscow
A. N. Khlyupin
MIPhT Engineering Center for Hard to Recover Minerals
Email: denis.uzhegov@phystech.edu
Russian Federation, Moscow
Supplementary files
