The linearization problem of a binary quadratic problem and its applications
From MaRDI portal
Publication:2070726
DOI10.1007/s10479-021-04310-xzbMath1478.90072arXiv1802.02426OpenAlexW3200189330MaRDI QIDQ2070726
Publication date: 24 January 2022
Published in: Annals of Operations Research (Search for Journal in Brave)
Full work available at URL: https://arxiv.org/abs/1802.02426
quadratic assignment problemlinearization problemquadratic shortest path problembinary quadratic programgeneralized Gilmore-Lawler bound
Related Items
The quadratic cycle cover problem: special cases and efficient bounds, Linearizable special cases of the quadratic shortest path problem, A linear time algorithm for linearizing quadratic and higher-order shortest path problems, Characterizing linearizable QAPs by the level-1 reformulation-linearization technique
Cites Work
- Unnamed Item
- Unnamed Item
- Linearizable special cases of the QAP
- Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation
- Two classes of quadratic assignment problems that are solvable as linear assignment problems
- On the complexity of Putinar's Positivstellensatz
- Improving the performance of standard solvers for quadratic 0-1 programs by a tight convex reformulation: The QCR method
- On lower bounds for a class of quadratic 0,1 programs
- On the quadratic assignment problem
- A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method
- A linear time algorithm for the Koopmans-Beckmann QAP linearization and related problems
- The bilinear assignment problem: complexity and polynomially solvable special cases
- A characterization of linearizable instances of the quadratic minimum spanning tree problem
- Special cases of the quadratic shortest path problem
- New special cases of the quadratic assignment problem with diagonally structured coefficient matrices
- The quadratic shortest path problem: complexity, approximability, and solution methods
- Combinatorial optimization with interaction costs: complexity and solvable cases
- The quadratic cycle cover problem: special cases and efficient bounds
- Representations of quadratic combinatorial optimization problems: a case study using quadratic set covering and quadratic knapsack problems
- Linear programming insights into solvable cases of the quadratic assignment problem
- Global Optimization with Polynomials and the Problem of Moments
- Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
- The Quadratic Assignment Problem
- An O(n4) Algorithm for the QAP Linearization Problem
- Assignment Problems and the Location of Economic Activities
- On Solving the Quadratic Shortest Path Problem
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- A New Lower Bound for the Quadratic Assignment Problem
- A Mean-Variance Model for Route Guidance in Advanced Traveler Information Systems
- The Variance-Constrained Shortest Path Problem
- Quadratic Combinatorial Optimization Using Separable Underestimators
- Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
- Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem