线性整数规划分支定界法并行化研究.doc

线性整数规划分支定界法并行化研究 　　摘要：规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。分支定界算法是解决整数规划的一个重要方法，然而算法的效率却有待提高。该文先对分支定界法解决线性整数规划问题的步骤进行阐述，再通过使用matlab提供的并行化的支持来实现对于分支定界法的并行化，并将算法并行前和并行后的运行时间进行分析，来研究并行化对于算法效率的提高。 　　关键词：线性整数规划；分支定界；matlab；算法效率；并行化处理 　　中图分类号：O246 文献标识码：A 文章编号：1009-3044（2016）24-0028-03 　　Abstact： Variables （all or part） is limited to an integer， called integer programming. If the linear model， limited to an integer variable， is called linear integer programming. Branch and bound algorithm is an important method to solve integer programming. However， the efficiency of the algorithm needs to be improved. The paper elaborates the steps of solving linear integer programming problem by the method of branch and bound， then through then achieve branch and bound method for parallelization of algorithms in the use of parallelism supported by matlab. Analysis the running time of both before and after parallel to study the parallelization algorithms for efficiency. 　　Key words： linear integer programming； branch and bound； matlab； algorithm efficiency； parallel processing 　　1 分支定界法简介 　　在线性规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常常会遇到一些变量的解必须是整数。例如，变化量表示的是机器的台数，工作的人数或装货的车数等。为了满足整数解的需求，一般来说只要化整已经得到了的非整数解。但是事实上化整也不一定能得到可行解和最优解，因此需要有特定的方法来求解整数规划[1]。 　　上个世纪60年代LandDoig和Dakin等人提出了可以求解整数或者是混合整数线性规划问题的分支定界算法。 　　该算法的思想是把有约束条件的最优化问题所拥有的所有可行的解空间进行搜索。具体执行算法时，会不断地分割所有可行的解空间成为越来越小的子集，然后将每个分割出的子集里面的目标函数值计算一个下界或上界。在每次分支之后，对所有界限超过了已知的可行解的值的那些子集不再分支。这样就可以去掉许多的子集，因此缩小了搜索的范围。重复这一过程一直到找出可行解的值不大于任何子集界限的可行解的位置。所以这个算法一般可以求得最优解[1]。 　　要将分支定界算法由串行计算转换为并行计算，难点在于要解决对二叉树的每个左右分支都实施并行计算所面临的计算数据组织、通信处理问题[2]。 　　接下来以下例来阐述分支定界法解线性整数规划的步骤。 　　由此可知，分支定界就是根据现有解不断将问题化为子问题，并更新上下界，直到求得我们需要的答案的过程。 　　2 在matlab中并行化的实现 　　2.1 Matlab并行计算的基本概念 　　Matlab依赖以下两个工具来实现并行计算架构：Matlab并行计算工具箱和分布式程序。用户使用Matlab提供的并行计算工具可以更加专注于并行计算算法的设计，很大程度上减少了用户用于解决网络通信等问题上投入的工作和精力[3]。 　　Matlab并行计算可以分为两类问题：第一类是distributed任务，各个作业之间完全独立，不需要进行数据通信，各个作业可以异步执行；第二类是parallel任务，任务的各个作业之间需要进行数据通信，必须同步执行[4]。 　　进行并行计算时，工作单元有job、task、client、work