zbMATH — the first resource for mathematics

Combinatorial algorithms for inverse network flow problems. (English) Zbl 1026.90089
Summary: 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\in 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 \(\|\cdot \|_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 \(\sum_{j\in J}w_j |d_j -c_j|\) for some index set \(J\) of variables) and under the \(l_\infty\) norm (where the objective is to minimize \(\max\{w_j |d_j-c_j |:j \in J \})\). We show that the unit weight (i.e., \(w_j=1\) for all \(j\in J)\) inverse minimum-cut problem under the \(l_1\) norm reduces to solving a maximum-flow problem, and under the \(l_\infty\) 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_\infty\) 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_\infty\) norm.

90C35 Programming involving graphs or networks
90B10 Deterministic network models in operations research
Full Text: DOI
[1] and Network flows: Theory, algorithms, and applications, Prentice-Hall, Englewood Cliffs, NJ, 1993.
[2] Ahuja, Oper Res 49 pp 771– (2001)
[3] Gabow, SIAM J Comput 18 pp 1013– (1989)
[4] Goldberg, SIAM J Comput 24 pp 494– (1995)
[5] Goldberg, J ACM 45 pp 783– (1998)
[6] and A new approach to the maximum flow problems, Proc 18th ACM Symp on the Theory of Computing, 1986, pp. 136-146.
[7] Goldberg, J ACM 35 pp 873– (1990)
[8] Hochbaum, J ACM 37 pp 843– (1990)
[9] Karp, Discr Math 23 pp 309– (1978) · Zbl 0386.05032
[10] Karp, Discr Appl Math 3 pp 37– (1981)
[11] Karzanov, SIAM J Comput 26 pp 1245– (1997)
[12] ?Optimal cycles in doubly weighted linear graphs,? Theory of graphs: International symposium, Dunod, Paris, Gordon and Breach, New York, 1966, pp. 209-213.
[13] McCormick, Math Program B 78 pp 179– (1997)
[14] Megiddo, Math Oper Res 4 pp 414– (1979)
[15] Orlin, Math Program 54 pp 41– (1992)
[16] ?Parametric flows, weighted means of cuts, and fractional combinatorial optimization,? Complexity in numerical optimization, (Editor), World Scientific, River Edge, NJ, 1983, pp. 351-386.
[17] Yang, Optimization 40 pp 147– (1997)
[18] Zhang, ZOR Math Methods Oper Res 48 pp 51– (1998)
[19] Zhang, J Comput Appl Math 72 pp 261– (1996)
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.