Refine
Document Type
- Doctoral Thesis (1)
- Preprint (1)
Language
- English (2)
Has Fulltext
- yes (2)
Keywords
- monotropic programming (2) (remove)
Faculty / Organisational entity
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.