Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

SA07

each time she only observes the total cost of the path traversed by the evader. We propose GRN policy and investigate its properties as well as necessity. Moreover, we show that convergence to the optimal solution takes a worst-case exponential time. In this sense, we consider different versions of imperfect and randomized feedback, and prove worst-case polynomial convergence bounds. 2 - On Bilevel Minimum and Bottleneck Spanning Tree Problems Xueyu Shi, University of Pittsburgh, 1, Pittsburgh, PA, United States, Bo Zeng, Oleg A. Prokopyev We study a class of bilevel spanning tree problems (BSTs) that involve two independent decision-makers (DMs), who jointly construct a spanning tree in a graph. One DM firstly selects a subset of edges from the set under her control. The other then completes the spanning tree construction using the edges selected. We study BSTs with the sum- and bottleneck-type objective functions for the two DMs. The polynomial-time algorithms are proposed in both optimistic and pessimistic settings for BSTs where at least one of the DMs has the bottleneck- type objective. For BST with the sum-type objectives for two DMs, we provide an equivalent single-level linear mixed-integer programming formulation. 3 - Minimum Cost Edge Blocker Clique Problem Foad Mahdavi Pajouh, University of Massachusetts-Boston, 100 Morrissey Boulevard, Boston, MA, 02125-3393, United States The minimum cost edge blocker clique problem (EBCP) is introduced as the problem of blocking a minimum cost subset of edges in a graph so that each clique’s weight is bounded above by some threshold. Large-weight cliques effectively model clusters of important actors with quick communications in real- world settings such as social, communication, and biological systems. This talk presents complexity results, polyhedral results, and two exact algorithms for this problem. 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. 4 - Critical Elements for Network Cascade Control Colin P. Gillen, University of Pittsburgh, 1025 Benedum Hall, 3700 O’Hara Street, Pittsburgh, PA, 15261, United States, Alexander Veremyev, Oleg A. Prokopyev, Eduardo Pasiliao Network cascades represent a number of real-life applications: social influence, electrical grid failures, viral spread, and so on. The commonality between these phenomena is that they begin from a set of seed nodes and spread to other regions of the network. We consider a robust critical elements detection problem where the decision-maker wishes to control the spread of cascading behavior via node threshold modification (within a budget). The arc weights - how much influence one node has on another - are uncertain. The solution approaches include robust mixed-integer programming and centrality-based heuristics. Extensive computational experiments demonstrate the value of these methods. Chair: Angelia Nedich, ASU, Tempe, AZ, 85281, United States 1 - A Push-pull Gradient Method for Distributed Optimization in Networks Shi Pu, ASU, Tempe, AZ, 85281, United States, Angelia Nedich We consider a new gradient-based method for distributed optimization in a directed network, where each agent has its own convex cost function and the goal is to minimize the sum of the functions. Each node maintains two estimates, namely, an estimate of the optimal decision variable and an estimate of the average gradient of the cost functions. From the viewpoint of an agent, the information about the decision variable (resp. gradients) is pushed to (resp. pulled from) the neighbors. The method unifies the algorithms with different distributed architecture, including decentralized and centralized ones. We show the algorithm converges linearly for strongly convex and smooth objective functions. 2 - A Dual Approach for Optimal Algorithms in Distributed Optimization Over Networks Cesar A. Uribe, University of Illinois at Urbana-Champaign, Urbana, IL, 610801, United States, Soomin Lee, Alexander Gasnikov, Angelia Nedich We study the optimal convergence rates for distributed convex optimization problems over networks, where the objective is to minimize the sum of local functions of the nodes in the network. We provide complexity bounds for four cases: each function is strongly convex and smooth, when it is either strongly convex or smooth, and when it is convex but neither strongly convex nor smooth. Our approach is based on the dual problem and includes the graph that models the communication restrictions. We show distributed algorithms with the same optimal rates as their centralized counterparts (up to logarithmic factors), with an additional cost related to the communication graph. n SA09 North Bldg 124B Advances in First-Order Methods Sponsored: Optimization/Nonlinear Programming Sponsored Session

n SA07 North Bldg 123 Optimization in Social Networks Sponsored: Optimization/Network Optimization Sponsored Session Chair: Balabhaskar Balasundaram, Stillwater, OK, 74078, United States 1 - Generalizations of the Dominating Set Problem on Social Networks Rui Zhang, University of Colorado, Boulder, CO, 80309, United States, Subramanian Raghavan The positive influence dominating set problem is a generalization of the dominating set problem that arises on social networks. First, we show that it can be solved in linear time on trees. Next, we provide a tight and compact extended formulation, and derive a complete description of its polytope on trees. The formulation is also valid on general graphs, thus providing a new and stronger one. Facet defining conditions for the new inequalities are provided. A computational study is conducted. 2 - On Detecting Second-order 2-clubs in Graphs Yajun Lu, Oklahoma State University, Stillwater, OK, United States, Baski Balasundaram This talk will discuss a decomposition approach to detect a type of “second-order” 2-club in graphs, called an r-robust 2-club. The problem is to find a subset of vertices with maximum cardinality such that there are at least r internally vertex- disjoint paths of length at most two in the induced subgraph. Complexity results, formulations, and preprocessing ideas will be discussed. Effectiveness of the algorithmic techniques in solving the problem will be demonstrated on a test-bed of instances. The numerical results show that our approach reduces the running times significantly in many cases. Extensions of this idea to other second-order 2- clubs will also be discussed. 3 - Interdicting Low-diameter Clusters in Graphs Hao Pan, Oklahoma State University, 4508 Aggie Drive, Stillwater, OK, 74074, United States, Juan Sebastian Borrero, Baski Balasundaram A k-club, for a positive integer k, is a subset of vertices that induces a subgraph of diameter at most k. It is a clique relaxation that can be used to model low- diameter clusters in graph-based data mining. The k-clubs have been used to detect cohesive subgroups in social networks and functional modules in protein interaction networks. In this talk, we will consider an interdiction counterpart: given a graph G and a positive integer b, the k-club interdiction problem is to find a vertex subset S of size at most b such that the maximum k-club in G-S is minimized. We will discuss formulation and solution techniques for this min-max problem and discuss our preliminary findings in solving the problem when k = 2. 4 - An Integer Programming Framework for Identifying Duplicate Network Personas Sean Suehr, North Carolina Agricultural and Technical State University, 1601 E. Market Street, Greensboro, NC, 27411, United States, Chrysafis Vogiatzis In this talk, we present an integer programming framework at the intersection of social network analysis and law enforcement intelligence that can identify persons of interest. Criminal networks are complex due to the limited and imperfect information available and the fact that participating entities misrepresent themselves so as to stay hidden. We formally define this problem and derive its computational complexity. We finish the talk with results on the criminal network of 9/11. Our approach identifies two distinct clusters of criminals participating in two separate subplots. Bilevel Models in Network Optimization Sponsored: Optimization/Network Optimization Sponsored Session Chair: Colin P. Gillen, University of Pittsburgh, 1025 Benedum Hall, 3700 O’Hara Street, Pittsburgh, PA, 15261, United States 1 - Sequential Shortest Path Interdiction with Incomplete Information and Limited Feedback Jing Yang, University of Pittsburgh, United States, Juan Sebastian Borrero, Oleg A. Prokopyev, Denis Saure We study a sequential interdiction problem where the interdictor has partial information about the network. At each period, interdictor blocks at most k arcs to maximize evader’s cost and then evader traverses the shortest path from two fixed nodes in the remaining graph. The interdictor doesn’t know real cost, and at n SA08 North Bldg 124A

4