Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

MD07

3 - Enhanced Algorithms for Solving Biobjective Mixed Integer Programs

We study quadratic optimization with indicator variables and an M-matrix, i.e., a PSD matrix with non-positive off-diagonal entries. We prove that the minimization problem is solvable in polynomial time by showing its equivalence to a submodular minimization problem. To strengthen the formulation, we decompose the quadratic function into a sum of simple quadratic functions with at most two indicator variables each, and provide the convex-hull descriptions of these sets. We also describe strong conic quadratic valid inequalities. Computational experiments indicate that the proposed inequalities can substantially improve the strength of the continuous relaxations. 2 - Strong Formulations for Conic Quadratic Optimization with Indicator Variables Andres Gomez, University of Pittsburgh, Pittsburgh, PA, 15217, United States We study the convex hull of a mixed-integer set given by a conic quadratic inequality and indicator variables. We provide the convex hull description of the set under consideration when the continuous variables are unbounded. We propose valid nonlinear inequalities for the bounded case, and show that they describe the convex hull for the two-variable case. All the proposed inequalities are described in the original space of variables and are SOCP-representable. We present computational experiments demonstrating the strength of the proposed formulations. 3 - Exact Semidefinite Formulations for a Class of Random Nonconvex Quadratic Programs Samuel Burer, University of Iowa, Dept Mgmt Sci/Tippie College of Business, S346 Pappajohn Business Building, Iowa City, IA, 52242- 1000, United States, Yinyu Ye We study a general class of random quadratically constrained quadratic programs (QCQPs), which has exact semidefinite relaxations with high probability as long as the number of variables is significantly larger than the number of constraints. 4 - Ambiguous Chance-constrained Binary Programs under Mean-covariance Information Yiling Zhang, University of Michigan, Ann Arbor, MI, 48105, United States, Ruiwei Jiang, Siqian Shen We consider chance-constrained binary programs, where each row of inequalities that involve an uncertain technology matrix needs to be satisfied probabilistically. With the information of the mean and covariance matrix available, we solve distributionally robust chance-constrained binary programs (DCBP). Using two different ambiguity sets, we equivalently reformulate the DCBPs as 0-1 second- order cone (SOC) programs. We further utilize the submodularity of 0-1 SOC constraints and lifting to derive extended polymatroid inequalities. We incorporate the valid inequalities in a branch-and-cut algorithm for efficiently solving DCBPs. Finally, we demonstrate the computational efficacy. n MD07 North Bldg 123 Network Optimization and Graph Algorithms I Sponsored: Optimization/Network Optimization Sponsored Session Chair: Bastian Matias Bahamondes, Universidad de Chile, Sur 1848 Maipu, Santiago, 9271708, Chile 1 - A Fast Max Flow Algorithm James B. Orlin, Massachusetts Institute of Technology, MIT E62- 570, Cambridge, MA, 02139, United States, Xiaoyue Gong In 2013, Orlin proved that the max flow problem could be solved in O(nm) time. For graphs with n nodes and m arcs, his algorithm ran in O(nm + m1.94) time, which is the fastest time for very sparse graphs. If the graph is not sufficiently sparse, the fastest running time was an algorithm due to King, Rao, and Tarjan [1994]. We describe a new variant of the excess scaling algorithm for the max flow problem. Its running time strictly dominates the running time of the algorithm by King, Rao, and Tarjan. 2 - A Nested Cluster Ratio Cut for Divisive Hierarchical Clustering Victoria Ellison, Duke University, Durham, NC, United States Building upon the strengths of the minimum cluster ratio cut problem and hierarchical clustering algorithms, we propose an optimization-based divisive hierarchical clustering algorithm for networks, which we call the Nested Cluster Ratios Algorithm. This algorithm uses a proposed extension of the cluster ratio cut. We demonstrate this problem’s hierarchical clustering property via its dual relationship with a modified uniform multicommodity flow problem. Finally, we give a parametric linear programming based heuristic for this algorithm and test performance on gene co-association networks.

Ian Herszterg, Georgia Institute of Technology, 755 Ferst Dr, Atlanta, GA, 30318, United States, Diego Pecin, Natashia Boland, Tyler Perini, Martin Savelsbergh We present fast and robust algorithms for solving biobjective mixed integer programs. The algorithms extend and merge ideas from two existing state of the art methods: the Boxed Line Method and the Epsilon-Tabu Method. We demonstrate their efficacy in an extensive computational study and demonstrate that they are capable of producing a high-quality approximation of the nondominated frontier in a fraction of the time required to produce the complete nondominated frontier. 4 - Decentralized Algorithms for Distributed Integer Programming Problems with a Coupling Knapsack Constraint Ezgi Karabulut, Rensselaer Polytechnic Institute, Troy, NY, 12180- 2406, United States, Shabbir Ahmed, George L. Nemhauser Distributed optimization has been a trending topic in the recent years with the use of multiple processors to solve optimization problems. We are interested in optimizing discrete problems that use a common resource, namely integer programming problems coupled with a cardinality constraint. We focus our research on finding the optimal allocation of the resource in a decentralized way. Our distributed auction algorithm outputs an optimal allocation for problems that possess concavity property, with computational complexity of O(K), where K is the amount of the resource. We further test the performance of the algorithm on problems without the optimality guarantee. 5 - Automatic Structure Detection in Mixed Integer Programs Taghi Khaniyev, MIT Sloan School of Management, Cambridge, MA, United States, Matthew Galati, Samir Elhedhli Bordered block diagonal structure in constraint matrices of integer programs lends itself to Dantzig-Wolfe decomposition. We introduce a new measure of goodness to capture desired features in such structures. We use it to propose a new approach to identify the best structure inherent in the constraint matrix. The main building block of the proposed approach is community detection which alleviates one major drawback of the existing approaches in the literature: predefining the number of blocks. When tested, the proposed algorithm was found to identify structures that lead to significant improvements both in computation time and optimality gap compared to those detected by the state-of- the-art. n MD05 North Bldg 122B Special Session: Recent Advances in Conic Optimization Sponsored: Optimization/Linear and Conic Optimization Sponsored Session Chair: Somayeh Moazeni, Stevens Institute of Technology, Stevens Institute of Technology, Hoboken, NJ, 07030, United States 1 - Facial Reduction in Cone Optimization with Applications to Matrix Completions Henry Wolkowicz, University of Waterloo, Faculty of Mathematics, Waterloo, ON, N2L 3G1, Canada Strictly feasibility is at the heart of convex optimization. This is needed for optimality conditions, stability, and algorithmic development. New optimization modelling techniques and convex relaxations for hard nonconvex problems have shown that the loss of strict feasibility is a much more pronounced phenomenon than previously realized. These new developments suggest a reappraisal. We describe the various reasons for the loss of strict feasibility, whether due to poor modelling choices or (more interestingly) rich underlying structure, and describe ways to cope with it and, in particular, “take advantage of it”. Joint Session OPT/Practice Curated: Theories and Applications of Noncovex Quadratic Programming Sponsored: Optimization/Global Optimization Sponsored Session Chair: Yiling Zhang, University of Michigan, Ann Arbor, MI, 48105, United States 1 - Strong Formulations for Quadratic Optimization with M-matrices and Indicator Variables Alper Atamturk, University of California-Berkeley, Industrial Eng. & Operations Research, 4141 Etcheverry Hall, MC 1777, Berkeley, CA, 94720-1777, United States, Andres Gomez n MD06 North Bldg 122C

215