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
  • Tobias Achterberg
    Gorubi Optimization
    Apr 24-28, 2023
  • Hessa Al-Thani
    University of Michigan
    Jan 29-Mar 18, 2023
  • Rachael Alfant
    Rice University
    Apr 24-28, 2023
  • Félix Almendra Hernández
    UC Davis
    Jan 30-Feb 3, 2023
  • Miguel Anjos
    University of Edinburgh
    Feb 18-May 6, 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
  • Ishan Bansal
    Cornell University
    Jan 30-Feb 3, 2023
  • Amitabh Basu
    Johns Hopkins University
    Mar 26-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
  • Dimitris Bertsimas
    MIT
    Jan 30-May 5, 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
  • Martina Cerulli
    ESSEC Business School of Paris
    Feb 26-Mar 4, 2023
  • Teressa Chambers
    Brown University
    Jan 30-Feb 3, 2023
  • Karthekeyan Chandrasekaran
    University of Illinois Urbana-Champaign
    Feb 6-May 6, 2023
  • Effrosyni Chasioti
    Kent State University
    Jan 30-May 6, 2023
  • Lin Chen
    Texas Tech University
    Feb 27-Mar 3, 2023
  • Zhongzhu Chen
    University of Michigan
    Jan 30-Mar 18, 2023
  • Gerard Cornuejols
    Carnegie Mellon University
    Mar 19-Apr 7, 2023
  • Francisco Criado Gallart
    CUNEF Universidad
    Jan 30-May 5, 2023
  • Claudia D'Ambrosio
    LIX - Ecole Polytechnique
    Mar 26-May 6, 2023
  • Daniel Dadush
    Centrum Wiskunde & Informatica
    Mar 26-Apr 28, 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; Jan 30-May 6, 2023
  • Daniel de Roux
    Carnegie Mellon University
    Feb 26-Mar 5, 2023
  • Alberto Del Pia
    University of Wisconsin-Madison
    Feb 26-Mar 4, 2023
  • Santanu Dey
    Georgia Institute of Technology.
    Mar 19-May 5, 2023
  • Antoine Deza
    McMaster University
    Mar 26-Apr 22, 2023
  • Bistra Dilkina
    University of Southern California
    Apr 23-29, 2023
  • Alina Ene
    Boston University
    Mar 27-31, 2023
  • Daniel Espinoza
    University of Chile
    Feb 26-Mar 4, 2023
  • Yuri Faenza
    Columbia University
    Jan 29-Feb 2, 2023; Feb 6-8, 2023; Feb 16-17, 2023; Feb 23-24, 2023; Feb 27-Mar 3, 2023; Mar 9-10, 2023; Mar 12-19, 2023; Mar 23-24, 2023; Mar 30-31, 2023; Apr 6-7, 2023; Apr 13-14, 2023; Apr 20-21, 2023; Apr 27-28, 2023; May 4-5, 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; Feb 27-Mar 3, 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
  • Rohan Ghuge
    University of Michigan
    Jan 30-Apr 3, 2023
  • Ambros Gleixner
    Zuse Institute Berlin
    Apr 23-29, 2023
  • Michel Goemans
    Massachusetts Institute of Technology
    Jan 30-May 5, 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
  • Anupam Gupta
    Carnegie Mellon University
    Mar 27-31, 2023
  • Swati Gupta
    Georgia Tech
    Mar 26-Apr 1, 2023; Apr 24-28, 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
  • Ilyia 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
  • Klaus Jansen
    Kiel University
    Feb 26-Apr 3, 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
  • Aida Khajavirad
    Lehigh University
    Jan 30-Feb 3, 2023
  • Sammy Khalife
    Johns Hopkins University
    Jan 30-May 5, 2023
  • Fatma Kılınç-Karzan
    Carnegie Mellon University
    Jan 30-May 5, 2023; 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
  • Kirill Kukharenko
    Otto von Guericke University Magdeburg
    Mar 27-31, 2023
  • Shubhang Kulkarni
    University of Illinois, Urbana-Champaign
    Jan 29-May 6, 2023
  • Anatoliy Kuznetsov
    Georgia Institute of Technology
    Feb 27-Mar 3, 2023
  • Jon Lee
    University of Michigan
    Jan 29-May 6, 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
  • Feng Liu
    Stevens Institute of Technology
    Feb 27-Mar 2, 2023
  • Siyue Liu
    Carnegie Mellon University
    Feb 27-Mar 3, 2023; Mar 27-31, 2023
  • Andrea Lodi
    Cornell Tech
    Apr 3-30, 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
  • 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
  • David Morton
    Northwestern University
    Feb 27-Mar 2, 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
  • 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
  • Ojas Parekh
    Sandia National Laboratories
    Apr 23-29, 2023
  • Ethan Partida
    Brown
    Jan 30-Feb 3, 2023
  • Britta Peis
    RWTH Aachen University
    Mar 19-Apr 3, 2023
  • Marc Pfetsch
    TU Darmstadt
    Feb 27-Mar 3, 2023; Apr 24-28, 2023
  • Sebastian Pokutta
    Zuse Institute Berlin (ZIB)
    Mar 25-31, 2023
  • Gabriel Ponte
    Federal University of Rio de Janeiro
    Jan 29-Feb 10, 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
  • 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
    Apr 23-29, 2023
  • Laura Sanità
    Bocconi University of Milan
    Jan 29-Feb 4, 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-Apr 8, 2023
  • Martin Skutella
    TU Berlin
    Mar 26-31, 2023
  • Renata Sotirov
    Tilburg University
    Feb 26-Mar 4, 2023
  • Emily Speakman
    University of Colorado - Denver
    Feb 26-Mar 4, 2023
  • Ola Svensson
    EPFL
    Mar 26-Apr 1, 2023
  • Mohit Tawarmalani
    Purdue University
    Feb 27-Mar 3, 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
  • Fei Wang
    University of Waterloo
    Jan 31-Mar 1, 2023
  • Chengyang Wang
    UC Davis
    Jan 29-Feb 4, 2023; Feb 26-Mar 4, 2023; Mar 6-May 5, 2023
  • Jie Wang
    Georgia Institute of Technology
    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
  • 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

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
    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
    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.
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 am - 12:00 pm EST
    Postdoc/ Grad Introductions
    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 am - 12:00 pm EST
    Postdoc/ Grad Introductions
    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
  • 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
  • 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
  • 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
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th Floor Collaborative Space
Friday, February 24, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 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
    • 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
    TBA
    11th Floor Lecture Hall
    • Speaker
    • Ricardo Fukasawa, University of Waterloo
    • Session Chair
    • Daniel Bienstock, Columbia University
  • 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
    TBA
    11th Floor Lecture Hall
    • Virtual Speaker
    • Matthias Köppe, UC Davis
    • Session Chair
    • Merve Bodur, University of Toronto
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:15 - 12:20 pm EST
    Group Photo - i=Immediately following talk
    Group Photo - 11th Floor Lecture Hall
  • 12:30 - 2:30 pm EST
    Lunch/Free Time
  • 2:30 - 3:30 pm EST
    Poster Session
    11th Floor Collaborative Space
  • 3:30 - 4:00 pm EST
    Coffee Break
    11th 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
    Reciprocity between tree ensemble optimization and multilinear optimization
    11th Floor Lecture Hall
    • Speaker
    • Mohit Tawarmalani, Purdue University
    • Session Chair
    • Yuan Zhou, University of Kentucky
    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.
  • 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
    TBA
    11th Floor Lecture Hall
    • Speaker
    • Alper Atamturk, University of California - Berkeley
    • Session Chair
    • Fatma Kılınç-Karzan, Carnegie Mellon University
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, University of Chile
    • 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
  • 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
  • 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
  • 3:30 - 4:00 pm EDT
    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
  • 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
  • 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
    Coffee Break
    11th Floor Collaborative Space
Thursday, March 23, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 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, 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
  • 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
  • 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
  • 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
  • 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
  • 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, May 1, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 3:30 - 4:00 pm EDT
    Coffee Break
    11th Floor Collaborative Space
Tuesday, May 2, 2023
Discrete Optimization: Mathematics, Algorithms, and Computation
  • 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 Standard Time / UTC-5).

All event times are listed in .

Your Visit to ICERM

ICERM Facilities
ICERM is located on the 10th & 11th floors of 121 South Main Street in Providence, Rhode Island. ICERM's business hours are 8:30am - 5:00pm during this event. See our facilities page for more info about ICERM and Brown's available facilities.
Traveling to ICERM
ICERM is located at Brown University in Providence, Rhode Island. Providence's T.F. Green Airport (15 minutes south) and Boston's Logan Airport (1 hour north) are the closest airports. Providence is also on Amtrak's Northeast Corridor. In-depth directions and transportation information are available on our travel page.
Lodging/Housing
Visiting ICERM for longer than a week-long workshop? ICERM staff works with participants to locate accommodations that fit their needs. Since short-term furnished housing is in very high demand, take advantage of the housing options ICERM may recommend. Contact housing@icerm.brown.edu for more details.
Childcare/Schools
Those traveling with family who are interested in information about childcare and/or schools should contact housing@icerm.brown.edu.
Technology Resources
Wireless internet access and wireless printing is available for all ICERM visitors. Eduroam is available for members of participating institutions. Thin clients in all offices and common areas provide open access to a web browser, SSH terminal, and printing capability. See our Technology Resources page for setup instructions and to learn about all available technology.
Accessibility
To request special services, accommodations, or assistance for this event, please contact accessibility@icerm.brown.edu as far in advance of the event as possible. Thank you.
Discrimination and Harassment Policy
ICERM is committed to creating a safe, professional, and welcoming environment that benefits from the diversity and experiences of all its participants. Brown University's "Code of Conduct", "Discrimination and Workplace Harassment Policy", "Sexual and Gender-based Misconduct Policy", and "Title IX Policy" apply to all ICERM participants and staff. Participants with concerns or requests for assistance on a discrimination or harassment issue should contact the ICERM Director or Assistant Director of Finance & Administration; they are the responsible employees at ICERM under this policy.
Exploring Providence
Providence's world-renowned culinary scene provides ample options for lunch and dinner. Neighborhoods near campus, including College Hill Historic District, have many local attractions. Check out the map on our Explore Providence page to see what's near ICERM.

Visa Information

Contact visa@icerm.brown.edu for assistance.

Need a US Visa?
J-1 visa requested via ICERM staff
Eligible to be reimbursed
B-1 or Visa Waiver Business (WB) –if you already have either visa – contact ICERM staff for a visa specific invitation letter.
Ineligible to be reimbursed
B-2 or Visa Waiver Tourist (WT)
Already in the US?

F-1 and J-1 not sponsored by ICERM: obtain a letter approving reimbursement from the International Office of your home institution PRIOR to travel.

H-1B holders do not need letter of approval.

All other visas: alert ICERM staff immediately about your situation.

ICERM does not reimburse visa fees. This chart is to inform visitors whether the visa they enter the US on allows them to receive reimbursement for the items outlined in their invitation letter.

Financial Support

This section is for general purposes only and does not indicate that all attendees receive funding. Please refer to your personalized invitation to review your offer.

ORCID iD
As this program is funded by the National Science Foundation (NSF), ICERM is required to collect your ORCID iD if you are receiving funding to attend this program. Be sure to add your ORCID iD to your Cube profile as soon as possible to avoid delaying your reimbursement.
Acceptable Costs
  • 1 roundtrip between your home institute and ICERM
  • Flights on U.S. or E.U. airlines – economy class to either Providence airport (PVD) or Boston airport (BOS)
  • Ground Transportation to and from airports and ICERM.
Unacceptable Costs
  • Flights on non-U.S. or non-E.U. airlines
  • Flights on U.K. airlines
  • Seats in economy plus, business class, or first class
  • Change ticket fees of any kind
  • Multi-use bus passes
  • Meals or incidentals
Advance Approval Required
  • Personal car travel to ICERM from outside New England
  • Multiple-destination plane ticket; does not include layovers to reach ICERM
  • Arriving or departing from ICERM more than a day before or day after the program
  • Multiple trips to ICERM
  • Rental car to/from ICERM
  • Flights on a Swiss, Japanese, or Australian airlines
  • Arriving or departing from airport other than PVD/BOS or home institution's local airport
  • 2 one-way plane tickets to create a roundtrip (often purchased from Expedia, Orbitz, etc.)
Travel Maximum Contributions
  • New England: $250
  • Other contiguous US: $750
  • Asia & Oceania: $2,000
  • All other locations: $1,500
  • Note these rates were updated in Spring 2022 and superseded any prior invitation rates. Any invitations without travel support will still not receive travel support.
Reimbursement Requests

Request Reimbursement with Cube

Refer to the back of your ID badge for more information. Checklists are available at the front desk and in the Reimbursement section of Cube.

Reimbursement Tips
  • Scanned original receipts are required for all expenses
  • Airfare receipt must show full itinerary and payment
  • ICERM does not offer per diem or meal reimbursement
  • Allowable mileage is reimbursed at prevailing IRS Business Rate and trip documented via pdf of Google Maps result
  • Keep all documentation until you receive your reimbursement!
Reimbursement Timing

6 - 8 weeks after all documentation is sent to ICERM. All reimbursement requests are reviewed by numerous central offices at Brown who may request additional documentation.

Reimbursement Deadline

Submissions must be received within 30 days of ICERM departure to avoid applicable taxes. Submissions after thirty days will incur applicable taxes. No submissions are accepted more than six months after the program end.

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"