Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

WB05

4 - Robust Optimization and Control for Electricity Generation and Transmission Haoxiang Yang, Northwestern University, 2145 Sheridan Road,

n WB05 North Bldg 122B Large-Scale Conic Optimization Sponsored: Optimization/Linear and Conic Optimization Sponsored Session

Evanston, IL, 60208, United States, David Morton, Chaithanya Bandi, Krishnamurthy Dvijotham

We consider a robust optimization problem for the electric power system under uncertain demand and availability of renewable energy resources. Based on the recently developed convex relaxation schemes for the alternating current optimal power flow (ACOPF) problem, we construct a robust convex optimization problem with recourse. We propose a cutting-plane method with enhancements to solve this problem, and we establish convergence and other desirable properties. Experimental results indicate that our robust convex relaxation of the ACOPF problem can provide a tight lower bound and an acceptable solution for the non-convex robust ACOPF problem. n WB04 North Bldg 122A Formulations and Algorithms for MIP Sponsored: Optimization/Integer and Discrete Optimization Sponsored Session Chair: Sahar Tahernejad, Lehigh University, Bethlehem, PA, 18015, United States 1 - Finding Feasible Solutions to Integer Programs with Bounded Integrality Gap in Polynomial Time Arash Haddadan, Carnegie Mellon University, 5000 Forbes Avenue, Pittsburgh, PA, 15213, United States, Robert D. Carr, Cynthia Phillips We present a new algorithm for finding a feasible solution for a mixed integer linear program. The algorithm runs in polynomial time and is guaranteed to find a feasible integral solution provided the integrality gap is bounded. The algorithm computes convex decompositions and it provides a suite of integral solutions. The main application of our algorithm is to experimentally evaluate the integrality gap of IP formulations. We apply this technique to several network design problems such as 2-edge-connected subgraph, vertex-cover, and tree augmentation. 2 - A New Integer Programming Formulation of the Graphical Traveling Salesman Problem Robert D. Carr, University of New Mexico, Albuquerque, NM, United States, Neil Simonetti In the Traveling Salesman Problem (TSP), a salesman wants to visit a set of cities and return home. There is a cost cij of traveling from city i to city j, which is the same in either direction for the Symmetric TSP. The objective is to visit each city exactly once, minimizing total travel costs. In the Graphical TSP, a city may be visited more than once, which may be necessary on a sparse graph. We present a new integer programming formulation for the Graphical TSP for sparse graphs. 3 - Two-stage Mixed-integer Stochastic Bilevel Optimization Problems Sahar Tahernejad, Lehigh University, Bethlehem, PA, 18015, United States, Ted K. Ralphs Two-stage mixed-integer stochastic bilevel optimization problems (2SMISBLPs) unify the multi-level and multi-stage stochastic optimization problems, while the numbers of decision makers (DMs) and time stages are limited to two, and a subset of variables are constrained to be discrete. The importance of this new framework arises from the fact that in many real-world problems, two DMs (with possibly competing objectives) make the decisions, while the accurate values of some input parameters are unknown at the beginning. In this talk, we describe special cases of 2SMISBLPs and illustrate how the algorithms for these special cases can be integrated to be employed for solving general 2SMISBLPs. 4 - Set Covering Problem with Conflict Constraints Saeed Saffari, North Carolina State University, Raleigh, NC, 27607, United States, Yahya Fathi We consider the well-known set covering problem in which we have incompatibilities between certain pairs of columns, i.e., from each conflicting pair at most one column can occur in the optimal subset. We introduce and discuss several classes of valid inequalities and pre-processing techniques for the IP model of this problem, and demonstrate their effectiveness in the context of a branch and cut algorithm.

Chair: Neal Parikh, Cornell University, Ithaca, NY, United States Co-Chair: Brendan O’Donoghue, Google DeepMind, United Kingdom 1 - Chordal Decomposition in Operator-splitting Methods for Sparse Semidefinite Programs Yang Zheng, University of Oxford, Oxford, United Kingdom, Giovanni Fantuzzi, Antonis Papachristodoulou, Paul Goulart, Andrew Wynn We employ chordal decomposition to reformulate a sparse SDP into an equivalent SDP with smaller positive semidefinite constraints. In contrast to previous approaches, the decomposed SDP is suitable for the application of first-order methods. We apply the alternating direction method of multipliers (ADMM) to solve decomposed SDPs either in primal, dual or self-dual embedding form. Each iteration of such ADMM algorithms requires a projection onto an affine subspace, and a set of projections onto small PSD cones that can be computed in parallel. All algorithms are implemented in the MATLAB solver CDCS. Numerical experiments on a range of sparse SDPs demonstrate the efficiency of our methods. 2 - Globally Convergent Type I Anderson Acceleration for Non-smooth Fixed Point Iterations We consider the application of the type-I Anderson acceleration to solving general non-smooth fixed-point problems. By interleaving with safe-guarding steps, and employing a Powell-type regularization and a re-start checking for strong linear independence of the updates, we propose the first globally convergent variant of Anderson acceleration assuming only that the fixed-point iteration is non- expansive. We show by extensive numerical experiments that many first order algorithms can be improved with the proposed algorithm. Our proposed method of acceleration is being implemented in SCS 2.0, one of the default solvers used in the convex optimization parser-solver CVXPY 1.0. 3 - On Robustness and Scalability of Semidefinite Relaxation Techniques for Optimal Power Flow Anders Eltved, DTU, Denmark Semidefinite relaxation techniques have shown great promise for nonconvex optimal power flow problems. However, a number of independent numerical experiments have led to concerns about scalability and robustness of existing SDP solvers. To address these concerns, we investigate some numerical aspects of the problem and compare different state-of-the-art solvers. Our results demonstrate that large problem instances with a positive semidefinite cone of order up to 25,000 can be solved reliably and to reasonable accuracy within minutes. 4 - Deep Belief Network with Surrogate Optimization for Cyanobacterial Risk Prediction Peng Jiang, Shanghai Jiao Tong University, Shanghai, 200240, China, Xiao LIU, Karina Yew Gin Cyanobacterial blooms are threatening human health and the sustainability of freshwater resources. For situations with massive data, deep learning models emerge to be workable solutions for predicting cyanobacterial risks. However, the high-dimensional hyperparameters of such a model are hard to calibrate. Traditional trial-and-error methods for tuning them are computationally expensive. We propose a surrogate optimization-assisted deep belief network model to predict cyanobacterial risks in a data-driven manner. Therein, a modified mixed-integer surrogate optimization algorithm is hybridized into the model. Finally, a real case is employed to demonstrate its effectiveness. Junzi Zhang, Stanford University, Stanford, CA, 94305, United States, Brendan O’Donoghue, Stephen P. Boyd

441