A New Algorithm for Solving a Special Matching Problem with a General Form Value Function under Constraints


Cite item

Full Text

Open Access Open Access
Restricted Access Access granted
Restricted Access Subscription Access

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

Supplementary Files
Action
1. JATS XML

Copyright (c) 2019 Pleiades Publishing, Inc.