Organizing Committee
Abstract

Discrete optimization is a vibrant area of computational mathematics devoted to efficiently finding optimal solutions among a finite or countable set of possible feasible solutions.

A famous and classical example of a problem in discrete optimization is the traveling salesperson problem: For given cities and distances of traveling from one city to another, we seek to find the shortest route that visits each city once and returns to the starting city. Discrete optimization problems naturally arise in many kinds of applications including bioinformatics, telecommunications network design, airline scheduling, circuit design, and efficient resource allocation. The field also connects to a variety of areas in mathematics, computer science, and data analytics including approximation algorithms, convex and tropical geometry, number theory, real algebraic geometry, parameterized complexity theory, quantum computing, machine learning, and mathematical logic.

The semester program will explore links between mathematical tools and unsolved fundamental questions in these areas. We plan to explore computational techniques from discrete optimization to experimentally attack classical problems in combinatorics and other areas of pure mathematics. We will also continue the tradition of designing new algorithms for applied and industrial problems which has been part of the subject since its inception. By bringing together a diverse group of researchers, we anticipate making new connections and collaborations as well as deepening existing ones.

Image for "Discrete Optimization: Mathematics,  Algorithms, and Computation"

Confirmed Speakers & Participants

Talks will be presented virtually or in-person as indicated in the schedule below.

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee
  • Ahmad Abdi
    London School of Economics
    Mar 26-Apr 8, 2023
  • Tobias Achterberg
    Gurobi Optimization
    Apr 24-28, 2023
  • Hessa Al-Thani
    University of Michigan
    Jan 29-May 5, 2023
  • Rachael Alfant
    Rice University
    Apr 24-28, 2023
  • Carlos Alfaro Montufar
    Banco de Mexico
    Mar 26-Apr 1, 2023
  • Félix Almendra Hernández
    UC Davis
    Jan 30-Feb 3, 2023
  • Miguel Anjos
    University of Edinburgh
    Feb 27-Mar 3, 2023; Mar 17-Apr 7, 2023
  • Kurt Anstreicher
    University of Iowa
    Feb 26-Apr 28, 2023
  • Nicholas Arosemena
    Brown University
    Jan 30-Feb 3, 2023
  • Nancy Maribel Arratia Martinez
    Universidad de las Américas Puebla
    Jan 29-May 6, 2023
  • Alper Atamturk
    University of California - Berkeley
    Feb 27-Mar 3, 2023
  • Gennady Averkov
    Brandeburg Technical University
    Feb 27-Mar 3, 2023
  • Utsav Awasthi
    University of Connecticut
    Feb 27-Mar 3, 2023
  • Catherine Babecki
    University of Washington, Seattle
    Feb 23-May 5, 2023
  • Suman Balasubramanian
    DePauw University
    Mar 26-31, 2023
  • Ishan Bansal
    Cornell University
    Jan 30-Feb 3, 2023
  • Amitabh Basu
    Johns Hopkins University
    Apr 2-May 6, 2023
  • Pietro Belotti
    Politecnico di Milano
    Feb 26-Mar 10, 2023; Apr 23-29, 2023
  • Hande Benson
    Drexel University
    Feb 27-Mar 3, 2023
  • Daniel Bienstock
    Columbia University
    Feb 27-Mar 3, 2023
  • Alex Black
    UC Davis
    Jan 30-May 5, 2023
  • Merve Bodur
    University of Toronto
    Feb 27-Mar 3, 2023
  • Tristram Bogart
    Universidad de los Andes
    Mar 26-31, 2023
  • Steffen Borgwardt
    University of Colorado Denver
    Mar 27-31, 2023
  • Enrico Bortoletto
    Zuse Institute Berlin
    Mar 27-31, 2023
  • Marie-Charlotte Brandenburg
    Max Planck Institute for Mathematics in the Sciences
    Mar 26-Apr 8, 2023
  • Hauke Brinkop
    Kiel University
    Feb 26-Mar 3, 2023
  • DENISE CARIAGA SANDOVAL
    University of Edinburgh
    Feb 26-Mar 3, 2023
  • Martina Cerulli
    ESSEC Business School of Paris
    Feb 26-Mar 4, 2023
  • Teressa Chambers
    Brown University
    Jan 30-Feb 3, 2023; Mar 27-31, 2023; Apr 24-28, 2023
  • Karthekeyan Chandrasekaran
    University of Illinois Urbana-Champaign
    Feb 6-May 6, 2023
  • Effrosyni Chasioti
    Kent State University
    Jan 30-May 6, 2023
  • Zhongzhu Chen
    University of Michigan
    Jan 30-Apr 2, 2023
  • Lin Chen
    Texas Tech University
    Feb 27-Mar 3, 2023
  • Carleton Coffrin
    Los Alamos National Laboratory
    Apr 24-28, 2023
  • Vincent Cohen-Addad
    CNRS & Sorbonne Université
    Mar 27-31, 2023
  • Andrei Comăneci
    Technische Universität Berlin
    Mar 27-31, 2023
  • Gerard Cornuejols
    Carnegie Mellon University
    Mar 19-Apr 7, 2023
  • Ryan Cory-Wright
    IBM Research and Imperial College London
    Feb 27-Mar 3, 2023
  • Francisco Criado Gallart
    CUNEF Universidad
    Jan 30-Apr 29, 2023
  • Claudia D'Ambrosio
    LIX - Ecole Polytechnique
    Mar 26-May 6, 2023
  • Daniel Dadush
    Centrum Wiskunde & Informatica
    Mar 26-Apr 29, 2023
  • Maria Dascalu
    University of Massachusetts Amherst
    Jan 29-Feb 4, 2023
  • Sanjeeb Dash
    IBM Research
    Mar 27-31, 2023
  • Jesús De Loera
    University of California, Davis
    Jan 29-May 6, 2023
  • Daniel de Roux
    Carnegie Mellon University
    Feb 26-Mar 5, 2023; Apr 23-28, 2023
  • Alberto Del Pia
    University of Wisconsin-Madison
    Feb 26-Mar 4, 2023
  • Santanu Dey
    Georgia Institute of Technology.
    Apr 10-30, 2023
  • Antoine Deza
    McMaster University
    Mar 26-Apr 22, 2023
  • Bistra Dilkina
    University of Southern California
    Apr 28, 2023
  • Alina Ene
    Boston University
    Mar 27-31, 2023
  • Daniel Espinoza
    Google Research
    Feb 26-Mar 4, 2023
  • Yuri Faenza
    Columbia University
    Jan 29-Feb 2, 2023; Feb 6-8, 2023; Feb 14-15, 2023; Feb 27-28, 2023; Mar 9-10, 2023; Mar 15-19, 2023; Mar 23-24, 2023; Mar 27-28, 2023; Apr 13-14, 2023; Apr 17-18, 2023; Apr 24-25, 2023; May 1-2, 2023
  • Marcia Fampa
    Federal University of Rio de Janeiro
    Jan 29-May 6, 2023
  • Samuel Fiorini
    Université libre de Bruxelles
    Mar 26-Apr 1, 2023
  • Allison Fitisone
    University of Kentucky
    Jan 30-Feb 3, 2023; Mar 27-31, 2023; Apr 24-28, 2023
  • Antonio Frangioni
    Università di Pisa
    Feb 27-Mar 3, 2023
  • Ricardo Fukasawa
    University of Waterloo
    Feb 27-Mar 3, 2023; Apr 24-28, 2023
  • Raul Garcia
    Rice University
    Apr 24-28, 2023
  • Rohan Ghuge
    University of Michigan
    Jan 30-Apr 3, 2023
  • Ambros Gleixner
    HTW & Zuse Institute Berlin
    Apr 23-29, 2023
  • Michel Goemans
    Massachusetts Institute of Technology
    Mar 28-31, 2023
  • Andres Gomez
    University of Southern California
    Feb 26-Mar 4, 2023
  • Weston Grewe
    University of Colorado Denver
    Jan 30-Feb 3, 2023
  • Monserrat Guedes Ayala
    The University of Edinburgh
    Feb 27-Mar 3, 2023
  • Oktay Gunluk
    Cornell University
    Feb 26-Mar 4, 2023
  • Swati Gupta
    Georgia Tech
    Mar 26-Apr 1, 2023; Apr 23-29, 2023
  • Anupam Gupta
    Carnegie Mellon University
    Mar 27-31, 2023
  • Akshay Gupte
    University of Edinburgh
    Feb 27-Mar 3, 2023
  • Chengyue He
    Columbia University
    Jan 29-May 6, 2023
  • Christoph Hertrich
    The London School of Economics and Political Science
    Mar 25-May 6, 2023
  • Illya Hicks
    Rice University
    Mar 26-Apr 1, 2023
  • Dorit Hochbaum
    University of California, Berkeley
    Feb 27-Mar 3, 2023
  • Fred Holt
    T-Mobile
    Feb 27-Mar 3, 2023
  • Joey Huchette
    Google
    Apr 23-29, 2023
  • Sophie Huiberts
    Columbia University
    Mar 26-Apr 1, 2023
  • Dylan Hyatt-Denesik
    Eindhoven University of Technology
    Jan 28-Feb 5, 2023
  • Satoru Iwata
    University of Tokyo
    Mar 27-31, 2023
  • Olaniyi Iyiola
    Clarkson University
    Mar 26-Apr 1, 2023
  • Klaus Jansen
    Kiel University
    Feb 26-Mar 8, 2023; Mar 27-31, 2023
  • Stefanie Jegelka
    MIT
    Apr 24-28, 2023
  • Sean Kafer
    University of Waterloo
    Jan 29-May 7, 2023
  • Volker Kaibel
    Otto-von-Guericke Universität Magdeburg
    Apr 20-29, 2023
  • Lennart Kauther
    RWTH Aachen University
    Jan 29-Feb 4, 2023; Mar 26-Apr 1, 2023
  • Aleksandr Kazachkov
    University of Florida
    Apr 24-28, 2023
  • Aida Khajavirad
    Lehigh University
    Jan 30-Feb 3, 2023; Feb 27-Mar 3, 2023
  • Sammy Khalife
    Johns Hopkins University
    Jan 30-May 5, 2023
  • Fatma Kılınç-Karzan
    Carnegie Mellon University
    Feb 27-Mar 3, 2023
  • Nathan Klein
    University of Washington
    Mar 26-Apr 1, 2023
  • Zhuan Khye Koh
    Centrum Wiskunde en Informatica
    Mar 26-Apr 15, 2023
  • Matthias Köppe
    UC Davis
    Feb 27-Mar 3, 2023
  • Simge Küçükyavuz
    Northwestern University
    Feb 26-Mar 4, 2023
  • Shubhang Kulkarni
    University of Illinois, Urbana-Champaign
    Jan 29-May 6, 2023
  • Anatoliy Kuznetsov
    Georgia Institute of Technology
    Feb 27-Mar 3, 2023
  • Hélène Langlois
    ENPC
    Mar 26-Apr 1, 2023
  • Jon Lee
    University of Michigan
    Jan 29-May 6, 2023
  • Yoonsang Lee
    Dartmouth College
    Mar 27-31, 2023
  • Miguel Lejeune
    George Washington University
    Feb 27-Mar 3, 2023
  • Yongchun Li
    Georgia Institute of Technology
    Feb 27-Mar 3, 2023
  • Leo Liberti
    Ecole Polytechnique
    Apr 24-28, 2023
  • Jeff Linderoth
    University of Wisconsin-Madison
    Feb 27-Mar 3, 2023
  • Siyue Liu
    Carnegie Mellon University
    Feb 27-Mar 3, 2023; Mar 27-31, 2023
  • Feng Liu
    Stevens Institute of Technology
    Feb 27-Mar 2, 2023
  • Vasilis Livanos
    University of Illinois Urbana-Champaign
    Mar 25-Apr 1, 2023
  • Andrea Lodi
    Cornell Tech
    Apr 3-30, 2023
  • Daniel Loredo Duran
    Columbia University
    Apr 24-28, 2023
  • Miles Lubin
    Hudson River Trading
    Apr 23-29, 2023
  • Moira MacNeil
    University of Toronto
    Mar 26-31, 2023
  • Tobia Marcucci
    MIT
    Feb 26-Mar 4, 2023
  • Juan Carlos Martinez Mori
    Cornell University
    Jan 29-May 5, 2023
  • Berenike Masing
    Zuse Institute Berlin
    Mar 26-Apr 1, 2023
  • Rahul Mazumder
    Massachusetts Institute of Technology
    Apr 24-28, 2023
  • Catherine McGeoch
    D-Wave Systems Inc.
    Apr 24-28, 2023
  • Chiara Meroni
    ICERM
    Jan 30-Jun 2, 2023
  • Frédéric Meunier
    École Nationale des Ponts et Chaussées, CERMICS
    Apr 5-May 5, 2023
  • Jared Miller
    Northeastern University
    Jan 30-Feb 3, 2023; Mar 27, 2023
  • Cristina Molero-Río
    École Polytechnique
    Apr 24-May 3, 2023
  • Gonzalo Muñoz
    Universidad de O'Higgins
    Feb 26-Mar 4, 2023
  • Giacomo Nannicini
    University of Southern California
    Apr 24-28, 2023
  • Anand Natarajan
    MIT
    Apr 24-28, 2023
  • Bento Natura
    Georgia Tech
    Jan 29-May 6, 2023
  • Gabriel Oliveira da Ponte
    Federal University of Rio de Janeiro
    Jan 29-Feb 10, 2023
  • Neil Olver
    London School of Economics
    Mar 27-31, 2023
  • Shmuel Onn
    Technion - Israel Institute of Technology
    Mar 14-May 6, 2023
  • Yuchong Pan
    MIT
    Jan 30-May 5, 2023
  • Dimitri Papadimitriou
    University of Antwerp
    Feb 27-Mar 3, 2023
  • Ojas Parekh
    Sandia National Laboratories
    Apr 23-29, 2023
  • Ethan Partida
    Brown
    Jan 30-Feb 3, 2023
  • Kanstantsin Pashkovich
    University of Waterloo
    Mar 27-31, 2023
  • Britta Peis
    RWTH Aachen University
    Mar 27-31, 2023
  • Marc Pfetsch
    TU Darmstadt
    Feb 27-Mar 3, 2023; Apr 24-28, 2023
  • Sebastian Pokutta
    Zuse Institute Berlin (ZIB)
    Mar 25-31, 2023
  • Lionel Pournin
    University of Paris 13
    Mar 26-Apr 22, 2023
  • Tianjie Qiu
    Brown University
    Jan 30-May 5, 2023
  • Yushan Qu
    University of Michigan
    Feb 27-Mar 3, 2023
  • Rodolfo Quintero Ospina
    Lehigh University
    Jan 30-Feb 3, 2023; Feb 27-Mar 3, 2023; Apr 24-28, 2023
  • Annie Raymond
    University of Massachusetts, Amherst
    Mar 26-Apr 1, 2023
  • Eleanor Rieffel
    NASA
    Apr 24-28, 2023
  • Bárbara Rodrigues
    University of Edinburgh
    Feb 26-Mar 4, 2023
  • Thomas Rothvoss
    University of Washington
    Mar 26-Apr 1, 2023
  • Michael Roysdon
    Tel Aviv University
    Sep 1, 2022-May 5, 2023
  • Nick Sahinidis
    Georgia Institute of Technology
    Feb 27-Mar 3, 2023; Apr 23-29, 2023
  • Laura Sanità
    Bocconi University of Milan
    Jan 29-Feb 4, 2023; Mar 27-31, 2023
  • Lisa Sauermann
    MIT
    Mar 27-31, 2023
  • Nimita Shinde
    IITB-Monash Research Academy
    Sep 1, 2022-May 31, 2023
  • Mohit Singh
    Georgia Tech
    Mar 26-31, 2023
  • Martin Skutella
    TU Berlin
    Mar 26-31, 2023
  • Masoumeh Soleimani Amirshekari
    Wesleyan university/ CREC
    Mar 27-31, 2023
  • Renata Sotirov
    Tilburg University
    Feb 26-Mar 4, 2023
  • Emily Speakman
    University of Colorado - Denver
    Feb 26-Mar 4, 2023
  • Renan Spencer Trindade
    École Polytechnique, France
    Apr 24-May 4, 2023
  • Reed Spitzer
    Brown University
    Apr 24-28, 2023
  • Nagisa Sugishita
    University of Edinburgh
    Apr 24-28, 2023
  • Shengding Sun
    Georgia Institute of Technology
    Mar 27-31, 2023
  • Ola Svensson
    EPFL
    Mar 26-Apr 1, 2023
  • Mohit Tawarmalani
    Purdue University
    Feb 27-Mar 3, 2023
  • Christian Tjandraatmadja
    Google
    Apr 24-28, 2023
  • Vera Traub
    University of Bonn
    Jan 29-Feb 4, 2023
  • Madison Van Dyk
    University of Waterloo
    Apr 23-29, 2023
  • László Végh
    London School of Economics
    Mar 26-Apr 8, 2023
  • Mauricio Velasco
    Universidad de Los Andes
    Jan 29-Feb 4, 2023
  • Lucy Verberk
    Eindhoven University of Technology
    Jan 29-Feb 3, 2023
  • Juan Pablo Vielma
    Google
    Apr 23-29, 2023
  • Aapeli Vuorinen
    Columbia University
    Jan 30-Feb 3, 2023
  • Jens Vygen
    University of Bonn
    Mar 27-31, 2023
  • Fei Wang
    University of Waterloo
    Jan 31-Mar 1, 2023
  • Jie Wang
    Georgia Institute of Technology
    Feb 27-Mar 3, 2023
  • Chengyang Wang
    UC Davis
    Jan 30-Feb 3, 2023; Feb 27-Mar 3, 2023
  • Stefan Weltge
    Technical University of Munich
    Mar 24-Apr 1, 2023
  • William Wesley
    University of California Davis
    Jan 30-Feb 3, 2023; Apr 24-28, 2023
  • Weijun Xie
    Georgia Institute of Technology
    Feb 27-Mar 3, 2023
  • Luze Xu
    University of California, Davis
    Jan 29-Apr 2, 2023
  • Chao Xu
    University of Electronic Science and Technology of China
    Jan 30-Feb 3, 2023; Feb 27-Mar 3, 2023; Mar 27-31, 2023
  • Liding Xu
    ECOLE POLYTECHNIQUE
    Feb 27-Mar 3, 2023; Mar 27-31, 2023; Apr 24-28, 2023
  • Youngho Yoo
    Texas A&M University
    Mar 27-31, 2023
  • Rico Zenklusen
    ETH Zurich
    Mar 26-Apr 1, 2023
  • Shixuan Zhang
    Brown University
    Sep 6, 2022-May 5, 2023
  • Yuan Zhou
    University of Kentucky
    Jan 29-May 6, 2023
  • Hang Zhou
    Ecole Polytechnique
    Mar 26-Apr 1, 2023
  • Yiran Zhu
    The University of Edinburgh
    Feb 27-Mar 3, 2023; Apr 24-28, 2023
  • Michael Zlatin
    Carnegie Mellon University
    Mar 27-31, 2023

Visit dates listed on the participant list may be tentative and subject to change without notice.

Semester Schedule

Monday, January 30, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 8:30 - 9:30 am EST
    Check In
    11th Floor Collaborative Space
  • 9:30 - 9:50 am EST
    Check In
    11th Floor Collaborative Space
  • 9:50 - 10:00 am EST
    Welcome
    11th Floor Lecture Hall
    • Brendan Hassett, ICERM/Brown University
  • 10:00 - 11:00 am EST
    Matching Theory and School Choice
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Yuri Faenza, Columbia University
    • Session Chair
    • Jon Lee, University of Michigan
    Abstract
    Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.
  • 11:00 - 11:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 11:30 am - 12:30 pm EST
    Matching Theory and School Choice
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Yuri Faenza, Columbia University
    • Session Chair
    • Jon Lee, University of Michigan
    Abstract
    Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.
  • 12:30 - 2:30 pm EST
    Lunch/Free Time
  • 2:30 - 3:30 pm EST
    Binary polynomial optimization: theory, algorithms, and applications
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Aida Khajavirad, Lehigh University
    • Session Chair
    • Marcia Fampa, Federal University of Rio de Janeiro
    Abstract
    In this mini-course, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higher-order Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 5:00 pm EST
    Binary polynomial optimization: theory, algorithms, and applications
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Aida Khajavirad, Lehigh University
    • Session Chair
    • Marcia Fampa, Federal University of Rio de Janeiro
    Abstract
    In this mini-course, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higher-order Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
  • 5:00 - 6:30 pm EST
    Reception
    11th Floor Collaborative Space
Tuesday, January 31, 2023
  • 9:00 - 10:00 am EST
    Approximation Algorithms for Network Design Problems
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Vera Traub, University of Bonn
    • Session Chair
    • Laura Sanità, Bocconi University of Milan
    Abstract
    The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2-approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first better-than-2 approximation algorithm for Weighted Connectivity Augmentation.
  • 10:00 - 10:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:30 am EST
    Approximation Algorithms for Network Design Problems
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Vera Traub, University of Bonn
    • Session Chair
    • Laura Sanità, Bocconi University of Milan
    Abstract
    The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2-approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first better-than-2 approximation algorithm for Weighted Connectivity Augmentation.
  • 11:45 am - 1:00 pm EST
    Problem Session
    11th Floor Lecture Hall
  • 1:00 - 3:00 pm EST
    Lunch/Free Time
  • 3:00 - 5:00 pm EST
    Poster Session / Coffee Break
    Poster Session - 11th Floor Collaborative Space
Wednesday, February 1, 2023
  • 9:00 - 10:00 am EST
    Polynomial optimization on finite sets
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Mauricio Velasco, Universidad de Los Andes
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in n-variables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms. In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss: How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity? If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization? Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$ Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems. The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a self-contained introduction to this vibrant and exciting research area.
  • 10:00 - 10:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:30 am EST
    Polynomial optimization on finite sets
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Mauricio Velasco, Universidad de Los Andes
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in n-variables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms. In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss: How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity? If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization? Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$ Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems. The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a self-contained introduction to this vibrant and exciting research area.
  • 11:40 - 11:45 am EST
    Group Photo (Immediately After Talk)
    11th Floor Lecture Hall
  • 11:45 am - 2:00 pm EST
    Lunch/Free Time
  • 2:00 - 3:00 pm EST
    Matching Theory and School Choice
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Yuri Faenza, Columbia University
    • Session Chair
    • Jon Lee, University of Michigan
    Abstract
    Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.
  • 3:00 - 3:30 pm EST
    Coffee Break
    11th Floor Collaborative Space
  • 3:30 - 4:30 pm EST
    Matching Theory and School Choice
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Yuri Faenza, Columbia University
    • Session Chair
    • Jon Lee, University of Michigan
    Abstract
    Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.
Thursday, February 2, 2023
  • 9:00 - 10:00 am EST
    Approximation Algorithms for Network Design Problems
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Vera Traub, University of Bonn
    • Session Chair
    • Laura Sanità, Bocconi University of Milan
    Abstract
    The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2-approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first better-than-2 approximation algorithm for Weighted Connectivity Augmentation.
  • 10:00 - 10:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:30 am EST
    Approximation Algorithms for Network Design Problems
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Vera Traub, University of Bonn
    • Session Chair
    • Laura Sanità, Bocconi University of Milan
    Abstract
    The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2-approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first better-than-2 approximation algorithm for Weighted Connectivity Augmentation.
  • 11:30 am - 1:30 pm EST
    Lunch/Free Time
  • 1:30 - 2:30 pm EST
    Binary polynomial optimization: theory, algorithms, and applications
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Aida Khajavirad, Lehigh University
    • Session Chair
    • Marcia Fampa, Federal University of Rio de Janeiro
    Abstract
    In this mini-course, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higher-order Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
  • 2:30 - 3:30 pm EST
    Coffee Break
    11th Floor Collaborative Space
  • 3:30 - 4:30 pm EST
    Rank-one Boolean tensor factorization and the multilinear polytope
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Aida Khajavirad, Lehigh University
    • Session Chair
    • Marcia Fampa, Federal University of Rio de Janeiro
    Abstract
    In this mini-course, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments. Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higher-order Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
Friday, February 3, 2023
  • 10:00 - 11:00 am EST
    Polynomial optimization on finite sets
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Mauricio Velasco, Universidad de Los Andes
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in n-variables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms. In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss: How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity? If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization? Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$ Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems. The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a self-contained introduction to this vibrant and exciting research area.
  • 11:00 - 11:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 11:30 am - 12:30 pm EST
    Polynomial optimization on finite sets
    Seminar - 11th Floor Lecture Hall
    • Speaker
    • Mauricio Velasco, Universidad de Los Andes
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in n-variables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms. In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss: How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity? If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization? Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$ Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems. The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a self-contained introduction to this vibrant and exciting research area.
  • 12:30 - 2:30 pm EST
    Lunch/Free Time
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Monday, February 6, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:30 - 10:00 am EST
    ICERM Director and Organizer Welcome
    Welcome - 11th Floor Lecture Hall
    • Jesús De Loera, University of California, Davis
    • Marcia Fampa, Federal University of Rio de Janeiro
    • Brendan Hassett, ICERM/Brown University
    • Volker Kaibel, Otto-von-Guericke Universität Magdeburg
    • Jon Lee, University of Michigan
  • 3:30 - 4:30 pm EST
    Informal Tea
    Coffee Break - 11th Floor Collaborative Space
Tuesday, February 7, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:30 - 10:30 am EST
    Director/Organizer Meeting
    Meeting - 11th Floor Conference Room
  • 12:00 - 1:00 pm EST
    Postdoc/Graduate Student Meeting with ICERM Director
    Meeting - 11th Floor Lecture Hall
  • 2:30 - 3:30 pm EST
    Meet to organize the mother of all seminar(s)
    Meeting - 11th Floor Lecture Hall
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Wednesday, February 8, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 10:00 - 10:05 am EST
    Hessa Al-Thani Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:05 - 10:10 am EST
    Alex Black Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:10 - 10:15 am EST
    Zhongzhu Chen Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:15 - 10:20 am EST
    Rohan Ghuge Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:20 - 10:25 am EST
    Chengyue He Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:25 - 10:30 am EST
    Juan Carlos Martinez Mori Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:30 - 10:40 am EST
    Sean Kafer Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:40 - 10:50 am EST
    Sammy Khalife Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:50 - 11:00 am EST
    Chiara Meroni Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Thursday, February 9, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 10:00 - 10:05 am EST
    Gabriel Ponte Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:05 - 10:10 am EST
    Tianjie Qiu Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:15 - 10:25 am EST
    Bento Natura Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:25 - 10:35 am EST
    Michael Roysdon Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:35 - 10:45 am EST
    Nimita Shinde Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:45 - 10:55 am EST
    Fei Wang Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 10:55 - 11:05 am EST
    Luze Xu Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 11:05 - 11:15 am EST
    Shixuan Zhang Introduction
    Lightning Talks - 11th Floor Lecture Hall
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Friday, February 10, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Monday, February 13, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Tuesday, February 14, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:00 - 10:00 am EST
    Professional Development: Ethics I
    Professional Development - 11th Floor Lecture Hall
  • 10:30 - 11:15 am EST
    Semialgebraic parametric analysis by metaprogramming and applications in optimization.
    Seminar - 11th Floor Lecture Hall
    • Yuan Zhou, University of Kentucky
    Abstract
    We develop a metaprogramming technique that transforms algebraic programs for testing a property for a given input parameter into programs that compute the parameter region (proof-cell) of the input for which the property holds. The obtained proof-cells are semialgebraic sets. We borrow techniques from global optimization for the simplification and representation of proof-cells, and we investigate strategies that lead to shorter proofs. We discuss a few applications of the SPAM technique to portfolio optimization, solving multi-parametric mixed-integer programs and automated proofs of cutting plane theorems.
  • 11:15 am - 12:00 pm EST
    The Euclidean Steiner Problem.
    Seminar - 11th Floor Lecture Hall
    • Marcia Fampa, Federal University of Rio de Janeiro
    Abstract
    The Euclidean Steiner tree problem asks for a network of minimum length interconnecting a given set of points in n-dimensional Euclidean space. We present a historical background for this problem, discuss mathematical programming models and algorithms to solve it, and identify characteristics of the problem that make its solution a big challenge when n is greater than 2.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Wednesday, February 15, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Thursday, February 16, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 2:00 - 2:30 pm EST
    Introduction to the Circuits of Polyhedra: Basics, Diameters, and Optimization
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Sean Kafer, University of Waterloo
    Abstract
    This talk will serve as a ground-up introduction to the topic of circuits of polyhedra. The circuits are a set of directions associated with a given polyhedron which generalize the set of its edge-directions. As such, they are studied for their relevance to diameters of polyhedra, as well as to linear optimization. We will discuss the fundamental properties of circuits that motivate their usefulness, and we will look at the circuits of the matching and fractional matching polytopes as a concrete example. We will then introduce the circuit diameter - a generalization of the combinatorial diameter - discuss the ways in which the circuit diameter differs substantially from the combinatorial diameter, and introduce some results on the topic. Finally, we will discuss some ways in which circuits have been applied to the topic of linear optimization.
  • 2:30 - 3:00 pm EST
    Dynamic Programming and the Knapsack Problem
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Juan Carlos Martinez Mori, Cornell University
    Abstract
    In this self-contained talk, I will explain a dynamic programming approach to solve the Knapsack Problem in pseudo-polynomial time due to Lawler. Then, I will explain how to turn this approach into a fully polynomial-time approximation scheme (FPTAS), which is to say that its running time depends polynomially on the desired approximation precision. This technique, due to Ibarra and Kim, is a classical example of the rounding data approach in dynamic programming.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Friday, February 17, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Tuesday, February 21, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:00 - 10:00 am EST
    Professional Development: Ethics II
    Professional Development - 11th Floor Lecture Hall
  • 10:30 - 11:15 am EST
    Polynomial upper bounds on the number of differing columns of $\Delta$-modular integer programs
    Seminar - 11th Floor Lecture Hall
    • Luze Xu, University of California, Davis
    Abstract
    We study integer-valued matrices with bounded determinants. Such matrices appear in the theory of integer programs (IP) with bounded determinants. One of the first works about the structure of the matrix with bounded determinants was that of Heller, who identified the maximum number of differing columns in a totally unimodular matrix. Each extension of Heller's bound to general determinants has been super-polynomial in the determinants or the number of equations. We provide the first column bound that is polynomial in both values. Furthermore, we show a tight bound on the number of differing columns in a bimodular matrix; this is the first tight bound since Heller. Our analysis reveals combinatorial properties of bimodular IPs that may be of independent interest.
  • 11:15 am - 12:00 pm EST
    On circuit imbalance measures and their role in linear programming
    Seminar - 11th Floor Lecture Hall
    • Bento Natura, Georgia Tech
    Abstract
    The geometry of polytopes as well as the efficiency of many algorithms for linear programs depends on certain condition numbers of the constraint matrix. We study the circuit imbalance measure, which bounds the ratio of non-zero entries of support-minimal non-zero vectors in the kernel of the constraint matrix. We further prove stronger upper bounds on circuit diameter and the iteration complexity of circuit augmentation schemes.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Wednesday, February 22, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Thursday, February 23, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 2:00 - 3:00 pm EST
    Maximum Entropy Sampling: Introduction and Complexity
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Hessa Al-Thani, University of Michigan
    • Zhongzhu Chen, University of Michigan
    Abstract
    The problem of maximum-entropy sampling (MESP) is a fundamental and highly challenging combinatorial optimization problem that finds its applications in spatial statistics. In this talk we will introduce the problem, talk about some techniques that reduce the upper bound and we will also look at the NP-hardness of different classes of the MESP. The MESP’s objective is to identify a maximum-determinant order-s principal submatrix of an order-n covariance matrix (C). Due to its NP-hard complexity, exact solutions to MESP rely on a branch-and-bound (B&B) framework. To ensure efficient computation using the B&B technique, it is necessary to establish tight upper bounds for the optimal value of MESP. We present a range of techniques that can enhance both current and future upper bounds of MESP. These techniques operate on the principle that the optimal value of MESP remains unaffected by them, while the upper bounds are highly sensitive to their application. For certain classes of the input C we can find exact algorithms that solve the MESP. This is the case when C is tridiagonal or when C’s support graph is a spider. For both cases we will present a dynamic programming algorithm that solves the MESP. We will also present and discuss some classes of C where the MESP is NP-Hard.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Friday, February 24, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:00 - 3:30 pm EST
    Coffee Break
    11th Floor Collaborative Space
Monday, February 27, 2023
  • 8:50 - 9:00 am EST
    Welcome
    11th Floor Lecture Hall
    • Brendan Hassett, ICERM/Brown University
  • 9:00 - 9:45 am EST
    On Constrained Mixed-Integer DR-Submodular Minimization
    11th Floor Lecture Hall
    • Speaker
    • Simge Küçükyavuz, Northwestern University
    • Session Chair
    • Jon Lee, University of Michigan
    Abstract
    Diminishing Returns (DR)-submodular functions encompass a broad class of functions that are generally non-convex and non-concave. We study the problem of minimizing any DR-submodular function, with continuous and general integer variables, under box constraints and possibly additional monotonicity constraints. We propose valid linear inequalities for the epigraph of any DR-submodular function under the constraints. We further provide the complete convex hull of such an epigraph, which, surprisingly, turns out to be polyhedral. We propose a polynomial-time exact separation algorithm for our proposed valid inequalities, with which we first establish the polynomial-time solvability of this class of mixed-integer nonlinear optimization problems. This is joint work with Kim Yu.
  • 10:00 - 10:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EST
    Semidefinite Optimization with Eigenvector Branching
    11th Floor Lecture Hall
    • Speaker
    • Kurt Anstreicher, University of Iowa
    • Session Chair
    • Jon Lee, University of Michigan
    Abstract
    Semidefinite programming (SDP) problems typically utilize the constraint that X-xx' is positive semidefinite to obtain a convex relaxation of the condition X=xx', where x is an n-vector. We consider a new hyperplane branching method for SDP based on using an eigenvector of X-xx'. This branching technique is related to previous work of Saxeena, Bonami and Lee who used such an eigenvector to derive a disjunctive cut. We obtain excellent computational results applying the new branching technique to difficult instances of the two-trust-region subproblem.
  • 11:30 am - 12:15 pm EST
    A Breakpoints Based Method for the Maximum Diversity and Dispersion Problems
    11th Floor Lecture Hall
    • Speaker
    • Dorit Hochbaum, University of California, Berkeley
    • Session Chair
    • Jon Lee, University of Michigan
    Abstract
    The maximum diversity, or dispersion, problem (MDP), is to select from a given set a subset of elements of given size (budget), so that the sum of pairwise distances, or utilities, between the selected elements is maximized. We introduce here a method, called the Breakpoints (BP) algorithm, based on a technique proposed in Hochbaum (2009), to generate the concave piecewise linear envelope of the solutions to the relaxation of the problem for all values of the budget. The breakpoints in this envelope are provably optimal for the respective budgets and are attained using a parametric cut procedure that is very efficient. The problem is then solved, for any given value of the budget, by applying a greedy-like method to add or subtract nodes from adjacent breakpoints. This method works well if for the given budget there are breakpoints that are ``close". However, for many data sets and budgets this is not the case, and the breakpoints are sparse. We introduce a perturbation technique applied to the utility values in cases where there is paucity of breakpoints, and show that this results in denser collections of breakpoints. Furthermore, each optimal perturbed solution is quite close to an optimal non-perturbed solution. We compare the performance of our breakpoints algorithm to leading methods for these problems: The metaheuristic OBMA, that was shown recently to perform better than GRASP, Neighborhood search and Tabu Search, and Gurobi--an integer programming software. It is demonstrated that our method dominates the performance of these methods in terms of computation speed and in comparable or better solution quality.
  • 12:30 - 2:30 pm EST
    Lunch/Free Time
  • 2:30 - 3:15 pm EST
    Approximating integer programs with monomial orders
    11th Floor Lecture Hall
    • Virtual Speaker
    • Akshay Gupte, University of Edinburgh
    • Session Chair
    • Dorit Hochbaum, University of California, Berkeley
    Abstract
    We consider the problem of maximizing a function over integer points in a compact set. Inner- and outer-approximations of the integer feasible set are obtained using families of monomial orders over the integer lattice. The convex hull is characterized when the monomial orders satisfy some properties. When the objective function is submodular or subadditive, we provide a theoretical guarantee on the quality of the inner-approximations in terms of their gap to the optimal value. An algorithm is proposed to generate feasible solutions, and it is competitive with a commercial solver in numerical experiments on benchmark test instances for integer LPs.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EST
    Solving ACOPF problems
    11th Floor Lecture Hall
    • Speaker
    • Daniel Bienstock, Columbia University
    • Session Chair
    • Dorit Hochbaum, University of California, Berkeley
    Abstract
    In this talk we will detail our recent experience in solving the ACOPF problem, a notorious MINLP. We will do this from two perspectives. First, we will detail our experience in the recent, and on-going GO competition for solving modern, large-scale versions of ACOPF which include scenario constraints and integer variables. Second, we will outline challenges to state-of-the-art MINLP solvers based on spatial branch-and-bound that arise in ACOPF instances. Finally we will discuss some fundamental issues related to numerical precision.
  • 5:00 - 6:30 pm EST
    Reception
    11th Floor Collaborative Space
Tuesday, February 28, 2023
  • 9:00 - 9:45 am EST
    Maximal quadratic free sets: basic constructions and steps towards a full characterization
    11th Floor Lecture Hall
    • Speaker
    • Gonzalo Muñoz, Universidad de O'Higgins
    • Session Chair
    • Daniel Bienstock, Columbia University
    Abstract
    In 1971, Balas introduced intersection cuts as a method for generating cutting planes in integer optimization. These cuts are derived from convex S-free sets, and inclusion-wise maximal S-free sets yield the strongest intersection cuts. When S is a lattice, maximal S-free sets are well-studied from theoretical and computational standpoints. In this talk, we focus on the case when S is defined by a general quadratic inequality and show how to construct basic maximal quadratic-free sets. Additionally, we explore how to generalize the basic procedure to construct a plethora of new maximal quadratic-free sets for homogeneous quadratics. Joint work with Joseph Paat and Felipe Serrano.
  • 10:00 - 10:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EST
    From micro to macro structure: a journey in company of the Unit Commitment problem
    11th Floor Lecture Hall
    • Speaker
    • Antonio Frangioni, Università di Pisa
    • Session Chair
    • Daniel Bienstock, Columbia University
    Abstract
    The fact that "challenging problems motivate methodological advances", as obvious as it may seem, is nonetheless very true. I was drawn long ago to Unit Commitment problems because of a specific methodology, but studying it led us to interesting results for entirely different ones. This talk will summarise on (the current status of) a long journey of discovery that ebbed and flowed between different notions of structure, starting from the "macro" one of spatial decomposition and its algorithmic implications, descending to the "micro" one of the Perspective Reformulation of tiny fragments of the problem, putting both back together to full-problem size with the definition of strong but large formulations (and the nontrivial trade-offs they entail), and finally skyrocketing to large- and huge-scale problems (stochastic UC, stochastic reservoirs optimization, long-term energy system design) where UC (and its sub-structures) is but one of the multiple nested forms of structure. The talk will necessarily have to focus on a few of the results that hopefully have broader usefulness than just UC, among which a recent one on the Convex Hull of Star-Shaped MINLPs, but it will also try to give a broad-brush of the larger picture, with some time devoted to discussing the nontrivial implications of actually implementing solution methods for huge-scale problems with multiple nested form of heterogeneous structure and the (surely partial and tentative) attempts at tackling these issues within the SMS++ modelling system.
  • 11:30 am - 12:15 pm EST
    A fast combinatorial algorithm for the bilevel knapsack interdiction problem
    11th Floor Lecture Hall
    • Speaker
    • Ricardo Fukasawa, University of Waterloo
    • Session Chair
    • Daniel Bienstock, Columbia University
    Abstract
    The single-level (classical) knapsack problem consists of picking a subset of n items maximizing profit, subject to a budget (knapsack) constraint. In the bilevel knapsack interdiction problem, there are two levels of decision-makers. The lower-level decision maker is attempting to solve the classical knapsack problem. The upper-level decision maker has the goal of minimizing the profit of the lower-level decision maker, by picking items that will be then unavailable. The upper-level has its own (independent) knapsack constraint to satisfy too. Previous approaches to this problem were based on using MIP solvers. We develop a branch-and-bound algorithm for the problem that relies on a strong lower bound and specialized branching, using combinatorial arguments. Our approach improves on the previous best approaches by up to two orders of magnitude in our test instances, significantly increasing the size of instances that can be consistently solved to optimality. This is joint work with Noah Weninger.
  • 12:30 - 2:30 pm EST
    Lunch/Free Time
  • 2:30 - 3:15 pm EST
    Network Design Queueing MINLP: Models, Reformulations, and Algorithms
    11th Floor Lecture Hall
    • Speaker
    • Miguel Lejeune, George Washington University
    • Session Chair
    • Merve Bodur, University of Toronto
    Abstract
    We present several queueing-based optimization models to design networks in which the objective is to minimize the response time. The networks are modelled as collections of interdependent M/G/1 or M/G/K queueing systems with fixed and mobile servers. The optimization models take the form of nonconvex MINLP problems with fractional and bilinear terms. We derive a reformulation approach and propose a solution method that features a warm-start component, new optimality-based bound tightening (OBBT) techniques, and an outer approximation algorithm. In particular, we propose new MILP and feasibility OBBT models that can derive multiple variable bounds at once. The proposed approach is applied to the drone-based delivery of automated external defibrillators to out-of-hospital cardiac arrests (OHCA) and naloxone to opioid overdoses. The computational experiments are based on real-life data from Virginia Beach, and ascertain the computational efficiency of the approach and its impact on the response time and the probability of survival of patients.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EST
    Integrated Computational and Experimental Research in Mixed Integer Programming with SageMath
    11th Floor Lecture Hall
    • Virtual Speaker
    • Matthias Köppe, UC Davis
    • Session Chair
    • Merve Bodur, University of Toronto
    Abstract
    I will introduce SageMath, a general-purpose, Python-based, open-source mathematics system in development since 2005, from the viewpoint of its use in Mixed Integer Programming research. Originally conceived as a computer algebra system focused on algebraic number theory, SageMath has grown to a major integrating force in the mathematical software world that provides convenient and unified access to the best libraries and systems for polyhedral geometry, mixed integer linear programming, lattices, graph theory, commutative algebra, symbolic computation, computational group theory, and more. I will demonstrate some of these capabilities. The SageMath community welcomes contributions in the form of expository mathematical writing, constructions, algorithm development and implementation, cataloging, mathematical software integration, and more. I will highlight some possible entry points for making such contributions.
Wednesday, March 1, 2023
  • 9:00 - 9:45 am EST
    Minimizing quadratics over integers
    11th Floor Lecture Hall
    • Speaker
    • Alberto Del Pia, University of Wisconsin-Madison
    • Session Chair
    • Nick Sahinidis, Georgia Institute of Technology
    Abstract
    Mixed integer quadratic programming is the problem of minimizing a quadratic polynomial over points in a polyhedral region with some integer components. It is a natural extension of mixed integer linear programming and it has a wide array of applications. In this talk, I will survey some recent theoretical developments in mixed integer quadratic programming, with a focus on complexity, algorithms, and fundamental properties.
  • 10:00 - 10:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EST
    Optimizing for Equity in Urban Planning
    11th Floor Lecture Hall
    • Speaker
    • Emily Speakman, University of Colorado - Denver
    • Session Chair
    • Nick Sahinidis, Georgia Institute of Technology
    Abstract
    In the Environmental Justice literature, the Kolm-Pollak Equally Distributed Equivalent (EDE) is the preferred metric for quantifying the experience of a population. The metric incorporates both the center and the spread of the distribution of the individual experiences, and therefore, captures the experience of an “average” individual more accurately than the population mean. In particular, the mean is unable to measure the equity of a distribution, while the Kolm-Pollak EDE is designed to penalize for inequity. In this talk, we explore the problem of finding an optimal distribution from various alternatives using the Kolm-Pollak EDE to quantify optimal. Unfortunately, optimizing over the Kolm-Pollak EDE in a mathematical programming model is not trivial because of the nonlinearity of the function. We discuss methods to overcome this difficulty and present computational results for practical applications. Our results demonstrate that optimizing over the Kolm-Pollak EDE in a standard facility location model has the same computational burden as optimizing over the population mean. Moreover, it often results in solutions that are significantly more equitable while having little impact on the mean of the distribution, versus optimizing over the mean directly. Joint work with Drew Horton, Tom Logan, and Daphne Skipper
  • 11:30 am - 12:15 pm EST
    Explicit convex hull description of bivariate quadratic sets with indicator variables
    11th Floor Lecture Hall
    • Speaker
    • Aida Khajavirad, Lehigh University
    • Session Chair
    • Nick Sahinidis, Georgia Institute of Technology
    Abstract
    We obtain an explicit description for the closure of the convex hull of bivariate quadratic sets with indicator variables the space of original variables. We present a simple separation algorithm that can be incorporated in branch-and-cut based solvers to enhance the quality of existing relaxations.
  • 12:25 - 12:30 pm EST
    Group Photo (Immediately After Talk)
    11th Floor Lecture Hall
  • 12:30 - 2:30 pm EST
    Networking Lunch
    Lunch/Free Time - 11th Floor Collaborative Space
  • 2:30 - 3:30 pm EST
    Poster Session
    10th Floor Collaborative Space
  • 3:30 - 4:00 pm EST
    Coffee Break
    10th Floor Collaborative Space
  • 4:00 - 4:45 pm EST
    Matrix Completion over GF(2) with Applications to Index Coding
    11th Floor Lecture Hall
    • Speaker
    • Jeff Linderoth, University of Wisconsin-Madison
    • Session Chair
    • Kurt Anstreicher, University of Iowa
    Abstract
    We discuss integer-programming-based approaches to doing low-rank matrix completion over the finite field of two elements. We are able to derive an explicit description for the convex hull of an individual matrix element in the decomposition, using this as the basis of a new formulation. Computational results showing the superiority of the new formulation over a natural formulation based on McCormick inequalities with integer-valued variables, and an extended disjunctive formulation arising from the parity polytope are given in the context of linear index coding.
Thursday, March 2, 2023
  • 9:00 - 9:45 am EST
    Dantzig-Wolfe Bound by Cutting Planes
    11th Floor Lecture Hall
    • Speaker
    • Oktay Gunluk, Cornell University
    • Session Chair
    • Yuan Zhou, University of Kentucky
    Abstract
    Dantzig-Wolfe (DW) decomposition is a well-known technique in mixed-integer programming for decomposing and convexifying constraints to obtain potentially strong dual bounds. We investigate Fenchel cuts that can be derived using the DW decomposition algorithm and show that these cuts can provide the same dual bounds as DW decomposition. We show that these cuts, in essence, decompose the objective function cut one can simply write using the DW bound. Compared to the objective function cut, these Fenchel cuts lead to a formulation with lower dual degeneracy, and consequently a better computational performance under the standard branch-and-cut framework in the original space. We also discuss how to strengthen these cuts to improve the computational performance further. We test our approach on the Multiple Knapsack Assignment Problem and show that the proposed cuts are helpful in accelerating the solution time without the need to implement branch and price.
  • 10:00 - 10:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EST
    Number of inequalities in integer-programming descriptions of a set
    11th Floor Lecture Hall
    • Virtual Speaker
    • Gennady Averkov, Brandeburg Technical University
    • Session Chair
    • Yuan Zhou, University of Kentucky
    Abstract
    I am going to present results obtained jointly with Manuel Aprile, Marco Di Summa, Christopher Hojny and Matthias Schymura. Assume you want to describe a set X of integer points as the set of integer solutions of a linear system of inequalities and you want to use a system for X with the minimum number of inequalities. Can you compute this number algorithmically? The answer is not known in general! Does the choice of the coefficient field (like the field of real and the fiel of rational numbers) have any influence on the number you get as the answer? Surprisingly, it does! On a philosophical level, should we do integer programming over the rationals or real coefficients? That's actually not quite clear, but for some aspects there is a difference so that it might be interesting to reflect on this point and weigh pros and cons.
  • 11:30 am - 12:15 pm EST
    2x2-Convexifications for Convex Quadratic Optimization with Indicator Variables
    11th Floor Lecture Hall
    • Speaker
    • Alper Atamturk, University of California - Berkeley
    • Session Chair
    • Yuan Zhou, University of Kentucky
    Abstract
    In this talk, we present new strong relaxations for the convex quadratic optimization problem with indicator variables. For the bivariate case, we describe the convex hull of the epigraph in the original space of variables, and also give a conic quadratic extended formulation. Then, using the convex hull description for the bivariate case as a building block, we derive an extended SDP relaxation for the general case. This new formulation is stronger than other SDP relaxations proposed in the literature for the problem, including Shor's SDP relaxation, the optimal perspective relaxation as well as the optimal rank-one relaxation. Computational experiments indicate that the proposed formulations are quite effective in reducing the integrality gap of the optimization problems. This is a joint work with Shaoning Han and Andres Gomez.
  • 12:30 - 2:30 pm EST
    Lunch/Free Time
  • 2:30 - 3:15 pm EST
    Integer Semidefinite Programming - a New Perspective
    11th Floor Lecture Hall
    • Speaker
    • Renata Sotirov, Tilburg University
    • Session Chair
    • Fatma Kılınç-Karzan, Carnegie Mellon University
    Abstract
    Integer semidefinite programming can be viewed as a generalization of integer programming where the vector variables are replaced by positive semidefinite integer matrix variables. The combination of positive semidefiniteness and integrality allows to formulate various optimization problems as integer semidefinite programs (ISDPs). Nevertheless, ISDPs have received attention only very recently. In this talk we show how to extend the Chv\'atal-Gomory (CG) cutting-plane procedure to ISDPs. We also show how to exploit CG cuts in a branch-and-cut framework for ISDPs. Finally, we demonstrate the practical strength of the CG cuts in our branch-and-cut algorithm. Our results provide a new perspective on ISDPs.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EST
    Reciprocity between tree ensemble optimization and multilinear optimization
    11th Floor Lecture Hall
    • Speaker
    • Mohit Tawarmalani, Purdue University
    • Session Chair
    • Fatma Kılınç-Karzan, Carnegie Mellon University
    Abstract
    We establish a polynomial equivalence between tree ensemble optimization and optimization of multilinear functions over the Cartesian product of simplices. Using this, we derive new formulations for tree ensemble optimization problems and obtain new convex hull results for multilinear polytopes. A computational experiment on multi-commodity transportation problems with costs modeled using tree ensembles shows the practical advantage of our formulation relative to existing formulations of tree ensembles and other piecewise-linear modeling techniques. We then consider piecewise polyhedral relaxation of multilinear optimization problems. We provide the first ideal formulation over non-regular partitions. We also improve the relaxations over regular partitions by adding linking constraints. These relaxations significantly improve performance of ALPINE and are included in the software.
    This is joint work with Jongeun Kim (Google) and J.-P. P. Richard (University of Minnesota).
Friday, March 3, 2023
  • 9:00 - 9:45 am EST
    Markov Chain-based Policies for Multi-stage Stochastic Integer Linear Programming
    11th Floor Lecture Hall
    • Speaker
    • Merve Bodur, University of Toronto
    • Session Chair
    • Pietro Belotti, Politecnico di Milano
    Abstract
    We introduce a novel aggregation framework to address multi-stage stochastic programs with mixed-integer state variables and continuous local variables (MSILPs). Our aggregation framework imposes additional structure to the integer state variables by leveraging the information of the underlying stochastic process, which is modeled as a Markov chain (MC). We present a novel branch-and-cut algorithm integrated with stochastic dual dynamic programming as an exact solution method to the aggregated MSILP, which can also be used in an approximation form to obtain dual bounds and implementable feasible solutions. Moreover, we apply two-stage linear decision rule (2SLDR) approximations and propose MC-based variants to obtain high-quality decision policies with significantly reduced computational effort. We test the proposed methodologies in a novel MSILP model for hurricane disaster relief logistics planning.
  • 10:00 - 10:30 am EST
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EST
    On practical first order methods for LP
    11th Floor Lecture Hall
    • Speaker
    • Daniel Espinoza, Google Research
    • Session Chair
    • Pietro Belotti, Politecnico di Milano
    Abstract
    Solving linear programs is nowadays an everyday task. Used even in embedded systems, but also run on very large hardware. However, solving very large models has remained a major challenge. Either because most successful algorithms require more than linear space to solve such models, or because they become extremely slow in practice. Although the concept of first order-methods, and potential function methods have been around for a long time, they have failed to be broadly applicable, or no competitive implementations are widely available. In this talk we will be motivating the need for such a class of algorithms, share some (known) evidence that such schemes have worked in special situations, and present results of experiments running one such algorithm (PDLP) both in standard benchmark models, and also on very large models arising from network planning. And also on a first order method for general LPs using an exponential potential function to deal with unstructured constraints.
  • 11:30 am - 1:30 pm EST
    Lunch/Free Time
  • 1:30 - 2:15 pm EST
    Ideal polyhedral relaxations of non-polyhedral sets
    11th Floor Lecture Hall
    • Speaker
    • Andres Gomez, University of Southern California
    • Session Chair
    • Marcia Fampa, Federal University of Rio de Janeiro
    Abstract
    Algorithms for mixed-integer optimization problems are based on the sequential construction of tractable relaxations of the discrete problem, until the relaxations are sufficiently tight to guarantee optimality of the resulting solution. For classical operational and logistics problems, which can be formulated as mixed-integer linear optimization problems, it is well-known that such relaxations should be polyhedral. Thus, there has been a sustained stream of research spanning several decades on constructing and exploiting linear relaxations. As a consequence, mixed-integer linear optimization problems deemed to be intractable 30 years old can be solved to optimality in seconds or minutes nowadays. Modern statistical and decision-making problems call for mixed-integer nonlinear optimization (MINLO) formulations, which inherently lead to non-polyhedral relaxations. There has been a substantial progress in extending and adapting techniques for both the mixed-integer linear optimization and continuous nonlinear literatures, but there may a fundamental limit on the effectiveness of such approaches as they fail to exploit the specific characteristics of MINLO problems. In this talk, we discuss recent progress in studying the fundamental structure of MINLO problems. In particular, we show that such problems have a hidden polyhedral substructure that captures the non-convexities associated with discrete variables. Thus, by exploiting this substructure, convexification theory and methods based on polyhedral theory can naturally be used study non-polyhedral sets. We also provide insights into how to design algorithms that tackle the ensuing relaxations.
  • 2:30 - 3:15 pm EST
    On Dantzig-Wolfe Relaxation of Rank Constrained Optimization: Exactness, Rank Bounds, and Algorithms
    11th Floor Lecture Hall
    • Speaker
    • Weijun Xie, Georgia Institute of Technology
    • Session Chair
    • Marcia Fampa, Federal University of Rio de Janeiro
    Abstract
    This paper studies the rank constrained optimization problem (RCOP) that aims to minimize a linear objective function over intersecting a prespecified closed rank constrained domain set with two-sided linear matrix inequalities. The generic RCOP framework exists in many nonconvex optimization and machine learning problems. Although RCOP is, in general, NP-hard, recent studies reveal that its Dantzig-Wolfe Relaxation (DWR), which refers to replacing the domain set by its closed convex hull, can lead to a promising relaxation scheme. This motivates us to study the strength of DWR. Specifically, we develop the first-known necessary and sufficient conditions under which the DWR and RCOP are equivalent. Beyond the exactness, we prove the rank bound of optimal DWR extreme points. We design a column generation algorithm with an effective separation procedure. The numerical study confirms the promise of the proposed theoretical and algorithmic results.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Monday, March 6, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Tuesday, March 7, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 10:30 - 11:15 am EST
    Small simplicial spheres of large diameter
    Seminar - 11th Floor Lecture Hall
    • Francisco Criado Gallart, CUNEF Universidad
    Abstract
    In this talk we study the topological version of the Hirsch conjecture. In this topological setting, we do not study the diameter of polyhedral graphs, rather we study what is the diameter of the dual graph of a triangulation of the sphere. This is motivated by Klee's remark: We need more examples of polytopes not satisfying the Hirsch bound to understand what makes a polytope non-Hirsch. Our approach uses computer-guided search to explore a large collection of non-Hirsch simplicial spheres, and uses simulated annealing to find the smallest topological examples yet: 8-dimensional simplicial spheres with 18 vertices exceeding the Hirsch bound. We do not know if any of these are polytopal yet. Reference: https://arxiv.org/abs/1807.03030
  • 11:15 am - 12:00 pm EST
    New Algorithmic Results for Scheduling via ILPs
    Seminar - 11th Floor Lecture Hall
    • Klaus Jansen, Kiel University
    Abstract
    In this talk we present an overview about new results for scheduling problems on identical machines. During the last years we have worked on the design of efficient exact and approximation algorithms for packing and scheduling problems. In order to obtain faster (implementable) algorithms we studied integer linear programming (ILP) formulations for these problems, developed new parameterized algorithms based on the Steinitz lemma and discrepancy bounds, and proved structural results for optimum solutions of the corresponding ILPs and lower bounds on the running time. This is joint work with Sebastian Berndt, Lin Chen, Max Deppert, Kim-Manuel Klein, Lars Rohwedder, José Verschae, and Gouchuan Zhang.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Wednesday, March 8, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Thursday, March 9, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 2:00 - 2:30 pm EST
    Introduction to Iterative Methods in Combinatorial Optimization
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Shubhang Kulkarni, University of Illinois, Urbana-Champaign
    Abstract
    This talk will be an introduction to the iterated rounding/relaxation framework in combinatorial optimization. At a high-level, iterated rounding/relaxation is an algorithmic technique where one tries to leverage extreme point properties of polyhedra via the following general iterative procedure: at every iteration, (1) obtain an extreme point solution to an LP for the problem instance, (2) round a subset of the variables based on extreme point properties, (3) relax a subset of the constraints, (4) update the problem instance based on the rounded variables and relaxed constraints. I will introduce the algorithmic technique by focusing on the familiar problem of finding the minimum-cost spanning tree in an undirected graph. Here, I will introduce the uncrossing and the (fractional) token-counting methods. Then, I will show how to extend these ideas to get an additive approximation algorithm for the NP-hard degree-bounded minimum-cost spanning tree problem. I will conclude the talk with some open questions in the area.
  • 2:30 - 3:00 pm EST
    Batched Dueling Bandits
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Rohan Ghuge, University of Michigan
    Abstract
    In this talk, we discuss the K-armed dueling bandits problem, a variation of the multi-armed bandit problem where the feedback is in the form of noisy pairwise comparisons. This problem has applications in a wide-variety of domains like search ranking, recommendation systems and sports ranking where eliciting qualitative feedback is easy while real-valued feedback is not easily interpretable. Previous works have only focused on the sequential setting where the learning policy adapts after every comparison. However, in many applications such as search ranking and recommendation systems, it is preferable to perform comparisons in a limited number of parallel batches. We introduce and study the batched dueling bandits problem, for which we design algorithms with a smooth trade-off between the number of batches and regret.
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Friday, March 10, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Monday, March 13, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Tuesday, March 14, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 10:30 - 11:15 am EDT
    MILPs to optimally select public-funded R&D projects
    Seminar - 11th Floor Lecture Hall
    • Nancy Maribel Arratia Martinez, Universidad de las Américas Puebla
    Abstract
    In this talk, I present the problem of portfolio selection of research and development (R&D) projects supported by public funds. I review the different problem classes, the state-of-the-art techniques to solve them, and the most recent applications. In particular, I discuss problems that involve inaccurate information in the portfolio selection. To this end, I explore fuzzy logic and fuzzy numbers to tackle the particular challenges of these problems. I conduct numerical experiments to explore the performance of methods applied in terms of solution quality and computing time. I conclude the talk with a discussion of these methods and open problems in portfolio selection of public-funded R&D projects.
  • 11:15 am - 12:00 pm EDT
    Neural networks with linear threshold activations: structure and algorithms
    Seminar - 11th Floor Lecture Hall
    • Sammy Khalife, Johns Hopkins University
    Abstract
    (Joint work with Hongyu Cheng and Amitabh Basu)
    In this talk I will present new results on neural networks with linear threshold activation functions. The class of functions that are representable by such neural networks can be fully characterized, and two hidden layers are necessary and sufficient to represent any function in the class. This is a surprising result in the light of recent exact representability investigations for neural networks using other popular activation functions like rectified linear units. I will present nearly tight bounds on the sizes of the neural network, as well as an algorithm to solve the empirical risk minimisation (ERM) problem to global optimality for these neural networks with a fixed architecture. The algorithm’s running time is polynomial in the size of the data sample, if the input dimension and the size of the network architecture are considered fixed constants. Finally I will present a new type of architecture, the shortcut linear threshold networks, a strict superclass of the rectified linear units (ReLU) neural networks, which has several desirable theoretical properties. In particular, the ERM problem can also be solved to global optimality with a similar algorithm.
  • 12:30 - 1:00 pm EDT
    PI DAY Coffee Break
    Coffee Break - 11th Floor Collaborative Space
Wednesday, March 15, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Thursday, March 16, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 2:00 - 2:30 pm EDT
    What the heck is a graphical design?
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Catherine Babecki, University of Washington, Seattle
    Abstract
    A graphical design is a quadrature rule for a graph inspired by classical numerical integration on the sphere. Broadly speaking, that means a graphical design is a relatively small subset of graph vertices chosen to capture the global behavior of functions from the vertex set to the real numbers. I will motivate and define graphical designs for graphs with positive edge weights. Time permitting, I will explain a combinatorial bijection between graphical designs and the faces of certain polytopes associated to a graph that arises through Gale duality.
  • 2:30 - 3:00 pm EDT
    SDP hierarchies for volume computation
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Chiara Meroni, ICERM
    Abstract
    How can we compute the volume of a semialgebraic set? There is a series of works by Henrion, Lasserre, and coauthors, in which they formulate the problem as an infinite-dimensional LP, and introduce a hierarchy of SDP relaxations. I will give you an overview of the content, show some experiments, and illustrate a trick to speed the implementation. The validity of this trick is proved in some case, but still open in others. For notes to go with the talk, see the following link: https://9c122863-03c5-4d20-9f29-cc3a6fed5770.filesusr.com/ugd/1eacd3_f4b6fa4a558b474c9f00bb0e612115a4.pdf
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Friday, March 17, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Monday, March 20, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Tuesday, March 21, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:00 - 10:00 am EDT
    Professional Development: Hiring Process
    Professional Development - 11th Floor Lecture Hall
  • 10:30 - 11:15 am EDT
    Memory-efficient approximation algorithm for SDPs and its application to Max-Cut, Max-k-Cut, and Correlation Clustering
    Seminar - 11th Floor Lecture Hall
    • Nimita Shinde, ICERM, Brown University
    Abstract
    Semidefinite programs (SDPs) are a special class of convex optimization problems that have a wide range of applications in areas such as control theory, statistical modeling, correlation clustering, community detection, angular synchronization, and combinatorial optimization. We discuss three fundamental graph partitioning problems Max-Cut, Max-k-Cut, and the Max-Agree variant of correlation clustering. Given a graph G = (V, E), Max-k-Cut aims to divide the nodes into k partitions such that the weight of the edges crossing the partitions is maximized. Max-Cut is a special case of Max-k-Cut with k = 2. While Max-Agree requires additional information about the ‘similarity’ or ‘dissimilarity’ of each pair of nodes (i, j) in E, and seeks to cluster the nodes of the graph such that the sum of the ‘similar’ edges within the cluster and ‘dissimilar’ edges across the clusters is maximized. For large-scale instances of problems, the memory required to solve SDPs becomes a key computational bottleneck. We review a Gaussian sampling-based technique that replaces the decision variable of SDP with a zero-mean Gaussian random vector whose covariance is equal to the value of the decision variable. This leads to a Frank-Wolfe based algorithmic framework that tracks the random vectors instead of the matrix iterates. We then apply this technique to the three combinatorial optimization problems, Max-Cut, Max-k-Cut, and Max-Agree. We show that the proposed algorithmic framework uses O(|V | + |E|) memory and generates an approximate solution to the input problem in polynomial time that nearly achieves the best existing approximation guarantees.
  • 11:15 am - 12:00 pm EDT
    Burer-Monteiro low-rank optimization for sum-of-square certification
    11th Floor Lecture Hall
    • Shixuan Zhang, Brown University
    Abstract
    To certify a sum of $k$ squares on a real projective variety, one can minimize the distance of the sum of squares of $k$ linear forms from it in the space of quadrics. When $k$ is smaller than the dimension of linear forms, the certification problem can be applied in low-rank semidefinite relaxation of polynomial optimization, dual to the Burer-Monteiro method. In this talk, we give some preliminary results on the existence of spurious stationary points in this certification problem by explicit examples and some further study on their structure when the varieties have minimal degrees. For general varieties, we propose algorithmic remedies that guarantee the convergence to global minima.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Wednesday, March 22, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Mentoring Coffee / Tea
    Coffee Break - 11th Floor Collaborative Space
Thursday, March 23, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 2:00 - 2:30 pm EDT
    Fourier on convex compact bodies: Siegel meets Minkowski
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Sammy Khalife, Johns Hopkins University
    Abstract
    In 1889, Minkowski provided a sufficient and necessary condition for a symmetric convex body K in R^d to contain an integral point in its interior, given by Vol(K) > 2^{d}. After introducing the relevant facts in Fourier Analysis, I will discuss how one can use them to get a stronger statement expressing the gap between Vol(K) and 2^{d} in general. These results can be easily extended to intersection with Lattices and to K being compact. An application will be to deduce an original characterization of the extremal bodies, i.e. convex symmetric bodies such that Vol(K)=2^d. They correspond to the bodies which, when scaled by half, tile R^d after translations by the integral points.
  • 2:30 - 3:00 pm EDT
    PPAD hardness – the complexity of Nash equilibrium
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Chengyue He, Columbia University
    Abstract
    PPAD is a class of search problems where the solution is shown to exist by a parity argument. Whether a PPAD-complete problem admits a polytime algorithm raises significant attention in the algorithmic game theory community. We will present a brief introduction to this class by both discrete (Sperner’s lemma) and continuous (Brouwer fixed point theorem) perspectives. In addition, we will see how this relates to some famous results like Nash equilibrium, Scarf’s lemma and hypergraphic stable matching.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Friday, March 24, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Monday, March 27, 2023
  • 8:30 - 8:50 am EDT
    Check In
    11th Floor Collaborative Space
  • 8:50 - 9:00 am EDT
    Welcome
    11th Floor Lecture Hall
    • Brendan Hassett, ICERM/Brown University
  • 9:00 - 9:45 am EDT
    Interior point methods are not worse than Simplex
    11th Floor Lecture Hall
    • Speaker
    • Daniel Dadush, Centrum Wiskunde & Informatica
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    Whereas interior point methods provide polynomial-time linear programming algorithms, the running time bounds depend on bit-complexity or condition measures that can be unbounded in the problem dimension. This is in contrast with the classical simplex method that always admits an exponential bound. We introduce a new polynomial-time path-following interior point method where the number of iterations also admits a combinatorial upper bound O(2^n n^{1.5} log n) for an n-variable linear program in standard form. This complements previous work by Allamigeon, Benchimol, Gaubert, and Joswig (SIAGA 2018) that exhibited a family of instances where any path-following method must take exponentially many iterations.

    The number of iterations of our algorithm is at most O(n^{1.5} log n) times the number of segments of any piecewise linear curve in the wide neighborhood of the central path. In particular, it matches the number of iterations of any path following interior point method up to this polynomial factor. The overall exponential upper bound derives from studying the ‘max central path’, a piecewise-linear curve with the number of pieces bounded by the total length of n shadow vertex simplex paths.

    This is joint work with Xavier Allamigeon (INRIA / Ecole Polytechnique), Georg Loho (U. Twente), Bento Natura (LSE), Laszlo Vegh (LSE).
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Partitioning over submodular structures
    11th Floor Lecture Hall
    • Speaker
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    In submodular k-partitioning problems, the input is a submodular set function (given via an evaluation oracle) along with a fixed positive integer k (e.g., k = 2, 3, 4, …) and the goal is to partition the ground set into k non-empty parts so as to minimize certain natural objectives of interest. Submodular k-partitioning generalizes partitioning problems over several interesting structures including graphs and hypergraphs. The case of 2-partitioning corresponds to the classic and well-studied submodular minimization problem which is polynomial-time solvable. In this talk, I will outline recent progress towards polynomial-time solvability of submodular k-partitioning for fixed constant integers k >= 3.
  • 11:30 am - 12:15 pm EDT
    The Polyhedral Structure of Graphical Designs
    11th Floor Lecture Hall
    • Speaker
    • Catherine Babecki, University of Washington, Seattle
    • Session Chair
    • Jesús De Loera, University of California, Davis
    Abstract
    A graphical design is a quadrature rule for a graph inspired by classical numerical integration on the sphere. Broadly speaking, that means a graphical design is a relatively small subset of graph vertices chosen to capture the global behavior of functions from the vertex set to the real numbers. We first motivate and define graphical designs for graphs with positive edge weights. Through Gale duality, we exhibit a combinatorial bijection between graphical designs and the faces of certain polytopes associated to a graph, called eigenpolytopes. This polytope connection has a variety of beautiful consequences, including a proof of existence, an upper bound on the cardinality of a graphical design, methods to compute, optimize, and organize graphical designs, the existence of random walks with improved convergence rates, and complexity results for associated computational problems. This talk is based on work with Rekha Thomas, Stefan Steinerberger and David Shiroma.
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
  • 2:30 - 3:15 pm EDT
    Two New Algorithms for Set Covering
    11th Floor Lecture Hall
    • Speaker
    • Anupam Gupta, Carnegie Mellon University
    • Session Chair
    • Yuri Faenza, Columbia University
    Abstract
    In the set covering problem we are given a set system, and we want to find a subcollection with few sets whose union is the entire universe. This problem is NP-hard to approximate to better than (ln n). Moreover we know matching algorithms which are achieved by both greedy and relax-and-round based algorithms. In this talk I will give two more algorithms which achieve the same guarantee (asymptotically), one based on local search, and another based on a learning-based framework (which also works in an online setting with random arrivals). These results are based on joint works with Greg Kehne, Euiwoong Lee, Roie Levin, and Jason Li.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Alternating Linear Minimization: Revisiting von Neumann’s alternating projections
    11th Floor Lecture Hall
    • Speaker
    • Sebastian Pokutta, Zuse Institute Berlin (ZIB)
    • Session Chair
    • Yuri Faenza, Columbia University
    Abstract
    In 1933 von Neumann proved a beautiful result that one can compute a point in the intersection of two convex sets (under suitable assumptions) by alternating projections, i.e., successively projecting on one set and then the other. This algorithm assumes that one has access to projection operators for both sets. Here we consider the much weaker setup where we have only access to linear minimization oracles over the convex sets and present an algorithm to find a point in the intersection of two convex sets. Moreover, we provide a modification of the algorithm to minimize a linear function over the intersection and discuss further extensions.
  • 5:00 - 6:30 pm EDT
    Reception
    11th Floor Collaborative Space
Tuesday, March 28, 2023
  • 9:00 - 9:45 am EDT
    Reusing Cuts in Iterative Projections over Submodular Polytopes
    11th Floor Lecture Hall
    • Speaker
    • Swati Gupta, Georgia Tech
    • Session Chair
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
    Abstract
    Optimization algorithms such as projected Newton's method, FISTA, mirror descent and its variants enjoy near-optimal regret bounds and convergence rates, but suffer from a computational bottleneck of computing projections"" in potentially each iteration (e.g., O(T^{0.5}) regret of online mirror descent). On the other hand, conditional gradient variants solve a linear optimization in each iteration, but result in suboptimal rates (e.g., OT^{0.75}) regret of online Frank-Wolfe). Motivated by this trade-off in runtime v/s convergence rates, we consider iterative projections of close-by points over widely-prevalent submodular base polytopes B(f). We develop a toolkit to speed up the computation of projections using both discrete and continuous perspectives. We subsequently adapt the away-step Frank-Wolfe algorithm to use this information and enable early termination.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Clique Trees and Disjunctive Constraints
    11th Floor Lecture Hall
    • Speaker
    • Illya Hicks, Rice University
    • Session Chair
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
    Abstract
    In this talk, we explore the concept of combinatorial disjunctive constraints (CDC) and their properties. In particular, we examine when one can build small ideal mixed-integer programming (MIP) formulations using CDCs and their linkages to clique trees. We also show that generalized special ordered sets (SOS k) can be modeled by CDCs with ties to clique trees.
  • 11:30 am - 12:15 pm EDT
    Lower Bounds on the Complexity of Mixed-Integer Programs for Stable Set and Knapsack
    11th Floor Lecture Hall
    • Speaker
    • Stefan Weltge, Technical University of Munich
    • Session Chair
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
    Abstract
    Standard mixed-integer programming formulations for the stable set problem on n-node graphs require n integer variables. We prove that this is almost optimal: We give an explicit family of stable set polytopes of n-node graphs for which every polynomial-size formulation requires Ω(n / log^2 n) integer variables. By a polyhedral reduction we obtain an analogous result for n-item knapsack polytopes. This improves the previously known bounds of Ω(√n / log n) by Cevallos, Weltge & Zenklusen (SODA 2018). To this end, we extend a result of Göös, Jain & Watson (FOCS 2016, SIAM J. Comput. 2018) showing that the linear extension complexity of stable set polytopes of some n-node graphs is 2^(Ω(n / log n)). We show that the same bound holds for ɛ/n-approximations of these polytopes, for some constant ɛ > 0. On this way, we simplify several of their original arguments to obtain a proof that is accessible to a broader community. For instance, our proof does not require reductions to certain CSP problems or the notion of Karchmer-Wigderson games. This is joint work with Jamico Schade and Makrand Sinha.
  • 12:30 - 2:00 pm EDT
    Networking Lunch
    Lunch/Free Time - 11th Floor Collaborative Space
  • 2:00 - 2:45 pm EDT
    Arc connectivity and submodular flows in digraphs
    11th Floor Lecture Hall
    • Speaker
    • Ahmad Abdi, London School of Economics
    • Session Chair
    • Steffen Borgwardt, University of Colorado Denver
    Abstract
    Given a digraph D, and an integer k>=1, a k-arc-connected flip is an arc subset whose reversal makes the digraph (strongly) k-arc-connected. The main result of this work introduces a sufficient condition for the existence of a k-arc-connected flip that is also a submodular flow for a crossing submodular function. The main result has several applications to graph orientations and combinatorial optimization. For instance, if the underlying graph of D is t-edge-connected for some integer t>=2, there exists a decomposition of the arc set into a k-arc-connected flip and a (t-k)-dijoin, for any integer k such that 1<=k<=t/2. This extends Nash-Williams’ weak orientation theorem, as well as proves a weaker variant of Woodall’s conjecture on such digraphs. The main result follows from a surprising sufficient condition for the existence of capacitated integral solutions to the intersection of two submodular flow systems. This result in turn has some applications for submodular optimization. For instance, in a weakly connected digraph, the intersection of two submodular flow systems defines an integral polyhedron. Joint work with Gerard Cornuejols and Giacomo Zambelli.
  • 3:00 - 3:45 pm EDT
    Smoothed Analysis of the Simplex Method
    11th Floor Lecture Hall
    • Speaker
    • Sophie Huiberts, Columbia University
    • Session Chair
    • Steffen Borgwardt, University of Colorado Denver
    Abstract
    Explaining why the simplex method is fast in practice, despite it taking exponential time in the theoretical worst case, continues to be a challenge. Smoothed analysis is a paradigm for addressing this question. During my talk I will present recent progress in the smoothed complexity of the simplex method, discussing both upper and lower bounds.
  • 4:00 - 4:30 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:30 - 6:00 pm EDT
    Poster Session
    10th Floor Collaborative Space
Wednesday, March 29, 2023
  • 9:00 - 9:45 am EDT
    Degree Sequence Optimization and Sparse Integer Programming
    11th Floor Lecture Hall
    • Speaker
    • Shmuel Onn, Technion - Israel Institute of Technology
    • Session Chair
    • Antoine Deza, McMaster University
    Abstract
    I will suggest several open problems on optimization over degree sequences of graphs and hypergraphs and over line sums of matrices; describe several recent partial results such as for convex functions, complete graphs, complete bipartite graphs and monotone matrices, and bounded tree width or depth; and outline some proof techniques, including our recent powerful theory of sparse integer programming in high dimensions, which will be explained.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Algorithmic, combinatorial, and geometric aspects of linear optimization
    11th Floor Lecture Hall
    • Speaker
    • Lionel Pournin, University of Paris 13
    • Session Chair
    • Antoine Deza, McMaster University
    Abstract
    The simplex and interior point methods are currently the most computationally successful algorithms for linear optimization. While simplex methods follow an edge path, interior point methods follow the central path. The complexity of these methods is closely related to the combinatorial and geometric structures of the feasible region. Focusing on the analysis of worst-case constructions leading to computationally challenging instances, recently obtained lower bounds on the largest possible diameter of lattice polytopes will be presented. These bounds, via lattice zonotopes, are established using tools from combinatorics and number theory. This talk is based on joint work with Antoine Deza.
  • 11:30 am - 12:15 pm EDT
    The Exact Bipartite Matching Polytope Has Exponential Extension Complexity
    11th Floor Lecture Hall
    • Speaker
    • Ola Svensson, EPFL
    • Session Chair
    • Antoine Deza, McMaster University
    Abstract
    Given a graph with edges colored red or blue and an integer k, the exact perfect matching problem asks if there exists a perfect matching with exactly k red edges. There exists a randomized polylogarithmic-time parallel algorithm to solve this problem, dating back to the eighties, but no deterministic polynomial-time algorithm is known, even for bipartite graphs. In this talk, we discuss known approaches and their limitations. In particular, we show that there is no sub-exponential-sized linear program that can describe the convex hull of exact matchings in bipartite graphs. In fact, we prove something stronger, that there is no sub-exponential-sized linear program to describe the convex hull of perfect matchings with an odd number of red edges. To prove our result, we devise an exponential set of valid constraints that we believe are interesting in their own right. In particular, we leave as an open problem whether they define the convex hull of perfect matchings with an odd number of red edges.

    This is joint work with Xinrui Jia and Weiqiang Yuan
  • 12:15 - 12:30 pm EDT
    Group Photo (Immediately After Talk)
    11th Floor Lecture Hall
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
  • 2:30 - 3:15 pm EDT
    Approximating Weighted Connectivity Augmentation Below Factor 2
    11th Floor Lecture Hall
    • Speaker
    • Rico Zenklusen, ETH Zurich
    • Session Chair
    • Sophie Huiberts, Columbia University
    Abstract
    The Weighted Connectivity Augmentation Problem (WCAP) asks to augment the edge-connectivity of a graph by adding a min cost edge set among given candidate edges. It is among the most elementary network design problems for which no better-than-2 approximation has been known, whereas 2-approximations can easily be obtained through a variety of well-known techniques. In this talk, I will discuss an approach showing that approximation factors below 2 are achievable for WCAP, ultimately leading to a (1.5+epsilon)-approximation. Our approach is based on a highly structured directed simplification of WCAP with planar optimal solutions. We show how one can successively improve solutions of this directed simplification by moving to mixed solutions, consisting of both directed and undirected edges. These insights can be leveraged in local search and relative greedy strategies, inspired by recent advances on the Weighted Tree Augmentation Problem, to obtain a (1.5+epsilon)-approximation. This is joint work with Vera Traub.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Unit and distinct distances in typical norms
    11th Floor Lecture Hall
    • Speaker
    • Lisa Sauermann, MIT
    • Session Chair
    • Sophie Huiberts, Columbia University
    Abstract
    Given n points in the plane, how many pairs among these points can have distance exactly 1? More formally, what is the maximum possible number of unit distances among a set of n points in the plane? This problem is a very famous and still largely open problem, called the Erdos unit distance problem. One can also study this problem for other norms on R^2 (or more generally on R^d for any dimension d) that are different from the Euclidean norm. This direction has been suggested in the 1980s by Ulam and Erdos and attracted a lot of attention over the years. We give an almost tight answer to this question for almost all norms on R^d (for any given d). Furthermore, for almost all norms on R^d, we prove an asymptotically tight bound for a related problem, the so-called Erdos distinct distances problem. Our proofs rely in part on arguments from polyhedral geometry (and some tools from matroid theory are also relevant). Joint work with Noga Alon and Matija Bucic.
Thursday, March 30, 2023
  • 9:00 - 9:45 am EDT
    Understanding graphs locally
    11th Floor Lecture Hall
    • Speaker
    • Annie Raymond, University of Massachusetts, Amherst
    • Session Chair
    • Mohit Singh, Georgia Tech
    Abstract
    Graphs are ubiquitous in modern applications---including some very large graphs. This leads one to wonder, "How can we understand such large graphs?" One prevalent idea is to observe them locally: to count how many times certain substructures appear. If one knows something about the number of some particular substructures in a graph, what can one say about the number of other substructures or about global properties of the graph in general? Such problems are at the heart of extremal graph theory. In this talk, we will discuss successes and challenges in proving inequalities involving these substructures. We will also encounter graph profiles, complicated objects that allow us to understand all polynomial inequalities involving some fixed set of substructures. This is joint work with Greg Blekherman, Mohit Singh, Rekha Thomas and Fan Wei.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Untangling near minimum cuts with applications in network design
    11th Floor Lecture Hall
    • Speaker
    • Nathan Klein, University of Washington
    • Session Chair
    • Mohit Singh, Georgia Tech
    Abstract
    The structure of the set of global minimum cuts of a graph is well understood and is captured by a cactus, as proved by Dinitz, Karzanov, and Lomonosov in the 70s. However, even for small epsilon, the set of (1+epsilon) near minimum cuts has a significantly more complex structure. Benczúr and Goemans studied near minimum cuts starting in the late 90s and showed that they admit a so-called polygon representation. In this talk I will show new algorithmically useful properties of this representation and demonstrate two applications in approximating network design problems.
  • 11:30 am - 12:15 pm EDT
    The Subspace Flatness Conjecture and Faster Integer Programming
    11th Floor Lecture Hall
    • Speaker
    • Thomas Rothvoss, University of Washington
    • Session Chair
    • Mohit Singh, Georgia Tech
    Abstract
    In a seminal paper, Kannan and Lov\'asz (1988) considered a quantity $\mu_{KL}(\Lambda,K)$ which denotes the best volume-based lower bound on the covering radius $\mu(\Lambda,K)$ of a convex body $K$ with respect to a lattice $\Lambda$. Kannan and Lov\'asz proved that $\mu(\Lambda,K) \leq n \cdot \mu_{KL}(\Lambda,K)$ and the Subspace Flatness Conjecture by Dadush (2012) claims a $O(\log n)$ factor suffices, which would match the lower bound from the work of Kannan and Lov\'asz. We settle this conjecture up to a constant in the exponent by proving that $\mu(\Lambda,K) \leq O(\log^{7}(n)) \cdot \mu_{KL} (\Lambda,K)$. Our proof is based on the Reverse Minkowski Theorem due to Regev and Stephens-Davidowitz (2017). Following the work of Dadush (2012, 2019), we obtain a $(\log n)^{O(n)}$-time randomized algorithm to solve integer programs in $n$ variables. Another implication of our main result is a near-optimal flatness constant of $O(n \log^{8}(n))$. This is joint work with Victor Reis.
  • 12:30 - 2:30 pm EDT
    Networking Lunch
    Lunch/Free Time - 11th Floor Collaborative Space
  • 2:30 - 3:15 pm EDT
    Transshipments over time, submodular functions, and discrete Newton
    11th Floor Lecture Hall
    • Speaker
    • Martin Skutella, TU Berlin
    • Session Chair
    • Annie Raymond, University of Massachusetts, Amherst
    Abstract
    The Quickest Transshipment Problem is to route flow as quickly as possible from sources with supplies to sinks with demands in a network with capacities and transit times on the arcs. It is of fundamental importance for numerous applications in areas such as logistics, traffic, evacuation, and finance. More than 25 years ago, Hoppe and Tardos presented the first (strongly) polynomial-time algorithm for this problem. Their approach, as well as subsequently derived algorithms with strongly polynomial running time, is hardly practical as it relies on parametric submodular function minimization via Megiddo's parametric search. We present considerably faster algorithms for the Quickest Transshipment Problem that instead employ a subtle extension of the Discrete Newton Method. This improves the previously best known running time of $\tilde{O}(m^4k^{14})$ to $\tilde O(m^2k^5+m^3k^3+m^3n)$, where $n$ is the number of nodes, $m$ the number of arcs, and $k$ the number of source and sink nodes. Furthermore, we show how to compute integral quickest transshipments in $\tilde O(m^2k^6+m^3k^4+m^3n)$ time.

    This is joint work with Miriam Schlöter and Khai Van Tran.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Openly Disjoint Paths, Jump Systems, and Discrete Convexity
    11th Floor Lecture Hall
    • Speaker
    • Satoru Iwata, University of Tokyo
    • Session Chair
    • Annie Raymond, University of Massachusetts, Amherst
    Abstract
    In 1978, Mader discovered a min-max theorem on the number of openly disjoint paths between terminals. Sadli and Sebo (2000) showed that the set of integer vectors in that appear as degree sequences of openly disjoint paths forms a jump system. In this talk, we describe an alternative proof of this fact by using a reduction to matroid matching, which was originally observed by Lovasz (1980). In addition, we show that a function on this jump system determined by the minimum total length of openly disjoint paths enjoys the M-convexity introduced by Murota (2006).
Friday, March 31, 2023
  • 9:00 - 9:45 am EDT
    Thin trees for laminar families
    11th Floor Lecture Hall
    • Speaker
    • Neil Olver, London School of Economics
    • Session Chair
    • Britta Peis, RWTH Aachen University
    Abstract
    In the strong form of the thin tree conjecture, formulated by Goddyn in 2004, we are given a k-edge-connected graph and wish to find a tree containing at most an O(1/k) fraction of the edges across every cut. This conjecture, if true, has a variety of implications in a number of areas such as graph theory and approximation algorithms. A natural relaxation of this problem is to find a tree with at most O(1/k) edges across a fixed collection of cuts, instead of all cuts. Via a simple reduction technique followed by iterative relaxation, we show that the thin tree conjecture is true for laminar families of cuts, resolving an open question of Olver and Zenklusen from 2013. Joint work with Nathan Klein.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Streaming algorithms for k-submodular maximization and ad allocation
    11th Floor Lecture Hall
    • Speaker
    • Alina Ene, Boston University
    • Session Chair
    • Britta Peis, RWTH Aachen University
    Abstract
    Maximizing a monotone k-submodular function subject to cardinality constraints is a general model for several applications ranging from influence maximization with multiple products to sensor placement with multiple sensor types and online ad allocation. Due to the large problem scale in many applications and the online nature of ad allocation, a need arises for algorithms that process elements in a streaming fashion and possibly make online decisions. In this talk, we present a streaming algorithm for maximizing a monotone k-submodular function subject to a per-coordinate cardinality constraint attaining an approximation guarantee close to the state of the art guarantee in the offline setting. We also give a variant of the algorithm that is able to leverage machine learning predictions.
  • 11:30 am - 12:15 pm EDT
    Non-Adaptive Matroid Prophet Inequalities
    11th Floor Lecture Hall
    • Speaker
    • Kanstantsin Pashkovich, University of Waterloo
    • Session Chair
    • Britta Peis, RWTH Aachen University
    Abstract
    We consider the matroid prophet inequality problem. This problem has been extensively studied in the case of adaptive mechanisms. In particular, there is a tight 2-competitive mechanism for all matroids. However, it is not known what classes of matroids admit non-adaptive mechanisms with constant guarantee. Recently, it was shown that there are constant-competitive non-adaptive mechanisms for graphic matroids. In this talk, we show that various known classes of matroids admit constant-competitive non-adaptive mechanisms.
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
  • 2:30 - 3:15 pm EDT
    Approximating Nash Social Welfare for Submodular Valuations
    11th Floor Lecture Hall
    • Speaker
    • László Végh, London School of Economics
    • Session Chair
    • Gerard Cornuejols, Carnegie Mellon University
    Abstract
    The Nash social welfare (NSW) problem asks for an allocation of indivisible items to agents in order to maximize the geometric mean of agents’ valuations. This is a common objective for fair division, representing a balanced tradeoff between the often conflicting requirements of fairness and efficiency. The problem is NP-complete already for additive valuation functions. We present a simple, deterministic 4-approximation algorithm for the Nash Social Welfare problem under the general class submodular valuation functions. The previous best approximation factor was 380 via a randomized algorithm. We also consider the asymmetric variant of the problem where the objective is to maximize the weighted geometric mean of agents’ valuations, and give a (α+2)e-approximation, where α is the ratio between largest weight and the average weight. This is joint work with Jugal Garg, Edin Husić, Wenzheng Li, and Jan Vondrák.
  • 3:30 - 4:15 pm EDT
    Optimal Deployment of Electric Vehicle Charging Infrastructure via Bilevel Optimization
    11th Floor Lecture Hall
    • Speaker
    • Miguel Anjos, University of Edinburgh
    • Session Chair
    • Gerard Cornuejols, Carnegie Mellon University
    Abstract
    The increase of electric vehicle (EV) adoption in recent years has correspondingly increased the importance of providing adequate charging infrastructure for EV users. For a charging service provider, the fundamental question is to determine the optimal location and sizing of charging stations with respect to a given objective and subject to budget and other practical constraints. One possible objective is to maximize EV adoption as part of a public policy on electric transportation. Alternatively, the objective may be to maximize the profit gained from providing this service, in which case the price of charging is also to be optimized. These problems are fundamentally combinatorial and frequently formulated using mixed-integer linear optimization. In this talk, the focus will be on the use of bilevel optimization in this area, in particular to more accurately capture the interactions between the charging service provider and the EV users.
  • 4:30 - 5:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Monday, April 3, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Tuesday, April 4, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:00 - 10:00 am EDT
    Professional Development: Papers and Journals
    Professional Development - 11th Floor Lecture Hall
  • 10:30 - 11:15 am EDT
    Generating Short Monotone Paths in 0/1 LPs
    Seminar - 11th Floor Lecture Hall
    • Sean Kafer, University of Waterloo
    Abstract
    Even after decades of study, it is unknown whether there exists a pivot rule for the Simplex method that always solves an LP with only a polynomial number of pivots. This remains unknown even in the special case of 0/1 LPs - those defined over polytopes whose vertices are in $\{0,1\}^n$ - a case that includes many extensively studied problems in combinatorial optimization. In the pursuit of better understanding the behavior of the Simplex method on 0/1 LPs, we study the length of the monotone path generated by following steepest edges, where here we determine steepness by normalizing with the 1-norm instead of the usual 2-norm. We show that this path is of a strongly-polynomial length and that it can be computed in polynomial time. We achieve this by first considering the length of the so-called circuit-path generated by steepest descent circuit steps, where the circuits are a set of augmentation directions that generalize the set of edges. We then show that, at an extreme point solution of a 0/1 LP, a steepest descent circuit step is always equal to a steepest descent edge step, i.e., that these concepts are unified in the setting of 0/1 LPs. In light of the fact that these results do not describe the behavior of the steepest edge Simplex pivot rule, we devise an alternate pivot rule for 0/1 LPs which is guaranteed to follow the path generated by steepest edges. That is, we show the existence of a Simplex pivot rule for 0/1 LPs which is guaranteed to require only a strongly-polynomial number of non-degenerate pivots. We build upon this by giving two additional Simplex pivot rules for 0/1 LPs - instead inspired by the classical Shadow Vertex pivot rule - whose number of non-degenerate pivots are, respectively, at most the number of variables and at most the the dimension of the feasible region, achieving optimal diameter bounds for the class of 0/1 polytopes. Joint work with JesUs De Loera, Laura Sanita, and Alex Black.
  • 11:15 am - 12:00 pm EDT
    Dyadic Linear Programming
    Seminar - 11th Floor Lecture Hall
    • Virtual Speaker
    • Gerard Cornuejols, Carnegie Mellon University
    Abstract
    A finite vector is dyadic if each of its entries is a dyadic rational number, i.e. if it has an exact floating point representation. In joint work with Ahmad Abdi, Bertrand Guenin, and Levent Tuncel, we study the problem of finding a dyadic optimal solution to a linear program, if one exists.
  • 12:15 - 12:30 pm EDT
    Organizer Group Photo
    Group Photo (Immediately After Talk) - 11th Floor Lecture Hall
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Wednesday, April 5, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Thursday, April 6, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 2:00 - 2:30 pm EDT
    Competitive Equilibrium and Lattice Polytopes
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Marie-Charlotte Brandenburg, Max Planck Institute for Mathematics in the Sciences
    Abstract
    The question of existence of a competitive equilibrium is a game theoretic question in economics. It can be posed as follows: In a given auction, can we make an offer to all bidders, such that no bidder has an incentive to decline our offer? We consider a mathematical model of this question in which the auction is modeled via weights on a simple graph. In this model, the existence of an equilibrium can be translated to a condition on certain lattice points in a lattice polytope. In this talk, we discuss this translation to the polyhedral language. Using polyhedral methods, we show that in the case of the complete graph a competitive equilibrium is indeed guaranteed to exist. Along the way, we are going to meet the correlation polytope (aka the boolean quadric polytope), which is a sibling of the even more famous cut-polytope, and we make use of an LP-relaxation of this polytope due to Padberg (1989) to obtain this result. This talk is based on joint work with Christian Haase and Ngoc Mai Tran.
  • 2:30 - 3:00 pm EDT
    ReLU Neural Networks of Polynomial Size for Exact Maximum Flow Computation
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Christoph Hertrich, The London School of Economics and Political Science
    Abstract
    Neural networks with rectified linear unit (ReLU) activations are one of the most popular modern machine learning models. A function can be computed by a ReLU network (of arbitrary size) if and only if it is continuous and piecewise linear. We pose the following fundamental question: Which functions can be computed by a ReLU network of polynomial size? In order to study this question, we propose to view ReLU networks as a model of (real-valued) computation and investigate the complexity of different problems in this model. Specifically, we show that there exist polynomial-size ReLU networks to compute (i) the value of a minimum spanning tree from given edge weights in a graph, and (ii) a maximum s-t-flow from given arc capacities in a flow network. These results imply in particular that the respective problems can be solved with strongly polynomial time algorithms that solely use affine transformations and maxima computations, but no conditional branchings. This is joint work with Leon Sering (ETH Zürich).
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Friday, April 7, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Monday, April 10, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Tuesday, April 11, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:00 - 10:00 am EDT
    Professional Development: Job Applications
    Professional Development - 11th Floor Lecture Hall
  • 10:30 - 11:15 am EDT
    Aggregations of quadratic inequalities and hyperplane hidden convexity
    Seminar - 11th Floor Lecture Hall
    • Santanu Dey, Georgia Institute of Technology.
    Abstract
    We study properties of the convex hull of a set S described by quadratic inequalities. A simple way of generating inequalities valid on S is to take a nonnegative linear combinations of the defining inequalities of S. We call such inequalities aggregations. Special aggregations naturally contain the convex hull of S, and we give sufficient conditions for such aggregations to define the convex hull. We introduce the notion of hidden hyperplane convexity (HHC), which is related to the classical notion of hidden convexity of quadratic maps. We show that if the quadratic map associated with S satisfies HHC, then the convex hull of S is defined by special aggregations. To the best of our knowledge, this result generalizes all known results regarding aggregations defining convex hulls. Using this sufficient condition, we are able to recognize previously unknown classes of sets where aggregations lead to convex hull. We show that the condition known as positive definite linear combination together with hidden hyerplane convexity is a sufficient condition for finitely many aggregations to define the convex hull. All the above results are for sets defined using open quadratic inequalities. For closed quadratic inequalities, we prove a new result regarding aggregations giving the convex hull, without topological assumptions on S. This is joint work with Grigoriy Blekherman and Shengding Sun.
  • 11:15 am - 12:00 pm EDT
    Admissibility of solution estimators in stochastic optimization
    Seminar - 11th Floor Lecture Hall
    • Amitabh Basu, Johns Hopkins University
    Abstract
    We look at stochastic optimization problems through the lens of statistical decision theory. In particular, we address admissibility, in the statistical decision theory sense, of the natural sample average estimator for a stochastic optimization problem (which is also known as the empirical risk minimization (ERM) rule in learning literature). It is well known that for some simple stochastic optimization problems, the sample average estimator may not be admissible. This is known as Stein's paradox in the statistics literature. We show that for optimizing stochastic linear functions over compact sets, the sample average estimator is admissible. Moreover, we study problems with convex quadratic objectives subject to box constraints. Stein's paradox holds when there are no constraints and the dimension of the problem is at least three. We show that in the presence of box constraints, admissibility is recovered for dimensions 3 and 4.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Wednesday, April 12, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Thursday, April 13, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Friday, April 14, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Monday, April 17, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Tuesday, April 18, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:00 - 10:00 am EDT
    Professional Development: Grant Proposals
    Professional Development - 11th Floor Lecture Hall
  • 10:30 - 11:15 am EDT
    Cyclic polytopes, curves, and volumes
    Seminar - 11th Floor Lecture Hall
    • Chiara Meroni, ICERM
    Abstract
    How can one compute the volume of the convex hull of a curve? I will try to answer this question, for special families of curves. This generalizes a previously known integral formula. Our methods involve approximating the curve with cyclic polytopes and using the tool of "path signature". I will give a geometric interpretation of this volume formula in terms of lengths and areas, and conclude with examples and an open conjecture. This is a joint work with Carlos Améndola and Darrick Lee.
  • 11:15 am - 12:00 pm EDT
    Kissing lattice polytopes
    Seminar - 11th Floor Lecture Hall
    • Antoine Deza, McMaster University
    Abstract
    Motivated by algorithmic applications we consider the smallest possible distance between two disjoint lattice polytopes in dimension d. Assuming that the polytopes are described as a convex hull of vertices whose coordinates are drawn from {0,1,….,k}, we show that, for d large enough, the distance between two disjoint lattice polytopes is at least 1 over (dk)^{2d} and exhibit polytopes at distance 1 over (k root(d))^root(d). Joint work with Shmuel Onn, Sebastian Pokutta, and Lionel Pournin.
  • 12:00 - 12:05 pm EDT
    Semester Program Group Photo
    Group Photo (Immediately After Talk) - 11th Floor Lecture Hall
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Wednesday, April 19, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Thursday, April 20, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 2:00 - 2:30 pm EDT
    On fast algorithms for fundamental problems in combinatorial optimization
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Bento Natura, Georgia Tech
    Abstract
    Over the past year, there have been tremendous developments in high-accuracy solvers for fundamental problems in combinatorial optimization and operational research, such as shortest path and minimum-cost flow. Notably, while some of these techniques rely on continuous optimization methods, the current fastest algorithm for shortest paths is purely combinatorial. In this talk, we will explore the key concepts of this algorithm and provide a general overview of recent advancements in this field.
  • 2:30 - 3:00 pm EDT
    Monotone Path Polytopes
    Post Doc/Graduate Student Seminar - 11th Floor Lecture Hall
    • Alex Black, UC Davis
    Abstract
    Understanding the worst-case run-time of the simplex method remains as one of the most fundamental open problems in the theory of linear programming. One of the primary challenges for this problem is that we don't know how to find short paths on polytopes that improve a linear objective function at each step, called monotone paths. However, in this talk, I will discuss how monotone paths on polytopes relate to geometric combinatorics. In particular, I will introduce the monotone path polytope construction from the theory of fiber polytopes by Billera and Sturmfels and discuss some of the remarkable combinatorics and open problems that arise from studying examples of monotone path polytopes.
  • 3:00 - 3:15 pm EDT
    Postdoc / Graduate Student Photo
    Group Photo (Immediately After Talk) - 11th Floor Collaborative Space
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Friday, April 21, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Monday, April 24, 2023
  • 8:30 - 8:50 am EDT
    Check In
    11th Floor Collaborative Space
  • 8:50 - 9:00 am EDT
    Welcome
    11th Floor Lecture Hall
    • Brendan Hassett, ICERM/Brown University
  • 9:00 - 9:45 am EDT
    Solving Mixed-Integer Semidefinite Programs
    11th Floor Lecture Hall
    • Speaker
    • Marc Pfetsch, TU Darmstadt
    • Session Chair
    • Santanu Dey, Georgia Institute of Technology.
    Abstract
    Mixed-integer semidefinite programs form an interesting generalization of mixed-integer linear programs with many applications. Here, some of the variables of a semidefinite program are required to be integer. This talk will introduce new methods as well as techniques that can be generalized from the linear to the semidefinite world. This includes presolving methods, e.g., fixing of variables, bound strengthening etc. Moreover, handling of symmetries and conflict analysis can be adapted and have a positive impact on the performance. The talk will also try to highlight the differences between the linear and semidefinite setting. The impact of the methods will be illustrated computationally, using SCIP-SDP, an open-source solver for mixed-integer semidefinite programs based on SCIP.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Measuring the Importance of Facets of Cyclic Group Polyhedra Using Solid Angles
    11th Floor Lecture Hall
    • Speaker
    • Yuan Zhou, University of Kentucky
    • Session Chair
    • Santanu Dey, Georgia Institute of Technology.
    Abstract
    Solid angle of a polyhedral cone, which indicates the proportion of space occupied by the cone, is of significant interest in discrete optimization. Gomory introduced the cyclic group relaxation of IP. The facets of the cyclic group polyhedra are useful in generating cutting planes. To predict the importance or relative size of each facet, researchers have used the shooting experiment, which provides an estimate of the solid angle subtended by the facet at the origin. However, the obtained sizes were not always consistent due to randomness. We propose to use the solid angles measure, whose closed formulas were well established in two and three dimensions. For higher dimensions, Aomoto and Ribando showed that the solid angle of a simplicial cone can be computed using a multivariable hypergeometric series, provided that the cone satisfies a certain condition related to positive-definiteness. We provide decomposition methods to ensure that the positive-definite criterion is met. We present our results of the solid angle measures and compare them with those obtained from the shooting experiments.
  • 11:30 am - 12:15 pm EDT
    Safe and verified cutting planes in an exact MIP framework
    11th Floor Lecture Hall
    • Speaker
    • Ambros Gleixner, HTW & Zuse Institute Berlin
    • Session Chair
    • Santanu Dey, Georgia Institute of Technology.
    Abstract
    The presence of floating-point roundoff errors compromises the results of virtually all fast mixed-integer programming solvers available today. In this talk we present recent advances in our endeavour to craft a performant mixed-integer optimizer that is not only free from roundoff errors, but also produces certificates of optimality that can be verified independently of the solving process. We provide an overview of the entire framework, which is an extension of the open solver SCIP. We focus in particular on the safe generation and verification of Gomory mixed-integer cuts via mixed-integer rounding. This is joint work with Sander Borst, Leon Eifler, Fabian Frickenstein, and Jules Nicolas-Thouvenin.
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
  • 2:30 - 3:15 pm EDT
    Linear lexicographic optimization and preferential bidding system
    11th Floor Lecture Hall
    • Speaker
    • Frédéric Meunier, École Nationale des Ponts et Chaussées, CERMICS
    • Session Chair
    • Amitabh Basu, Johns Hopkins University
    Abstract
    Some airlines use the preferential bidding system to construct the schedules of their pilots. In this system, the pilots bid on the different activities and the schedules that lexicographically maximize the scores of the pilots according to their seniority are selected. A sequential approach to solve this maximization problem is natural: the problem is first solved with the bids of the most senior pilot; then it is solved with those of the second most senior without decreasing the score of the most senior, and so on. The literature admits that the structure of the problem somehow imposes such an approach. The problem can be modeled as an integer linear lexicographic program. We propose a new exact method, which relies on column generation for solving its continuous relaxation. To design this column generation, we prove that bounded linear lexicographic programs admit “primal-dual” feasible bases and we show how to compute such bases efficiently. Another contribution on which our exact method relies consists in the extension of standard tools for resource-constrained longest path problems to their lexicographic versions. Numerical experiments show that this new method is already able to solve industrial instances provided by Air France, with up to 150 pilots. Joint work with Nour ElHouda Tellache and Axel Parmentier
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Mathematical Optimization for Traffic Management in Urban Air Mobility
    11th Floor Lecture Hall
    • Speaker
    • Claudia D'Ambrosio, LIX - Ecole Polytechnique
    • Session Chair
    • Amitabh Basu, Johns Hopkins University
    Abstract
    We focus on how mathematical optimization (MO) could help build the bricks to develop Urban Air Mobility (UAM). In particular, we focus on passengers’ transportation via eVTOLs, i.e., electric flying vehicles that will allow exploiting the sky to help smooth ground traffic in densely populated areas. Clearly, one of the biggest challenges in UAM is to ensure safety. From an operational viewpoint, the flights planning can be highly affected by different kinds of disruptions, which have to be solved at the tactical deconfliction level. Inspired by the classical aircraft deconfliction, we propose a MO formulation based on a mathematical definition of vehicles separation, specialized in the UAM context. The deconfliction is based on speed changes or delayed takeoff, when possible. To the best of our knowledge, our MO model is the first that considers the whole set of conflicts at the same time. In the computational study, we, thus, compare our approach against a variant considering only pairwise conflicts, on three sets of realistic scenarios. More details can be found in Pelegrin et. al (2021).
  • 5:00 - 6:30 pm EDT
    Reception
    11th Floor Collaborative Space
Tuesday, April 25, 2023
  • 9:00 - 9:45 am EDT
    A NASA Perspective on Quantum Computing, with Emphasis on Recent Results in Distributed Computing
    11th Floor Lecture Hall
    • Speaker
    • Eleanor Rieffel, NASA
    • Session Chair
    • Giacomo Nannicini, University of Southern California
    Abstract
    The NASA Quantum Artificial Intelligence Laboratory (QuAIL) performs research to assess the potential impact of quantum computers on challenging computational problems relevant to NASA missions of the future, with particular emphasis on discrete optimization. The talk will begin with a brief overview of the QuAIL team and some general remarks on the status of and prospects for quantum computing. The talk will then transition to a discussion of distributed quantum computing, with an emphasis on recent results in the quantum CONGEST-CLIQUE Model (qCCM). I’ll introduce both the classical and quantum CONGEST-CLIQUE Models of distributed computation, and then outline two quantum algorithms that succeed with high probability; one yields an approximately optimal Steiner Tree, and the other an exact directed minimum spanning tree, each using asymptotically fewer rounds of communication than any known algorithms in the classical CONGEST-CLIQUE model. We achieve these results by combining classical algorithms with fast quantum subroutines. Additionally, we characterize the constants and logarithmic factors involved in our algorithms, as well as related prior classical and quantum algorithms, revealing the importance of “small” factors and highlighting that advances are needed to render both practical. The talk will conclude with some open questions.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Compiled nonlocal games: sum-of-squares optimization meets cryptography?
    11th Floor Lecture Hall
    • Speaker
    • Anand Natarajan, MIT
    • Session Chair
    • Giacomo Nannicini, University of Southern California
    Abstract
    Nonlocal games are a fundamental tool for testing quantum systems, but their power depends on spatial separation: a verifier must be able to separately interact with two quantum systems that cannot communicate with each other. In 2022, Kalai, Lombardi, Vaikuntanathan, and Yang proposed a method to "compile" any nonlocal game into an interaction with a *single* quantum device, using cryptography to simulate spatial separation. However, they could not characterize the behavior of quantum devices in their protocols (only classical devices). In this work, we make progress on this question by showing that the compiled version of the CHSH game forces the device to use two anti-commuting observables, just as the nonlocal version does, and as a consequence obtain an efficient argument system for polynomial-time quantum computations. Our proof is based on a modification of the noncommutative sum-of-squares method, which is one of the few general techniques known to analyze nonlocal games. Joint work with Tina Zhang, MIT.
  • 11:30 am - 12:15 pm EDT
    Approximation and Hardness Results for Quantum Max Cut
    11th Floor Lecture Hall
    • Speaker
    • Ojas Parekh, Sandia National Laboratories
    • Session Chair
    • Giacomo Nannicini, University of Southern California
    Abstract
    We will explore synergies between classical discrete optimization problems and the Local Hamiltonian problem, a natural quantum generalization of classical constraint satisfaction problems (CSPs). We will consider Quantum Max Cut, a QMA-hard 2-Local Hamiltonian problem. Quantum Max Cut is emerging as a testbed for approximating 2-Local Hamiltonian problems analogously to Max Cut’s role as a canonical CSP and discrete optimization problem that has driven development of classical heuristics, approximation algorithms, and hardness results.  We will discuss several recent results including an optimal product-state approximation for Quantum Max Cut based on a quantum version of the Lasserre hierarchy, as well as prospects for Unique-Games hardness. This talk is aimed at a broad audience and assumes no background in quantum physics.
  • 12:30 - 2:30 pm EDT
    Networking Lunch
    Lunch/Free Time - 11th Floor Collaborative Space
  • 2:30 - 3:15 pm EDT
    Quantum Annealing and Combinatorial Optimization
    11th Floor Lecture Hall
    • Speaker
    • Carleton Coffrin, Los Alamos National Laboratory
    • Session Chair
    • Swati Gupta, Georgia Tech
    Abstract
    Over the past decade the usefulness of quantum computing hardware for combinatorial optimization has been the subject of much debate. One of the central challenges of this discussion is that theoretical analysis thus far only predicts a quadratic improvement in computational complexity for quantum-accelerated optimization algorithms. In this regime runtime performance benchmarking plays an important role in understanding and quantifying the potential benefits of quantum computing for optimization tasks. In this work, we will review the mathematical foundations of the Quantum Annealing algorithm for combinatorial optimization and conduct a performance assessment of D-Wave Systems' most recent “Advantage Performance Update” computer. We show that classes of contrived problems exist where this quantum annealer can provide run time benefits over a collection of established solution methods. Although this work does not present strong evidence of an irrefutable performance benefit for this emerging quantum optimization technology, it does exhibit encouraging progress, signaling potential impacts on practical optimization tasks in the future.
  • 3:30 - 4:00 pm EDT
    Poster Session Blitz
    Lightning Talks - 11th Floor Collaborative Space
    • Speakers
    • Rachael Alfant, Rice University
    • Cristina Molero-Río, École Polytechnique
    • Renan Spencer Trindade, École Polytechnique, France
    • Nagisa Sugishita, University of Edinburgh
    • William Wesley, University of California Davis
    • Session Chair
    • Swati Gupta, Georgia Tech
  • 4:00 - 5:00 pm EDT
    Poster Session / Coffee Break
    Poster Session - 10th Floor Collaborative Space
Wednesday, April 26, 2023
  • 9:00 - 9:45 am EDT
    Milestones on the Quantum Utility Highway
    11th Floor Lecture Hall
    • Speaker
    • Catherine McGeoch, D-Wave Systems Inc.
    • Session Chair
    • Swati Gupta, Georgia Tech
    Abstract
    We introduce Quantum Utility, an approach to quantum performance evaluation that aims to capture the user experience by considering overhead costs associated with the quantum computation. We define Milestones, which may be thought of as demonstrations of quantum utility in restricted contexts associated with subsets of overheads. We evaluate performance of a D-Wave Advantage system with respect to three Milestones, and discuss these results in the context of technological progress of annealing based QPUs.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    First-order methods for LP
    11th Floor Lecture Hall
    • Speaker
    • Miles Lubin, Hudson River Trading
    • Session Chair
    • Juan Pablo Vielma, Google
    Abstract
    We present new approaches for solving linear programming problems based on first-order methods and discuss some of the implications for computational discrete optimization. Among other advantages over simplex and barrier methods, these approaches have demonstrated scalability to very large instances (billions of variables) and have the potential to run on new hardware platforms. The talk covers recent theoretical and computational developments, including the release of PDLP in the OR-Tools library, and reviews preliminary applications in integer programming. This talk describes work completed while the speaker was at Google Research.
  • 11:30 am - 12:15 pm EDT
    Neural Network Verification As Piecewise Linear Optimization
    11th Floor Lecture Hall
    • Speaker
    • Joey Huchette, Google
    • Session Chair
    • Juan Pablo Vielma, Google
    Abstract
    In this talk we discuss how neural network verification (and related tasks) can be fruitfully modeled and solved using piecewise linear optimization techniques from operations research.
  • 12:25 - 12:30 pm EDT
    Group Photo (Immediately After Talk)
    11th Floor Lecture Hall
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
  • 2:30 - 3:15 pm EDT
    Machine Learning for discrete optimization: Graph Neural Networks, generalization under shifts, and loss functions
    11th Floor Lecture Hall
    • Speaker
    • Stefanie Jegelka, MIT
    • Session Chair
    • Andrea Lodi, Cornell Tech
    Abstract
    Graph Neural Networks (GNNs) have become a popular tool for learning algorithmic tasks, in particular related to combinatorial optimization. In this talk, we will focus on the “algorithmic reasoning” task of learning a full algorithm. While GNNs have shown promising empirical results, their generalization properties are less well understood. We will try to understand in particular out-of-distribution generalization in widely used message passing GNNs, with an eye on applications in learning for optimization: what may be an appropriate metric for measuring shift? Under what conditions will a GNN generalize to larger graphs? In the last part of the talk, we will take a brief look at objective (loss) functions for learning with discrete objects, beyond GNNs. In particular, neural networks work best with continuous, high-dimensional spaces. Can we integrate this into appropriate loss functions?
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Understanding Neural Network Expressivity via Polyhedral Geometry
    11th Floor Lecture Hall
    • Speaker
    • Christoph Hertrich, The London School of Economics and Political Science
    • Session Chair
    • Andrea Lodi, Cornell Tech
    Abstract
    Neural networks with rectified linear unit (ReLU) activations are one of the standard models in modern machine learning. Despite their practical importance, fundamental theoretical questions concerning ReLU networks remain open until today. For instance, what is the precise set of (piecewise linear) functions representable by ReLU networks with a given depth? Even the special case asking for the number of layers to compute a function as simple as max{0, x1, x2, x3, x4} has not been solved yet. In this talk we will explore the relevant background to understand this question and report about recent progress using polyhedral geometry as well as a computer-aided approach based on mixed-integer programming.
Thursday, April 27, 2023
  • 9:00 - 9:45 am EDT
    Using Trained Machine Learning Predictors in Gurobi
    11th Floor Lecture Hall
    • Speaker
    • Tobias Achterberg, Gurobi Optimization
    • Session Chair
    • Volker Kaibel, Otto-von-Guericke Universität Magdeburg
    Abstract
    In this talk, we are interested in using machine learning predictors to model relationships between variables of a MIP optimization model in Gurobi. The inputs of the trained machine learning model are MIP decision variables, and the predicted output can be used in the objective function or in other constraints. In November 2022 we released the first version of the open-source ""gurobi-machinelearning"" Python package on github.com. This package aims at making it easy to insert regression models trained by popular frameworks (e.g., scikit-learn, Keras, PyTorch) into a Gurobi model. The regression model may be a linear or logistic regression, a neural network, or based on decision trees. While the resulting optimization models have interesting potential applications, unfortunately they are often intractable with current technology. We present algorithmic improvements to Gurobi that improve performance on MIP models that include regression models--in particular optimization models with embedded ReLU neural networks. Following Fischetti and Jo (2018), we apply optimization based bound tightening on the aggregated input variable of each neuron, processing neurons in layers from the input to the output layer. But since the MIP solver is unaware of the neural network structure, we first need to identify the layers of the network from the MIP formulation. This is done by a clustering algorithm, which is also discussed in this talk.
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Global optimization with integers: model-based and data-driven approaches
    11th Floor Lecture Hall
    • Speaker
    • Nick Sahinidis, Georgia Institute of Technology
    • Session Chair
    • Volker Kaibel, Otto-von-Guericke Universität Magdeburg
    Abstract
    We present recent methodological developments in the context of three closely related computational optimization projects: 1. The BARON project for algebraic optimization through a spatial branch-and-bound algorithm that exploits various convexification techniques. 2. The ALAMO project, which relies on algebraic global optimization (BARON) to build simple models from data while enforcing shape constraints. 3. The BAM project for data-driven optimization through the integration of sampling, partitioning, and global optimization (BARON) of local algebraic surrogates constructed from data (ALAMO). We discuss connections between the three projects, report on the status of each project and their integration, and present computations on established benchmarks and applications.
  • 11:30 am - 12:15 pm EDT
    Convex hull of a monomial on a two-variable conic domain
    11th Floor Lecture Hall
    • Speaker
    • Pietro Belotti, Politecnico di Milano
    • Session Chair
    • Volker Kaibel, Otto-von-Guericke Universität Magdeburg
    Abstract
    We consider a monomial function with real exponents, which is of interest in optimization. Specifically, global mixed-integer nonlinear optimization solvers need tight convex relaxations of sets defined by nonconvex functions to find a valid lower bound. The convex hull of the monomial in two variables on a bounding box is known for some special cases. We discuss the convex hull of a generic monomial in two variables restricted to a cone rather than a bounding box. We then look at how to compute the volume of such convex hull, which is also of interest in global optimization: branching operations of branch-and-bound solvers have a great impact in solver efficiency, in particular some branching techniques that aim at minimizing the total resulting volume of the two new subproblems.
  • 12:30 - 2:30 pm EDT
    Networking Lunch
    Lunch/Free Time - 11th Floor Collaborative Space
  • 2:30 - 3:15 pm EDT
    Modeling and Duality in Domain Specific Languages for Mathematical Optimization
    11th Floor Lecture Hall
    • Speaker
    • Juan Pablo Vielma, Google
    • Session Chair
    • Marc Pfetsch, TU Darmstadt
    Abstract
    Domain specific languages (DSL) for mathematical optimization allow users to write problems in a natural algebraic format. In this talk we explore the design and implementation of OR-Tools’ MathOpt DSL.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
  • 4:00 - 4:45 pm EDT
    Solving a family of mixed integer nonlinear programs with convex first order method roots
    11th Floor Lecture Hall
    • Speaker
    • Rahul Mazumder, Massachusetts Institute of Technology
    • Session Chair
    • Marc Pfetsch, TU Darmstadt
    Abstract
    We consider a family of convex integer programming problems arising in statistics/machine learning with sparsity structures. Unlike a line of work which relies on commercial MILP solvers, we design a specialized nonlinear branch-and-bound (BnB) framework, by critically exploiting the problem structure. An important component in our framework lies in efficiently solving the node relaxations using a specialized first-order methods (e.g., coordinate descent). Our first-order methods effectively leverage information across the BnB nodes through using warm starts, active sets, and screening---some old, and some new tools developed in the context of large-scale convex optimization.
Friday, April 28, 2023
  • 9:00 - 9:45 am EDT
    Continuous cutting plane algorithms in integer programming
    11th Floor Lecture Hall
    • Speaker
    • Andrea Lodi, Cornell Tech
    • Session Chair
    • Tobias Achterberg, Gurobi Optimization
    Abstract
    Cutting planes for mixed-integer linear programs (MILPs) are typically computed in rounds by iteratively solving optimization problems, the so-called separation. Instead, we reframe the problem of finding good cutting planes as a continuous optimization problem over weights parametrizing families of valid inequalities. This problem can also be interpreted as optimizing a neural network to solve an optimization problem over subadditive functions, which we call the subadditive primal problem of the MILP. To do so, we propose a concrete two-step algorithm, and demonstrate empirical gains when optimizing generalized Gomory mixed-integer inequalities over various classes of MILPs. (Joint work with Didier Chételat.)
  • 10:00 - 10:30 am EDT
    Coffee Break
    11th Floor Collaborative Space
  • 10:30 - 11:15 am EDT
    Large Neighborhood Search for ILPs with Relaxation-based and Contrastive-Learning-based Heuristics
    11th Floor Lecture Hall
    • Virtual Speaker
    • Bistra Dilkina, University of Southern California
    • Session Chair
    • Tobias Achterberg, Gurobi Optimization
    Abstract
    Large Neighborhood Search (LNS) is an effective heuristic algorithm for finding high quality solutions of combinatorial optimization problems, including for large-scale Integer Linear Programs (ILPs). It starts with an initial solution to the problem and iteratively improves it by searching a large neighborhood around the current best solution. LNS relies on destroy heuristics to select neighborhoods to search in by un-assigning a subset of the variables and then re-optimizing their assignment. We focus on designing effective and efficient heuristics in LNS for integer linear programs (ILP). Local Branching (LB) is an heuristic that selects the neighborhood that leads to the largest improvement over the current solution in each iteration of LNS (the optimal subset of variables to ‘destroy’ within the Hamming ball of the incumbent solutions). LB is often slow since it needs to solve an ILP of the same size as input. First we propose LB-relaxation-based heuristics that compute as effective neighborhoods as LB but run faster and achieve state-of-the-art anytime performance on several ILP benchmarks. Next, we propose a novel ML-based LNS for ILPs, namely CL, that uses contrastive learning (CL) to learn to imitate the LB heuristic. We not only use the optimal subsets provided by LB as the expert demonstration, but also leverage intermediate solutions and perturbations to collect sets of positive and negative samples. We use graph attention networks and a richer set of features to further improve its performance. Empirically, CL outperforms state-of-the-art ML and non-ML approaches at different runtime cutoffs in terms of multiple metrics, including the primal gap, the primal integral, the best performing rate and the survival rate, and achieves good generalization performance.
  • 12:30 - 2:30 pm EDT
    Lunch/Free Time
Monday, May 1, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 9:00 - 9:45 am EDT
    A comparative study of reformulations for piecewise-convex optimization
    Seminar - 11th Floor Lecture Hall
    • Renan Spencer Trindade, École Polytechnique, France
    Abstract
    Our research focuses on mixed integer nonlinear programming problems (MINLP) in which all nonconvex functions are univariate and separable. We employ the Sequential Convex MINLP technique to solve this class of problems to obtain a global optimal solution. This method uses piecewise linear relaxation, where only the concave parts are replaced by linear functions. In contrast, the convex intervals are handled by generating cut planes using the perspective cuts. This work presents a comprehensive theoretical and computational analysis of the different possible reformulations to the original problem. We show and demonstrate that while they are equivalent in the case of purely linear problems, they are not equivalent when considering nonlinear convex intervals
  • 9:45 - 10:30 am EDT
    Mathematical optimization at the service of classification and regression trees
    Seminar - 11th Floor Lecture Hall
    • Cristina Molero-Río, École Polytechnique
    Abstract
    Contrary to classic classification and regression trees, built in a greedy heuristic manner, designing the tree model through an optimization problem allows us to easily include desirable properties in Machine Learning in addition to prediction accuracy. In this talk, we present a Continuous Optimization approach that is scalable with respect to the size of the training sample, and illustrate this flexibility to model several important issues in Explainable and Fair Machine Learning. These include sparsity, as a proxy for interpretability, by reducing the amount of information necessary to predict well; fairness, by aiming to avoid predictions that discriminate against sensitive features such as gender or race; the cost-sensitivity for groups of individuals in which prediction errors are more critical, such as patients of a disease, by ensuring an acceptable accuracy performance for them; local explainability, where the goal is to identify the predictor variables that have the largest impact on the individual predictions; as well as data complexity in the form of observations of functional nature. The performance of our approach is illustrated on real and synthetic data sets.
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Tuesday, May 2, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 8:30 - 9:00 am EDT
    Closing Breakfast
    Coffee Break - 11th Floor Collaborative Space
  • 9:00 - 9:20 am EDT
    How to best slice a polytope
    11th Floor Lecture Hall
    • Chiara Meroni, ICERM
  • 9:25 - 9:45 am EDT
    Unification and extension: Solving subclasses of linear programs
    11th Floor Lecture Hall
    • Bento Natura, Georgia Tech
  • 9:45 - 10:00 am EDT
    Break
    Coffee Break
  • 10:00 - 10:20 am EDT
    Random Shadows of Fixed Polytopes
    11th Floor Lecture Hall
    • Alex Black, UC Davis
  • 10:25 - 10:45 am EDT
    Writing integer PSD matrices as rank-one sums
    11th Floor Lecture Hall
    • Shixuan Zhang, Brown University
  • 10:45 - 11:00 am EDT
    Break
    Coffee Break
  • 11:00 - 11:20 am EDT
    Information complexity, branch-and-cut and GNNs
    11th Floor Lecture Hall
    • Amitabh Basu, Johns Hopkins University
  • 11:25 - 11:45 am EDT
    On principal partition sequences of submodular functions
    11th Floor Lecture Hall
    • Karthekeyan Chandrasekaran, University of Illinois Urbana-Champaign
  • 11:45 am - 12:00 pm EDT
    Break
    Coffee Break
  • 12:00 - 12:45 pm EDT
    I was kicking myself when I saw what you did
    11th Floor Lecture Hall
    • Jon Lee, University of Michigan
    Abstract
    I will talk about these four papers, all over 30 years old, which have a total of 18 google-scholar citations, most being self citations.
    1) J.L. A spectral approach to polyhedral dimension. Mathematical Programming, Series A, 47(3):441-459, 1990. 2) J.L. Canonical equation sets for classes of concordant polytopes. Discrete Applied Mathematics, 28(3):207-221, 1990. 3) J.L. Characterizations of the dimension for classes of concordant polytopes. Mathematics of Operations Research, 15(1):139-154, 1990. 4) J.L and Yew Sing Lee. A spectral method for concordant polyhedral faces. Linear Algebra and its Applications, 159:11-41, 1991.
  • 1:00 - 2:00 pm EDT
    End of Semester Networking Lunch
    Working Lunch - 11th Floor Collaborative Space
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Wednesday, May 3, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Thursday, May 4, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Friday, May 5, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space

All event times are listed in ICERM local time in Providence, RI (Eastern Daylight Time / UTC-4).

All event times are listed in .

Associated Semester Workshops

Linear and Non-Linear Mixed Integer Optimization
Image for "Linear and Non-Linear Mixed Integer Optimization"
Combinatorics and Optimization
Image for "Combinatorics and Optimization"
Trends in Computational Discrete Optimization
Image for "Trends in Computational Discrete Optimization"

Publications

  • Marie-Charlotte Brandenburg, Jesús A. De Loera, Chiara Meroni, The Best Ways to Slice a Polytope, arXiv:2304.14239, 2023.