The IPCO summer school will be online on May 17-18, 2021! Register here for the summer school and conference. The speakers will be
Moon Duchin, Tufts University.
Simge Küçükyavuz, Northwestern University.
László Végh, London School of Economics.
Schedule (All times in Eastern time):
| 9:30-11:00 | 11:00-11:30 | 11:30-1pm | 1-2pm | 2-3:30 | 3:30-4:15 | |
| May 17 | László Végh | Tea | Moon Duchin | Lunch | Simge Küçükyavuz | Discussion + Social |
| May 18 | Moon Duchin | Tea | László Végh | Lunch | Simge Küçükyavuz | Discussion + Social |
Moon Duchin, Tufts University.
Title: How redistricting is and is not an optimization problem
Abstract: Congressional redistricting is dividing up a state into an assigned number of districts, which will each hold independent elections and send the plurality winner to Washington. Since districts are composed of Census blocks, it’s exactly rephraseable as a graph partition problem on a large but finite graph. Unfair or “gerrymandered” districts are bad in some way (though opinions differ on exactly what way). So can’t we just agree on the fairness metric and optimize? In my talks I’ll explain some optimization perspectives on redistricting and I’ll argue for where the interesting action is, including some open and approachable real-world problems for you to explore. I’ll talk about joint work with many collaborators in my lab, with an especially large role played by Amariah Becker.
Simge Küçükyavuz, Northwestern University
Title: Mixed-Integer Programming for Stochastic Optimization
Abstract: Many practical optimization problems involve decision-making under uncertainty and risk. We present two classes of such stochastic optimization problems, namely two-stage stochastic integer programming and chance-constrained programming. These problems result in large-scale mixed-integer programming formulations with certain structures. For each class of problems, we review mixed-integer programming techniques that enable effective solution approaches that exploit the underlying structures. These techniques span disjunctive programming, Gomory cuts, submodularity, mixing sets, mixed-integer conic programming, and Benders decomposition.
László Végh, London School of Economics.
Title: Linear programming and circuit imbalances
Abstract: The lectures will study special classes of linear programs that can be solved in strongly polynomial time, combining perspectives from continuous and combinatorial optimization. A famous 1986 result by Tardos on “combinatorial linear programs” showed that a linear program can be exactly solved in poly(n,m,log Delta) arithmetic operations, where Delta is the maximum subdeterminant of the integer constraint matrix. Note that this bound is independent from the right hand side and the cost vector. This was strengthened by Vavasis and Ye in 1996, who gave a ‘layered least squares’ (LLS) interior-point method with running time polynomial in n, m, and a certain condition number of the constraint matrix. The result enhances standard interior point methods using beautiful combinatorial ideas.
Recent work has focused on the `circuit imbalance measure’ of a matrix: this is the largest ratio between the absolute values between the nonzero entries of a support minimal vector in the kernel of the matrix. The lectures will explore the combinatorics and proximity theory of circuits, and present stronger variants of the Tardos and Vavasis-Ye results from this perspective.