二次指派问题的Gilmore-Lawler界的改进(英文)  

Improved Gilmore-Lawler Bound for Quadratic Assignment Problems

作　　者：夏勇[1] 

机构地区：[1]中国科学院数学与系统科学研究院计算数学所

出　　处：《工程数学学报》2007年第3期401-413,共13页Chinese Journal of Engineering Mathematics

基　　金：This research is supposed by NNSFC (10231060).

摘　　要：二次指派问题是组合优化领域最大的挑战之一。下界技术在精确求解该类离散最小化问题中起关键性作用。本文中我们改进了二次指派问题的Gilmore-Lawler界并且得到了一些新的有前景的下界。我们还提出了一个实际效果很好的模糊下界,由此引入了一个公开问题:什么时候该模糊下界是真实下界。The quadratic assignment problem （QAP） is one of the great challenges in combinatorial optimization. Lower bounding techniques always play crucial roles in solving these discrete minimization problems, the Gilmore-Lawler bound （GLB） is a well-known lower bound for QAP. In this paper, we improve this canonical bounding technique and get several new promising bounds. We also establish a well-behaved fuzzy bound and we leave the problem where it is an exact lower bound open.

关 键 词：二次指派问题 下界 线性规划 LAGRANGIAN松弛 Lagrangian分解 

分 类 号：O221.4[理学—运筹学与控制论]