A Dualization Method for Some Inverse Optimization Problems

摘要

We suggest a method to solve some inverse combinatorial optimization problems which first uses optimality conditions to formulate an inverse problem as a linear programming problem, then find its dual problem and construct a suitable network model to convert the dual problem into a minimum cost circulation problem. By using this method, a class of inverse problems can be handled uniformly with a strongly polynomial complexity. In this paper we shall use the inverse minimum spanning tree problem to introduce this method.