Operations Research and Statistics Seminar

Fall 2022

• Nov

  10
• SuiteSparse:GraphBLAS: Graph Algorithms in the Language of Sparse Linear Algebra

  Tim Davis

  Texas A&M University

  Location: CH 110

  Time: 12:00 PM

  View Abstract

  SuiteSparse: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.

• Sep

  30
• Optimizing Cooperative Interdependent Attack Graphs to Compromise Network Infrastructures

  Joe Alameda

  USNA

  Location: CH351

  Time: 03:45 PM

  View Abstract

  As 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.

• Aug

  31
• Protecting Facilities When the Effect of Protection is Imperfect

  Hugh Medal

  University of Tennessee

  Location: CH351

  Time: 03:45 PM

  View Abstract

  Most 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.