Informs Annual Meeting 2017

SC72

INFORMS Houston – 2017

SC72

4 - Real-time Data-driven Decision-support Toolkit for the Incentivization and Guidance of Shared Electrified and Automated Vehicles Chenfeng Xiong, Assistant Research Professor, University of Maryland, 1173 Glenn Martin Hall, College Park, MD, 20770, United States, cxiong@umd.edu, Lei Zhang, Ya Ji We develop an integrated, personalized, real-time traveler information and incentive technology to incentivize energy-efficient travel, such as the adoption of Shared, Electrified, and Automated Vehicles. Based on machine learning and artificial intelligence, a behaviorally sound and computationally efficient agent- based model is developed to simulate the transportation systems in real-time. The online training of the AI models is based on real-time big-data streams leveraging the biggest transportation data warehouse in the U.S., the Regional Integrated Transportation Information System, which enables accurate system monitoring and effective control/operations. 5 - Augmenting Text Mining to Numerical Analysis to Improve Lift Anurag Agarwal, Professor, University of South Florida, Information Systems and Decision Sciences, College of Business, Sarasota, FL, 34243, United States, agarwala@usf.edu We show how lift and classification accuracy can be improved by augmenting numerical data analysis with text mining, if text data is available in addition to numeric data for a classification problem. 371F Non-convex and Convex Optimization Sponsored: Optimization, Global Optimization Sponsored Session Chair: Daniel Bienstock, Columbia University, New York, NY, 10027, United States, dano@columbia.edu 1 - On the Construction of Converging Hierarchies for Polynomial Optimization Based on Certificates of Global Positivity Amir Ali Ahmadi, Princeton University, Dept. of Operations Research&Financial Eng., Sherrerd Hall (Room 329), Charlton Street, Princeton, NJ, 08544, United States, a_a_a@princeton.edu, Georgina Hall In recent years, techniques based on convex optimization that produce converging hierarchies of lower bounds for polynomial optimization problems (POPs) have gained much popularity. At their heart, these hierarchies rely crucially on Positivstellensatze from the late 20th century (e.g., due to Putinar and Schmudgen) that certify positivity of a polynomial on an arbitrary basic semialgebraic set. In this paper, we show that such hierarchies could in fact be designed from much more limited Positivstellensatze dating back to the early 20th century that only certify positivity of a polynomial globally. 2 - Rank-one Generated Spectral Cones Defined by Homogeneous Linear Matrix Inequalities Charles J. Argue, Carnegie Mellon University, Pittsburgh, PA, 15213, United States, cjargue@gmail.com, Fatma Kilinc-Karzan A cone K which is a subset of positive semidefinite cone, is called rank-one generated (ROG) if all of its all of its extreme rays are rank one matrices. Semidefinite relaxations of non-convex quadratic optimization problems are exact for every linear objective function if and only if they lead to conic programs over ROG cones. We study the necessary and sufficient conditions under which the intersection of the positive semidefinite cone with two homogeneous linear matrix inequalities is an ROG cone. Our results also yield a method for giving efficient certificates for whether such a cone is ROG or not. 3 - Volume Computation for Sparse Boolean Quadric Relaxations Jon Lee, University of Michigan, 1205 Beal Avenue, Ann Arbor, MI, 48109-2117, United States, jonxlee@umich.edu, Daphne Skipper Motivated by understanding the quality of tractable convex relaxations of intractable polytopes, Ko et al. gave a closed-form expression for the volume of a standard relaxation Q(G) of the BQP P(G) of the complete graph. We extend to structured sparse graphs, giving: (i) an efficient algorithm for calculating vol(Q) when G has bounded tree width, (ii) closed-form expressions (and asymptotic behaviors) for vol(Q) for all stars, paths, and cycles, and (iii) a closed-form expression for vol(P) for all cycles. We show that when G is a cycle, the light Q is a very close model for the heavy P. 4 - Computational Experiments and Methodology for QCQPs Daniel Bienstock, Columbia University, Dept of IEOR, 342 Mudd, New York, NY, 10027, United States, dano@columbia.edu We describe current computational work using linear relaxations and binary approximations to continuous variables in the context of polynomial optimization problems. SC71

372A Network Optimization I Sponsored: Optimization, Network Optimization Sponsored Session Chair: Colin P Gillen, University of Pittsburgh, 1025 Benedum Hall, Pittsburgh, PA, 15261, United States, cpg12@pitt.edu 1 - An Efficient Algorithm of Constructing Highly Fault Tolerantvirtual Backbone to Reduce the Transmission Cost with Damage Loss Uncertainty in Wireless Network Mengnan Chen, University of Central Florida, 12800 Pegasus Drive, P.O. Box 162993, Orlando, FL, 32816-2993, United States, cmn891127@knights.ucf.edu We study the problem of constructing virtual backbones in wireless network to reduce the transmission cost and maintain the network when the backbone nodes are damaged, called the virtual backbones for cost reduction and network maintenance (VBRM) problem. The backbone node is the foundation of this routing scheme. This is two level problem modeled by the stochastic programming. Our model can find the optimal solution between guaranteed rates of data delivery within different situation.We also consider to improve energy- efficient of data communications by reducing the transmission cost. 2 - Exact Algorithms for the Minimum Cost Vertex Blocker Clique Problem Farzaneh Nasirian, University of Massachusetts Boston, 100 William T. Morrissey Blvd, Boston, MA, 02125, United States, Farzaneh.Nasirian001@umb.edu, Foad Mahdavi Pajouh, Josephine Namayanja This talk addresses the minimum cost vertex blocker clique problem which is to find a minimum cost subset of vertices whose removal bounds the maximum weight of a clique in a network. We propose a new characterization of the set of feasible solutions that results in new linear 0-1 programming formulations solved by lazy-fashioned branch-and-cut algorithms. We also develop the first combinatorial branch-and-bound algorithm for this problem. The computational performance of these exact algorithms is studied on a test-bed of randomly- generated and real-life instances. 3 - Maximum Induced Path in a Graph Dmytro Matsypura, The University of Sydney, Sydney, 2006, Australia, dmytro.matsypura@sydney.edu.au, Alexander Veremyev, Oleg A.Prokopyev, Eduardo Pasiliao We consider the problem of finding the maximum induced path in a graph. We develop three conceptually different MIP formulations and study their properties. We develop a number of valid inequalities and various enhancements to the proposed MIPs. We also propose exact iterative algorithms to solve the problems. Finally, we conduct an extensive computational study to evaluate the performance of the proposed algorithms and to reveal the properties of the proposed formulations. 4 - Robust Node Hardening Against Influence Propagation Colin P. Gillen, University of Pittsburgh, 405 Franklin Avenue, #1, Pittsburgh, PA, 15221, United States, cpg12@pitt.edu We consider a variation of the classical Linear Threshold model in which the node thresholds are known, but the arc weights (influence) is uncertain. The decision maker wishes to harden a set of nodes, within a limited budget, in order to minimize the spread of influence given a set of seed nodes. NP-hardness of the problem is proved, some polyhedral results are discussed, and solution approaches are presented. Some computational results demonstrating the effectiveness of our algorithms and their enhancements are shown.

93