Combinatorial algorithms for inverse network flow problems

An inverse optimization problem is defined as follows: Let S denote the set of feasible solutions of an optimization problem P, let c be a specified cost vector, and x(0) is an element of S. We want to perturb the cost vector c to d so that x(0) is an optimal solution of P with respect to the cost vector d, and wparallel tod - cparallel to(p) is minimum, where parallel to . parallel to(p) denotes some selected I-p norm and w is a vector of weights. In this paper, we consider inverse minimum-cut and minimum-cost flow problems under the I-1 normal (where the objective is to minimize Sigma(j)is an element of(J)w(j)\d(j) - c(j)\ for some index set J of variables) and under the I-infinity norm (where the objective is to minimize max{w(j)\d(j) - c(j)\: j is an element of J}). We show that the unit weight (i.e., w(j) = 1 for all j is an element of J) inverse minimum-cut problem under the norm reduces to solving a maximum-flow problem, and under the I-1 norm, it requires solving a polynomial sequence of minimum-cut problems. The unit weight inverse minimum-cost flow problem under the I-1 norm reduces to solving a unit capacity minimum-cost circulation problem, and under the I-infinity norm, it reduces to solving a minimum mean cycle problem. We also consider the nonunit weight versions of inverse minimum-cut and minimum-cost flow problems under the I-infinity norm. (C) 2002 Wiley Periodicals, Inc.