A solution to the inverse minimum cut problem in dynamic network flows. (English) Zbl 1356.90030

Banikhademi, Hajar; Fathabadi, Hasan Salehi

Adv. Appl. Stat. 49, No. 4, 267-285 (2016).

Summary: We study the problem of inverse minimum dynamic cut (IMDC), which changes a capacity vector \(u\) in such a way that a given dynamic cut and the applied changes are minimum, using the Euclidean norm \(l_1\) to measure these changes. Our aim is to solve an inverse minimum dynamic cut, by finding a maximum dynamic flow in a time-expanded network flow and, having calculated the appropriate algorithm, analyzing the relationships between the time-expanded networks, the maximum flow, and the minimum cut. First, we show a specified dynamic cut, to be optimized; the capacity of arcs should be reduced. This study is useful in cases where the network should be divided into two parts by cutting such that this cut has the minimum weight. It is applicable in physics, chemistry, computer networks and electrical circuits, etc. The advantage of this method is the use of time-expanded network to be static corresponding to a dynamic network and algorithm is easily displayed on this network. Finally, the algorithm is implemented on a numerical example of dynamic network flow.

MSC:

90B10	Deterministic network models in operations research
90C35	Programming involving graphs or networks
90C05	Linear programming

Keywords:

dynamic network flow; inverse optimization; minimum dynamic cut; time-expanded network