2017/11/19 by Dey, Santanu S., Iroume, Andres, Wang, Guanyi
#FOS: Mathematics #Optimization and Control (math.OC)
paper · doi:10.48550/arxiv.1711.06963
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∈ ℤn+ | Ax≤ b\ where for a given column j, Aij 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.