Experiments with two-row cuts from degenerate tableaux

DOI10.1287/IJOC.1100.0437MaRDI QIDQ2899149zbMATH OpenOpenAlexFDO

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)

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

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)

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.

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

Cited in

(18)

• The (not so) trivial lifting in two dimensions
• On the practical strength of two-row tableau cuts
• 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
• A geometric approach to cut-generating functions
• Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts
• Intersection cuts from multiple rows: a disjunctive programming approach
• Partial hyperplane activation for generalized intersection cuts
• When Lift-and-Project Cuts Are Different
• Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
• Can cut-generating functions be good and efficient?
• 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

Describes a project that uses

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)