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.

This Boot-camp will be the opening event of the semester and it aims to attract young researchers to this topic.The four mini courses, presented by four speakers known for high-quality exposition, will cover various subjects such as new advances in approximation algorithms, mixed integer non-linear programming, algebraic techniques in optimization and applications to social sciences. The event provides a taste of the many methods and hot topics to be discussed during the semester. The event will also include a poster session to allow graduate students to present their work and other community building activities.

Image for "Current Themes of Discrete Optimization: Boot-camp for early-career researchers"

Confirmed Speakers & Participants

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

  • Speaker
  • Poster Presenter
  • Attendee
  • Virtual Attendee
  • Hessa Al-Thani
    University of Michigan
  • Félix Almendra Hernández
    UC Davis
  • Nicholas Arosemena
    Brown University
  • Nancy Maribel Arratia Martinez
    Universidad de las Américas Puebla
  • Ishan Bansal
    Cornell University
  • Alex Black
    UC Davis
  • Teressa Chambers
    Brown University
  • Effrosyni Chasioti
    Kent State University
  • Zhongzhu Chen
    University of Michigan
  • Francisco Criado Gallart
    CUNEF Universidad
  • Maria Dascalu
    University of Massachusetts Amherst
  • Jesús De Loera
    University of California, Davis
  • Yuri Faenza
    Columbia University
  • Marcia Fampa
    Federal University of Rio de Janeiro
  • Allison Fitisone
    University of Kentucky
  • Rohan Ghuge
    University of Michigan
  • Weston Grewe
    University of Colorado Denver
  • Chengyue He
    Columbia University
  • Dylan Hyatt-Denesik
    Eindhoven University of Technology
  • Sean Kafer
    University of Waterloo
  • Lennart Kauther
    RWTH Aachen University
  • Aida Khajavirad
    Lehigh University
  • Sammy Khalife
    Johns Hopkins University
  • Shubhang Kulkarni
    University of Illinois, Urbana-Champaign
  • Jon Lee
    University of Michigan
  • Juan Carlos Martinez Mori
    Cornell University
  • Chiara Meroni
    ICERM
  • Jared Miller
    Northeastern University
  • Bento Natura
    Georgia Tech
  • Yuchong Pan
    MIT
  • Ethan Partida
    Brown
  • Gabriel Ponte
    Federal University of Rio de Janeiro
  • Rodolfo Quintero Ospina
    Lehigh University
  • Laura Sanità
    Bocconi University of Milan
  • Nimita Shinde
    IITB-Monash Research Academy
  • Vera Traub
    University of Bonn
  • Mauricio Velasco
    Universidad de Los Andes
  • Lucy Verberk
    Eindhoven University of Technology
  • Aapeli Vuorinen
    Columbia University
  • Fei Wang
    University of Waterloo
  • Chengyang Wang
    UC Davis
  • William Wesley
    University of California Davis
  • Chao Xu
    University of Electronic Science and Technology of China
  • Luze Xu
    University of California, Davis
  • Shixuan Zhang
    Brown University
  • Yuan Zhou
    University of Kentucky

Workshop Schedule

Monday, January 30, 2023
  • 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

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

All event times are listed in .

Mini-Courses

Binary polynomial optimization: theory, algorithms, and applications

Aida Khajavirad (Lehigh University)

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.

Matching Theory and School Choice

Yuri Faenza (Columbia University)

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.

Approximation Algorithms for Network Design Problems

Vera Traub (ETH Zurich)

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.

Polynomial optimization on finite sets

Mauricio Velasco (U. Andes Colombia)

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:

  1. 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?
  2. If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization?
  3. 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.

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"