位置：成果数据库 > 期刊 > 期刊详情页
二次指派问题的Gilmore-Lawler界的改进
  • ISSN号：1005-3085
  • 期刊名称：《工程数学学报》
  • 时间：0
  • 分类：O221.4[理学—运筹学与控制论;理学—数学]
  • 作者机构：[1]中国科学院数学与系统科学研究院计算数学所,北京100080, [2]中国科学院研究生院,北京100080
  • 相关基金：Foundation item： This research is supposed by NNSFC （10231060）.Acknowledgement The author thanks Prof. Ya-Xiang Yuan for his guidance and advice.
作者： 夏勇[1,2]
关键词： 二次指派问题, 下界, 线性规划, Lagrangian松弛, Lagrangian分解, quadratic assignment problem, lower bound, linear programming, Lagrangian relaxation, Lagrangian decomposition
中文摘要：

二次指派问题是组合优化领域最大的挑战之一。下界技术在精确求解该类离散最小化问题中起关键性作用。本文中我们改进了二次指派问题的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.

同期刊论文项目
大规模优化算法，理论以及应用
期刊论文 89 会议论文 12 著作 3
同项目期刊论文
Linear systems associated with
A nonmonotone second order ste
Convergence properties of mult
A 3-approximation algorithm fo
Nonmonotone adaptive trust reg
An adaptive trust-region metho
An excluding algorithm for tes
Solving non-additive traffic a
An outcome-space finite algori
Optimal preemptive online sche
Theoretical and numerical comp
A branch and bound algorithm f
A Feasible Direction Algorithm
股指期货定价方法研究
Mean-variance portfolio optima
On maximizing the throughput?
Non-monotone trust region meth
A truly globally convergent fe
A practical penalty trust-regi
Properties of Hadamard Product
Some results on resource const
Convergence of an inexact smoo
A multiple penalty function me
A new linearization method for
A Subspace implementation of
An adaptive approach of conic
Nonmonotone descent algorithm
On the quadratic convergence o
Duality and Lagrange multiplie
A new two level linear relaxed
Conic Trust region method for
Mixed duality without a constr
A new modified Goldstein-Levit
New decomposition methods for
一个求解大规模优化的有限内存方
关于非负不可约矩阵的广义Perron
A proximal decomposition algor
A trust region method for solv
On-line scheduling with extend
Computing a Celis-Dennis-Tapia
A new stepsize for the steepes
A Class of globally convergent
Adaptive nonmonotone trust reg
Alternate minimization gradien
An effective continuous algori
A nonmonotone line search algo
The application of log barrier
An optimal self-scaling strate
A nonsmooth trust region algor
A simpler proof on global conv
H-Matrices and S-Doubly Diagon
Proximal point algorithm for m
Analysis of monotone gradient
Optimality and mixed duality f
Maximizing the total profit of
Optimality and duality without
Convergence and regularity of
Feasible SQP Descent Method for Inequality Constrained Optimization Problems and Its Convergence
一个自动确定信赖域半径的信赖域方法
求解二次半定规划的原对偶内点算法
一种新的二次插值模型算法
T-型树T(1,l,m)可由其谱唯一决定
不动点与稳定点存在性关系及判定定理
带有线搜索的新的非单调自适应信赖域算法
A NEW SQP-FILTER METHOD PROGRAMMING FOR SOLVING NONLINEAR PROBLEMS
基于稀疏主成分的股票指数追踪研究
优化矿井通风系统方案的灰色关联模型
LC^1无约束优化问题的非单调线搜索算法
ON THE SEPARABLE NONLINEAR LEAST SQUARES PROBLEMS
COMPUTE A CELIS-DENNIS-TAPIA STEP
VaR模型及其在上海股市中的应用
复合非光滑优化的一种非单调线搜索方法
AN OPTIMAL SELF-SCALING STRATEGY TO THE MODIFIED SYMMETRIC RANK ONE UPDATING
DISTURBED SPARSE LINEAR EQUATIONS OVER THE 0-1 FINITE FIELD
A NEW STEPSIZE FOR THE STEEPEST DESCENT METHOD
T-型树谱唯一性的一个简单刻画
CONVERGENCE PROPERTIES OF MULTI-DIRECTIONAL PARALLEL ALGORITHMS FOR UNCONSTRAINED MINIMIZATION
A FEASIBLE DIRECTION ALGORITHM WITHOUT LINE SEARCH FOR SOLVING MAX-BISECTION PROBLEMS
A Switching Algorithm Based on Modified Quasi-Newton Equation
AN ADAPTIVE NONMONOTONIC TRUST REGION METHOD WITH CURVILINEAR SEARCHES
一个解无约束优化问题的过滤信赖域方法
A NONMONOTONE SECOND-ORDER STEPLENGTH METHOD FOR UNCONSTRAINED MINIMIZATION
AN EFFECTIVE CONTINUOUS ALGORITHM FOR APPROXIMATE SOLUTIONS OF LARGE SCALE MAX-CUT PROBLEMS
Nonmonotone Adaptive Trust Region Algorithms with Indefinite Dogleg Path for Unconstrained Minimization
期刊信息
  • 《工程数学学报》
  • 北大核心期刊（2011版）
  • 主管单位:教育部
  • 主办单位:西安交通大学
  • 主编：李大潜
  • 地址：西宁市咸宁西路28号西安交通大学数学与统计学院
  • 邮编：710049
  • 邮箱：jgsx@mail.xjtu.edu.cn
  • 电话：029-82667877
  • 国际标准刊号：ISSN：1005-3085
  • 国内统一刊号：ISSN：61-1269/O1
  • 邮发代号:
  • 获奖情况:
  • 《中文核心期刊要目总览》核心期刊,《中国科学引文数据库》核心期刊,《中国数学文摘》核心期刊,陕西省优秀科技期刊
  • 国内外数据库收录:
  • 俄罗斯文摘杂志,美国数学评论（网络版）,德国数学文摘,荷兰文摘与引文数据库,日本日本科学技术振兴机构数据库,中国中国科技核心期刊,中国北大核心期刊（2004版）,中国北大核心期刊（2008版）,中国北大核心期刊（2011版）,中国北大核心期刊（2014版）,中国北大核心期刊（2000版）
  • 被引量:6741