A new separation algorithm for the Boolean quadric and cut polytopes

DOI10.1016/j.disopt.2014.07.002zbMath1308.90209OpenAlexW2006798861WikidataQ57702137 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

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