A study of the quadratic semi-assignment polytope |
| |
Authors: | Hiroo Saito Tetsuya Fujie Tomomi Matsui Shiro Matuura |
| |
Institution: | 1. Graduate School of Information Science and Technology, University of Tokyo, Tokyo 113-8656, Japan;2. School of Business Administration, University of Hyogo, Kobe 651-2197, Japan |
| |
Abstract: | We study a polytope which arises from a mixed integer programming formulation of the quadratic semi-assignment problem. We introduce an isomorphic projection and transform the polytope to a tractable full-dimensional polytope. As a result, some basic polyhedral properties, such as the dimension, the affine hull, and the trivial facets, are obtained. Further, we present valid inequalities called cut- and clique-inequalities and give complete characterizations for them to be facet-defining. We also discuss a simultaneous lifting of the clique-type facets. Finally, we show an application of the quadratic semi-assignment problem to hub location problems with some computational experiences. |
| |
Keywords: | |
本文献已被 ScienceDirect 等数据库收录! |
|