Experiments with two-row cuts from degenerate tableaux

DOI10.1287/IJOC.1100.0437zbMATH Open1243.90143arXiv1701.06589OpenAlexW2113612338MaRDI QIDQ2899149FDOQ2899149

Authors: Amitabh Basu, Pierre Bonami, Gérard Cornuéjols, François Margot 

Publication date: 28 July 2012

Published in: INFORMS Journal on Computing (Search for Journal in Brave)

Abstract: There has been a recent interest in cutting planes generated from two or more rows of the optimal simplex tableau. One can construct examples of integer programs for which a single cutting plane generated from two rows dominates the entire split closure. Motivated by these theoretical results, we study the effect of adding a family of cutting planes generated from two rows on a set of instances from the MIPLIB library. The conclusion of whether these cuts are competitive with GMI cuts is very sensitive to the experimental setup. In particular, we consider the issue of reliability versus aggressiveness of the cut generators, an issue that is usually not addressed in the literature.

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

Recommendations

• Experiments with two row tableau cuts
• On the practical strength of two-row tableau cuts
• Computing with Multi-row Gomory Cuts
• Computational experiments with cross and crooked cross cuts
• Intersection cuts from multiple rows: a disjunctive programming approach

zbMATH Keywords

cutting planesmixed-integer programming\texttt{MIPLIB}

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)

Cited In (18)

• The (not so) trivial lifting in two dimensions
• On the practical strength of two-row tableau cuts
• Can Cut-Generating Functions Be Good and Efficient?
• Theoretical challenges towards cutting-plane selection
• Decomposition tables for experiments. II: Two-one randomizations
• Multirow Intersection Cuts Based on the Infinity Norm
• The strength of multi-row models
• Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts
• A geometric approach to cut-generating functions
• Partial hyperplane activation for generalized intersection cuts
• Intersection cuts from multiple rows: a disjunctive programming approach
• When Lift-and-Project Cuts Are Different
• Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
• A probabilistic analysis of the strength of the split and triangle closures
• Experiments with two row tableau cuts
• Computational experiments with cross and crooked cross cuts
• Intersection cuts for single row corner relaxations
• An algorithm for the separation of two-row cuts

Uses Software

• MIPLIB

This page was built for publication: Experiments with two-row cuts from degenerate tableaux

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