Speeding up IP-based algorithms for constrained quadratic 0-1 optimization

DOI10.1007/s10107-010-0377-3zbMath1198.90313OpenAlexW2073457547MaRDI QIDQ2638389

Christoph Buchheim, Frauke Liers, Marcus Oswald

Publication date: 16 September 2010

Published in: Mathematical Programming. Series A. Series B (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/s10107-010-0377-3

zbMATH Keywords

quadratic programmingcrossing minimizationquadratic knapsacklocal cutsmaximum-cut problemsimilar subgraphs

Mathematics Subject Classification ID

Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20) Combinatorial optimization (90C27)

Related Items

Reformulating the disjunctive cut generating linear program, Local cuts for mixed-integer programming, A computational study and survey of methods for the single-row facility layout problem, Combinatorial optimization with one quadratic term: spanning trees and forests, Target Cuts from Relaxed Decision Diagrams, An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations, Global Approaches for Facility Layout and VLSI Floorplanning

Uses Software

• QAPLIB

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Local cuts revisited
• Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
• QAPLIB - a quadratic assignment problem library
• A semidefinite programming approach to the quadratic knapsack problem
• The cut polytope and the Boolean quadric polytope
• Constrained 0-1 quadratic programming: basic approaches and extensions
• Exact Algorithms for the Quadratic Linear Ordering Problem
• Efficient Reduction of Polynomial Zero-One Optimization to the Quadratic Case
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• On the cut polytope
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
• Some Network Flow Problems Solved with Pseudo-Boolean Programming
• A Branch and Bound Algorithm for Max-Cut Based on Combining Semidefinite and Polyhedral Relaxations
• Geometry of cuts and metrics