Operations Research and Statistics Seminar
SuiteSparse:GraphBLAS: Graph Algorithms in the Language of Sparse Linear AlgebraTim DavisTexas A&M UniversityLocation: CH 110Time: 12:00 PM
View AbstractSuiteSparse:GraphBLAS is a full implementation of the GraphBLAS standard, which defines a set of sparse matrix operations on an extended algebra of semirings using an almost unlimited variety of operators and types. When applied to sparse adjacency matrices, these algebraic operations are equivalent to computations on graphs. GraphBLAS provides a powerful and expressive framework for creating graph algorithms based on the elegant mathematics of sparse matrix operations on a semiring. Key features and performance of the SuiteSparse implementation of GraphBLAS package are described. The implementation appears in Linux distros, forms the basis of the RedisGraph module of Redis (a commercial graph database system), appears as C=A*B in MATLAB, and will become the core sparse matrix package in the Julia Language. In terms of performance, graph algorithms written in GraphBLAS can rival or even outperform highly-tuned specialized kernels, while being far simpler for the end user to write.
Optimizing Cooperative Interdependent Attack Graphs to Compromise Network InfrastructuresJoe AlamedaUSNALocation: CH351Time: 03:45 PM
View AbstractAs infrastructures in our society become increasingly interdependent on one another, the possibility of attacks on these infrastructures utilizing these interdependencies also increases. In this paper, we consider attacks from multiple attackers working fully-cooperatively to reach their goals. Moreover, we model the possibility that more than one exploit may have to be used by an attacker to reach their objective. We provide a mixed-integer program for this attacker model, and we provide an algorithm that gives us an optimal solution. Furthermore, we provide preliminary analysis showing the computational effectiveness of our algorithm when compared to the MIP.
Protecting Facilities When the Effect of Protection is ImperfectHugh MedalUniversity of TennesseeLocation: CH351Time: 03:45 PM
View AbstractMost system protection optimization models assume that protection actions are perfect in the sense that if a system component is protected it is guaranteed to not fail. In this presentation we study a system protection problem in which protecting a component reduces its likelihood of failure but does not eliminate the chance of failure. In particular, we study a class of facility protection problems in which a defender allocates continuous protection resources to a set of facilities in order to maximize the expected coverage provided by the facilities. The probability that a facility fails depends on the amount of protection resources allocated to it. Exploiting the submodularity of the problem, we first develop a description of the hypograph of continuous submodular functions and then develop a cutting plane algorithm that finds approximate solutions and bounds. Next, we develop a spatial branch-and-bound approach that utilizes the approximate cutting plane algorithm to form an outer approximation and obtain upper bounds for a region. We present computational results that compare our method with a state-of-the-art solver.