A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
From MaRDI portal
Publication:3197621
DOI10.1137/0403036zbMath0712.90050OpenAlexW2049143039MaRDI QIDQ3197621
Hanif D. Sherali, Warren P. Adams
Publication date: 1990
Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1137/0403036
Integer programming (90C10) Linear programming (90C05) Combinatorial optimization (90C27) Boolean programming (90C09)
Related Items
A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems, Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, Sum-of-squares rank upper bounds for matching problems, The QAP-polytope and the graph isomorphism problem, Integrality gaps for strengthened linear relaxations of capacitated facility location, Duality for mixed-integer convex minimization, On integrality ratios for asymmetric TSP in the Sherali-Adams hierarchy, Lifting inequalities: a framework for generating strong cuts for nonlinear programs, Conic mixed-integer rounding cuts, Characterization of the split closure via geometric lifting, Integer programming formulations for the elementary shortest path problem, A model for clustering data from heterogeneous dissimilarities, Deriving convex hulls through lifting and projection, Matroid optimisation problems with nested non-linear monomials in the objective function, Surrogate-RLT cuts for zero-one integer programs, Binary extended formulations of polyhedral mixed-integer sets, Theoretical challenges towards cutting-plane selection, Enhanced compact models for the connected subgraph problem and for the shortest path problem in digraphs with negative cycles, A bilevel partial interdiction problem with capacitated facilities and demand outsourcing, Multiple asymmetric traveling salesmen problem with and without precedence constraints: performance comparison of alternative formulations, Generating cutting planes for the semidefinite relaxation of quadratic programs, A modified lift-and-project procedure, Semidefinite programming in combinatorial optimization, On decomposability of multilinear sets, Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators, Semidefinite representations for finite varieties, On the bridge between combinatorial optimization and nonlinear optimization: a family of semidefinite bounds for 0--1 quadratic problems leading to quasi-Newton methods, Semidefinite relaxations of ordering problems, A level-2 reformulation-linearization technique bound for the quadratic assignment problem, Links between linear bilevel and mixed 0-1 programming problems, Strong lift-and-project cutting planes for the stable set problem, The matching problem has no small symmetric SDP, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, An efficient linearization technique for mixed 0-1 polynomial problem, The coastal seaspace patrol sector design and allocation problem, A branch-and-cut decomposition algorithm for solving chance-constrained mathematical programs with finite support, Rank of Handelman hierarchy for Max-Cut, Lifted polynomial size formulations for the homogeneous and heterogeneous vehicle routing problems, Knapsack problem with probability constraints, Domain reduction techniques for global NLP and MINLP optimization, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Tightening simple mixed-integer sets with guaranteed bounds, Low degree Nullstellensatz certificates for 3-colorability, Foundation-penalty cuts for mixed-integer programs., Minimal arc-sets spanning dicycles, On linear programs with linear complementarity constraints, Projecting systems of linear inequalities with binary variables, A note on representations of linear inequalities in non-convex mixed-integer quadratic programs, A Lagrange decomposition based branch and bound algorithm for the optimal mapping of cloud virtual machines, Handelman's hierarchy for the maximum stable set problem, Branch-and-cut for complementarity-constrained optimization, Using symmetry to optimize over the Sherali-Adams relaxation, Extended formulations for convex envelopes, A global optimization algorithm for polynomial programming problems using a reformulation-linearization technique, The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling, Approximate formulations for 0-1 knapsack sets, A network approach for specially structured linear programs arising in 0-1 quadratic optimization, Rank bounds for a hierarchy of Lovász and Schrijver, Cutting planes from extended LP formulations, Intermediate integer programming representations using value disjunctions, An eigenvalue decomposition based branch-and-bound algorithm for nonconvex quadratic programming problems with convex quadratic constraints, The MIN-cut and vertex separator problem, A new reformulation-linearization technique for bilinear programming problems, Higher-level RLT or disjunctive cuts based on a partial enumeration strategy for 0-1 mixed-integer programs, Cutting planes and the parameter cutwidth, A brief history of lift-and-project, RLT: A unified approach for discrete and continuous nonconvex optimization, Lift-and-project for mixed 0-1 programming: recent progress, Cutting planes in integer and mixed integer programming, Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique, Strong multi-commodity flow formulations for the asymmetric traveling salesman problem, Valid inequalities for mixed integer linear programs, An algorithm for the generalized quadratic assignment problem, Block-diagonal semidefinite programming hierarchies for 0/1 programming, Uncapacitated flow-based extended formulations, On the polyhedral lift-and-project methods and the fractional stable set polytope, A geometric characterization of ``optimality-equivalent relaxations, Tight rank lower bounds for the Sherali-Adams proof system, Using rank-1 lift-and-project closures to generate cuts for 0-1 MIPs, a computational investigation, Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem, A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions, Enumeration approach for linear complementarity problems based on a reformulation-linearization technique, On the Chvátal rank of the pigeonhole principle, Projections of the capacitated network loading problem, Lower bounds for nonlinear assignment problems using many body interactions, Extended formulations for convex hulls of some bilinear functions, An approximate approach of global optimization for polynomial programming problems, New modeling approaches for the design of local access transport area networks, Stable sets and polynomials, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, Polynomial optimization with applications to stability analysis and control -- alternatives to sum of squares, A global optimization RLT-based approach for solving the fuzzy clustering problem, Recent advances for the quadratic assignment problem with special emphasis on instances that are difficult for meta-heuristic methods, Logic-based modeling and solution of nonlinear discrete/continuous optimization problems, A conditional logic approach for strengthening mixed 0-1 linear programs, A hierarchy of relaxations leading to the convex hull representation for general discrete optimization problems, Projection, lifting and extended formulation integer and combinatorial optimization, Some classes of valid inequalities and convex hull characterizations for dynamic fixed-charge problems under nested constraints, A dynamic inequality generation scheme for polynomial programming, A lift-and-project cutting plane algorithm for mixed 0-1 programs, Lift-and-project ranks and antiblocker duality, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, A sensitive-eigenvector based global algorithm for quadratically constrained quadratic programming, A global optimization algorithm for reliable network design, Small Chvátal rank, The quadratic three-dimensional assignment problem: exact and approximate solution methods, Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs, Tree-width and the Sherali-Adams operator, An explicit semidefinite characterization of satisfiability for Tseitin instances on toroidal grid graphs, Two-stage stochastic hierarchical multiple risk problems: Models and algorithms, Constraint selection in a build-up interior-point cutting-plane method for solving relaxations of the stable-set problem, Handelman rank of zero-diagonal quadratic programs over a hypercube and its applications, Configuration of airspace sectors for balancing air traffic controller workload, Discrete dynamical system approaches for Boolean polynomial optimization, High-dimensional change-point estimation: combining filtering with convex optimization, A bounded degree SOS hierarchy for polynomial optimization, A 2-approximation for the bounded treewidth sparsest cut problem in \textsf{FPT} Time, Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering, Tighter representations for set partitioning problems, A note on the Lasserre hierarchy for different formulations of the maximum independent set problem, Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem, MTZ-primal-dual model, cutting-plane, and combinatorial branch-and-bound for shortest paths avoiding negative cycles, Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints, Integer programming approaches to the multiple team formation problem, A ``joint + marginal heuristic for 0/1 programs, Product assortment and space allocation strategies to attract loyal and non-loyal customers, A cut-and-branch algorithm for the quadratic knapsack problem, \texttt{EXPEDIS}: an exact penalty method over discrete sets, Integrality gaps for colorful matchings, Branch and cut algorithms for detecting critical nodes in undirected graphs, Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs, On the impact of running intersection inequalities for globally solving polynomial optimization problems, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring, Breaking symmetries to rescue sum of squares in the case of makespan scheduling, Achieving consistency with cutting planes, A penalized nonlinear ADMM algorithm applied to the multi-constrained traffic assignment problem, Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems, A Benders decomposition approach for an integrated airline schedule design and fleet assignment problem with flight retiming, schedule balance, and demand recapture, A decomposition approach for solving a broadcast domination network design problem, Elliptic approximations of propositional formulae, Bi-criteria and approximation algorithms for restricted matchings, Reduced first-level representations via the reformulation-linearization technique: Results, counterexamples, and computations, An improved linearization strategy for zero-one quadratic programming problems, Unification of lower-bound analyses of the lift-and-project rank of combinatorial optimization polyhedra, Strengthening convex relaxations of 0/1-sets using Boolean formulas, New global algorithms for quadratic programming with a few negative eigenvalues based on alternative direction method and convex relaxation, Lift \& project systems performing on the partial-vertex-cover polytope, Branch-and-price-and-cut on the clique partitioning problem with minimum clique size requirement, Two new reformulation convexification based hierarchies for 0-1 MIPs, Convex hull representation of the deterministic bipartite network interdiction problem, A new lift-and-project operator, Mathematical optimization approaches for facility layout problems: the state-of-the-art and future research directions, Global optimization of general nonconvex problems with intermediate polynomial substructures, Geometric proofs for convex hull defining formulations, An RLT approach for solving the binary-constrained mixed linear complementarity problem, RLT insights into lift-and-project closures, A bilevel fixed charge location model for facilities under imminent attack, Notoriously hard (mixed-)binary QPs: empirical evidence on new completely positive approaches, Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming, Partial convexification cuts for 0--1 mixed-integer programs, A polyhedral study of the generalized vertex packing problem, A class of lifted path and flow-based formulations for the asymmetric traveling salesman problem with and without precedence constraints, An improved semidefinite programming relaxation for the satisfiability problem, Conic approximation to nonconvex quadratic programming with convex quadratic constraints, Penalized semidefinite programming for quadratically-constrained quadratic optimization, Polyhedral properties of the induced cluster subgraphs, 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, A survey on conic relaxations of optimal power flow problem, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, Polynomial-size formulations and relaxations for the quadratic multiple knapsack problem, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, An evaluation of semidefinite programming based approaches for discrete lot-sizing problems, Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Lift-and-project methods for set cover and knapsack, Approximating graph-constrained max-cut, Semidefinite and linear programming integrality gaps for scheduling identical machines, Extension complexity of the correlation polytope, Convexification techniques for linear complementarity constraints, Bilevel programming methods for computing single-leader-multi-follower equilibria in normal-form and polymatrix games, Convex hull representations of special monomials of binary variables, Matroid optimization problems with monotone monomials in the objective, An optimal data-splitting algorithm for aircraft sequencing on a single runway, 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, A global optimization RLT-based approach for solving the hard clustering problem, Sherali-Adams relaxations of graph isomorphism polytopes, Symmetry-exploiting cuts for a class of mixed-\(0/1\) second-order cone programs, Linear programming insights into solvable cases of the quadratic assignment problem, Polyhedra related to integer-convex polynomial systems, Approximate extended formulations, Approximate fixed-rank closures of covering problems, Sparse learning via Boolean relaxations, A gentle, geometric introduction to copositive optimization, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Detecting copositivity of a symmetric matrix by an adaptive ellipsoid-based approximation scheme, Between steps: intermediate relaxations between big-M and convex hull formulations, Univariate parameterization for global optimization of mixed-integer polynomial problems, Lasserre integrality gaps for graph spanners and related problems, Narrow Proofs May Be Maximally Long, LP relaxations for a class of linear semi-infinite programming problems, Beating the SDP bound for the floor layout problem: a simple combinatorial idea, Stochastic Quadratic Knapsack with Recourse, Strength of Three MIP Formulations for the Prize Collecting Steiner Tree Problem with a Quota Constraint, Taking advantage of symmetry in some quadratic assignment problems, Lifting for Simplicity: Concise Descriptions of Convex Sets, Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization, Matrix Relaxations in Combinatorial Optimization, Limitations of Algebraic Approaches to Graph Isomorphism Testing, Query Complexity in Expectation, Sherali-Adams Relaxations for Valued CSPs, Approximation Limits of Linear Programs (Beyond Hierarchies), Mathematical Programming Models and Exact Algorithms, Making the Long Code Shorter, PEBBLE GAMES AND LINEAR EQUATIONS, Unnamed Item, Lehman's Theorem and the Directed Steiner Tree Problem, Max-Cut Under Graph Constraints, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Communication Lower Bounds via Critical Block Sensitivity, Uncertainty Preferences in Robust Mixed-Integer Linear Optimization with Endogenous Uncertainty, Semidefinite Programming Relaxations of the Traveling Salesman Problem and Their Integrality Gaps, SOME EXPERIENCES WITH SOLVING SEMIDEFINITE PROGRAMMING RELAXATIONS OF BINARY QUADRATIC OPTIMIZATION MODELS IN COMPUTATIONAL BIOLOGY, Tractable Relaxations of Composite Functions, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, Enhanced Models for a Mixed Arrival-Departure Aircraft Sequencing Problem, The Power of Sherali--Adams Relaxations for General-Valued CSPs, PTAS for Sparse General-valued CSPs, Definable Ellipsoid Method, Sums-of-Squares Proofs, and the Graph Isomorphism Problem, Efficient separation of RLT cuts for implicit and explicit bilinear products, New Enhancements for the Exact Solution of the Vehicle Routing Problem with Time Windows, Throughput optimization for the Robotic Cell Problem with Controllable Processing Times, LP-Based Algorithms for Capacitated Facility Location, Unnamed Item, Binarisation for Valued Constraint Satisfaction Problems, Proof Complexity Meets Algebra, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, The Complexity of Valued CSPs, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, Solving Quadratic Programming by Cutting Planes, A guide to conic optimisation and its applications, Quasi-PTAS for scheduling with precedences using LP hierarchies, Exact solution of emerging quadratic assignment problems, The Multilinear Polytope for Acyclic Hypergraphs, LP Formulations for Polynomial Optimization Problems, A general system for heuristic minimization of convex functions over non-convex sets, Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes, 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, Global solution of non-convex quadratically constrained quadratic programs, Two-Stage Stochastic Mixed-Integer Programs: Algorithms and Insights, Cones of multipowers and combinatorial optimization problems, Cutting Planes and the Parameter Cutwidth, BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS, Computational and statistical tradeoffs via convex relaxation, Smoothing and Regularization for Mixed-Integer Second-Order Cone Programming with Applications in Portfolio Optimization, Branch and cut methods for network optimization, A Lagrangian relaxation approach to the edge-weighted clique problem, Elementary closures for integer programs., A Polyhedral Characterization of Border Bases, Unnamed Item, Global optimization of general non-convex problems with intermediate bilinear substructures, Resolution Width and Cutting Plane Rank Are Incomparable, Unnamed Item, Unnamed Item, Multi-period maintenance scheduling of tree networks with minimum flow disruption, Semidefinite relaxations for partitioning, assignment and ordering problems, Convex Relaxations and Integrality Gaps, Approximating $k$-Median via Pseudo-Approximation, Sum-of-squares hierarchies for binary polynomial optimization, A tight approximation algorithm for the cluster vertex deletion problem, Semidefinite relaxations for partitioning, assignment and ordering problems, Reformulations in Mathematical Programming: Definitions and Systematics, Tightening concise linear reformulations of 0-1 cubic programs, Sum-of-squares hierarchies for binary polynomial optimization, A tight approximation algorithm for the cluster vertex deletion problem, A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem, No Small Linear Program Approximates Vertex Cover Within a Factor 2 − ɛ, Convex Relaxations for Quadratic On/Off Constraints and Applications to Optimal Transmission Switching, New Tools for Graph Coloring, Unnamed Item, Short Proofs Are Hard to Find, Unnamed Item, Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope, Sherali-adams strikes back, Sum-of-Squares Rank Upper Bounds for Matching Problems, Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem, Allocating nodes to hubs for minimizing the hubs processing resources: A case study, Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs, The Power of Linear Programming for General-Valued CSPs, Unnamed Item, Unnamed Item, Unnamed Item, Minimum Congestion Mapping in a Cloud, Superlinear Integrality Gaps for the Minimum Majority Problem, A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem, The Complexity of General-Valued Constraint Satisfaction Problems Seen from the Other Side, Formulations and a Lagrangian relaxation approach for the prize collecting traveling salesman problem, A survey on bilevel optimization under uncertainty, Outcome-space branch-and-bound outer approximation algorithm for a class of non-convex quadratic programming problems, Tight lower bounds for the traveling salesman problem with draft limits, Circular (Yet Sound) Proofs in Propositional Logic, Number of Variables for Graph Differentiation and the Resolution of Graph Isomorphism Formulas, Polyhedral techniques in combinatorial optimization: matchings and tours, Branch-and-bound performance estimation programming: a unified methodology for constructing optimal optimization methods, Characterizing linearizable QAPs by the level-1 reformulation-linearization technique, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, A knapsack intersection hierarchy, A \(7 / 3\)-approximation algorithm for feedback vertex set in tournaments via Sherali-Adams, An LP-based characterization of solvable QAP instances with chess-board and graded structures, A theoretical and computational study of green vehicle routing problems, Shortest Paths in Graphs of Convex Sets
