INFORMS 2021 Program Book

INFORMS Anaheim 2021

TD28

3 - Lower Bounds on the Size of General Branch-and-Bound Trees Yatharth Dubey, Georgia Institute of Technology, Kendall Park, NJ, 08824-1486, United States A general branch-and-bound tree is a branch-and-bound tree which is allowed to use general split disjunctions to create child nodes. We construct a packing instance, a set covering instance, and a Traveling Salesman Problem instance, such that any general branch-and-bound tree that solves these instances must be of exponential size. We also verify that an exponential lower bound on the size of general branch-and-bound trees persists when we add Gaussian noise to the coefficients of the cross polytope, thus showing that polynomial-size ``smoothed analysis’’ upper bound is not possible. The results in this paper can be viewed as the branch-and-bound analog of the seminal paper by Chvatal et al., who proved lower bounds for the Chvatal-Gomory rank. TD27 CC Room 206B In Person: Advances in Nonlinear and Stochastic Optimization I General Session Chair: Baoyu Zhou, Lehigh University, Bethlehem, PA, 18015, United States 1 - A Smoothing-based Decomposition Algorithm for Nonlinear Two-state Problems Andreas Waechter, Northwestern University, Department Of Industrial Eng. The Technological In, Evanston, IL, 60208-0834, United States, Shenyinying Tu, Ermin Wei A decomposition algorithm for nonlinear two-stage optimization problems is presented. The second-stage value function is smoothed by means of a barrier term. As a result, the first-stage problem can be solved directly with a nonlinear optimization algorithm. Fast local convergence is achieved by lifting second-stage constraints to avoid ill-conditioning near the optimal solution. 2 - A One-Bit Gradient Estimator for Comparison-Based Optimization Daniel Mckenzie, University of California, Los Angeles, Los Angeles, CA, United States, HanQin Cai, Wotao Yin, Zhenliang Zhang Comparison-based optimization is a particularly restrictive form of derivative-free optimization. Instead of having access to function evaluations one only assumes access to an oracle which, given two points x and y, returns a single bit of information indicating which is larger, f(x) or f(y). This paradigm arises frequently in practice in optimization problems where humans are providing the feedback, e.g. website AB testing, as asking humans to compare two options is typically more reliable than asking them to assign a numerical score of “goodness”.In this talk we will survey recent progress on making comparison-based optimization more query efficient, with an emphasis on a recent work by the listed authors that exploits gradient sparsity to construct an algorithm with query complexity sub-linear in the problem dimension. In Person Technology Tutorial: New Developments in AMPL: Solver Callbacks, Spreadsheet Interfaces, and Cloud Licensing Technology Tutorial 1 - New Developments in AMPL: Solver Callbacks, Spreadsheet Interfaces, and Cloud Licensing Robert Fourer, AMPL Optimization Inc., Evanston, IL, 60201- 2308, United States Built on the concept of model-based optimization, AMPL’s intuitive algebraic modeling language and prototyping environment give you a fast start on prescriptive decision-making projects. AMPL’s APIs for popular programming languages then help you build completed optimization models into your applications. Now AMPL’s APIs also help you get more functionality from widely- used MIP solvers, by providing access to a variety of solver callbacks. This presentation introduces AMPL’s generic solver callback features through two Python notebook examples: implementation of custom-designed solver stopping rules, and dynamic generation of cuts (constraints) during the solution process. Our presentation concludes with summaries of other notable developments in AMPL, including improved interfaces to spreadsheets and databases, and flexible licensing for deployment in virtual environments such as cloud services and containers. TD28 CC Room 207B

TD25 CC Room 205B In Person: Optimization in Julia General Session

Chair: Chenyang Yuan, Massachusetts Institute of Technology 1 - Conic Formulation Choice in Interior Point and Outer Approximation Algorithms Chris Coey, Massachusetts Institute of Technology, Cambridge, MA, United States, Juan Pablo Vielma Any (mixed-integer) convex problem can be reformulated as a (mixed-integer) conic problem. We introduce a variety of proper cones, which we use to write simple, natural formulations for many applied examples. We generate a diverse set of continuous and mixed-integer benchmark instances. We solve these instances using our new generic implementations of interior point and outer approximation algorithms. Our results may be helpful for practitioners deciding how to formulate conic models. 2 - Recent Advancements in Hypatia Lea Kapelevich, Massachusetts Institute of Technology, 238 Prospect St Apt 2, Cambridge, MA, 02139-1784, United States, Chris D. Coey, Juan Pablo Vielma We will discuss recent advancements in our interior point solver, Hypatia. In particular, we will look at some new cones, their barrier functions, and oracles.We will show that many advanced oracles that make our interior point algorithm more efficient are available in analytic form, which reduces the gap in the efficiency of oracles between standard and exotic cones. 3 - A Method for Large Scale Sum of Squares Optimization Chenyang Yuan, Massachusetts Institute of Technology, Cambridge, MA, United States, Benoît Legat, Pablo A. Parrilo Determining if a polynomial is a sum of squares involves solving a large semidefinite program, which quickly runs into scalability issues. We propose applying the Burer-Monteiro method to a sampled version of the problem, where equality constraints are enforced by evaluating the polynomial at random points. This method is easily parallelizable and scalable, and the problem can be solved using stochastic gradient descent. TD26 CC Room 206A In Person: Binary Decision Diagrams for Optimization General Session Chair: Yatharth Dubey, Georgia Institute of Technology, Atlanta, GA, 30318, United States 1 - Graph Coloring with Decision Diagrams: An Analysis of Variable Ordering Anthony Karahalios, Carnegie Mellon University, Pittsburgh, PA, United States, Willem-Jan van Hoeve A decision diagram approach was recently introduced to generate lower bounds for the graph coloring problem. It uses compilation via iterative refinement, which requires a variable ordering to be specified in advance. Oftentimes no single variable ordering dominates all others for a set of problem instances. This work provides an analysis and experimental evaluation of different variable ordering strategies including using portfolios of variable orderings. 2 - Deepest Cuts for Benders Decomposition Mojtaba Hosseini, Paul Merage School of Business, UCI, Irvine, CA, United States, John G. Turner Benders Decomposition (BD) has been successfully applied to a wide range of large-scale mixed-integer (linear) problems. We introduce deepest Benders cuts, a new unifying Benders cut selection technique based on a geometric interpretation of cut “depth”, and provide a comprehensive study of their properties. We further propose a generalization of the Benders separation problem that brings several well-known cut selection strategies under one umbrella. We propose the Guided Projections Algorithm for producing deepest Benders cuts and demonstrate their effectiveness in improving the convergence of the BD algorithm.

133