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

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