Search

This study aims to extend the existing climate-change-induced flood mitigation research. We introduce an at-risk network to evaluate optimal cost–benefit strategies for creating dikes and levees to mitigate flood hazard over multiple years. Our proposed model includes the expected flood costs, estimated using possible climate-change-induced sea-level states throughout the planning horizon, and the investment costs for developing dikes and levees via land elevations across the at-risk network. Further, given the limitations on infrastructure investment, our model incorporates a budget constraint. The problem is modeled as a multistage stochastic program with recourse that minimizes overall expected costs over the planning horizon. Exploiting open-source and freely accessible data sets, the flood risk mitigation model elaborated here can be applied to most urban coastal situations due to its general nature. Using Boston as a case study, our proposed method resulted in a cost reduction of as much as 92.2%, with an average of 63.2%, compared to a "do nothing" strategy in a simulation-based experiment. Under a high sea-level rise scenario, the average cost savings observed by implementing the solution suggested by our model could be even 15% higher. This proposed approach offers decision-makers a tool to frequently assess the costs and risks faced by their cities enabling them to effectively mitigate the potential flooding risks. [ABSTRACT FROM AUTHOR]

Given a graph with weights on its vertices and blocking costs on its edges, and a user-defined threshold τ > 0 , the minimum cost edge blocker clique problem (EBCP) is introduced as the problem of blocking a minimum cost subset of edges so that each clique's weight is bounded above by τ . Clusters composed of important actors with quick communications can be effectively modeled as large-weight cliques in real-world settings such as social, communication, and biological systems. Here, we prove that EBCP is NP-hard even when τ is a fixed parameter, and propose a combinatorial lower bound for its optimal objective. A class of inequalities that are valid for the set of feasible solution to EBCP is identified, and sufficient conditions for these inequalities to induce facets are presented. Using this class of inequalities, EBCP is formulated as a linear 0–1 program including potentially exponential number of constraints. We develop the first problem-specific branch-and-cut algorithm to solve EBCP, which utilizes the aforementioned constraints in a lazy manner. We also developed the first combinatorial branch-and-bound solution approach for this problem, which aims to handle large graph instances. Finally, computational results of solving EBCP on a collection of random graphs and power-law real-world networks by using our proposed exact algorithms are also provided. [ABSTRACT FROM AUTHOR]

Graph clustering (partitioning) is a helpful tool in understanding complex systems and analyzing their structure and internal properties. One approach for graph clustering is based on partitioning the graph into cliques. However, clique models are too restrictive and prone to errors given imperfect data. Thus, using clique relaxations instead may provide a more reasonable and applicable partitioning of the graph. An s-club is a distance-based relaxation of a clique and is formally defined as a subset of vertices inducing a subgraph with a diameter of at most s. In this work, we study the minimum s-club partitioning problem, which is to partition the graph into a minimum number of non-overlapping s-club clusters. Integer programming techniques and combinatorial branch-and-bound framework are employed to develop exact algorithms to solve this problem. We also study and compare the computational performance of the proposed algorithms for the special cases of s = 2 and s = 3 on a test-bed of randomly generated instances and real-life graphs. [ABSTRACT FROM AUTHOR]

Detecting large 2-clubs in biological, social and financial networks can help reveal important information about the structure of the underlying systems. In large-scale networks that are error-prone, the uncertainty associated with the existence of an edge between two vertices can be modeled by assigning a failure probability to that edge. Here, we study the problem of detecting large 'risk-averse' 2-clubs in graphs subject to probabilistic edge failures. To achieve risk aversion, we first model the loss in 2-club property due to probabilistic edge failures as a function of the decision (chosen 2-club cluster) and randomness (graph structure). Then, we utilize the conditional value-at-risk (CVaR) of the loss for a given decision as a quantitative measure of risk for that decision, which is bounded in the model. More precisely, the problem is modeled as a CVaR-constrained single-stage stochastic program. The main contribution of this article is a new Benders decomposition algorithm that outperforms an existing decomposition approach on a test-bed of randomly generated instances, and real-life biological and social networks. [ABSTRACT FROM AUTHOR]

We study the minimum vertex blocker clique problem (VBCP),1 which is to remove a subset of vertices of minimum cardinality in a weighted undirected graph, such that the maximum weight of a clique in the remaining graph is bounded above by a given integer r ≥ 1. Cliques are among the most popular concepts used to model cohesive clusters in different graph-based applications, such as social, biological, and communication networks. The general case of VBCP on weighted graphs is known to be NP-hard, and we show that the special case on unweighted graphs is also NP-hard for any fixed integer r ≥ 1. We present an analytical lower bound on the cardinality of an optimal solution to VBCP, as well as formulate VBCP as a linear 0-1 program with an exponential number of constraints. Facet-inducing inequalities for the convex hull of feasible solutions to VBCP are also identified. Furthermore, we develop the first exact algorithm for solving VBCP, which solves the proposed formulation by using a row generation approach. Computational results obtained by utilizing this algorithm on a test-bed of randomly generated instances are also provided. © 2014 Wiley Periodicals, Inc. NETWORKS, Vol. 64(1), 48-64 2014 [ABSTRACT FROM AUTHOR]

Detecting quasi-cliques in graphs is a useful tool for detecting dense clusters in graph-based data mining. Particularly in large-scale data sets that are error-prone, cliques are overly restrictive and impractical. Quasi-clique detection has been accomplished using heuristic approaches in various applications of graph-based data mining in protein interaction networks, gene co-expression networks, and telecommunication networks. Quasi-cliques are not hereditary, in the sense that every subset of a quasi-clique need not be a quasi-clique. This lack of heredity introduces interesting challenges in the development of exact algorithms to detect maximum cardinality quasi-cliques. The only exact approaches for this problem are limited to two mixed integer programming formulations that were recently proposed in the literature. The main contribution of this article is a new combinatorial branch-and-bound algorithm for the maximum quasi-clique problem. [ABSTRACT FROM AUTHOR]

This article investigates the local maxima properties of a box-constrained quadratic optimization formulation of the maximum independent set problem in graphs. Theoretical results characterizing binary local maxima in terms of certain induced subgraphs of the given graph are developed. We also consider relations between continuous local maxima of the quadratic formulation and binary local maxima in the Hamming distance-1 and distance-2 neighborhoods. These results are then used to develop an efficient local search algorithm that provides considerable speed-up over a typical local search algorithm for the binary Hamming distance-2 neighborhood. [ABSTRACT FROM AUTHOR]