Diagnosing infeasibilities in network flow problems

作     者：Aggarwal, CC Ahuja, RK Hao, JX Orlin, JB 

作者机构：MIT Sloan Sch Management Cambridge MA 02139 USA GTE Labs Inc Waltham MA 02154 USA Indian Inst Technol Dept Ind & Management Engn Kanpur 208016 Uttar Pradesh India IBM Thomas J Watson Res Ctr Hawthorne NY 10532 USA 

出 版 物：《MATHEMATICAL PROGRAMMING》 (数学规划)

年 卷 期：1998年第81卷第3期

页      面：263-280页

核心收录：

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

基　　金：Office of Naval Research, ONR, (NOOO14-94-1-0099) UPS Foundation 

主　　题：network flows maximum flow problem preflow-push algorithm 

摘      要：We consider the problem of finding a feasible flow in a directed network G = (N,A) in which each node i is an element of N has a supply b(i), and each are (i,j) is an element of A has a zero lower bound on flow and an upper bound u(ij). It is well known that this feasibility problem can be transformed into a maximum flow problem. It is also well known that there is no feasible how in the network G if and only if there is a subset S of nodes such that the net supplies of the nodes in S exceeds the capacity of the arcs emanating from S. Such a set S is called a witness of infeasibility (or, simply, a witness) of the network flow problem. In the case that there are many different witnesses for an infeasible problem, a small cardinality witness may be preferable in practice because it is generally easier for the user to assimilate, and may provide more guidance to the user on how to identify the cause of the infeasibility. Here we show that the problem of finding a minimum cardinality witness is NP-hard. We also consider the problem of determining a minimal witness, that is, a witness S such that no proper subset of S is also a witness. In this paper, we show that we can determine a minimal witness by solving a sequence of at most n maximum flow problems. Moreover, if we use the preflow-push algorithm to solve the resulting maximum flow problems and organize computations properly, then the total time taken by the algorithm is comparable to that of solving a single maximum flow problem. This approach determines a minimal cardinality witness in O(n(2)m(1/2)) time using simple data structures and in O(nm log n) time using the standard implementation of the dynamic tree data structures. We also show that the recognition version of the minimal witness problem is equivalent to a recognition version of a related problem known as the minimum rooted cut problem. (C) 1998 The Mathematical Programming Society, Inc. Published by Elsevier Science B.V.