Title: Aggregation-based cutting-planes for packing and covering integer programs
| Speaker: | Merve Bodur |
| Affiliation: | University of Toronto |
| Room: | MC 5501 |
Abstract:
We study the strength of Chvatal-Gomory (CG) cuts and more generally aggregation cuts for packing and covering integer programs (IPs). Aggregation cuts are obtained as follows: Given an IP formulation, we first generate a single implied inequality using aggregation of the original constraints, then obtain the integer hull of the set defined by this single inequality with variable bounds, and finally use the inequalities describing the integer hull as cutting-planes. Our main result is to show that for packing and covering IPs, the CG and aggregation closures can be 2-approximated by simply generating the respective closures for each of the original formulation constraints, without using any aggregations. On the other hand, for general IPs, we show that aggregation cuts can be arbitrarily stronger than cuts from individual constraints. Finally, we examine the strength of cuts based on k different aggregation inequalities simultaneously, and show that every packing or covering IP with a large integrality gap also has a large k-aggregation closure rank.
This is joint work with Alberto Del Pia, Santanu Dey, Marco Molinaro and Sebastian Pokutta.