Loading...
Organizing Committee
University of California, Davis
McMaster University
Federal University of Rio de Janeiro
Otto-von-Guericke Universität Magdeburg
University of Michigan
Bocconi University of Milan
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.
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.
Loading...
Loading participant list in background...
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
Wednesday, February 01, 2023
9:00 - 10:00 AM EST
Polynomial optimization on finite sets
Seminar - 11th Floor Lecture Hall
Speaker
Mauricio Velasco, Universidad de Los Andes
Session Chair
Jesús De Loera, University of California, Davis
Abstract
If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in n-variables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms.
In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss:
How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity?
If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization?
Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$
Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems.
The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a self-contained introduction to this vibrant and exciting research area.
10:00 - 10:30 AM EST
Coffee Break
11th Floor Collaborative Space
10:30 - 11:30 AM EST
Polynomial optimization on finite sets
Seminar - 11th Floor Lecture Hall
Speaker
Mauricio Velasco, Universidad de Los Andes
Session Chair
Jesús De Loera, University of California, Davis
Abstract
If $X\subseteq \mathbb{R}^n$ is a finite set then every function on $X$ can be written as the restriction of a polynomial in n-variables. As a result, polynomial optimization on finite sets is literally the same as general (nonlinear) optimization on such sets. Thinking of functions as polynomials, however, provides us with plenty of additional structures which can be leveraged for constructing better (or at least different) optimization algorithms.
In these lectures, we will overview some of the key problems and results coming from this algebraic point of view. Specifically, we will discuss:
How to prove that a polynomial function is nonnegative on a finite set X? What kind of algebraic certificates (proofs) are available and what can we say about their size and complexity?
If the set $X$ has symmetries, can we leverage them in some systematic way that is useful for optimization?
Characterizing the affine linear functions that are nonnegative on $X$ gives a description of the polytope $P={\rm Conv}(X)$. Stratifying such functions by the degree of their nonnegativity certificates leads to (semidefinite) hierarchies of approximation for the polytope $P$ and it is natural to ask about their speed of convergence and its relationship with the combinatorics of $P$
Finally, if time permits we will discuss some recent ideas combining the above methods with reinforcement learning as a way to improve scalability for combinatorial optimization problems.
The results in (1),(2), (3) above are due to Blekherman, Gouveia, Laurent, Nie, Parrilo, Saunderson, Thomas, and others. These lectures intend to be a self-contained introduction to this vibrant and exciting research area.
11:40 - 11:45 AM EST
Group Photo (Immediately After Talk)
11th Floor Lecture Hall
11:45 AM - 2:00 PM EST
Lunch/Free Time
2:00 - 3:00 PM EST
Matching Theory and School Choice
Seminar - 11th Floor Lecture Hall
Speaker
Yuri Faenza, Columbia University
Session Chair
Jon Lee, University of Michigan
Abstract
Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.
3:00 - 3:30 PM EST
Coffee Break
11th Floor Collaborative Space
3:30 - 4:30 PM EST
Matching Theory and School Choice
Seminar - 11th Floor Lecture Hall
Speaker
Yuri Faenza, Columbia University
Session Chair
Jon Lee, University of Michigan
Abstract
Many questions in resource allocation can be formulated as matching problems, where nodes represent the agents/goods, and each node corresponding to an agent is endowed with a preference profile on the (sets of) its neighbors in the graph. Starting with the classical marriage setting by Gale and Shapley, we will investigate algorithmic and structural properties of these models, and discuss applications to the problem of allocating seats in public schools.
Thursday, February 02, 2023
9:00 - 10:00 AM EST
Approximation Algorithms for Network Design Problems
Seminar - 11th Floor Lecture Hall
Speaker
Vera Traub, University of Bonn
Session Chair
Laura Sanità, Bocconi University of Milan
Abstract
The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2-approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first better-than-2 approximation algorithm for Weighted Connectivity Augmentation.
10:00 - 10:30 AM EST
Coffee Break
11th Floor Collaborative Space
10:30 - 11:30 AM EST
Approximation Algorithms for Network Design Problems
Seminar - 11th Floor Lecture Hall
Speaker
Vera Traub, University of Bonn
Session Chair
Laura Sanità, Bocconi University of Milan
Abstract
The goal of network design is to construct cheap networks that satisfy certain connectivity requirements. A celebrated result by Jain [Combinatorica, 2001] provides a 2-approximation algorithm for a wide class of these problems. However, even for many very basic special cases nothing better is known. In this lecture series, we present an introduction and some of the new techniques underlying recent advances in this area. These techniques led for example to a new algorithm for the Steiner Tree Problem and to the first better-than-2 approximation algorithm for Weighted Connectivity Augmentation.
11:30 AM - 1:30 PM EST
Lunch/Free Time
1:30 - 2:30 PM EST
Binary polynomial optimization: theory, algorithms, and applications
Seminar - 11th Floor Lecture Hall
Speaker
Aida Khajavirad, Lehigh University
Session Chair
Marcia Fampa, Federal University of Rio de Janeiro
Abstract
In this mini-course, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments.
Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higher-order Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
2:30 - 3:30 PM EST
Coffee Break
11th Floor Collaborative Space
3:30 - 4:30 PM EST
Rank-one Boolean tensor factorization and the multilinear polytope
Seminar - 11th Floor Lecture Hall
Speaker
Aida Khajavirad, Lehigh University
Session Chair
Marcia Fampa, Federal University of Rio de Janeiro
Abstract
In this mini-course, I present an overview of some recent advances in the theory of binary polynomial optimization together with specific applications in data science and machine learning. First utilizing a hypergraph representation scheme, I describe the connection between hypergraph acyclicity and the complexity of unconstrained binary polynomial optimization. As a byproduct, I present strong linear programming relaxations for general binary polynomial optimization problems and demonstrate their impact via extensive numerical experiments.
Finally, I focus on two applications from data science, namely, Boolean tensor factorization and higher-order Markov random fields, and demonstrate how our theoretical findings enable us to obtain efficient algorithms with theoretical performance guarantees for these applications.
Friday, February 03, 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
