Kaiserslautern - Fachbereich Mathematik
Refine
Document Type
- Preprint (3)
- Doctoral Thesis (1)
Language
- English (4)
Has Fulltext
- yes (4)
Keywords
- inverse optimization (2)
- inverse problems (2)
- monotropic programming (2)
- network flows (2)
- cuts (1)
- matroid flows (1)
- maximum capacity path (1)
- maximum flows (1)
- minimum cost flows (1)
- minimum cut (1)
- tension problems (1)
- tensions (1)
Faculty / Organisational entity
In this paper, we study the inverse maximum flow problem under \(\ell_\infty\)-norm and show that this problem can be solved by finding a maximum capacity path on a modified graph. Moreover, we consider an extension of the problem where we minimize the number of perturbations among all the optimal solutions of Chebyshev norm. This bicriteria version of the inverse maximum flow problem can also be solved in strongly polynomial time by finding a minimum \(s - t\) cut on the modified graph with a new capacity function.
In the context of inverse optimization, inverse versions of maximum flow and minimum cost flow problems have thoroughly been investigated. In these network flow problems there are two important problem parameters: flow capacities of the arcs and costs incurred by sending a unit flow on these arcs. Capacity changes for maximum flow problems and cost changes for minimum cost flow problems have been studied under several distance measures such as rectilinear, Chebyshev, and Hamming distances. This thesis also deals with inverse network flow problems and their counterparts tension problems under the aforementioned distance measures. The major goals are to enrich the inverse optimization theory by introducing new inverse network problems that have not yet been treated in the literature, and to extend the well-known combinatorial results of inverse network flows for more general classes of problems with inherent combinatorial properties such as matroid flows on regular matroids and monotropic programming. To accomplish the first objective, the inverse maximum flow problem under Chebyshev norm is analyzed and the capacity inverse minimum cost flow problem, in which only arc capacities are perturbed, is introduced. In this way, it is attempted to close the gap between the capacity perturbing inverse network problems and the cost perturbing ones. The foremost purpose of studying inverse tension problems on networks is to achieve a well-established generalization of the inverse network problems. Since tensions are duals of network flows, carrying the theoretical results of network flows over to tensions follows quite intuitively. Using this intuitive link between network flows and tensions, a generalization to matroid flows and monotropic programs is built gradually up.
Given a directed graph G = (N,A), a tension is a function from A to R which satisfies Kirchhoff\\\'s law for voltages. There are two well-known tension problems on graphs. In the minimum cost tension problem (MCT), a cost vector is given and a tension satisfying lower and upper bounds is seeked such that the total cost is minimum. In the maximum tension problem (MaxT), the graph contains 2 special nodes and an arc between them. The aim is to find the maximum tension on this arc. In this study we assume that both problems are feasible and have finite optimal solutions and analyze their inverse versions under rectilinear and Chebyshev distances. In the inverse minimum cost tension problem we adjust the cost parameter to make a given feasible solution the optimum, whereas in inverse maximum tension problem the bounds of the arcs are modified. We show, by extending the results of Ahuja and Orlin (2002), that these inverse tension problems are in a way \\\"dual\\\" to the inverse network flows. We prove that the inverse minimum cost tension problem under rectilinear norm is equivalent to solving a minimum cost tension problem, while under unit weight Chebyshev norm it can be solved by finding a minimum mean cost residual cut. Moreover, inverse maximum tension problem under rectilinear norm can be solved as a maximum tension problem on the same graph with new arc bounds. Finally, we provide a generalization of the inverse problems to monotropic programming problems with linear costs.
Given a directed graph G = (N,A) with arc capacities u and a minimum cost flow problem defined on G, the capacity inverse minimum cost flow problem is to find a new capacity vector u' for the arc set A such that a given feasible flow x' is optimal with respect to the modified capacities. Among all capacity vectors u' satisfying this condition, we would like to find one with minimum ||u' - u|| value. We consider two distance measures for ||u' - u||, rectilinear and Chebyshev distances. By reduction from the feedback arc set problem we show that the capacity inverse minimum cost flow problem is NP-hard in the rectilinear case. On the other hand, it is polynomially solvable by a greedy algorithm for the Chebyshev norm. In the latter case we propose a heuristic for the bicriteria problem, where we minimize among all optimal solutions the number of affected arcs. We also present computational results for this heuristic.