2016/06/29 by Merve Bodur, Bodur, Merve, Alberto Del Pia +7
Business, Management and Accounting · Computer Science · Decision Sciences · #Advanced Graph Theory Research #Auction Theory and Applications #FOS: Mathematics #Optimization and Control (math.OC) #Supply Chain and Inventory Management
paper · pdf · doi:10.48550/arxiv.1606.08951
openalex publication_date 2016/06/29 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
In this paper, we study the strength of Chvatal-Gomory (CG) cuts and more\ngenerally aggregation cuts for packing and covering integer programs (IPs).\nAggregation cuts are obtained as follows: Given an IP formulation, we first\ngenerate a single implied inequality using aggregation of the original\nconstraints, then obtain the integer hull of the set defined by this single\ninequality with variable bounds, and finally use the inequalities describing\nthe integer hull as cutting-planes. Our first main result is to show that for\npacking and covering IPs, the CG and aggregation closures can be 2-approximated\nby simply generating the respective closures for each of the original\nformulation constraints, without using any aggregations. On the other hand, we\nuse computational experiments to show that aggregation cuts can be arbitrarily\nstronger than cuts from individual constraints for general IPs. The proof of\nthe above stated results for the case of covering IPs with bounds require the\ndevelopment of some new structural results, which may be of independent\ninterest. Finally, we examine the strength of cuts based on k different\naggregation inequalities simultaneously, the so-called multi-row cuts, and show\nthat every packing or covering IP with a large integrality gap also has a large\nk-aggregation closure rank. In particular, this rank is always at least of the\norder of the logarithm of the integrality gap.\n