Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

TC05

4 - A Local Search Framework for Compiling Relaxed Decision Diagrams Michael Roemer, Martin Luther University, Universitatsring 3, Halle, Saale, 06108, Germany, Andre Augusto Cire, Louis-Martin Rousseau We presents a local search framework for compiling relaxed decision diagrams (DDs). It consists of a set of elementary DD manipulation operations including a redirect operation introduced in this paper and a general algorithmic scheme. We show that the framework can be used to reproduce standard DD compilation schemes and to create new compilation strategies. In experiments for the knapsack problem, the multidimensional knapsack problem and the set covering problem we compare different compilation methods. It turns out that a new strategy based on our framework consistently yields better bounds, for limited- width DDs than previously published heuristic strategies. Conic Optimization in Robust Optimization Sponsored: Optimization/Linear and Conic Optimization Sponsored Session Chair: Jonathan Yu-Meng Li, Telfer School of Management, University of Ottawa, Ottawa, ON, K1N 6N5, Canada 1 - Robust Quadratic Programming with Mixed-integer Uncertainty Areesh Mittal, University of Texas at Austin, Austin, TX, 78703, United States, Can Gokalp, Grani Adiwena Hanasusanto We study robust convex quadratic programs where the uncertain problem parameters can contain both continuous and integer components. We show that these problems can be reformulated as copositive programs of polynomial size. These convex optimization problems admit a tractable semidefinite programming approximation. We prove that the popular approximate S-Lemma method, valid only in the case of continuous uncertainty, is weaker than our approximation. We extend the results to the two-stage robust quadratic optimization problem if the problem has complete recourse. We demonstrate the superiority of our proposed method over the state-of-the-art solution schemes on several problem instances. 2 - Solving Robust Counterparts of Risk-Averse Stochastic Optimization Problems as Second-Order Cone Programs Jonathan Li, Telfer School of Management, University of Ottawa, Ottawa, ON, K1N 6N5, Canada We show how robust solutions can be derived for risk-averse stochastic optimization problems when only the mean-covariance information is available for the uncertain parameters. We prove that for any such problem that employs a coherent risk measure, the robust solution can always be obtained by solving certain second-order cone programs. Moreover, we identify the corresponding worst-case scenario (distribution) in closed-form, which sheds light on the connection between one’s risk aversion attitude and the worst-case distribution. 3 - Risk-averse Two-stage Stochastic Convex Optimization with First-stage Mixed Integer Problem Ricardo A. Collado, Stevens Institute of Technology, 36 Gates Ave., Gillette, NJ, 007933, United States, Somayeh Moazeni We formulate a risk-averse two-stage stochastic optimization problem and present solution strategies based on methods such as L-shape and the cutting-plane method. We extend our formulation to a general two-stage risk-averse convex stochastic optimization problem and discuss regularized cutting-plane methods for solution and approximation. Next we extend our results to the case where the first-stage variables are mixed integer but the recourse variables are continuous. Finally, we present results obtained from applying our methods to a problem on resource allocation for contingency planning. 4 - Preference Elicitation and Robust Optimization with Multi-attribute Quasi-concave Choice Functions Wenjie Huang, National University of Singapore, Singapore, William Haskell, Huifu Xu In this paper, we consider ambiguity in choice functions over a multi-attribute prospect space. Our main result is a robust preference model where the optimal decision is based on the worst-case choice function from an ambiguity set constructed through preference elicitation with pairwise comparisons of prospects. Differing from existing works in the area, our focus is on quasi-concave choice functions which enables us to cover a wide range of utility/risk preference problems. We propose two approaches based respectively on the support functions and level functions of quasi-concave functions to develop tractable formulations of the maximin preference robust optimization model. n TC05 North Bldg 122B

n TC06 North Bldg 122C Joint Session OPT/Practice Curated: MINLP Theories and Applications Sponsored: Optimization/Global Optimization Sponsored Session Chair: Asteroide Santana, ISyE, Georgia Tech, Atlanta, GA, United States 1 - A Minor Perspective on Rank Constrained Optimization Shixuan Zhang, Georgia Institute of Technology, Atlanta, GA, United States, Andy Sun Many combinatorial and mixed-integer nonlinear optimization problems can be formulated with constraints on matrix ranks. We propose a new perspective on dealing with rank constraints by reformulations using matrix minors. We investigate the implications of this minor perspective on generating convexification hierarchy and strong valid inequalities for the cut polytope and some QCQPs in complex variables such as AC optimal power flow. 2 - Preprocessing Algorithms and Tightening Constraints for Multiperiod Blend Scheduling Problem Yifu Chen, University of Wisconsin-Madison, Madison, WI, United States, Christos T. Maravelias The multiperiod blend scheduling problem (MBSP) considers the scheduling in a production environment that includes blending processes. MBSP can be considered as a scheduling extension of the pooling problem. In this work, we first introduce novel preprocessing algorithms to calculate bounds on critical variables in MBSP. The bounds obtained from the preprocessing algorithms, along with the new variables we defined to address the product specific features in MSBP, are used to generate tightening constraints. The methods are applicable to previously proposed MINLP models for MBSP, as well as MILP models obtained using different linear relaxation/approximation methods. 3 - A Compact Linear Programming Formulation of the Steiner Tree Problem for a Fixed Number of Terminals Matias Siebert, Georgia Institute of Technology, Atlanta, GA, United States, Shabbir Ahmed, George L. Nemhauser Given an undirected graph G=(V,E) with non-negative edge weights, and a subset R of the vertices V, the Steiner tree problem seeks to find the minimum weighted tree T that connects all vertices in R. This problem can be equivalently stated as selecting an arbitrary node r in R, and finding the minimum weighted arborescence rooted in r, whose leaves correspond to nodes in R\{r}, in the directed version of graph G. We observe that in any of those r-arborescences, the paths connecting r to the nodes in R\{r} form a Laminar family. This fact leads to a new linear programming formulation of polynomial size for fixed |R|, whose extreme points are integer and whose optimal solution is an optimal Steiner tree. 4 - New SOCP Relaxation and Branching Rules for Bipartite Bilinear Programs Asteroide Santana, Georgia Tech, Atlanta, GA, 30318, United States The bipartite bilinear program (BBP) is a QCQP where the variables can be partitioned into two sets such that fixing the variables in any one of the sets results in a linear program. We propose a new second order cone representable (SOCP) relaxation for BBP, which we show is stronger than the standard SDP relaxation intersected with the boolean quadratic polytope. We then propose a new branching rule inspired by the construction of the SOCP relaxation and show that our approach outperforms the commercial solver BARON in obtaining dual bounds for instances of a new application of BBP.

308