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

李平风　刘海峰

摘要：规划中的变量（全部或部分）限制为整数，称为整数规划。若在线性模型中，变量限制为整数，则称为整数线性规划。分支定界算法是解决整数规划的一个重要方法，然而算法的效率却有待提高。该文先对分支定界法解决线性整数规划问题的步骤进行阐述，再通过使用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、worker。其中client相当于计算机的界面，负责完成几乎所有的用户交互操作；job负责管理worker和分配task，每一个job包含多个task，每个task都要通过job分配给worker执行，并将执行结果返回[5]。client、job、worker运行在同一台或者是多台网络上的计算机上。

程序执行时，task是Matlab处理待完成的并行计算的基本单元，每个任务都是由一个或者是多个task组成的。由用户编写并行程序来创建和划分job和task来完成待解决的并行计算任务。

开发Matlab并行程序首先要采用串行方法运行程序；然后选择合适的并行方法，采用Matlab并行结构或者创建通用的并行计算程序；之后再控制数据和任务分配；然后采用pmode调试并行功能；配置local，在本地多核计算机执行并行任务[6]。

2.2 Matlab中的并行计算支持

为了支持并行计算，Matlab为开发者提供了许多的并行结构，这些结构中包括了Parfor循环结构，SPMD并行结构，分布式阵列，分布式数值处理算法和消息传递函数等。本文采用的是Parfor循环结构来实现分支定界法解线性规划问题的并行化。

由for关键字表示的循环可以通过使用parfor关键字代替进行并行。Matlab执行代码过程中，如果循环体使用的是for关键字，则采用串行方式执行；如果循环体使用的是parfor关键字，则采用并行方式执行。

在使用parfor关键字代替for关键字并行执行循环时，会将循环分为很多部分，每个部分交给不同的worker执行。因此对于执行效率来说，假设使用的worker的数量为n，循环次数为m，则m如果能被n整除的话，则将循环均匀划分；如果不能被整除的话，则将循环非均匀划分，其中某些worker会执行较多的循环次数。

默认情况matlab启动时只有一个进程，因此默认情况下执行parfor关键字标志的循环时是串行执行的。因此在执行前必须先打开Matlab并行计算池。

Matlab并行计算池管理很多个worker，每个worker都可以执行分配的并行计算任务，其对应的物理单元即处理器或处理器核。

Parfor循环将for循环分解为子循环，分解后得到的子循环由不同的处理单元处理，用此来减少整个循环执行所需要的时间，提高计算效率。而在使用Parfor循环代替for循环之前一定要先使用matlabpool命令启动所需要的处理单元，然后将循环体中的for关键字修改为parfor关键字，通过Matlab的程序解释器将此循环交由matlabpool启动的多个处理单元完成[7]。

3 用matlab实现分支定界法解线性规划并行化

解决线性规划问题时，分支定界法是一项相当重要的方法。因此，研究该算法的并行化对于提高解决线性规划问题而言是特别有意义的。

在使用分支定界法时，最重要的就是分支和剪枝。并且耗时最长循环最多的地方也是这里，因此我们选择将这一部分并行处理。

我们仍然用开头所用的例子来进行测试，比较使用了并行和未并行的情况下计算出结果分别所使用的时间。

因为使用了matlab所提供的计算线性规划的函数linprog，因此我们需要将求解最大值问题转换为求解最小值问题。只需要将函数加负号就能解决，而且这并不影响我们的测试[8]。

用matlab提供的时间函数来记录程序运行的时间，分别记录开启并行时和未开启时分别的运行速度来进行比较。

测试使用的是一台四核计算机，理论来说的话上可以将计算速度提高四倍，然而实际效果却达不到这个效果。这是由于该算法对二叉树的每个左右分支实施并行计算及并行计算数据组织、通信与处理时对算法运行效率影响较高，因此达不到理想效果。但是从测试结果来看，并行化后的程序的确大大提升了运行效率。

参考文献：

[1] 孙小玲， 李端. 整数规划新进展[J]. 运筹学学报， 2014， 18（1）： 40-65.

[2] Jack Dongarra.并行计算综论[M]. 北京： 电子工业出版社， 2005

[3] 胡良剑， 孙晓君. Matlab 数学实验[M]. 北京： 高等教育出版社， 2006.

[4] 陈国良. 并行算法实践[M]. 北京： 高等教育出版社， 2004.

[5] 楼顺天. Matlab程序设计语言[M]. 西安： 西安电子科技大学出版社， 1997.

[6] 陈国良. 并行算法实践[M]. 北京： 高等教育出版社， 2004.

[7] 刘维. 实战Matlab并行程序设计[M]. 北京： 北京航空航天大学出版社， 2012.

[8] 郭志军. 分支定界算法的MATLAB实现[J]. 江西教育学院学报， 2007（28）： 5-7.