A study of the quadratic semi-assignment polytope

DOI10.1016/J.DISOPT.2008.08.003zbMath1160.90586OpenAlexW2011828788MaRDI QIDQ1013294

Hiroo Saito, Tetsuya Fujie, Shiro Matuura, Tomomi Matsui

Publication date: 17 April 2009

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

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

zbMATH Keywords

polytopefacethub locationquadratic semi-assignment problem

Mathematics Subject Classification ID

Quadratic programming (90C20) Boolean programming (90C09)

Related Items (14)

The Boolean Quadric Polytope ⋮ The bipartite quadratic assignment problem and extensions ⋮ Algorithm for the discrete Weber's problem with an accuracy estimate ⋮ The Boolean quadratic programming problem with generalized upper bound constraints ⋮ Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems ⋮ Unbounded convex sets for non-convex mixed-integer quadratic programming ⋮ Approximation Algorithm for Cycle-Star Hub Network Design Problems and Cycle-Metric Labeling Problems ⋮ An exact algorithm for the minimum squared load assignment problem ⋮ Perspectives on modeling hub location problems ⋮ Quadratic assignment problem variants: a survey and an effective parallel memetic iterated tabu search ⋮ Approximation algorithms for the single allocation problem in hub-and-spoke networks and related metric labeling problems ⋮ Generalized network design polyhedra ⋮ Affine maps between quadratic assignment polytopes and subgraph isomorphism polytopes ⋮ Cutting planes for RLT relaxations of mixed 0-1 polynomial programs

Uses Software

• CPLEX
• OR-Library

Cites Work

• Unnamed Item
• Unnamed Item
• The indefinite zero-one quadratic problem
• Adapting polyhedral properties from facility to hub location problems
• A quadratic integer program for the location of interacting hub facilities
• The Boolean quadratic polytope: Some characteristics, facets and relatives
• Experiments in quadratic 0-1 programming
• A polynomially solvable class of quadratic semi-assignment problems
• Exact and heuristic algorithms for the uncapacitated multiple allocation \(p\)-hub median problem
• The partial constraint satisfaction problem: Facets and lifting theorems
• Lower bounds for the quadratic semi-assignment problem
• A branch and cut algorithm for hub location problems with single assignment
• An algorithm for the multiprocessor assignment problem
• The cut polytope and the Boolean quadric polytope
• A simultaneous lifting strategy for identifying new classes of facets for the Boolean quadric polytope
• On the SQAP-Polytope
• Projecting the flow variables for hub location problems
• Convex quadratic and semidefinite programming relaxations in scheduling
• Approximation algorithms for classification problems with pairwise relationships
• Allocating programs containing branches and loops within a multiple processor system
• A Tight Linearization and an Algorithm for Zero-One Quadratic Programming Problems
• Multiprocessor Scheduling with the Aid of Network Flow Algorithms
• The single allocation problem in the interacting three-hub network
• Geometry of cuts and metrics
• Best reduction of the quadratic semi-assignment problem
• The QAP-polytope and the star transformation
• Box-inequalities for quadratic assignment polytopes

This page was built for publication: A study of the quadratic semi-assignment polytope