第24卷第3期2003年9月
军 事 通 信 技 术
JournalofMilitaryCommunicationsTechnology
Vol.24No.3Sep.2003
解整数线性规划问题的并行直接搜索算法
于战科1,倪明放2,陈建文3
(1.解放军理工大学通信工程学院研究生3队,江苏南京210007;
2.解放军理工大学通信工程学院电信工程系;3.总参谋部通信部网管中心,北京100840)
摘 要:文中提出一种求解整数线性规划问题并行直接搜索的算法。算法能获取一个较好的初始可行解,然
后用遗传算法构造l个搜索方向,沿着这些方向并行一维搜索,求出问题的最优解或近似最优解。算法简单,容易操作并能推广到求解大规模整数线性规划问题。计算实例表明算法是有效的。
关键词:整数线性规划;线性规划;并行搜索;遗传算法中图分类号:O221.2
文献标识码:A
文章编号:0032-1289(2003)03-0009-04
AParellelDirectSearchAlgorithmforSolvingInteger
LinearProgramming
123
YUZhan-ke,NIMing-fang,CHENJian-wen,
(1.PostgraduateTeam3ICE,PLAUST,Nanjing210007,China;2.DepartmentofTelecommunications.
EngineeringICE,PLAUST;3.GeneralStaffMinistryofCommunication,Beijing100840,China)
Abstract:Aparelleldirectsearchalgorithmforsolvingintegerlinearprogrammingispre-sentedinthispaper.Agoodinitialfeasiblesolutioncanbeobtained,thenldirectionsaremadebyusingGA.Anoptimalsolutionoranapproximationsolutioncanbeobtainedbyonedimensionsearchingalongthesedirections.Thealgorithmcanbeeasilyappliedtosolvinglargescaleintegerprogrammingproblems.Thecomputationexampleshowsthealgorithmiseffective.
Keywords:integerlinearprogramming;linearprogramming;parellelsearch;GA
整数线性规划问题是一类非常重要的优化问题,它属于NP完全(困难)问题,目前尚无有效的通用求解方法。由于整数线性规划问题在许多领域有着广泛的应用,如资源分配、网络设计、运输网络、证券组合、效能评估等等,整数线性规划理论和算法一直是人们关心的热点问题。目前关于它的求解方法大致有分支定界法、割平面法、分解方法、近似方法等[1~3]。本文提出一种求解整数线性规划问题并行直接搜索的方法,先求出一个初始可行解,用遗传算法构造l个搜索方向,并行搜索,求出最优解或近似最优解。
1 方法的描述
设整数线性规划问题的形式为
n
maxf(x)=s.tgi(x)=
∑
cjxj
ij
j=1
∑a
xj+bi≥0 i∈(1)
xj≥0,整数,j∈N
收稿日期:2003-03-01;修回日期:2003-03-31
:(),男,.
关于非线性规划问题的并行算法_理学_高等教育_教育专区。数学算法长江大学学报 (自科版) 2006 年 12 月第 3 卷第 4 期 理工卷 Journal of Yangtze University...
禁忌搜索算法应用于解整数线性规划问题 的实践 禁忌搜索算法应用于解整数线性规划问题的实践 福州教育学院 陈伟 〔 摘要〕 禁忌搜 索算法 的技 术 问题 预处理 ...
求解整数线性规划问题的一种新算法_专业资料。提出了一种求解整数线性规划问题的新方法。利用流动等值面技术的原单纯形方法,从初始整数可行解出发,逐步寻找下一个更...
优先搜索( 使搜索向着最可能 1 分支定界算法— — P 0 问题: 考虑如下 ILP...增刊 2 于战科等: 整数线性规划的改进分支定界算法 37 且若有最优解, 经过...
搜 试试 7 帮助 全部 DOC PPT TXT PDF XLS ...用模拟退火算法并行求解整数规划问题_理学_高等教育_...另外 ,注意到算法并未 用到 问题的“ 线性 ”这 ...
遗 传算法是一种全局搜索算法,简单、通用、鲁棒性...不要求连续,也不 要求可导,适用于并行分布处理,...解非线性规划问题的有效的算法, 年代又得到进一步的...
线性规划问题的算法综述_理学_高等教育_教育专区。综述...Np - hard问题 ,如 TSP 问题 ,整数规划问题 等...相对单纯形法来说 , 单纯形法最多能搜索与当前极 ...
混合整数非线性规划问题的改进差分进化算法_专业资料。提出一种改进差分进化算法...提高算法的搜索性能;提出一种自适应保留不可行解的方法处理约束条件,并对差分...
非线性规划问题的算法_数学_自然科学_专业资料。 一...直接搜索法 ?以梯度法为基础的间接法 ?无约束规划...一类非线性两级混合整数... 8页 免费 关于非线性...
问题 的最 优解 ()+ 2 16() 进行并行搜索 , 更利于全局最 优化解的搜索...遗传算法求解约束非线性... 5页 1下载券 非线性整数规划的遗传算... 7页 ...
热门文档