Inverse Maximum Flow Problem Under the Combination of the Weighted l $$_2$$2 Norm and the Weighted Hamming Distance
- PDF / 282,953 Bytes
- 10 Pages / 439.37 x 666.142 pts Page_size
- 88 Downloads / 211 Views
Inverse Maximum Flow Problem Under the Combination of the Weighted l2 Norm and the Weighted Hamming Distance Long-Cheng Liu1
· Han Gao1 · Chao Li2
Received: 16 May 2018 / Revised: 22 May 2019 / Accepted: 11 October 2019 © Operations Research Society of China, Periodicals Agency of Shanghai University, Science Press, and Springer-Verlag GmbH Germany, part of Springer Nature 2019
Abstract The idea of the inverse optimization problem is to adjust the values of the parameters so that the observed feasible solutions are indeed optimal. The modification cost is measured by different norms, such as l1 , l2 , l∞ norms and the Hamming distance, and the goal is to adjust the parameters as little as possible. In this paper, we consider the inverse maximum flow problem under the combination of the weighted l2 norm and the weighted Hamming distance, i.e., the modification cost is fixed in a given interval and depends on the modification out of the given interval. We present a combinatorial algorithm which can be finished in O(nm) to solve it due to the minimum cut of the residual network. Keywords Maximum flow · Minimum cut · Inverse problem · Residual network · Strongly polynomial algorithm Mathematics Subject Classification 05C21 · 68Q25 · 90B10 · 90C27
This research is supported by the Fundamental Research Funds for the Central Universities (No. 20720190068) and the China Scholarship Council (No. 201706315073).
B
Long-Cheng Liu [email protected] Han Gao [email protected] Chao Li [email protected]
1
School of Mathematical Sciences, Xiamen University, Xiamen 361005, Fujian, China
2
School of Mathematics and Computer, Wuyi University, Wuyishan 354300, Fujian, China
123
L.-C. Liu et al.
1 Introduction Let N (V , A, c) be a connected and directed network, where V (|V | = n) is the node set, A (|A| = m) is the arc set and c is the capacity vector for the arcs. Each component ci j of c is called the capacity of the arc (i, j). There are two special nodes in V : the source node s and the sink node t. If a network has more than a source node or more than a sink node, it can be transformed into an s − t network by introducing a super-source node and a super-sink node [1]. A feasible (s, t)-flow or simply flow is a function f : A → R |A| that satisfies the capacity constraints 0 f i j ci j
for each (i, j) ∈ A,
and the flow conservation constraints j
fi j −
j
f ji
⎧ i = s, ⎨ v( f ), = −v( f ), i = t, ⎩ 0, other i,
where v( f ) is the value of the flow f from s to t. The maximum flow problem is to find a flow with the maximum flow value. It is a classical network optimization problem that has many applications. It is well known that maximum flow problem can be solved in strongly polynomial time [1]. Conversely, an inverse maximum flow problem is to modify the arc capacity vector as little as possible such that a given flow can form a maximum flow in the modified network. Yang et al. [2] showed that the inverse maximum flow problem under the l1 norm is strongly polynomial time solvable. For th
Data Loading...
