A lift-and-project cutting plane algorithm for mixed 0-1 programs

DOI10.1007/BF01581273zbMath0796.90041OpenAlexW1970193303MaRDI QIDQ2367913

Sebastián Ceria, Egon Balas, Cornuéjols, Gérard

Publication date: 17 August 1993

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01581273

zbMATH Keywords

cutting plane sequential convexification facial disjunctive programs mixed 0-1 linear program

Mathematics Subject Classification ID

Mixed integer programming (90C11) Computational methods for problems pertaining to operations research and mathematical programming (90-08)

Related Items (only showing first 100 items - show all)

Beating the SDP bound for the floor layout problem: a simple combinatorial idea ⋮ Comparing Imperfection Ratio and Imperfection Index for Graph Classes ⋮ Algorithms and Software for Convex Mixed Integer Nonlinear Programs ⋮ Subgradient Based Outer Approximation for Mixed Integer Second Order Cone Programming ⋮ Disjunctive Cuts for Nonconvex MINLP ⋮ Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization ⋮ A Conic Representation of the Convex Hull of Disjunctive Sets and Conic Cuts for Integer Second Order Cone Optimization ⋮ SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY ⋮ Logic-Based Benders Decomposition and Binary Decision Diagram Based Approaches for Stochastic Distributed Operating Room Scheduling ⋮ Tractable Relaxations of Composite Functions ⋮ Decomposition Algorithms for Two-Stage Distributionally Robust Mixed Binary Programs ⋮ Disjunctive cuts in mixed-integer conic optimization ⋮ Integer programming solution approach for inventory‐production–distribution problems with direct shipments ⋮ Spherical cuts for integer programming problems ⋮ Combining semidefinite and polyhedral relaxations for integer programs ⋮ Combining and strengthening Gomory cuts ⋮ Scanning integer points with lex-inequalities: a finite cutting plane algorithm for integer programming with linear objective ⋮ A note on the SDP relaxation of the minimum cut problem ⋮ Monoidal strengthening of simple \(\mathcal{V} \)-polyhedral disjunctive cuts ⋮ Perspective Relaxation of Mixed Integer Nonlinear Programs with Indicator Variables ⋮ Disjunctive Cuts for Non-convex Mixed Integer Quadratically Constrained Programs ⋮ Using Two-Dimensional Projections for Stronger Separation and Propagation of Bilinear Terms ⋮ Quantifying the benefits of customized vaccination strategies: A network‐based optimization approach ⋮ Distributionally risk‐receptive and risk‐averse network interdiction problems with general ambiguity set ⋮ Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory ⋮ The Ramping Polytope and Cut Generation for the Unit Commitment Problem ⋮ Relaxations of mixed integer sets from lattice-free polyhedra ⋮ Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes ⋮ Lift-and-Project Cuts for Mixed Integer Convex Programs ⋮ Design and Verify: A New Scheme for Generating Cutting-Planes ⋮ An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming ⋮ Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack ⋮ Convexification Techniques for Linear Complementarity Constraints ⋮ Quadratic knapsack relaxations using cutting planes and semidefinite programming ⋮ Two-Stage Stochastic Mixed-Integer Programs: Algorithms and Insights ⋮ IFORS' Operational Research Hall of Fame ⋮ BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS ⋮ Smoothing and Regularization for Mixed-Integer Second-Order Cone Programming with Applications in Portfolio Optimization ⋮ Relaxations of mixed integer sets from lattice-free polyhedra ⋮ Branch and cut methods for network optimization ⋮ Elementary closures for integer programs. ⋮ The ABACUS system for branch-and-cut-and-price algorithms in integer programming and combinatorial optimization ⋮ Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables ⋮ Partial reformulation-linearization based optimization models for the Golomb ruler problem ⋮ Sum-of-squares hierarchies for binary polynomial optimization ⋮ Convex Relaxations for Quadratic On/Off Constraints and Applications to Optimal Transmission Switching ⋮ When Lift-and-Project Cuts Are Different ⋮ Unnamed Item ⋮ Unnamed Item ⋮ Computational study of a family of mixed-integer quadratic programming problems ⋮ Rank of random half-integral polytopes — extended abstract — ⋮ A disjunctive cut strengthening technique for convex MINLP ⋮ Lift-and-project ranks and antiblocker duality ⋮ Perspective reformulations of mixed integer nonlinear programs with indicator variables ⋮ Small Chvátal rank ⋮ Convex relaxations of non-convex mixed integer quadratically constrained programs: Extended formulations ⋮ Strong valid inequalities for orthogonal disjunctions and bilinear covering sets ⋮ Mixed-integer sets from two rows of two adjacent simplex bases ⋮ An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs ⋮ A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming ⋮ Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem ⋮ On optimizing over lift-and-project closures ⋮ Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications ⋮ Local cuts for mixed-integer programming ⋮ Discrete dynamical system approaches for Boolean polynomial optimization ⋮ Sparse multi-term disjunctive cuts for the epigraph of a function of binary variables ⋮ Tighter representations for set partitioning problems ⋮ Partial hyperplane activation for generalized intersection cuts ⋮ Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem ⋮ Generalised 2-circulant inequalities for the max-cut problem ⋮ A note on the 2-circulant inequalities for the MAX-cut problem ⋮ Integrality gaps for colorful matchings ⋮ Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs ⋮ Fenchel decomposition for stochastic mixed-integer programming ⋮ Split cuts from sparse disjunctions ⋮ Generalized intersection cuts and a new cut generating paradigm ⋮ Achieving consistency with cutting planes ⋮ The Steiner connectivity problem ⋮ Coordinated cutting plane generation via multi-objective separation ⋮ Integer set reduction for stochastic mixed-integer programming ⋮ A decomposition approach to the two-stage stochastic unit commitment problem ⋮ Semidefinite programming relaxations for the graph partitioning problem ⋮ On the facet defining inequalities of the mixed-integer bilinear covering set ⋮ On the facets of lift-and-project relaxations under graph operations ⋮ Decomposition algorithms with parametric Gomory cuts for two-stage stochastic integer programs ⋮ Bi-criteria and approximation algorithms for restricted matchings ⋮ Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations ⋮ Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra ⋮ Disjunctive cuts for continuous linear bilevel programming ⋮ Exact MAX-2SAT solution via lift-and-project closure ⋮ Constrained 0-1 quadratic programming: basic approaches and extensions ⋮ Design and verify: a new scheme for generating cutting-planes ⋮ Convex hull representation of the deterministic bipartite network interdiction problem ⋮ Optimizing over the split closure ⋮ Projected Chvátal-Gomory cuts for mixed integer linear programs ⋮ RLT insights into lift-and-project closures ⋮ A semidefinite programming heuristic for quadratic programming problems with complementarity constraints ⋮ Second order cone programming relaxation of nonconvex quadratic optimization problems

Cites Work

This page was built for publication: A lift-and-project cutting plane algorithm for mixed 0-1 programs