線性整數規(guī)劃分支定界法并行化研究

李平風　劉海峰

摘要：規(guī)劃中的變量（全部或部分）限制為整數，稱為整數規(guī)劃。若在線性模型中，變量限制為整數，則稱為整數線性規(guī)劃。分支定界算法是解決整數規(guī)劃的一個重要方法，然而算法的效率卻有待提高。該文先對分支定界法解決線性整數規(guī)劃問題的步驟進行闡述，再通過使用matlab提供的并行化的支持來實現(xiàn)對于分支定界法的并行化，并將算法并行前和并行后的運行時間進行分析，來研究并行化對于算法效率的提高。

關鍵詞：線性整數規(guī)劃；分支定界；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 分支定界法簡介

在線性規(guī)劃問題中，有些最優(yōu)解可能是分數或小數，但對于某些具體問題，常常會遇到一些變量的解必須是整數。例如，變化量表示的是機器的臺數，工作的人數或裝貨的車數等。為了滿足整數解的需求，一般來說只要化整已經得到了的非整數解。但是事實上化整也不一定能得到可行解和最優(yōu)解，因此需要有特定的方法來求解整數規(guī)劃[1]。

上個世紀60年代LandDoig和Dakin等人提出了可以求解整數或者是混合整數線性規(guī)劃問題的分支定界算法。

該算法的思想是把有約束條件的最優(yōu)化問題所擁有的所有可行的解空間進行搜索。具體執(zhí)行算法時，會不斷地分割所有可行的解空間成為越來越小的子集，然后將每個分割出的子集里面的目標函數值計算一個下界或上界。在每次分支之后，對所有界限超過了已知的可行解的值的那些子集不再分支。這樣就可以去掉許多的子集，因此縮小了搜索的范圍。重復這一過程一直到找出可行解的值不大于任何子集界限的可行解的位置。所以這個算法一般可以求得最優(yōu)解[1]。

要將分支定界算法由串行計算轉換為并行計算，難點在于要解決對二叉樹的每個左右分支都實施并行計算所面臨的計算數據組織、通信處理問題[2]。

接下來以下例來闡述分支定界法解線性整數規(guī)劃的步驟。

由此可知，分支定界就是根據現(xiàn)有解不斷將問題化為子問題，并更新上下界，直到求得我們需要的答案的過程。

2 在matlab中并行化的實現(xiàn)

2.1 Matlab并行計算的基本概念

Matlab依賴以下兩個工具來實現(xiàn)并行計算架構：Matlab并行計算工具箱和分布式程序。用戶使用Matlab提供的并行計算工具可以更加專注于并行計算算法的設計，很大程度上減少了用戶用于解決網絡通信等問題上投入的工作和精力[3]。

Matlab并行計算可以分為兩類問題：第一類是distributed任務，各個作業(yè)之間完全獨立，不需要進行數據通信，各個作業(yè)可以異步執(zhí)行；第二類是parallel任務，任務的各個作業(yè)之間需要進行數據通信，必須同步執(zhí)行[4]。

進行并行計算時，工作單元有job、task、client、worker。其中client相當于計算機的界面，負責完成幾乎所有的用戶交互操作；job負責管理worker和分配task，每一個job包含多個task，每個task都要通過job分配給worker執(zhí)行，并將執(zhí)行結果返回[5]。client、job、worker運行在同一臺或者是多臺網絡上的計算機上。

程序執(zhí)行時，task是Matlab處理待完成的并行計算的基本單元，每個任務都是由一個或者是多個task組成的。由用戶編寫并行程序來創(chuàng)建和劃分job和task來完成待解決的并行計算任務。

開發(fā)Matlab并行程序首先要采用串行方法運行程序；然后選擇合適的并行方法，采用Matlab并行結構或者創(chuàng)建通用的并行計算程序；之后再控制數據和任務分配；然后采用pmode調試并行功能；配置local，在本地多核計算機執(zhí)行并行任務[6]。

2.2 Matlab中的并行計算支持

為了支持并行計算，Matlab為開發(fā)者提供了許多的并行結構，這些結構中包括了Parfor循環(huán)結構，SPMD并行結構，分布式陣列，分布式數值處理算法和消息傳遞函數等。本文采用的是Parfor循環(huán)結構來實現(xiàn)分支定界法解線性規(guī)劃問題的并行化。

由for關鍵字表示的循環(huán)可以通過使用parfor關鍵字代替進行并行。Matlab執(zhí)行代碼過程中，如果循環(huán)體使用的是for關鍵字，則采用串行方式執(zhí)行；如果循環(huán)體使用的是parfor關鍵字，則采用并行方式執(zhí)行。

在使用parfor關鍵字代替for關鍵字并行執(zhí)行循環(huán)時，會將循環(huán)分為很多部分，每個部分交給不同的worker執(zhí)行。因此對于執(zhí)行效率來說，假設使用的worker的數量為n，循環(huán)次數為m，則m如果能被n整除的話，則將循環(huán)均勻劃分；如果不能被整除的話，則將循環(huán)非均勻劃分，其中某些worker會執(zhí)行較多的循環(huán)次數。

默認情況matlab啟動時只有一個進程，因此默認情況下執(zhí)行parfor關鍵字標志的循環(huán)時是串行執(zhí)行的。因此在執(zhí)行前必須先打開Matlab并行計算池。

Matlab并行計算池管理很多個worker，每個worker都可以執(zhí)行分配的并行計算任務，其對應的物理單元即處理器或處理器核。

Parfor循環(huán)將for循環(huán)分解為子循環(huán)，分解后得到的子循環(huán)由不同的處理單元處理，用此來減少整個循環(huán)執(zhí)行所需要的時間，提高計算效率。而在使用Parfor循環(huán)代替for循環(huán)之前一定要先使用matlabpool命令啟動所需要的處理單元，然后將循環(huán)體中的for關鍵字修改為parfor關鍵字，通過Matlab的程序解釋器將此循環(huán)交由matlabpool啟動的多個處理單元完成[7]。

3 用matlab實現(xiàn)分支定界法解線性規(guī)劃并行化

解決線性規(guī)劃問題時，分支定界法是一項相當重要的方法。因此，研究該算法的并行化對于提高解決線性規(guī)劃問題而言是特別有意義的。

在使用分支定界法時，最重要的就是分支和剪枝。并且耗時最長循環(huán)最多的地方也是這里，因此我們選擇將這一部分并行處理。

我們仍然用開頭所用的例子來進行測試，比較使用了并行和未并行的情況下計算出結果分別所使用的時間。

因為使用了matlab所提供的計算線性規(guī)劃的函數linprog，因此我們需要將求解最大值問題轉換為求解最小值問題。只需要將函數加負號就能解決，而且這并不影響我們的測試[8]。

用matlab提供的時間函數來記錄程序運行的時間，分別記錄開啟并行時和未開啟時分別的運行速度來進行比較。

測試使用的是一臺四核計算機，理論來說的話上可以將計算速度提高四倍，然而實際效果卻達不到這個效果。這是由于該算法對二叉樹的每個左右分支實施并行計算及并行計算數據組織、通信與處理時對算法運行效率影響較高，因此達不到理想效果。但是從測試結果來看，并行化后的程序的確大大提升了運行效率。

參考文獻：

[1] 孫小玲， 李端. 整數規(guī)劃新進展[J]. 運籌學學報， 2014， 18（1）： 40-65.

[2] Jack Dongarra.并行計算綜論[M]. 北京： 電子工業(yè)出版社， 2005

[3] 胡良劍， 孫曉君. Matlab 數學實驗[M]. 北京： 高等教育出版社， 2006.

[4] 陳國良. 并行算法實踐[M]. 北京： 高等教育出版社， 2004.

[5] 樓順天. Matlab程序設計語言[M]. 西安： 西安電子科技大學出版社， 1997.

[6] 陳國良. 并行算法實踐[M]. 北京： 高等教育出版社， 2004.

[7] 劉維. 實戰(zhàn)Matlab并行程序設計[M]. 北京： 北京航空航天大學出版社， 2012.

[8] 郭志軍. 分支定界算法的MATLAB實現(xiàn)[J]. 江西教育學院學報， 2007（28）： 5-7.