Informs Annual Meeting Phoenix 2018

INFORMS Phoenix – 2018

TA04

2 - The Impact of Knowledge Transfer on Knowledge Development Strategies Wenli Xiao, University of San Diego, 5998 Alcala Park, Olin Hall 335, San Diego, CA, 92110, United States, Cheryl Gaimon We introduce a dynamic model to explore a manager’s pursuit of a new product development project and an existing product improvement project. Two key features of our model are the characterization of the knowledge transfer process from the new product development project to the existing product improvement project, and the absorptive capacity for both knowledge development and knowledge transfer. We provide the optimal strategies for knowledge development and knowledge transfer for the two projects. 3 - Search for the Best Alternative: An Experimental Approach Gulru Ozkan-Seely, University of Washington, Seattle, WA, United States, David C. Hall, Jeremy Hutchison-Krupat We use a controlled experiment to study how this behavior is impacted by two factors: the difficulty associated with an initiative, and the degree to which its value is sensitive to time. Our results indicate that, individuals who face a more difficult initiative under-invest to a greater extent than those who face a simpler initiative. 4 - Blockchain and the Value of Operational Transparency for Supply- Chain Finance Gerry Tsoukalas, Wharton School of Business, 3730 Walnut Street, 567 Jon M. Huntsman Hall, Philadelphia, PA, 19104, United States, Jiri Chod, Nikolaos Trichakis, Henry Aspegren, Mark Weber We examine how blockchains, which were originally designed to provide verifiability of digital goods transactions, can provide verifiability of physical goods transactions. We identify some of the unique implementation challenges and propose ways to mitigate them. To exemplify, we describe an open-source blockchain platform we developed and one of its use cases in agricultural supply chains. We then develop a theory showing how the proposed blockchain-enabled verifiability of physical goods transactions can be leveraged by high-quality firms to signal their operational capabilities through their upstream inventory orders, and thereby finance their operations more efficiently. Joint Session OPT/Practice Curated: Mixed-Integer Quadratic Programming Sponsored: Optimization/Integer and Discrete Optimization Sponsored Session Chair: Richard Forrester, Dickinson College, Department of Mathematics, College and Louther Street, Carlisle, PA, 17013, United States 1 - Representability in Mixed-Integer Quadratic Programming Jeffrey Poskin, Boeing, Seattle, WA, United States, Alberto Del Pia Representability results play a fundamental role in optimization since they provide characterizations of the feasible sets that arise from optimization problems. In this work we study the sets that appear in the feasibility version of Mixed-Integer Quadratic Programming (MIQP) problems. MIQP has a number of practical applications, including in power systems and portfolio optimization, and also serves as a first generalization of Mixed-Integer Linear Programming to Mixed-Integer Nonlinear Programming. This work continues the study of representability in Mixed-Integer Nonlinear Programming performed by the authors as well as Lubin, Zadik, and Vielma. We provide a number of complete characterizations of the sets that appear in different classes of convex MIQPs. These settings include (i) bounded convex MIQPs, (ii) continuous convex QPs, and (iii) mixed binary convex quadratic optimization problems. 2 - Efficient Ways of Computing Strong Upper and Lower Bounds for Generalized Quadratic Assignment Problems Monique Guignard-Spielberg, Professor, University of Pennsylvania, 500 JMHH-OID Department, Wharton School/Univ Penn, Philadelphia, PA, 19104-6340, United States, Aykut Ahlatcioglu, Jongwoo Park The Generalized Quadratic Assignment Problem (GQAP) assigns a job to one machine but a machine can handle several jobs, within its capacity. Assignment costs depend on pairwise combinations of assignments. We describe the Convex Hull Heuristic and use it to generate quickly good feasible solutions. We also show how to compute RLT2-quality bounds by computing Lagrangean bounds for a special 0-1 RLT1-like model. We present results for GQAP instances from the literature as well as for the special case of the Crossdock Door Assignment Problem with up to 6000 0-1 variables. n TA04 North Bldg 122A

3 - Optimal Solutions to the Quadratic Knapsack Problems: Experiments with Improved Linearization Yu Du, Professor, University of Colorado Denver, 1475 Lawrence Street, Office 5021, Denver, CO, 80202-2219, United States, Gary A. Kochenberger, Fred W. Glover, Haibo Wang A common approach for finding optimal solutions to Quadratic Knapsack Problems (QKP) is to adopt an equivalent linearization of the quadratic model and then solve the linear model with an exact solver such as CPLEX. Previous studies have demonstrated the potential of this approach. At the same time, these studies have exposed a limitation in terms of long solution times as problems scale in size.In this study we adopt a successful linearization and experiment with simple ways to enhance its performance by strengthening a key parameter (bound) in the model. Substantial computational experience is provided giving guidance for improved practice. 4 - A Computational Study of Linearization Strategies for 0-1 Quadratic Programs Richard Forrester, Professor of Mathematics, Dickinson College, Department of Mathematics, College and Louther Street, Carlisle, PA, 17013, United States A common approach for solving 0-1 quadratic programs is to recast the nonlinear program into an equivalent form through the introduction of auxiliary variables and constraints. Then the resulting model can be solved using a standard mixed 0-1 solver. In this talk we present the results of an extensive computational study examining the strengths and weaknesses of the many different linearization approaches considered in the literature. In addition, we provide recommendations for which approach to use based on the specific class of 0-1 quadratic programs to be optimized. Recent Advances in Optimization Algorithms Sponsored: Optimization/Linear and Conic Optimization Sponsored Session Chair: Robert Michael Freund, Massachusetts Institute of Technology, 77 Massachusetts Avenue E62-567, E62-567, Cambridge, MA, 02139- 4307, United States 1 - Accelerating Greedy Coordinate Descent Methods Robert Michael Freund, Professor, Massachusetts Institute of Technology, 77 Massachusetts Avenue E62-567, E62-567, Cambridge, MA, 02139-4307, United States, Haihao Lu, Vahab Mirrokni We study ways to accelerate greedy coordinate descent in theory, in practice, or both. We introduce and study two algorithms: Accelerated Semi-Greedy Coordinate Descent (ASCD) and Accelerated Greedy Coordinate Descent (AGCD). While ASCD takes greedy steps in the x-updates and randomized steps in the z- updates, AGCD only takes greedy steps (but lacks acceleration guarantees). We show that ASCD achieves O(1/k2) convergence. Our computational experiments demonstrate that AGCD and ASCD outperform Accelerated Randomized Coordinate Descent on a wide variety of instances. We also present a Lyapunov energy function argument that yields insight into the different performance of these methods. 2 - Solving Linear Inequalities via Non-convex Optimization Jourdain Lamperski, MIT, Cambridge, MA, 02139, United States We mainly consider solving homogeneous linear inequalities. We formulate a non-convex optimization problem in a slightly lifted space, whose critical points map to feasible solutions of the linear inequalities. We show various properties of the non-convex objective function and develop an algorithm that computes critical points thereof, thus yielding an algorithm for linear inequalities. We establish convergence guarantees for the algorithm and further investigate its performance via computational experiments. 3 - An Optimal Algorithm for Stochastic Three Composite Optimization Renbo Zhao, MIT, Muckley Bldg, 1 Amherst St, Cambridge, MA, Boston, MA, 02142, United States We develop an optimal primal-dual first-order algorithm for a class of stochastic three-composite convex minimization problems. The convergence rate of our method not only improves upon the existing methods, but also matches a lower bound derived for all first-order methods that solve this problem. We extend our proposed algorithm to solve a composite stochastic program with any finite number of nonsmooth functions. In addition, we generalize an optimal stochastic alternating direction method of multipliers algorithm proposed for the two- composite case to solve this problem, and establish its connection to our optimal primal-dual algorithm. n TA05 North Bldg 122B

244