Intersection Cuts—A New Type of Cutting Planes for Integer Programming

DOI10.1287/opre.19.1.19zbMath0219.90035OpenAlexW2171238021WikidataQ61687550 ScholiaQ61687550MaRDI QIDQ5624984

Egon Balas

Publication date: 1971

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

Full work available at URL: https://doi.org/10.1287/opre.19.1.19

Mathematics Subject Classification ID

Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Linear programming (90C05)

Related Items

Maximal Quadratic-Free Sets, Constructing Lattice-Free Gradient Polyhedra in Dimension Two, Intersection Disjunctions for Reverse Convex Sets, Cutting Plane Generation through Sparse Principal Component Analysis, Multirow Intersection Cuts Based on the Infinity Norm, Monoidal strengthening and unique lifting in MIQCPs, Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts, Towards a characterization of maximal quadratic-free sets, Optimal Cutting Planes from the Group Relaxations, A survey on mixed-integer programming techniques in bilevel optimization, On polytopes with linear rank with respect to generalizations of the split closure, The polyhedral-surface cutting plane method of optimization over a vertex-located set, Enumeration and unimodular equivalence of empty delta-modular simplices, Cut search methods in integer programming, Integer programming and convex analysis: Intersection cuts from outer polars, Polaroids: A new tool in non‐convex and in integer programming, Relaxations of mixed integer sets from lattice-free polyhedra, Classical cuts for mixed-integer programming and branch-and-cut, Lattice Reformulation Cuts, Relaxations of mixed integer sets from lattice-free polyhedra, Elementary closures for integer programs., Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs, Intersection cuts for nonlinear integer programming: convexification techniques for structured sets, On the Facets of Mixed Integer Programs with Two Integer Variables and Two Constraints, On the implementation and strengthening of intersection cuts for QCQPs, On the implementation and strengthening of intersection cuts for QCQPs, Equivariant Perturbation in Gomory and Johnson's Infinite Group Problem. I. The One-Dimensional Case, Computational study of a family of mixed-integer quadratic programming problems, Largest integral simplices with one interior integral point: solution of Hensley's conjecture and related results, Intersection cuts for single row corner relaxations, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Obtaining Tighter Relaxations of Mathematical Programs with Complementarity Constraints, Computing deep facet-defining disjunctive cuts for mixed-integer programming, Characterization of the split closure via geometric lifting, Two row mixed-integer cuts via lifting, Strong valid inequalities for orthogonal disjunctions and bilinear covering sets, Intersection Cuts for Bilevel Optimization, Theoretical challenges towards cutting-plane selection, A constructive characterization of the split closure of a mixed integer linear program, On the facets of mixed integer programs with two integer variables and two constraints, On optimizing over lift-and-project closures, General purpose heuristics for integer programming. I, On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts, On the polyhedrality of cross and quadrilateral closures, Discrete dynamical system approaches for Boolean polynomial optimization, Lattice-free simplices with lattice width \(2d - o(d)\), Partial hyperplane activation for generalized intersection cuts, Unique lifting of integer variables in minimal inequalities, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, Practical strategies for generating rank-1 split cuts in mixed-integer linear programming, On finitely generated closures in the theory of cutting planes, Lattice closures of polyhedra, On the NP-hardness of deciding emptiness of the split closure of a rational polytope in the 0,1 hypercube, Lifting Integer Variables in Minimal Inequalities Corresponding to Lattice-Free Triangles, Strengthening cuts for mixed integer programs, On the relative strength of split, triangle and quadrilateral cuts, Two-term disjunctions on the second-order cone, Reverse convex programming, Outer-product-free sets for polynomial optimization and oracle-based cuts, Generalized intersection cuts and a new cut generating paradigm, A proof of Lovász's theorem on maximal lattice-free sets, On the Practical Strength of Two-Row Tableau Cuts, A note on the MIR closure and basic relaxations of polyhedra, A probabilistic comparison of the strength of split, triangle, and quadrilateral cuts, Monoidal cut strengthening revisited, On linear programs with linear complementarity constraints, A note on the split rank of intersection cuts, Intersection cuts from multiple rows: a disjunctive programming approach, Improved strategies for branching on general disjunctions, A branch-and-cut algorithm for mixed integer bilevel linear optimization problems and its implementation, The mixing-MIR set with divisible capacities, Can Cut-Generating Functions Be Good and Efficient?, Accelerating convergence of cutting plane algorithms for disjoint bilinear programming, A branch-and-cut algorithm using polar cuts for solving nonconvex quadratic programming problems, A Probabilistic Analysis of the Strength of the Split and Triangle Closures, Mixed multigraph approach to scheduling jobs on machines of different types^∗, Intermediate integer programming representations using value disjunctions, How to convexify the intersection of a second order cone and a nonconvex quadratic, Intersection cuts -- standard versus restricted, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, Mixed integer programming with a class of nonlinear convex constraints, Intersection cuts for convex mixed integer programs from translated cones, The triangle closure is a polyhedron, Nondifferentiable reverse convex programs and facetial convexity cuts via a disjunctive characterization, A brief history of lift-and-project, Branching on general disjunctions, Quasi-concave minimization subject to linear constraints, Equivalence between intersection cuts and the corner polyhedron, Improved convexity cuts for lattice point problems, Bilinear programming: An exact algorithm, First facets of the octahedron, Polyhedral annexation in mixed integer and combinatorial programming, Split closure and intersection cuts, Two dimensional lattice-free cuts and asymmetric disjunctions for mixed-integer polyhedra, Pivot-and-reduce cuts: an approach for improving Gomory mixed-integer cuts, Disjunctive cuts for cross-sections of the second-order cone, The (not so) trivial lifting in two dimensions, A branch-and-cut algorithm for mixed-integer bilinear programming, Valid inequalities for mixed integer linear programs, A finitely convergent algorithm for bilinear programming problems using polar cuts and disjunctive face cuts, The Cutting Plane Method is Polynomial for Perfect Matchings, The strength of multi-row models, A note on the continuous mixing set, On the use of intersection cuts for bilevel optimization, On Minimal Valid Inequalities for Mixed Integer Conic Programs, On pathological disjunctions and redundant disjunctive conic cuts, Convexification techniques for linear complementarity constraints, On tackling reverse convex constraints for non-overlapping of unequal circles, Characterization of facets for multiple right-hand choice linear programs, Large-scale 0-1 linear programming on distributed workstations, When Lift-and-Project Cuts Are Different, Computational study of a family of mixed-integer quadratic programming problems, On convergence of scatter search and star paths with directional rounding for 0--1 mixed integer programs, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, Cutting-planes for programs with disjunctive constraints, Ranking the facets of the octahedron, Stable sets, corner polyhedra and the Chvàtal closure, Enhanced intersection cutting-plane approach for linear complementarity problems, On cutting planes for cardinality-constrained linear programs, Convergence of a subgradient method for computing the bound norm of matrices, Polyhedra related to integer-convex polynomial systems, A geometric approach to cut-generating functions, Polyhedral convexity cuts and negative edge extensions, On a generalization of the Chvátal-Gomory closure, Maximal quadratic-free sets, Constructing lattice-free gradient polyhedra in dimension two, Depth-optimized convexity cuts, Light on the infinite group relaxation. I: Foundations and taxonomy