back to list of all courses

Advances in Integer Programming

This course is taught in English. Seminar in Winter Term 2020/21.

Description

Mathematical programming is a tool for modelling real-life problems using variables with certain constraints imposed on them and an objective function that one seeks to minimise or maximise. Integer programs (IP) require said variables to be integral, and are in general computationally hard (NP-hard) to solve.

Recent techniques ought to exploit the structural properties of IP problems, and they have a great performance in case the size of certain (hidden or explicit) parameters can be bounded. The aim of this seminar is to get familiar with the most recent results on IP complexity and algorithms.

Requirements

We are looking for enthusiastic students who have an interest in optimisation and integer programming algorithms. The papers to be covered are sometimes technical and require basic knowledge of operations research and complexity theory.

Tasks

The seminar will cover 10 recent topics from the area of integer programming. Each topic will be covered by one student, who will summarise a recent result in a 30-minute presentation and a written report of 5-10 pages. As a bonus, demonstrating and comparing an implementation of the algorithm (the student's own or the authors') using simulations and test runs is highly appreciated.

Setup

All presentations will be scheduled on a one-day session on the last academic week of December (14-18 December), where each 30-minute talk is followed by up to 15 minutes discussion. There is a maximum number of 10 participants.

There will be an introductory meeting at 13:00 on 12^th November, when the exact date of the presentation session will be decided. Participation in both occasions is mandatory.

Topics

The topics will be assigned to students by taking into account their preferences:

1. About the Complexity of Two-Stage Stochastic IPs
2. The Double Exponential Runtime is Tight for 2-Stage Stochastic ILPs 
3. New Bounds on Augmenting Steps of Block-structured Integer Programs 
4. Parameterized Integer Quadratic Programming: Variables and Coefficients 
5. Improving proximity bounds using sparsity
6. Tight lower bounds for ILP with few constraints 
7. Sparsity of Integer Solutions in the Average Case 
8. Integrality Gaps of Integer Knapsack Problems 
9. Integer convex minimization by mixed integer linear optimization 
10. Mixed integer reformulations of integer programs and the affine TU-dimension of a matrix