Solving inverse spanning tree problems through network flow techniques

作     者：Sokkalingam, PT Ahuja, RK Orlin, JB 

作者机构：CISCO CDC Ctr HCL Chennai India Univ Florida Gainesville FL 32611 USA MIT Cambridge MA 02139 USA 

出 版 物：《OPERATIONS RESEARCH》 (运筹学)

年 卷 期：1999年第47卷第2期

页      面：291-298页

核心收录：

学科分类：1201[管理学-管理科学与工程(可授管理学、工学学位)] 07[理学] 070104[理学-应用数学] 0701[理学-数学] 

主　　题：Algorithms Mathematical vectors Transportation costs Optimal solutions Transportation Minimax Cost estimates Cost allocation Objective functions 

摘      要：Given a solution x* and an a priori estimated cost vector c, the inverse optimization problem is to identify another cost vector d so that x* is optimal with respect to the cost vector d and its deviation from c is minimum. In this paper, we consider the inverse spanning tree problem on an undirected graph G = (N, A) with n nodes and m arcs, and where the deviation between c and d is defined by the rectilinear distance between the two vectors, that is, L-1 norm. We show that the inverse spanning tree problem can be formulated as the dual of an assignment problem on a bipartite network G(0) = (N-0, A(0)) with N-0 = N-1 boolean OR N-2 and A(0) subset of or equal to N-1 x N-2. The bipartite network satisfies the property that \N-1\ = (n - 1), \N-2\ = (m - n + 1), and \A(0)\ = O(nm). In general, \N-1\ much less than \N-2\. Using this special structure of the assignment problem, we develop a specific implementation of the successive shortest path algorithm that runs in O(n(3)) time. We also consider the weighted version of the inverse spanning tree problem in which the objective function is to minimize the sum of the weighted deviations of arcs. The weighted inverse spanning tree can be formulated as the dual of the transportation problem. Using a cost scaling algorithm, this transportation problem can be solved in O(n(2) mlog(nC)) time, where C denotes the largest are cost in the data. Finally, we consider a minimax version of the inverse spanning tree problem and show that it can be solved in O(n(2)) time.