|
Combinatorial algorithms for inverse network flow problems R.K. Ahuja and J.B. Orlin, Networks 40, 181-187, 2002 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° E S. We want to perturb the cost vector c to d so that x° 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 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 Σ[j]∈[J]w[j]|d[j] - c[j]| for some index set J of variables) and under the I∞ norm (where the objective is to minimize max{w[j]|d[j] - c[j]|: j E J}). We show that the unit weight (I.e., w[j] = 1 for all j ∈ J) inverse minimum-cut problem under the I[1] norm reduces to solving a maximum-flow problem, and under the I∞ 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∞ 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∞ norm. |