Cones of Matrices and Set-Functions and 0–1 Optimization

DOI10.1137/0801013zbMath0754.90039OpenAlexW2106264302WikidataQ90164260 ScholiaQ90164260MaRDI QIDQ4012419

László Lovász, Alexander Schrijver

Publication date: 27 September 1992

Published in: SIAM Journal on Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1137/0801013

zbMATH Keywords

Möbius functionpolyhedral combinatoricssubmodular functionsvertex packing polytope\(t\)-perfect graphs

Mathematics Subject Classification ID

Extremal problems in graph theory (05C35) Special polytopes (linear programming, centrally symmetric, etc.) (52B12) Integer programming (90C10) Combinatorial optimization (90C27) Boolean programming (90C09)

Related Items

A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems, Copositive and semidefinite relaxations of the quadratic assignment problem, Lift-and-project ranks of the stable set polytope of joined \(a\)-perfect graphs, Sum-of-squares rank upper bounds for matching problems, Globally solving box-constrained nonconvex quadratic programs with semidefinite-based finite branch-and-bound, 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, Copositive programming motivated bounds on the stability and the chromatic numbers, Conic mixed-integer rounding cuts, Exploiting group symmetry in semidefinite programming relaxations of the quadratic assignment problem, A computational study for bilevel quadratic programs using semidefinite relaxations, A survey for the quadratic assignment 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, Phase retrieval for imaging problems, A modified lift-and-project procedure, Semidefinite programming in combinatorial optimization, A computational study and survey of methods for the single-row facility layout problem, Minimal \(N_{+}\)-rank graphs: progress on Lipták and Tunçel's conjecture, Semidefinite representations for finite varieties, Semidefinite programming relaxations for graph coloring and maximal clique problems, Strengthened semidefinite programming bounds for codes, 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, The quadratic knapsack problem -- a survey, A characterization of Delsarte's linear programming bound as a ratio bound, Stochastic nuclear outages semidefinite relaxations, Semidefinite bounds for the stability number of a graph via sums of squares of polynomials, Links between linear bilevel and mixed 0-1 programming problems, Polytopes of minimum positive semidefinite rank, Strong lift-and-project cutting planes for the stable set problem, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, Theoretical filtering of RLT bound-factor constraints for solving polynomial programming problems to global optimality, Gap inequalities for non-convex mixed-integer quadratic programs, Rank of Handelman hierarchy for Max-Cut, A semidefinite optimization approach to the target visitation problem, Strong LP formulations for scheduling splittable jobs on unrelated machines, Algebraic proof systems over formulas., On the behavior of the \(N_{+}\)-operator under blocker duality, Copositive optimization -- recent developments and applications, Think co(mpletely)positive! Matrix properties, examples and a clustered bibliography on copositive optimization, Robust semidefinite relaxations for a quadratic OFDMA resource allocation scheme, Towards strong nonapproximability results in the Lovász-Schrijver hierarchy, A new semidefinite programming hierarchy for cycles in binary matroids and cuts in graphs, Low degree Nullstellensatz certificates for 3-colorability, Random half-integral polytopes, Improved estimation of duality gap in binary quadratic programming using a weighted distance measure, 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, New bounds on the unconstrained quadratic integer programming problem, The mixing-MIR set with divisible capacities, Handelman's hierarchy for the maximum stable set problem, Binary positive semidefinite matrices and associated integer polytopes, The equivalence of semidefinite relaxations of polynomial 0-1 and \(\pm 1\) programs via scaling, Approximate formulations for 0-1 knapsack sets, Rank bounds for a hierarchy of Lovász and Schrijver, Intermediate integer programming representations using value disjunctions, Lovász-Schrijver SDP-operator, near-perfect graphs and near-bipartite graphs, An axiomatic duality framework for the theta body and related convex corners, Simple solution methods for separable mixed linear and quadratic knapsack problem, 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, Semidefinite programming for discrete optimization and matrix completion problems, Improving an upper bound on the stability number of a graph, An algorithm for nonlinear optimization problems with binary variables, On linear and semidefinite programming relaxations for hypergraph matching, Extensions on ellipsoid bounds for quadratic integer programming, Valid inequalities for mixed integer linear programs, New semidefinite programming relaxations for the linear ordering and the traveling salesman problem, Block-diagonal semidefinite programming hierarchies for 0/1 programming, Community detection in sparse networks via Grothendieck's inequality, Linear programming relaxations and marginal productivity index policies for the buffer sharing problem, Faster, but weaker, relaxations for quadratically constrained quadratic programs, 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, On the Lovász \(\vartheta\)-number of almost regular graphs with application to Erdős-Rényi graphs, A reformulation-linearization technique (RLT) for semi-infinite and convex programs under mixed 0-1 and general discrete restrictions, On the Chvátal rank of the pigeonhole principle, Commutative association schemes, Role of redundant constraints for improving dual bounds in polynomial optimization problems, Lower bounds for nonlinear assignment problems using many body interactions, The strong perfect graph conjecture: 40 years of attempts, and its resolution, Spectral characterizations of the Lovász number and the Delsarte number of a graph, Stable sets and polynomials, Semidefinite programming, Strengthened semidefinite relaxations via a second lifting for the Max-Cut problem, On the Slater condition for the SDP relaxations of nonconvex sets, 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, A dynamic inequality generation scheme for polynomial programming, Narrow Proofs May Be Maximally Long, Beating the SDP bound for the floor layout problem: a simple combinatorial idea, Rank of random half-integral polytopes — extended abstract —, Exploiting low-rank structure in semidefinite programming by approximate operator splitting, SDP vs. LP Relaxations for the Moment Approach in Some Performance Evaluation Problems, Exploiting aggregate sparsity in second-order cone relaxations for quadratic constrained quadratic programming problems, A quadratic semidefinite relaxation approach for resource allocation in orthogonal frequency division multiple access, Lifting for Simplicity: Concise Descriptions of Convex Sets, Linear Programming Relaxations of Quadratically Constrained Quadratic Programs, Computation with Polynomial Equations and Inequalities Arising in Combinatorial Optimization, Matrix Relaxations in Combinatorial Optimization, Approximation Limits of Linear Programs (Beyond Hierarchies), Mathematical Programming Models and Exact Algorithms, Unnamed Item, Obtaining Tighter Relaxations of Mathematical Programs with Complementarity Constraints, Convex Relaxations for Permutation Problems, A Derivation of Lovász' Theta via Augmented Lagrange Duality, Lehman's Theorem and the Directed Steiner Tree Problem, Semidefinite and Linear Programming Integrality Gaps for Scheduling Identical Machines, Communication Lower Bounds via Critical Block Sensitivity, Lovász and Schrijver $$N_+$$-Relaxation on Web Graphs, 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, The stable set problem: clique and nodal inequalities revisited, The Unbounded Integrality Gap of a Semidefinite Relaxation of the Traveling Salesman Problem, Ellipsoidal Relaxations of the Stable Set Problem: Theory and Algorithms, The Power of Sherali--Adams Relaxations for General-Valued CSPs, Nonlinear formulations and improved randomized approximation algorithms for multicut problems, Combining semidefinite and polyhedral relaxations for integer programs, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, Linear programing relaxations for a strategic pricing problem in electricity markets, Characterizing N+-perfect line graphs, Lovász-Schrijver PSD-operator and the stable set polytope of claw-free graphs, Proof Complexity Meets Algebra, Exploring the Limits of Subadditive Approaches: Parallels between Optimization and Complexity Theory, Quadratic 0–1 programming: Tightening linear or quadratic convex reformulation by use of relaxations, Improved Approximation Guarantees through Higher Levels of SDP Hierarchies, A guide to conic optimisation and its applications, Complexity Analyses of Bienstock–Zuckerberg and Lasserre Relaxations on the Matching and Stable Set Polytopes, Design and Verify: A New Scheme for Generating Cutting-Planes, An Iterative Scheme for Valid Polynomial Inequality Generation in Binary Polynomial Programming, A New Approach to the Stable Set Problem Based on Ellipsoids, Integrality Gaps of Linear and Semi-Definite Programming Relaxations for Knapsack, Quadratic knapsack relaxations using cutting planes and semidefinite programming, Global optimization, Interior Point Methods for Nonlinear Optimization, Cones of multipowers and combinatorial optimization problems, BREAKING THE RECTANGLE BOUND BARRIER AGAINST FORMULA SIZE LOWER BOUNDS, Semidefinite relaxation and nonconvex quadratic optimization, Copositive realxation for genera quadratic programming, Semidefinite relaxation for linear programs with equilibrium constraints, Smoothing and Regularization for Mixed-Integer Second-Order Cone Programming with Applications in Portfolio Optimization, Robust Optimization of Sums of Piecewise Linear Functions with Application to Inventory Problems, Branch and cut methods for network optimization, A Lagrangian relaxation approach to the edge-weighted clique problem, A projected gradient algorithm for solving the maxcut SDP relaxation, Second order cone programming relaxation of nonconvex quadratic optimization problems, Unnamed Item, Convex quadratic relaxations of nonconvex quadratically constrained quadratic programs, Resolution Width and Cutting Plane Rank Are Incomparable, A characterization of the weighted version of McEliece–Rodemich–Rumsey–Schrijver number based on convex quadratic programming, A Comprehensive Analysis of Polyhedral Lift-and-Project Methods, The Complexity of Propositional Proofs, Unnamed Item, Exponential Lower Bounds for Polytopes in Combinatorial Optimization, The Cutting Plane Method is Polynomial for Perfect Matchings, Semidefinite relaxations for partitioning, assignment and ordering problems, Convex Hulls of Algebraic Sets, Convex Relaxations and Integrality Gaps, SDP Relaxations for Some Combinatorial Optimization Problems, Global Approaches for Facility Layout and VLSI Floorplanning, Sparse PCA: Convex Relaxations, Algorithms and Applications, Sum-of-squares hierarchies for binary polynomial optimization, Semidefinite relaxations for partitioning, assignment and ordering problems, Sum-of-squares hierarchies for binary polynomial optimization, A Notion of Total Dual Integrality for Convex, Semidefinite, and Extended Formulations, 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, On semidefinite bounds for maximization of a non-convex quadratic objective over thel<sub>1</sub>unit ball, Interior point methods, a decade after Karmarkar—a survey, with application to the smallest eigenvalue problem, Unnamed Item, Size-degree trade-offs for sums-of-squares and positivstellensatz proofs, Exploring the disjunctive rank of some facet-inducing inequalities of the acyclic coloring polytope, Unnamed Item, Unnamed Item, Lovász-Schrijver PSD-Operator on Claw-Free Graphs, Strengthening Chvátal-Gomory Cuts for the Stable Set Problem, Sum-of-Squares Rank Upper Bounds for Matching Problems, Strength of facets for the set covering and set packing polyhedra on circulant matrices, Some advances on Lovász-Schrijver relaxations of the fractional stable set polytope, On the facets of the lift-and-project relaxations of graph subdivisions, Near-perfect graphs with polyhedral, Approximating Rectangles by Juntas and Weakly Exponential Lower Bounds for LP Relaxations of CSPs, Exact Solution of Two Location Problems via Branch-and-Bound, Global Registration of Multiple Point Clouds Using Semidefinite Programming, Unnamed Item, Mixed linear and semidefinite programming for combinatorial and quadratic optimization, Superlinear Integrality Gaps for the Minimum Majority Problem, A Hierarchy of Standard Polynomial Programming Formulations for the Maximum Clique Problem, A lift-and-project cutting plane algorithm for mixed 0-1 programs, On NP-hardness of the clique partition -- independence number gap recognition and related problems, Lift-and-project ranks and antiblocker duality, Small Chvátal rank, 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, Partial Lagrangian relaxation for general quadratic programming, Some geometric results in semidefinite programming, A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming, An application of the Lovász-Schrijver \(M(K, K)\) operator to the stable set problem, 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, Discrete dynamical system approaches for Boolean polynomial optimization, Elementary polytopes with high lift-and-project ranks for strong positive semidefinite operators, A note on the Lasserre hierarchy for different formulations of the maximum independent set problem, A spatial branch-and-cut method for nonconvex QCQP with bounded complex variables, The archievable region method in the optimal control of queueing systems; formulations, bounds and policies, Dynamic intersection of multiple implicit Dantzig-Wolfe decompositions applied to the adjacent only quadratic minimum spanning tree problem, A ``joint + marginal heuristic for 0/1 programs, Integrality gaps for colorful matchings, Dynamic Lagrangian dual and reduced RLT constructs for solving \(0-1\) mixed-integer programs, Sum-of-squares hierarchy lower bounds for symmetric formulations, Outer-product-free sets for polynomial optimization and oracle-based cuts, A computational study of exact subgraph based SDP bounds for max-cut, stable set and coloring, Separation and relaxation for cones of quadratic forms, Rank complexity gap for Lovász-Schrijver and Sherali-Adams proof systems, The symmetric quadratic traveling salesman problem, The Steiner connectivity problem, Unbounded convex sets for non-convex mixed-integer quadratic programming, Minimal arc-sets spanning dicycles, Elliptic approximations of propositional formulae, Semidefinite programming relaxations for the graph partitioning problem, A compact variant of the QCR method for quadratically constrained quadratic \(0-1\) programs, Complexity and nonlinear semidefinite programming reformulation of \(\ell_1\)-constrained nonconvex quadratic optimization, On the facets of lift-and-project relaxations under graph operations, Some advances on Lovász-Schrijver semidefinite programming relaxations of the fractional stable set polytope, Facets from gadgets, Chromatic Gallai identities operating on Lovász number, A note on representations of linear inequalities in non-convex mixed-integer quadratic programs, Bi-criteria and approximation algorithms for restricted matchings, Enhancing semidefinite relaxation for quadratically constrained quadratic programming via penalty methods, 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, 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, Constrained 0-1 quadratic programming: basic approaches and extensions, Lift \& project systems performing on the partial-vertex-cover polytope, Two new reformulation convexification based hierarchies for 0-1 MIPs, Branch-and-bound algorithms: a survey of recent advances in searching, branching, and pruning, On the Lovász theta function and some variants, General cut-generating procedures for the stable set polytope, A linear complementarity based characterization of the weighted independence number and the independent domination number in graphs, Integer programming approach to static monopolies in graphs, Design and verify: a new scheme for generating cutting-planes, Convex hull representation of the deterministic bipartite network interdiction problem, A new lift-and-project operator, A finite branch-and-bound algorithm for nonconvex quadratic programming via semidefinite relaxations, Geometric proofs for convex hull defining formulations, Lift-and-project ranks of the set covering polytope of circulant matrices, A computational study on the quadratic knapsack problem with multiple constraints, Reoptimization in Lagrangian methods for the \(0\)-\(1\) quadratic knapsack problem, Globally solving nonconvex quadratic programming problems via completely positive programming, A semidefinite programming heuristic for quadratic programming problems with complementarity constraints, A new algorithm for concave quadratic programming, Exploring the relationship between max-cut and stable set relaxations, Decomposition with branch-and-cut approaches for two-stage stochastic mixed-integer programming, Partial convexification cuts for 0--1 mixed-integer programs, On the gap between the quadratic integer programming problem and its semidefinite relaxation, An improved semidefinite programming relaxation for the satisfiability problem, Semidefinite programming lower bounds and branch-and-bound algorithms for the quadratic minimum spanning tree problem, Several notes on the power of Gomory-Chvátal cuts, Penalized semidefinite programming for quadratically-constrained quadratic optimization, On the commutativity of antiblocker diagrams under lift-and-project operators, A survey on conic relaxations of optimal power flow problem, A strictly contractive Peaceman-Rachford splitting method for the doubly nonnegative relaxation of the minimum cut problem, On extracting maximum stable sets in perfect graphs using Lovász's theta function, A new approximation algorithm for unrelated parallel machine scheduling with release dates, An evaluation of semidefinite programming based approaches for discrete lot-sizing problems, Phase recovery, MaxCut and complex semidefinite programming, Sparse semidefinite programs with guaranteed near-linear time complexity via dualized clique tree conversion, Lift-and-project methods for set cover and knapsack, Semidefinite and linear programming integrality gaps for scheduling identical machines, Matroid optimization problems with monotone monomials in the objective, On the Lovász-Schrijver PSD-operator on graph classes defined by clique cutsets, Computing in combinatorial optimization, Cuts for mixed 0-1 conic programming, Set characterizations and convex extensions for geometric convex-hull proofs, On the finite convergence of successive SDP relaxation methods, Sherali-Adams relaxations of graph isomorphism polytopes, Polyhedra related to integer-convex polynomial systems, Computational experience with a bundle approach for semidefinite cutting plane relaxations of Max-Cut and equipartition, Approximate extended formulations, Approximate fixed-rank closures of covering problems, Sparse learning via Boolean relaxations, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs, Robust computation of linear models by convex relaxation, A new semidefinite relaxation for \(L_{1}\)-constrained quadratic, Between steps: intermediate relaxations between big-M and convex hull formulations, Lasserre integrality gaps for graph spanners and related problems, A note on the SDP relaxation of the minimum cut problem, Strong SDP based bounds on the cutwidth of a graph, An extended formulation for the 1‐wheel inequalities of the stable set polytope, Conic optimization: a survey with special focus on copositive optimization and binary quadratic problems, On polytopes with linear rank with respect to generalizations of the split closure, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, A knapsack intersection hierarchy, PCA Sparsified, Shortest Paths in Graphs of Convex Sets, Elementary closures for integer programs., Linear lower bound on degrees of Positivstellensatz calculus proofs for the parity, Complexity of Null- and Positivstellensatz proofs, Eigenvalue, quadratic programming, and semidefinite programming relaxations for a cut minimization problem, A characterization of the weighted Lovász number based on convex quadratic programming