Combinatorial algorithms for inverse network flow problems

✍ Scribed by Ravindra K. Ahuja; James B. Orlin

• Publisher: John Wiley and Sons
• Year: 2002
• Tongue: English
• Weight: 122 KB
• Volume: 40
• Category: Article
• ISSN: 0028-3045
• DOI: 10.1002/net.10048

✦ Synopsis

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 minimumcost 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.