The Strength of Multi-row Aggregation Cuts for Sign-pattern Integer Programs

Abstract

In this paper, we study the strength of aggregation cuts for sign-pattern integer programs (IPs). Sign-pattern IPs are a generalization of packing IPs and are of the form $\{x\in {\mathbb{Z}}_{+}^n|Ax\le b\}$ where for a given column $j$, $A_{ij}$ is either non-negative for all $i$ or non-positive for all $i$. Our first result is that the aggregation closure for such sign-pattern IPs can be 2-approximated by the original 1-row closure. This generalizes a result for packing IPs. On the other hand, unlike in the case of packing IPs, we show that the multi-row aggregation closure cannot be well approximated by the original multi-row closure. Therefore for these classes of integer programs general aggregated multi-row cutting planes can perform significantly better than just looking at cuts from multiple original constraints.