Theoretical challenges towards cutting-plane selection
From MaRDI portal
Publication:1650776
DOI10.1007/S10107-018-1302-4zbMATH Open1391.90427arXiv1805.02782OpenAlexW2964289932WikidataQ129762351 ScholiaQ129762351MaRDI QIDQ1650776FDOQ1650776
Santanu S. Dey, Marco Molinaro
Publication date: 13 July 2018
Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)
Abstract: While many classes of cutting-planes are at the disposal of integer programming solvers, our scientific understanding is far from complete with regards to cutting-plane selection, i.e., the task of selecting a portfolio of cutting-planes to be added to the LP relaxation at a given node of the branch-and-bound tree. In this paper we review the different classes of cutting-planes available, known theoretical results about their relative strength, important issues pertaining to cut selection, and discuss some possible new directions to be pursued in order to accomplish cutting-plane selection in a more principled manner. Finally, we review some lines of work that we undertook to provide a preliminary theoretical underpinning for some of the issues related to cut selection.
Full work available at URL: https://arxiv.org/abs/1805.02782
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Mixed integer programming (90C11)
Cites Work
- Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra
- Cook, Kannan and Schrijver's example revisited
- Testing cut generators for mixed-integer linear programming
- On cutting-plane proofs in combinatorial optimization
- On the matrix-cut rank of polyhedra.
- On the rank of disjunctive cuts
- On the Rank of Cutting-Plane Proof Systems
- On mixed-integer sets with two integer variables
- Computation of the Lasserre Ranks of Some Polytopes
- Exponential Lower Bounds on the Lengths of Some Classes of Branch-and-Cut Proofs
- Lower bounds for the Chvàtal-Gomory rank in the 0/1 cube
- A Class of Hard Small 0-1 Programs
- On the \(0/1\) knapsack polytope
- Lifted flow cover inequalities for mixed \(0\)-\(1\) integer programs
- Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations
- Computing with Multi-row Gomory Cuts
- On Mixing Inequalities: Rank, Closure, and Cutting-Plane Proofs
- Lifting the facets of zero–one polytopes
- Composite lifting of group inequalities and an application to two-row mixing inequalities
- A note on the split rank of intersection cuts
- A Probabilistic Comparison of Split and Type 1 Triangle Cuts for Two-Row Mixed-Integer Programs
- Characterization of facets for multiple right-hand choice linear programs
- A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts
- A computational study of the cutting plane tree algorithm for general mixed-integer linear programs
- Subset Algebra Lift Operators for 0-1 Integer Programming
- Lexicography and degeneracy: Can a pure cutting plane algorithm work?
- Computing deep facet-defining disjunctive cuts for mixed-integer programming
- How tight is the corner relaxation? Insights gained from the stable set problem
- An algorithm for the separation of two-row cuts
- Experiments with two-row cuts from degenerate tableaux
- Experiments with Two Row Tableau Cuts
- Submodularity and valid inequalities in capacitated fixed charge networks
- Large sparse numerical optimization
- Integer Programming
- Cutting planes from extended LP formulations
- Finitely Convergent Decomposition Algorithms for Two-Stage Stochastic Pure Integer Programs
- Strengthened Benders Cuts for Stochastic Integer Programs with Continuous Recourse
- On the rank of mixed 0,1 polyhedra.
- A Probing Algorithm for MINLP with Failure Prediction by SVM
- New inequalities for finite and infinite group problems from approximate lifting
- Degree-two Inequalities, Clique Facets, and Biperfect Graphs
- Improving LP-Representations of Zero-One Linear Programs for Branch-and-Cut
- Elementary closures for integer programs.
- On the relative strength of different generalizations of split cuts
- Two-step MIR inequalities for mixed integer programs
- The M{\texttt{CF}}-separator: Detecting and exploiting multi-commodity flow structures in MIPs
- A Convergent Duality Theory for Integer Programming
- On the safety of Gomory cut generators
- A hybrid branch-and-bound approach for exact rational mixed-integer programming
- On learning and branching: a survey
- A Machine Learning-Based Approximation of Strong Branching
- Mod‐2 Cuts Generation Yields the Convex Hull of Bounded Integer Feasible Sets
- New Variants of Lift-and-Project Cut Generation from the LP Tableau: Open Source Implementation and Testing
- Mixed integer rounding cuts and master group polyhedra
- Lifting two-integer knapsack inequalities
- Some lower bounds on sparse outer approximations of polytopes
- Coordinated cutting plane generation via multi-objective separation
- Computational Experiments with Cross and Crooked Cross Cuts
- A Probabilistic Analysis of the Strength of the Split and Triangle Closures
- Reverse Chvátal--Gomory Rank
- Cut Generation through Binarization
- Lifting properties of maximal lattice-free polyhedra
- Reverse split rank
- Approximating polyhedra with sparse inequalities
- Cutting-plane proofs in polynomial space
- A simple finite cutting plane algorithm for integer programs
- Sparsity of Lift-and-Project Cutting Planes
- Learning a classification of mixed-integer quadratic programming problems
- Approximation of corner polyhedra with families of intersection cuts
- Minimal cut-generating functions are nearly extreme
- Learning when to use a decomposition
- A geometric approach to cut-generating functions
- On the notions of facets, weak facets, and extreme functions of the Gomory-Johnson Infinite Group problem
- High degree sum of squares proofs, Bienstock-Zuckerberg hierarchy and CG cuts
- A comprehensive analysis of polyhedral lift-and-project methods
- The cutting plane method is polynomial for perfect matchings
- Cut-generating functions for integer variables
- Split rank of triangle and quadrilateral inequalities
- On the Hardest Problem Formulations for the 0/1 Lasserre Hierarchy
- On Counting Lattice Points and Chvátal-Gomory Cutting Planes
- Operations that Preserve the Covering Property of the Lifting Region
- Path Cover and Path Pack Inequalities for the Capacitated Fixed-Charge Network Flow Problem
- 0/1 Polytopes with Quadratic Chvátal Rank
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- Title not available (Why is that?)
- SCIP: solving constraint integer programs
- New computer-based search strategies for extreme functions of the Gomory-Johnson infinite group problem
- Global optimization with polynomials and the problem of moments
- Valid inequalities for mips and group polyhedra from approximate liftings
- Strengthening cuts for mixed integer programs
- The 0-1 knapsack problem with a single continuous variable
- Corner polyhedra and their connection with cutting planes
- T-space and cutting planes
- Cyclic group and knapsack facets
- On the facets of the mixed-integer knapsack polyhedron
- Strengthening Chvátal-Gomory cuts and Gomory fractional cuts
- An electronic compendium of extreme functions for the Gomory-Johnson infinite group problem
- A lift-and-project cutting plane algorithm for mixed 0-1 programs
- A 3-slope theorem for the infinite relaxation in the plane
- Conflict analysis in mixed integer programming
- Some polyhedra related to combinatorial problems
- Gomory cuts revisited
- Valid inequalities based on simple mixed-integer sets
- Light on the infinite group relaxation. I: Foundations and taxonomy
- Two row mixed-integer cuts via lifting
- A \((k+1)\)-slope theorem for the \(k\)-dimensional infinite group relaxation
- Unique minimal liftings for simplicial polytopes
- Constrained Infinite Group Relaxations of MIPs
- A Geometric Perspective on Lifting
- Minimal Valid Inequalities for Integer Constraints
- Maximal Lattice-Free Convex Sets in Linear Subspaces
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- Outline of an algorithm for integer solutions to linear programs
- Solving Large-Scale Zero-One Linear Programming Problems
- Cones of Matrices and Set-Functions and 0–1 Optimization
- Faces for a linear inequality in 0–1 variables
- Facet of regular 0–1 polytopes
- Facets of the knapsack polytope
- Facets of the Knapsack Polytope From Minimal Covers
- Mixed 0-1 Programming by Lift-and-Project in a Branch-and-Cut Framework
- Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case
- Cut-Generating Functions and S-Free Sets
- Equivariant perturbation in Gomory and Johnson's infinite group problem. III: Foundations for the \(k\)-dimensional case with applications to \(k=2\)
- Revival of the Gomory cuts in the 1990's
- Facets of Two-Dimensional Infinite Group Problems
- Inequalities from Two Rows of a Simplex Tableau
- Intersection Cuts—A New Type of Cutting Planes for Integer Programming
- Some continuous functions related to corner polyhedra
- Some continuous functions related to corner polyhedra, II
- A Comparison of the Sherali-Adams, Lovász-Schrijver, and Lasserre Relaxations for 0–1 Programming
- On the extreme inequalities of infinite group problems
- Relations between facets of low- and high-dimensional group problems
- Conflict graphs in solving integer programming problems
- Embedding \(\{0, \frac{1}{2}\}\)-cuts in a branch-and-cut framework: a computational study
- Numerically safe Gomory mixed-integer cuts
- Reduce-and-Split Cuts: Improving the Performance of Mixed-Integer Gomory Cuts
- Disjunctive Programming
- Sparse Matrix Methods in Optimization
- Optimizing over the first Chvátal closure
- Lower bounds for resolution and cutting plane proofs and monotone computations
- L-shaped decomposition of two-stage stochastic programs with integer recourse
- \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
- The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification
- Mixing mixed-integer inequalities
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Worst-case comparison of valid inequalities for the TSP
- Cutting-plane theory: Algebraic methods
- Minimal inequalities
- On the Group Problem and a Subadditive Approach to Integer Programming
- A Strong Dual for Conic Mixed-Integer Programs
- Lift-and-project for mixed 0-1 programming: recent progress
- A relax-and-cut framework for Gomory mixed-integer cuts
- Split closure and intersection cuts
- A recursive procedure to generate all cuts for 0-1 mixed integer programs
- Mixed \(n\)-step MIR inequalities: facets for the \(n\)-mixing set
- On optimizing over lift-and-project closures
- Edmonds polytopes and a hierarchy of combinatorial problems
- Intersection cuts with infinite Split rank
- \(k\)-cuts: a variation of Gomory mixed integer cuts from the LP tableau
- Sequence Independent Lifting for Mixed-Integer Programming
- On \(t\)-branch split cuts for mixed-integer programs
- A heuristic to generate rank-1 GMI cuts
- On the relative strength of split, triangle and quadrilateral cuts
- Chvátal closures for mixed integer programming problems
- Mingling: mixed-integer rounding with bounds
- Valid inequalities for mixed 0-1 programs
- Improving Integrality Gaps via Chvátal-Gomory Rounding
- Valid Linear Inequalities for Fixed Charge Problems
- Progress in Linear Programming-Based Algorithms for Integer Programming: An Exposition
- Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation
- A convex-analysis perspective on disjunctive cuts
- Finite Disjunctive Programming Characterizations for General Mixed-Integer Linear Programs
- On the exact separation of mixed integer knapsack cuts
- A disjunctive cutting plane procedure for general mixed-integer linear programs
- Generalized intersection cuts and a new cut generating paradigm
- On the relative strength of families of intersection cuts arising from pairs of tableau constraints in mixed integer programs
- On Cutting Planes
- Cutting planes in integer and mixed integer programming
- On convergence in mixed integer programming
Cited In (16)
- Special issue: Global solution of integer, stochastic and nonconvex optimization problems
- Machine learning for combinatorial optimization: a methodological tour d'horizon
- Cutting Plane Generation through Sparse Principal Component Analysis
- Enhancing cut selection through reinforcement learning
- Cutting planes and the parameter cutwidth
- Sparse PSD approximation of the PSD cone
- A lexicographic pricer for the fractional bin packing problem
- Gaining or losing perspective
- Selection of stockplate characteristics and cutting style for two dimensional cutting stock situations
- Adaptive cut selection in mixed-integer linear programming
- A branch\&cut approach to recharging and refueling infrastructure planning
- Exact and heuristic algorithms for the weighted total domination problem
- A knapsack intersection hierarchy
- Computing the volume of the convex hull of the graph of a trilinear monomial using mixed volumes
- Achieving consistency with cutting planes
- CUTTING PLANE WITH NON-UNIFORM DISTRIBUTIONS
Uses Software
This page was built for publication: Theoretical challenges towards cutting-plane selection
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1650776)
