The Summer School will be held online on 6 and 7 June, on the two days preceding the IPCO conference.
The speakers are Santanu S. Dey, Bertrand Guenin, and Laura Sanità.
Anyone may register for the summer school.
Schedule
Speakers
Santanu S. Dey
Video for lecture 1
Video for lecture 2
Lecture slides
Title: Some convexification techniques in global optimization
Abstract: Non-convex nonlinear optimization problems are solved to global optimality by spacial branch-and-bound tree based algorithm. A key component of the computational success of any branch-and-bound tree based algorithm depends on the convexification scheme used at each node of the tree. We will present some techniques that are used to build convex hulls and convex relaxations of simple nonlinear sets. These techniques, some of which have also been extensively used in the integer programming literature, include the study of edge concave functions over polytopes, reverse convex sets, sets described by ‘one continuous constraint’, disjunctions and the role of positively homogenous functions. We will also discuss the quality of some of the well-known polyhedral and the mixed integer linear outer approximations of nonlinear sets.
Bio: Santanu S. Dey is A. Russell Chandler III Professor in the H. Milton Stewart School of Industrial and Systems Engineering at Georgia Institute of Technology. Dr. Dey holds a Ph.D. in Industrial Engineering from Purdue University. Prior to joining Georgia Tech, he worked as a post-doctoral fellow at the Center for Operations Research and Econometrics (CORE) of the Catholic University of Louvain in Belgium. Dr Dey's research interests are in the area of non-convex optimization, and in particular mixed integer linear and nonlinear programming.
Dr Dey has served as the vice chair for Integer Programming for INFORMS Optimization Society (2011-2013) and has served on the program committees of Mixed Integer Programming Workshop 2013 and Integer Programming and Combinatorial Optimization 2017. He currently serves on the editorial board of Computational Optimization and Applications, MOS-SIAM book series on Optimization, is an area editor for Mathematical Programming C and is an associate editor for INFORMS Journal on Computing, Mathematical Programming A, and SIAM Journal on Optimization.
Bertrand Guenin
Video for lecture 1
Video for lecture 2
Lecture slides:
Lecture 1 (covered during day 1)
Lecture 2 (covered during day 1)
Lecture 3 (started in day 1, completed in day 2)
Lecture 4 (covered during day 2)
Title: Packing and covering
Abstract: The set-packing and set-covering problems are classical integer programs. The class of set-packing problems that can be solved by considering their linear programming relaxations is exactly the class of problems that arises from perfect graphs. Thus we may ask, "What is the class of set-covering problems that can be solved by considering their linear programming relaxations?" We will study the deep and still developing theory around this question. This brings together tools from optimization, graph and matroid theory, geometry, and linear algebra.
Bio: Bertrand Guenin is a Professor at the Department of Combinatorics and Optimization, University of Waterloo. He received his Ph.D. in Algorithms, Combinatorics and Optimization from Carnegie Mellon University under the supervision of Gérard Cornuéjols. After spending a year at Georgia Tech and a year at the Fields Institute, he moved to the University of Waterloo. He is the recipient of the highly prestigious Fulkerson prize for his characterization of weakly bipartite graphs, a groundbreaking piece of work in Integer Programming and Combinatorial Optimization.
Laura Sanità
Video for lecture 1
Video for lecture 2
Lecture slides
Title: Diameter of polytopes: algorithmic and combinatorial aspects
Abstract: The diameter of a polytope P is the maximum length of a shortest path between a pair of vertices of P, when one is allowed to walk on the edges (1-dimensional faces) of P. Despite decades of studies, it is still not known whether the diameter of a d-dimensional polytope with n facets can be bounded by a polynomial function of n and d. This is a fundamental open question in discrete mathematics, motivated by the (still unknown) existence of a polynomial pivot rule for the Simplex method for solving Linear Programs.
In these lectures, we will discuss some algorithmic and complexity results on the diameter of polyhedra, highlighting long-standing conjectures and open questions. A special focus will be on polyhedra that describe the set of feasible solutions of fundamental combinatorial optimization problems, such as matching and TSP. Eventually, we will delve into the generalized notion of circuit-diameter, and the framework of circuit-based augmentation algorithms.
Bio: Laura Sanità is an Associate Professor at the Department of Combinatorics and Optimization, University of Waterloo. She received her Ph.D. in Operations Research in 2009 from the University of Rome Sapienza and was subsequently a postdoctoral fellow at EPFL in Switzerland. She is internationally renowned for her significant contributions to Combinatorial Optimization and Approximation Algorithms. She is the recipient of an Ontario Early Research Award and a Discovery Accelerator Supplements Award from the Natural Sciences and Engineering Research Council of Canada.