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 x0 ∈ S. We want to perturb the cost vector c to d so that x0 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 lp norm and w is a vector of weights. In this paper, we consider inverse minimum-cut and minimum-cost flow problems under the l1 normal (where the objective is to minimize Σj∈Jwj|dj − cj| for some index set J of variables) and under the l∞ norm (where the objective is to minimize max{wj|dj − cj|:j∈J}). We show that the unit weight (i.e., wj = 1 for all j∈J) inverse minimum-cut problem under the l1 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 l1 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.
