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)

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

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)