On the cut polytope

DOI10.1007/BF02592023zbMath0616.90058OpenAlexW2012605254MaRDI QIDQ4726054

Francisco Barahona, Ali Ridha Mahjoub

Publication date: 1986

Published in: Mathematical Programming (Search for Journal in Brave)

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

zbMATH Keywords

facet-defining inequalities cut polytope polyhedral combinatorics adjacency facets of polyhedra max cut problem

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Combinatorial optimization (90C27) Polytopes and polyhedra (52Bxx)

Related Items

The partition problem, A unified framework for obtaining improved approximation algorithms for maximum graph bisection problems, On the optimality of the random hyperplane rounding technique for MAX CUT, The Boolean Quadric Polytope, Normal binary graph models, Gorenstein cut polytopes, Speeding up IP-based algorithms for constrained quadratic 0-1 optimization, On random 2-adjacent 0/1-polyhedra, The equipartition polytope. I: Formulations, dimension and basic facets, The equipartition polytope. II: Valid inequalities and facets, LP and SDP branch-and-cut algorithms for the minimum graph bisection problem: a computational comparison, Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization, Necessary conditions for extended noncontextuality in general sets of random variables, Generalised 2-circulant inequalities for the max-cut problem, A note on the 2-circulant inequalities for the MAX-cut problem, Quantum Annealing versus Digital Computing, Trader multiflow and box-TDI systems in series-parallel graphs, The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints, On the bond polytope, A branch-and-cut algorithm for the connected max-\(k\)-cut problem, A Comparative Study of Linear and Semidefinite Branch-and-Cut Methods for Solving the Minimum Graph Bisection Problem, Binary Positive Semidefinite Matrices and Associated Integer Polytopes, The <scp>K‐partitioning</scp> problem: Formulations and <scp>branch‐and‐cut</scp>, Faster exact solution of sparse maxcut and QUBO problems, A new global algorithm for max-cut problem with chordal sparsity, A Hierarchy of Subgraph Projection-Based Semidefinite Relaxations for Some NP-Hard Graph Optimization Problems, Crossing Minimization in Storyline Visualization, A polyhedral study of lifted multicuts, Generalized cut polytopes for binary hierarchical models, Cycle algebras and polytopes of matroids, The st-bond polytope on series-parallel graphs, Optimal price zones of electricity markets: a mixed-integer multilevel model and global solution approaches, Lower and upper bounds for the linear arrangement problem on interval graphs, The Multilinear Polytope for Acyclic Hypergraphs, Generating facets for the cut polytope of a graph by triangular elimination, Facet-defining inequalities for the simple graph partitioning polytope, Transitive packing, Improving spectral bounds for clustering problems by Lagrangian relaxation, The cut cone. III: On the role of triangle facets, A Lagrangian relaxation approach to the edge-weighted clique problem, The QAP-polytope and the star transformation, Exploring the relationship between max-cut and stable set relaxations, The cut cone. III: On the role of triangle facets, Exact ground states of Ising spin glasses: new experimental results with a branch-and-cut algorithm, Max-multiflow/min-multicut for G+H series-parallel, DECOMPOSITION AND PARALLELIZATION TECHNIQUES FOR ENUMERATING THE FACETS OF COMBINATORIAL POLYTOPES, New quadratic models for the maximum weighted cut problem, A semidefinite programming based polyhedral cut and price approach for the maxcut problem, Semidefinite relaxations for partitioning, assignment and ordering problems, Computational Approaches to Max-Cut, Global Approaches for Facility Layout and VLSI Floorplanning, Semidefinite relaxations for partitioning, assignment and ordering problems, Spectral bounds for the maximum cut problem, From Graph Orientation to the Unweighted Maximum Cut, Sherali-adams strikes back, Enumeration of the facets of cut polytopes over some highly symmetric graphs, On fractional cut covers, A Cycle-Based Formulation and Valid Inequalities for DC Power Transmission Problems with Switching, Generalized network design polyhedra, Unnamed Item, A note on the Boolean quadric polytope, Complexity of the Positive Semidefinite Matrix Completion Problem with a Rank Constraint, Cuts for mixed 0-1 conic programming, Unnamed Item, A new separation algorithm for the Boolean quadric and cut polytopes, New approaches for optimizing over the semimetric polytope, Branch and Cut based on the volume algorithm: Steiner trees in graphs and Max-cut, Tight Cycle Relaxations for the Cut Polytope, On the diameter of cut polytopes, Mixed integer formulations using natural variables for single machine scheduling around a common due date, Globally solving nonconvex quadratic programming problems with box constraints via integer programming methods, Decomposition and optimization over cycles in binary matroids, On the magnetisation of the ground states in two dimensional Ising spin glasses, Application of cut polyhedra. I, Applications of cut polyhedra. II, The expected relative error of the polyhedral approximation of the max- cut problem, A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope, On a positive semidefinite relaxation of the cut polytope, Extremal positive semidefinite matrices whose sparsity pattern is given by graphs without \(K_{5}\) minors, Solving Max-cut to optimality by intersecting semidefinite and polyhedral relaxations, Mining for diamonds -- matrix generation algorithms for binary quadratically constrained quadratic problems, Facets of the \(k\)-partition polytope, Improved compact formulations for metric and cut polyhedra, An extended edge-representative formulation for the \(K\)-partitioning problem, Some new classes of facets for the equicut polytope, Solving the max-cut problem using eigenvalues, Stochastic graph partitioning: quadratic versus SOCP formulations, Polyhedral combinatorics of the \(K\)-partitioning problem with representative variables, Improved exact approaches for row layout problems with departments of equal length, A polynomial characterization of some graph partitioning problems, Semidefinite programming in combinatorial optimization, Cuts, matrix completions and graph rigidity, On decomposability of multilinear sets, Simple odd \(\beta \)-cycle inequalities for binary polynomial optimization, A computational study and survey of methods for the single-row facility layout problem, Cardinality constrained Boolean quadratic polytope, A branch-and-cut algorithm for the equicut problem, On the partial order polytope of a digraph, Hilbert bases of cuts, Graphic vertices of the metric polytope, Compressed polytopes and statistical disclosure limitation, The Boolean quadratic polytope: Some characteristics, facets and relatives, On cutting-plane proofs in combinatorial optimization, On a class of metrics related to graph layout problems, Generalized cut and metric polytopes of graphs and simplicial complexes, Experiments in quadratic 0-1 programming, Exploiting sparsity for the min \(k\)-partition problem, A connection between positive semidefinite and Euclidean distance matrix completion problems, One-third-integrality in the max-cut problem, A class of spectral bounds for max \(k\)-cut, Some thoughts on combinatorial optimisation, Small bipartite subgraph polytopes, Combinatorial and geometric properties of the max-cut and min-cut problems, Retracts and algebraic properties of cut algebras, On the polyhedral structure of uniform cut polytopes, Lifting and separation procedures for the cut polytope, Gap inequalities for non-convex mixed-integer quadratic programs, Computing the Grothendieck constant of some graph classes, New bounds for the \(\max\)-\(k\)-cut and chromatic number of a graph, Minimizing breaks by maximizing cuts., Cardinality constrained combinatorial optimization: complexity and polyhedra, Complexity results for the gap inequalities for the max-cut problem, A branch-and-cut algorithm based on semidefinite programming for the minimum \(k\)-partition problem, Cycle bases in graphs characterization, algorithms, complexity, and applications, Lifting facets of the cut polytope, Facets from gadgets, Using separation algorithms to generate mixed integer model reformulations, Binary positive semidefinite matrices and associated integer polytopes, The max-cut problem and quadratic 0-1 optimization; polyhedral aspects, relaxations and bounds, Seminormality, canonical modules, and regularity of cut polytopes, The real positive semidefinite completion problem for series-parallel graphs, Exploiting planarity in separation routines for the symmetric traveling salesman problem, Mixed-integer programming techniques for the connected max-\(k\)-cut problem, Local search inequalities, On the \(p\)-median polytope and the directed odd cycle inequalities: triangle-free oriented graphs, Improved compact formulations for a wide class of graph partitioning problems in sparse graphs, Projection results for the \(k\)-partition problem, On graphs of the cone decompositions for the min-cut and max-cut problems, Compositions in the bipartite subgraph polytope, Facets for the cut cone. I, Facets for the cut cone. II: Clique-web inequalities, The inequicut cone, The even and odd cut polytopes, Max-cut in circulant graphs, On cuts and matchings in planar graphs, From equipartition to uniform cut polytopes: extended polyhedral results, Normality of cut polytopes of graphs is a minor closed property, Optimal linear arrangements using betweenness variables, Pseudo-Boolean optimization, Global optimization of multilevel electricity market models including network design and graph partitioning, An exact approach to the problem of extracting an embedded network matrix, Linear size MIP formulation of max-cut: new properties, links with cycle inequalities and computational results, Efficient semidefinite branch-and-cut for MAP-MRF inference, An evolutionary heuristic for quadratic 0-1 programming, Cliques and clustering: A combinatorial approach, The CW-inequalities for vectors in \(\ell_ 1\), Formulations and valid inequalities of the node capacitated graph partitioning problem, The cut polytope and the Boolean quadric polytope, Role of redundant constraints for improving dual bounds in polynomial optimization problems, The node capacitated graph partitioning problem: A computational study, Extended formulations for convex hulls of some bilinear functions, Tight compact extended relaxations for nonconvex quadratic programming problems with box constraints, Separating subdivision of bicycle wheel inequalities over cut polytopes, On some weakly bipartite graphs, \(K_ i\)-covers. I: Complexity and polytopes, Min-cut clustering, A fast algorithm for minimum weight odd circuits and cuts in planar graphs, Collapsing and lifting for the cut cone

Cites Work