The primary goal of this research is to model and develop efficient solution techniques for graph theoretical problems with topologically stochastic information that manifests in a various forms. We employ a stochastic programming framework that is based on a formalism of coherent risk measures in order to find minimum-risk graph structures with stochastic vertex weights. Namely, we propose a class of risk-averse maximum weighted subgraph problems that represent a stochastic extension of the so-called maximum weight subgraph problems considered in graph-theoretical literature.
The structural nature of these model poses a twofold challenge in developing efficient solution algorithms.
First, accurate quantification of uncertainties in mathematical programming via risk measures in the form of convex constraints typically requires very large representative scenario sets, thus incurring lengthy solution times. In this regard, we first introduce an efficient algorithms for solving large-scale stochastic optimization problems involving measures of risk that are based on centrality equivalents.
The second major challenge relates to the fact that problems of finding a maximum subset of a defined property within a network are generally not solvable in polynomial time. Nevertheless, much emphasis has been placed on developing faster exact combinatorial solution methodologies that exploit the structural nature of the sought subgraphs. In pursuance of analogous frameworks, we propose a graph-based branch-and-bound algorithm for solving models in the risk-averse maximum weighted subgraph problem class that is generally applicable to problems where a subgraph's weight is given by a super-additive function whose evaluation requires solving an optimization problem. As an illustrative example of the developed concepts, we consider risk-averse maximum weighted clique and k-club problems. The mentioned network studies address problems with topologically exogenous information in the form uncertainties induced by stochastic factors associated with vertices. This assumption clearly relies on the premise that the network is structurally unvarying. For many application, however, it may also be of interest to examine decision making under conditions that admit topological changes of the network. To this end, we consider a two-stage stochastic recourse maximum clique problem that seeks to maximize the expected size of a clique over the decision time horizon. Namely, a subset of vertices composing a clique is select in the first-stage, after which realizations of uncertainty in the form of edge failures and creations arise. Then, the second-stage recourse is taken to "repair" the subset selected in the first stage by adding or removing nodes in order to ascertain its completeness. Numerical experiments for the above studies demonstrating the underlying problem properties and improvements in computational time achieved by the developed algorithms are conducted.
| Identifer | oai:union.ndltd.org:uiowa.edu/oai:ir.uiowa.edu:etd-7994 |
| Date | 01 May 2014 |
| Creators | Rysz, Maciej Wladyslaw |
| Contributors | Krokhmal, Pavlo |
| Publisher | University of Iowa |
| Source Sets | University of Iowa |
| Language | English |
| Detected Language | English |
| Type | dissertation |
| Format | application/pdf |
| Source | Theses and Dissertations |
| Rights | Copyright © 2014 Maciej Wladyslaw Rysz |
Page generated in 0.0019 seconds