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

From MaRDI portal

Publication:2367913

Jump to:navigation, search

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

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, 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, The disjunctive procedure and blocker duality, A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems, Reformulating the disjunctive cut generating linear program, Column basis reduction and decomposable knapsack problems, Solving \(0/1\) integer programs with enumeration cutting planes, Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs, Integrality gaps for strengthened linear relaxations of capacitated facility location, Conic mixed-integer rounding cuts, Computing deep facet-defining disjunctive cuts for mixed-integer programming, Characterization of the split closure via geometric lifting, An approach to the asymmetric multi-depot capacitated arc routing problem, Binary extended formulations of polyhedral mixed-integer sets, Theoretical challenges towards cutting-plane selection, Generating cutting planes for the semidefinite relaxation of quadratic programs, A modified lift-and-project procedure, Semidefinite programming in combinatorial optimization, On the relationship between standard intersection cuts, lift-and-project cuts, and generalized intersection cuts, Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture, Relaxations of linear programming problems with first order stochastic dominance constraints, Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators, Semidefinite representations for finite varieties, The quadratic knapsack problem -- a survey, Links between linear bilevel and mixed 0-1 programming problems, Strong lift-and-project cutting planes for the stable set problem, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, An efficient linearization technique for mixed 0-1 polynomial problem, Stochastic and risk management models and solution algorithm for natural gas transmission network expansion and LNG terminal location planning, A heuristic to generate rank-1 GMI cuts, Rank of Handelman hierarchy for Max-Cut, On the relative strength of split, triangle and quadrilateral cuts, Cut generation through binarization, Two-term disjunctions on the second-order cone, On the behavior of the \(N_{+}\)-operator under blocker duality, Tightening simple mixed-integer sets with guaranteed bounds, Random half-integral polytopes, Foundation-penalty cuts for mixed-integer programs., Split cuts for robust mixed-integer optimization, Minimal arc-sets spanning dicycles, An exact algorithm for the 0-1 linear knapsack problem with a single continuous variable, On linear programs with linear complementarity constraints, Projecting systems of linear inequalities with binary variables, Lift and project relaxations for the matching and related polytopes, A note on the split rank of intersection cuts, Intersection cuts from multiple rows: a disjunctive programming approach, Reflections on generating (disjunctive) cuts, Convex relaxations of non-convex mixed integer quadratically constrained programs: projected formulations, New bounds on the unconstrained quadratic integer programming problem, The mixing-MIR set with divisible capacities, Monoidal cut strengthening and generalized mixed-integer rounding for disjunctions and complementarity constraints, Large-scale unit commitment under uncertainty: an updated literature survey, Strong-branching inequalities for convex mixed integer nonlinear programs, Computations with disjunctive cuts for two-stage stochastic mixed 0-1 integer programs, Exploiting equalities in polynomial programming, Almost robust discrete optimization, Global optimization of generalized semi-infinite programs using disjunctive programming, Approximate formulations for 0-1 knapsack sets, Pseudo basic steps: bound improvement guarantees from Lagrangian decomposition in convex disjunctive programming, The ancestral Benders' cutting plane algorithm with multi-term disjunctions for mixed-integer recourse decisions in stochastic programming, An algorithmic framework for convex mixed integer nonlinear programs, Intermediate integer programming representations using value disjunctions, Two new reformulation convexification based hierarchies for 0-1 MIPs, How to convexify the intersection of a second order cone and a nonconvex quadratic, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, A new lift-and-project operator, Geometric proofs for convex hull defining formulations, Lift-and-project ranks of the set covering polytope of circulant matrices, A brief history of lift-and-project, Revival of the Gomory cuts in the 1990's, RLT: A unified approach for discrete and continuous nonconvex optimization, Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem, Lift-and-project for mixed 0-1 programming: recent progress, Cutting planes in integer and mixed integer programming, On the complexity of cutting-plane proofs using split cuts, Branching on general disjunctions, Lagrangian decomposition of block-separable mixed-integer all-quadratic programs, Valid inequalities for mixed integer linear programs, Block-diagonal semidefinite programming hierarchies for 0/1 programming, On the polyhedral lift-and-project methods and the fractional stable set polytope, A geometric characterization of ``optimality-equivalent relaxations, Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation, A linearization framework for unconstrained quadratic (0-1) problems, A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions, Fixing variables and generating classical cutting planes when using an interior point branch and cut method to solve integer programming problems, A cutting-plane approach to mixed 0-1 stochastic integer programs, Projections of the capacitated network loading problem, Lower bounds for nonlinear assignment problems using many body interactions, ProGen/\(\pi x\) -- An instance generator for resource-constrained project scheduling problems with partially renewable resources and further extensions, Generating lift-and-project cuts from the LP simplex tableau: open source implementation and testing of new variants, Extended formulations for convex hulls of some bilinear functions, A variant of time minimizing assignment problem, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Logic cuts for processing networks with fixed charges, Depth-optimized convexity cuts, Rapid prototyping of optimization algorithms using COIN-OR: a case study involving the cutting-stock problem, Logic-based modeling and solution of nonlinear discrete/continuous optimization problems, A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems, Projection, lifting and extended formulation integer and combinatorial optimization, Strengthening Chvátal-Gomory cuts and Gomory fractional cuts, Light on the infinite group relaxation. I: Foundations and taxonomy, A dynamic inequality generation scheme for polynomial programming, 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, Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming, Perspective cuts for a class of convex 0-1 mixed integer programs, Unnamed Item, Unnamed Item, Unnamed Item, Clutter nonidealness, Partial convexification cuts for 0--1 mixed-integer programs, A convex-analysis perspective on disjunctive cuts, On the gap between the quadratic integer programming problem and its semidefinite relaxation, An improved semidefinite programming relaxation for the satisfiability problem, Exact algorithms based on Benders decomposition for multicommodity uncapacitated fixed-charge network design, Several notes on the power of Gomory-Chvátal cuts, A generalized Benders decomposition-based branch and cut algorithm for two-stage stochastic programs with nonconvex constraints and mixed-binary first and second stage variables, On the commutativity of antiblocker diagrams under lift-and-project operators, Pivot-and-reduce cuts: an approach for improving Gomory mixed-integer cuts, On solving discrete two-stage stochastic programs having mixed-integer first- and second-stage variables, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, The Cutting Plane Method is Polynomial for Perfect Matchings, On pathological disjunctions and redundant disjunctive conic cuts, Convexification techniques for linear complementarity constraints, Balas formulation for the union of polytopes is optimal, Cluster based branching for the asymmetric traveling salesman problem, Using cutting planes in an interactive reference point approach for multiobjective integer linear programming problems, Disjunctive Decomposition for Two-Stage Stochastic Mixed-Binary Programs with Generalized Upper Bound Constraints, Computational study of a family of mixed-integer quadratic programming problems, Combinatorial optimization and small polytopes, Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope, On solving two-stage distributionally robust disjunctive programs with a general ambiguity set, Matroid optimization problems with monotone monomials in the objective, On convergence of scatter search and star paths with directional rounding for 0--1 mixed integer programs, Strength of facets for the set covering and set packing polyhedra on circulant matrices, On the dominating set polytope of web graphs, Disjunctive ranks and anti-ranks of some facet-inducing inequalities of the acyclic coloring polytope, A note on modeling multiple choice requirements for simple mixed integer programming solvers, Gomory cuts revisited, ``Facet separation with one linear program, The \(C^3\) theorem and a \(D^2\) algorithm for large scale stochastic mixed-integer programming: set convexification, Cuts for mixed 0-1 conic programming, The aggregation closure is polyhedral for packing and covering integer programs, Lift-and-project for general two-term disjunctions, A combinatorial cut-and-lift procedure with an application to 0-1 second-order conic programming, Decomposition of loosely coupled integer programs: a multiobjective perspective, A decomposition method for distributionally-robust two-stage stochastic mixed-integer conic programs, Polyhedra related to integer-convex polynomial systems, Mixed integer models for the stationary case of gas network optimization, Valid inequalities based on simple mixed-integer sets, On mathematical programming with indicator constraints, An L-shaped method with strengthened lift-and-project cuts, Large-scale unit commitment under uncertainty, On the exact separation of cover inequalities of maximum-depth

Cites Work

Retrieved from "https://portal.mardi4nfdi.de/w/index.php?title=Publication:2367913&oldid=14985684"