Summer School

The IPCO summer school will be held on June 25-26, 2022.

IPCO Summer School program

Saturday June 25

08:00	-	08:45	registration and coffee
9.00	-	10.30	Stefan Weltge (Lecture 1)
10.30	-	11.00	Coffee break
11.00	-	12.30	Shipra Agrawal (Lecture 1)
12.30	-	14.00	Lunch break
14.00	-	15.30	Shayan Oveis Gharan (Lecture 1)
15.30	-	16.00	Coffee break
16.00	-	17.00	Student exercises

Sunday June 26

08:30	-	09:00	Coffee
9.00	-	10.30	Shipra Agrawal (Lecture 2)
10.30	-	11.00	Coffee break
11.00	-	12.30	Shayan Oveis Gharan (Lecture 2)
12.30	-	14.00	Lunch break
14.00	-	15.30	Stefan Weltge (Lecture 2)

 

Shipra Agrawal, Columbia University

Title: An introduction to reinforcement learning with applications to integer programming

Abstract: In this lecture, I will first give a brief introduction to reinforcement learning (RL), including modeling considerations and algorithms. Next, I will discuss some work on using reinforcement learning for combinatorial optimization, in particular, our recent work (with Yunhao Tang and Yuri Faenza) on using RL for learning to add cuts in order to solve integer programs.

Shipra Agrawal is an Associate Professor of the Department of Industrial Engineering and Operations Research at Columbia University. She is also affiliated with the Department of Computer Science and the Data Science Institute. She received her PhD in Computer Science from Stanford University in June 2011 under the guidance of Prof. Yinyu Ye, and was a researcher at Microsoft Research India from July 2011 to August 2015. Her research spans several areas of optimization and machine learning, including online optimization under uncertainty, multi-armed bandits, online learning, and reinforcement learning. She is also interested in prediction markets and game theory. Shipra serves as an associate editor for Management Science and Mathematics of Operations Research, INFORMS Journal on Optimization and Journal of Machine Learning Research (JMLR). Her research is supported by a Google Faculty research award (2017), Amazon research award (2017), and an NSF CAREER Award.

 

Shayan Oveis Gharan, University of Washington

Title: Maximum Entropy Rounding and Applications to Combinatorial Optimization

Abstract: In this short course, I will talk about the fruitful approach of rounding a solution of a linear programming relaxation by sampling from a maximum entropy distribution that preserves the given solution as the marginals. I will discuss several properties of the resulting maximum entropy distribution such as negative dependence and concentration inequalities. For concrete applications, we will see connections to network optimization problems such as the traveling salesperson problem or the minimum cost k-edge connected subgraph problem. Finally, we conclude by a list of open problems and open future directions.

Shayan Oveis Gharan is an associate professor in the Paul Allen School of Computer Science and Engineering at University of Washington. He received his PhD from the Management Science and Engineering department at Stanford University in 2013. Before joining UW he spent one and a half years as a postdoctoral Miller Fellow at UC Berkeley.

Shayan's research exploits several tools in Mathematics such as theory of real stable and log-concave polynomials, and spectral graph theory to design and analyze algorithms for discrete objects.

 

Stefan Weltge, TU Munich 

Title: Determinants in IPCO

Abstract: We explore the particular role of determinants in integer programming and combinatorial optimization. In the first part, we discuss recent exciting developments that refine the complexity of integer programming using the notion of subdeterminants. In the second part, we learn how the computation of determinants led to fast algorithms for combinatorial optimization problems such as the matching problem.

Stefan Weltge received his PhD from the University of Magdeburg in 2016. He spent two years as a postdoc at ETH Zurich and is an assistant professor at the Technical University of Munich since 2018. Stefan's research is on linear and integer programming theory, with a particular emphasis on polyhedral combinatorics. His focus is on questions about best possible descriptions of discrete optimization problems in different mixed-integer programming settings. He is particularly known for several contributions to the field of extended formulations. In recent years, he has worked on integer programs defined by coefficient matrices with bounded subdeterminants.

---

We thank EURANDOM for partially sponsoring the keynote lectures in the summer school.