A new separation algorithm for the Boolean quadric and cut polytopes

DOI10.1016/J.DISOPT.2014.07.002zbMath1308.90209DBLPjournals/disopt/LetchfordS14OpenAlexW2006798861WikidataQ57702137 ScholiaQ57702137MaRDI QIDQ2339832

Adam N. Letchford, Michael Malmros Sørensen

Publication date: 9 April 2015

Published in: Discrete Optimization (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.disopt.2014.07.002

zbMATH Keywords

branch-and-cutmax-cut problempolyhedral combinatoricszero-one quadratic programming

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20) Boolean programming (90C09)

Related Items (11)

The Boolean Quadric Polytope ⋮ Exact Facetial Odd-Cycle Separation for Maximum Cut and Binary Quadratic Optimization ⋮ Generalised 2-circulant inequalities for the max-cut problem ⋮ A note on the 2-circulant inequalities for the MAX-cut problem ⋮ The Bipartite Boolean Quadric Polytope with Multiple-Choice Constraints ⋮ Semidefinite Approaches for MIQCP: Convex Relaxations and Practical Methods ⋮ Dendrograms, minimum spanning trees and feature selection ⋮ Exact and heuristic algorithms for the weighted total domination problem ⋮ Volume computation for sparse Boolean quadric relaxations ⋮ Exact and heuristic algorithms for the maximum weighted submatrix coverage problem ⋮ Extended formulations for convex hulls of some bilinear functions

Uses Software

• Concorde
• Biq Mac
• BiqMac

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• A note on two problems in connexion with graphs
• Lifting and separation procedures for the cut polytope
• Enhancing RLT relaxations via a new class of semidefinite cuts
• Pseudo-Boolean optimization
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• Max-cut in circulant graphs
• Geometric algorithms and combinatorial optimization
• A polyhedral approach for nonconvex quadratic programming problems with box constraints
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Separating subdivision of bicycle wheel inequalities over cut polytopes
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• The cut polytope and the Boolean quadric polytope
• On a positive semidefinite relaxation of the cut polytope
• Fifty-Plus Years of Combinatorial Integer Programming
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• On the cut polytope
• Fibonacci heaps and their uses in improved network optimization algorithms
• Geometry of cuts and metrics
• On disjunctive cuts for combinatorial optimization

This page was built for publication: A new separation algorithm for the Boolean quadric and cut polytopes