A new separation algorithm for the Boolean quadric and cut polytopes

DOI10.1016/J.DISOPT.2014.07.002MaRDI QIDQ2339832zbMATH OpenOpenAlexDBLPWikidataFDO

Authors 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

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

Recommendations

• Separating subdivision of bicycle wheel inequalities over cut polytopes
• Lifting and separation procedures for the cut polytope
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• Separating clique tree and bipartition inequalities in polynomial time
• The cut polytope and the Boolean quadric polytope

Cites work

• \(\{ 0,\frac12\}\)-Chvátal-Gomory cuts
• A note on two problems in connexion with graphs
• A polyhedral approach for nonconvex quadratic programming problems with box constraints
• Chvátal Cuts and Odd Cycle Inequalities in Quadratic 0–1 Optimization
• Cut-Polytopes, Boolean Quadric Polytopes and Nonnegative Quadratic Pseudo-Boolean Functions
• Enhancing RLT relaxations via a new class of semidefinite cuts
• Experiments in quadratic 0-1 programming
• Fibonacci heaps and their uses in improved network optimization algorithms
• Fifty-plus years of combinatorial integer programming
• Geometric algorithms and combinatorial optimization
• Geometry of cuts and metrics
• scientific article; zbMATH DE number 3152649 (Why is no real title available?)
• scientific article; zbMATH DE number 1175943 (Why is no real title available?)
• scientific article; zbMATH DE number 1175944 (Why is no real title available?)
• Lifting and separation procedures for the cut polytope
• Max-cut in circulant graphs
• New facets and a branch-and-cut algorithm for the weighted clique problem.
• On a positive semidefinite relaxation of the cut polytope
• On disjunctive cuts for combinatorial optimization
• On the cut polytope
• Pseudo-Boolean optimization
• Separating subdivision of bicycle wheel inequalities over cut polytopes
• Solving quadratic (0,1)-problems by semidefinite programs and cutting planes
• Testing the Odd Bicycle Wheel Inequalities for the Bipartite Subgraph Polytope
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The cut polytope and the Boolean quadric polytope
• The edge-weighted clique problem: Valid inequalities, facets and polyhedral computations
• The traveling salesman problem. A computational study.

Cited in

(15)

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

Describes a project that uses

Uses Software

• Concorde
• Biq Mac
• BiqMac

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2339832)