An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations

DOI10.1016/j.disopt.2015.10.002zbMath1387.90173OpenAlexW2320945305MaRDI QIDQ1751141

Frauke Liers, Lena Hupp, Laura Klein

Publication date: 24 May 2018

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

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

zbMATH Keywords

polyhedral combinatoricsbinary quadratic optimisation problemquadratic matching problemreformulation linearisation technique (RLT)

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Integer programming (90C10) Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Quadratic programming (90C20) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Discrete location and assignment (90B80) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (3)

Matroid optimisation problems with nested non-linear monomials in the objective function ⋮ Matroid optimization problems with monotone monomials in the objective ⋮ Complete Description of Matching Polytopes with One Linearized Quadratic Term for Bipartite Graphs

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Combinatorial optimization with one quadratic term: spanning trees and forests
• Corrigendum to our paper The ellipsoid method and its consequences in combinatorial optimization
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• Local cuts revisited
• Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
• Improved compact linearizations for the unconstrained quadratic 0-1 minimization problem
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• The ellipsoid method and its consequences in combinatorial optimization
• On the quadratic assignment problem
• An algorithm for the quadratic assignment problem using Benders' decomposition
• Location, scheduling, design and integer programming
• A semidefinite programming approach to the quadratic knapsack problem
• A recipe for semidefinite relaxation for \((0,1)\)-quadratic programming
• Minimizing submodular functions over families of sets
• Cutting planes for RLT relaxations of mixed 0-1 polynomial programs
• Comparisons and enhancement strategies for linearizing mixed 0-1 quadratic programs
• The symmetric quadratic traveling salesman problem
• Constrained 0-1 quadratic programming: basic approaches and extensions
• Speeding up IP-based algorithms for constrained quadratic 0-1 optimization
• The Quadratic Assignment Problem
• Assignment Problems and the Location of Economic Activities
• Odd Minimum Cut Sets and b-Matchings Revisited
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Odd Minimum Cut-Sets and b-Matchings
• Optimal Solution of Scheduling Problems Using Lagrange Multipliers: Part I
• Improved Linear Integer Programming Formulations of Nonlinear Integer Problems
• P-Complete Approximation Problems
• Technical Note—Converting the 0-1 Polynomial Programming Problem to a 0-1 Linear Program
• Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
• Maximum matching and a polyhedron with 0,1-vertices
• Duality in Nonlinear Programming: A Simplified Applications-Oriented Development
• Benchmarking optimization software with performance profiles.

This page was built for publication: An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations