摘要
二次指派问题是组合优化领域最大的挑战之一。下界技术在精确求解该类离散最小化问题中起关键性作用。本文中我们改进了二次指派问题的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.
出处
《工程数学学报》
CSCD
北大核心
2007年第3期401-413,共13页
Chinese Journal of Engineering Mathematics
基金
This research is supposed by NNSFC (10231060).
