Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

WA06

n WA06 North Bldg 122C Journal of Global Optimization: INFORMS Issue Highlights Sponsored: Optimization/Global Optimization Sponsored Session Chair: Sergiy Butenko, Texas A&M University, College Station, TX, 77843-3131, United States 1 - On Branching-point Selection for Trilinear Monomials in Spatial Branch-and-bound: The Hull Relaxation Emily Speakman, Otto von Guericke University, Universitatplatz 2, IMO, G2-213, Magdeburg, 39106, Germany, Jon Lee In Speakman and Lee (2017), we analytically developed the idea of using volume as a measure for comparing relaxations in the context of spatial branch-and- bound. Specifically, for trilinear monomials, we analytically compared the three possible ``double-McCormick relaxations’’ with the tight convex-hull relaxation. Here, again using volume as a measure, for the convex-hull relaxation of trilinear monomials, we establish simple rules for determining the optimal branching variable and optimal branching point. Additionally, we compare our results with current software practice. 2 - Unifying Local-global Type Properties in Vector Optimization Ovidiu Bagdasar, University of Derby, Derby, United Kingdom, Nicolae Popovici It is well-known that all local minimum points of a semistrictly quasiconvex real- valued function are global minimum points. Also, any local maximum point of an explicitly quasiconvex real-valued function is a global minimum point, provided that it belongs to the intrinsic core of the function’s domain. We have shown that these “local min - global min and “local max - global min type properties can be extended and unified by a general local-global extremality principle for generalized convex vector-valued functions with respect to two proper subsets of the outcome space. 3 - A Simplicial Homology Algorithm for Lipschitz Optimisation Stefan Endres, University of Pretoria, Pretoria, South Africa, Carl Sandrock, Walter W. Focke The simplicial homology global optimisation (SHGO) algorithm is a general purpose global optimisation algorithm based on applications of simplicial integral homology and combinatorial topology. SHGO approximates the homology groups of a complex built on a hypersurface homeomorphic to a complex on the objective function. This provides both approximations of locally convex subdomains in the search space through Sperner’s lemma and a useful visual tool for characterising and efficiently solving higher dimensional black and grey box optimisation problems. The algorithm is specialised in finding all the local minima of an objective function with expensive function evaluations efficiently. 4 - A Nonconvex Quadratic Optimization Approach to the Maximum Edge Weight Clique Problem Seyedmohammadhossein Hosseinian, Texas A&M University, College Station, TX, 77843-3131, United States, Dalila B.M.M. Fontes, Sergiy Butenko Given an undirected and edge-weighted graph, the maximum edge weight clique (MEWC) problem is to find a subset of vertices inducing a complete subgraph with the maximum total sum of edge weights. We propose a quadratic optimization formulation for the MEWC problem and study characteristics of this formulation in terms of local and global optimality. In addition, we present an exact algorithm to solve the MEWC problem. The algorithm is a combinatorial branch-and-bound procedure that takes advantage of a new upper bound as well as an efficient construction heuristic based on the proposed quadratic formulation. Results of computational experiments on some benchmark instances are also presented. 5 - Exploiting Algebraic Structure in the Belgian Chocolate Problem Zachary Burr Charles, University of Wisconsin, Madison, WI, United States The Belgian chocolate problem involves maximizing a parameter delta over a non-convex region of polynomials. Prior methods may require many iterations or find non-optimal delta. We give a global optimization method that outperforms these methods by exploiting algebraic structure. This allows us to find large values of delta via a simpler combinatorial optimization problem. Our approach leads to the largest known value of delta to date, delta = 0.9808348. We also show that in low degree settings, our method recovers previous known upper bounds on delta.

n WA07 North Bldg 123 Social Networks and Algorithms Sponsored: Optimization/Network Optimization Sponsored Session Chair: Ali Rahim Taleqani, Upper Great Plains Transportation Institute, 310 East Bison Court, Fargo, ND, 58102, United States 1 - Understanding the Positions, Activeness and Contributions in Online Task-oriented Community Network Ruiyao Xie, Xi’an Jiaotong University, Xi’an, 710049, China City University of Hong Kong, Kowloon, Nam Shan Chuen Road, Nam Shan Building, Hong Kong, Qingpeng Zhang, Wentian Cui Open source software community is a prominent case of online task-oriented community. We focused on the relationship between actors’ positions in the network and contributions. Through the empirical study, we found that: Structural holes have the advantage in coding contributions. Brokerage of developers’ positions is positively associated with coding contributions; Closure of positions is negatively associated with coding contributions; Developers’ activeness moderates the relationship between closure positions and two types contributions. We analyzed time-lag effects of relationship between coding contribution and structural hole positions. 2 - Applied Lagrangian Relaxed Linear Sum Assignment Problem in Social Networks Analysis Ivan Belik, Norwegian School of Economics, Helleveien 30, Bergen, 5045, Norway We present a reformulation of the linear sum assignment problem (LSAP) and Lagrangian relaxation algorithm for the social networks analysis. The Lagrangian relaxation has only one Lagrangian multiplier that can only take on a limited number of values, making the search for the optimal multiplier easy. The interpretation of the optimal Lagrangian parameter is that its value is equal to the price that has to be paid to get all n objects assigned. In the given research, we show the practical application of the Lagrangian-relaxed LSAP in the quantitative analysis of social networks. 3 - An Algorithm to Find Multiple Distinct K-clubs in an Undirected Graph Ali Rahim Taleqani, North Dakota State University, 310 East Bison Court, Fargo, ND, 58102, United States, Chrysafis Vogiatzis, Jill Hough In this work, we discussed a new algorithm to identify multiple distinct highly centralized k-clubs. A k-club is connected set of nodes of a restricted diameter that is, where any two nodes are reachable within k hops using nodes inside the set. K-clubs have many applications in social network analysis, computer network, and communications. We implemented and evaluated the algorithm on a bike-sharing system. Stochastic Optimization Algorithms Sponsored: Optimization/Nonlinear Programming Sponsored Session Chair: Filip Hanzely, King Abdullah University of Science and Technology, Jeddah, 23955, Saudi Arabia Co-Chair: Nicolas Loizou 1 - Accelerated Minibatch Coordinate Descent Method with Arbitrary Sampling Filip Hanzely, King Abdullah University of Science and Technology, Thuwal, Jeddah, 23955, Saudi Arabia, Peter Richtarik Accelerated coordinate descent is a widely popular optimization algorithm due to its efficiency on large-dimensional problems. It achieves state-of-the-art complexity on an important class of empirical risk minimization problems. In this paper we design and analyze an accelerated coordinate descent (ACD) method which in each iteration updates a random subset of coordinates according to an arbitrary but fixed probability law. We therefore generalize “NUACDM” of Allen- Zhu et al (ICML 2016), which performs a single coordinate update. We also provide importance sampling for more popular mini-batch variants of ACD, which yields a faster convergence than the standard uniform mini-batch sampling. n WA08 North Bldg 124A

412