The strength of multi-row aggregation cuts for sign-pattern integer programs

DOI10.1016/J.ORL.2018.11.001MaRDI QIDQ2294249zbMATH OpenOpenAlexFDO

Authors Santanu S. Dey, Andres Iroume, Guanyi Wang

Publication date 10 February 2020

Published in Operations Research Letters (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1711.06963

zbMATH Keywords

aggregationcutting-planemulti-row cuts

Mathematics Subject Classification ID

Integer programming (90C10)

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 $xinmathbb{Z}_{+}^n|Axleb$ 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.

Recommendations

• Aggregation-based cutting-planes for packing and covering integer programs
• The aggregation closure is polyhedral for packing and covering integer programs
• The strength of multi-row models
• On the relative strength of different generalizations of split cuts
• Aggregation and Mixed Integer Rounding to Solve MIPs

Cites work

• scientific article; zbMATH DE number 7051293 (Why is no real title available?)
• A \((k+1)\)-slope theorem for the \(k\)-dimensional infinite group relaxation
• Aggregation and Mixed Integer Rounding to Solve MIPs
• Aggregation-based cutting-planes for packing and covering integer programs
• Approximation of corner polyhedra with families of intersection cuts
• Constrained infinite group relaxations of MIPs
• Equivariant perturbation in Gomory and Johnson's infinite group problem. III: Foundations for the \(k\)-dimensional case with applications to \(k=2\)
• Facets of Two-Dimensional Infinite Group Problems
• Inequalities from Two Rows of a Simplex Tableau
• Lifting properties of maximal lattice-free polyhedra
• Minimal valid inequalities for integer constraints
• On the exact separation of mixed integer knapsack cuts
• On the existence of optimal solutions to integer and mixed-integer programming problems
• On the facets of mixed integer programs with two integer variables and two constraints
• On the knapsack closure of 0-1 integer linear programs
• On the relative strength of different generalizations of split cuts
• Polyhedral properties for the intersection of two knapsacks
• Relations between facets of low- and high-dimensional group problems
• Solving Large-Scale Zero-One Linear Programming Problems
• The group-theoretic approach in mixed integer programming
• Zero-coefficient cuts

Cited in

(3)

• Aggregation-based cutting-planes for packing and covering integer programs
• Two-halfspace closure
• The aggregation closure is polyhedral for packing and covering integer programs

Describes a project that uses

Uses Software

• infinite group relaxation

This page was built for publication: The strength of multi-row aggregation cuts for sign-pattern integer programs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2294249)