DOI

10.17077/etd.2tv2grfj

Document Type

Dissertation

Date of Degree

Spring 2014

Degree Name

PhD (Doctor of Philosophy)

Degree In

Industrial Engineering

First Advisor

Krokhmal, Pavlo

First Committee Member

Chen, Yong

Second Committee Member

Thomas, Geb

Third Committee Member

Abdel-Malek, Karim

Fourth Committee Member

Bhatti, Asghar

Abstract

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.

Keywords

clique, network, optimization, portfolio, risk, stochastic

Pages

x, 118 pages

Bibliography

Includes bibliographical references (pages 114-118).

Copyright

Copyright © 2014 Maciej Wladyslaw Rysz

Share

COinS