A level-2 reformulation-linearization technique bound for the quadratic assignment problem
From MaRDI portal
Publication:872113
DOI10.1016/j.ejor.2006.03.051zbMath1121.90082OpenAlexW2165567889MaRDI QIDQ872113
Monique Guignard, Peter M. Hahn, William L. Hightower, Warren P. Adams
Publication date: 27 March 2007
Published in: European Journal of Operational Research (Search for Journal in Brave)
Full work available at URL: https://doi.org/10.1016/j.ejor.2006.03.051
combinatorial optimizationbranch and boundquadratic assignment problemassignmentreformulation-linearization technique
Polyhedral combinatorics, branch-and-bound, branch-and-cut (90C57) Combinatorial optimization (90C27) Discrete location and assignment (90B80)
Related Items
Taking advantage of symmetry in some quadratic assignment problems, Symmetry in RLT-type relaxations for the quadratic assignment and standard quadratic optimization problems, Mathematical modeling and efficient optimization methods for the distance-dependent rearrangement clustering problem, Lower bounding procedure for the asymmetric quadratic traveling salesman problem, The quadratic three-dimensional assignment problem: exact and approximate solution methods, A survey for the quadratic assignment problem, A New Semidefinite Programming Relaxation for the Quadratic Assignment Problem and Its Computational Perspectives, Lower bounds for the quadratic minimum spanning tree problem based on reduced cost computation, Fast simulated annealing for single-row equidistant facility layout, Strengthening a linear reformulation of the 0-1 cubic knapsack problem via variable reordering, Solving the quadratic assignment problem by means of general purpose mixed integer linear programming solvers, A Branch-and-Bound Algorithm for Team Formation on Social Networks, Strong RLT1 bounds from decomposable Lagrangean relaxation for some quadratic \(0-1\) optimization problems with linear constraints, DRL\(^*\): A hierarchy of strong block-decomposable linear relaxations for 0-1 mips, A new exact discrete linear reformulation of the quadratic assignment problem, The multi-story space assignment problem, Integrating combinatorial algorithms into a linear programming solver, Characterizing linearizable QAPs by the level-1 reformulation-linearization technique, Sinkhorn Algorithm for Lifted Assignment Problems, An LP-based characterization of solvable QAP instances with chess-board and graded structures, A Graphics Processing Unit Algorithm to Solve the Quadratic Assignment Problem Using Level-2 Reformulation-Linearization Technique, Level 2 Reformulation Linearization Technique–Based Parallel Algorithms for Solving Large Quadratic Assignment Problems on Graphics Processing Unit Clusters, Using symmetry to optimize over the Sherali-Adams relaxation, Exact solution of emerging quadratic assignment problems, Constrained 0-1 quadratic programming: basic approaches and extensions, An exact solution method for quadratic matching: the one-quadratic-term technique and generalisations, Mapping the convergence of genetic algorithms, A new lift-and-project operator, RLT insights into lift-and-project closures, Effective formulation reductions for the quadratic assignment problem, Algorithms for the generalized quadratic assignment problem combining Lagrangean decomposition and the reformulation-linearization technique, Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search, An algorithm for the generalized quadratic assignment problem, A mixed 0-1 linear programming formulation for the exact solution of the minimum linear arrangement problem, Semi-definite programming relaxation of quadratic assignment problems based on nonredundant matrix splitting, A linear formulation with \(O(n^2)\) variables for quadratic assignment problems with Manhattan distance matrices, Tightening concise linear reformulations of 0-1 cubic programs, A Level-3 Reformulation-Linearization Technique-Based Bound for the Quadratic Assignment Problem, The single-finger keyboard layout problem, $L_p$-norm Regularization Algorithms for Optimization Over Permutation Matrices, Concise RLT forms of binary programs: A computational study of the quadratic knapsack problem, Exact Solution of Two Location Problems via Branch-and-Bound, Linear programming insights into solvable cases of the quadratic assignment problem, A revised reformulation-linearization technique for the quadratic assignment problem, Cutting planes for RLT relaxations of mixed 0-1 polynomial programs
Uses Software
Cites Work
- Unnamed Item
- Unnamed Item
- Unnamed Item
- Unnamed Item
- QAPLIB-A quadratic assignment problem library
- A reformulation-linearization technique for solving discrete and continuous nonconvex problems
- A branch-and-bound algorithm for the quadratic assignment problem based on the Hungarian method
- A hierarchy of relaxations and convex hull characterizations for mixed- integer zero-one programming problems
- Solving large quadratic assignment problems on computational grids
- Lower Bounds for the Quadratic Assignment Problem Based upon a Dual Formulation
- Solving quadratic assignment problems using convex quadratic programming relaxations
- The Quadratic Assignment Problem
- A Hierarchy of Relaxations between the Continuous and Convex Hull Representations for Zero-One Programming Problems
- A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
- Computing Lower Bounds for the Quadratic Assignment Problem with an Interior Point Algorithm for Linear Programming
- Linearization Strategies for a Class of Zero-One Mixed Integer Programming Problems
- Optimal and Suboptimal Algorithms for the Quadratic Assignment Problem
- A new bound for the quadratic assignment problem based on convex quadratic programming
