Combinatorial algorithms for inverse network flow problems

Abstract 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 ∈ 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 w ∥ d − c ∥ p is minimum, where ∥ · ∥ p denotes some selected l p norm and w is a vector of weights. In this paper, we consider inverse minimum‐cut and minimum‐cost flow problems under the l 1 normal (where the objective is to minimize ∑ j ∈ J w j | d j − c j | for some index set J of variables) and under the l ∞ norm (where the objective is to minimize max w j | d j − c j |: j ∈ J). We show that the unit weight (i. e. , w j = 1 for all j ∈ J) inverse minimum‐cut problem under the l 1 norm reduces to solving a maximum‐flow problem, and under the l ∞ norm, it requires solving a polynomial sequence of minimum‐cut problems. The unit weight inverse minimum‐cost flow problem under the l 1 norm reduces to solving a unit capacity minimum‐cost circulation problem, and under the l ∞ 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 l ∞ norm. © 2002 Wiley Periodicals, Inc.