A polyhedral characterization of linearizable quadratic combinatorial optimization problems

DOI10.1016/J.DAM.2025.06.035MaRDI QIDQ6930329zbMATH OpenFDO

Authors Lucas A. Waddell

Publication date 16 September 2025

Published in Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1016/J.DAM.2025.06.035

zbMATH Keywords

linearizablenonlinear combinatorial optimizationquadratic minimum spanning tree

Mathematics Subject Classification ID

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

Cites work

• A characterization of linearizable instances of the quadratic minimum spanning tree problem
• A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique
• A level-2 reformulation-linearization technique bound for the quadratic assignment problem
• A level-3 reformulation-linearization technique-based bound for the quadratic assignment problem
• A linear time algorithm for linearizing quadratic and higher-order shortest path problems
• A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
• A note on a polynomial time solvable case of the quadratic assignment problem
• A solvable case of the quadratic assignment problem
• An \(O(n^{4})\) algorithm for the QAP linearization problem
• An LP-based characterization of solvable QAP instances with chess-board and graded structures
• Another well-solvable case of the QAP: maximizing the job completion time variance
• Characterizing linearizable QAPs by the level-1 reformulation-linearization technique
• Combinatorial optimization. Theory and algorithms.
• scientific article; zbMATH DE number 35513 (Why is no real title available?)
• scientific article; zbMATH DE number 714527 (Why is no real title available?)
• scientific article; zbMATH DE number 2107836 (Why is no real title available?)
• Linear programming insights into solvable cases of the quadratic assignment problem
• Linearizable special cases of the QAP
• Linearizable special cases of the quadratic shortest path problem
• Lower bounds and exact algorithms for the quadratic minimum spanning tree problem
• Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
• Solving large quadratic assignment problems on computational grids
• Special cases of the quadratic shortest path problem
• The bilinear assignment problem: complexity and polynomially solvable special cases
• The quadratic assignment problem is easy for Robinsonian matrices with Toeplitz structure
• The quadratic assignment problem with a monotone anti-Monge and a symmetric Toeplitz matrix: Easy and hard cases
• The quadratic assignment problem. Theory and algorithms
• The quadratic minimum spanning tree problem and its variations
• The quadratic shortest path problem: complexity, approximability, and solution methods
• The Wiener maximum quadratic assignment problem
• Well-solvable cases of the QAP with block-structured matrices

This page was built for publication: A polyhedral characterization of linearizable quadratic combinatorial optimization problems

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