Premium
Combinatorial algorithms for inverse network flow problems
Author(s) -
Ahuja Ravindra K.,
Orlin James B.
Publication year - 2002
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.10048
Subject(s) - mathematics , inverse , minimum cost flow problem , norm (philosophy) , combinatorics , maximum flow problem , inverse problem , unit vector , flow network , minimum weight , mathematical optimization , mathematical analysis , geometry , law , political science
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.