整数规划范文

引言：寻求写作上的突破？我们特意为您精选了4篇整数规划范文，希望这些范文能够成为您写作时的参考，帮助您的文章更加丰富和深入。

篇1

中图分类号：TP319 文献标识码：A 文章编号：1009-3044（2013）09-2122-03

1 Matlab语言线性规划函数linprog介绍

[x，fval，exitflag，output，lambda]=linprog（f，a，b，aeq，beq，lb，ub）.

在输入部分，f是目标函数，它以列向量形式出现；a、b分别是线性规划中不等式约束的技术系数矩阵和资源向量；aeq、beq分别是线性规划中的技术系数矩阵和资源向量；这其中如有缺省，则以[] 代替；lb是决策变量下界，ub是决策变量上界。在输出部分，x是线性规划最优解，fval是线性规划最优值；exitflag是输出标记，当exitflag=1时，表示线性规划有解，当exitflag=-1时，表示线性规划无解；output是指算法和迭代情况；lambda是指存储情况。当程序通过时，屏目上有一段文字：Optimization terminated successfully（最优化成功地结束），它表示程序通过。当程序中有问题时， 屏目上会用红字告知，在某行某列有什么性质的问题。这些都显示出Matlab语言的智能化的优势。下面举例说明Matlab语言线性规划函数的应用。

3 结束语

Matlab语言是由美国Marhwords公司于1984年正式推出，后集语言专家和各类技术专家的共同努力，版本逐次更新， 功能更为完善。该文采用的是2007年1月发行的Matlab 7.4版，跟原有的计算机语言相比，它具有简洁、直观和智能化的优势。作者所提算法较原有算法，具有简洁、快捷和直观的特点，值得推广。

参考文献：

[1] 张志涌.精通MATLAB 6.5版[M].北京：北京航空航天大学出版社，2003.3.

[2] 胡运权.运筹学教程[M].2版.北京：清华大学出版社，2003.

[3] 胡知能，徐玖平.运筹学——线性系统优化[M].北京：科学出版社，2003.

[4] 刁在筠，郑汉鼎，刘家壮，等.运筹学[M]. 2版.北京：高等教育出版社，2001.9.

[5] 吴良刚，徐选华，王坚强，等.运筹学[M].长沙：湖南人民出版社，2001.3.

篇2

中图分类号：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.

篇3

中图分类号：TU992.3 文献识别码：A 文章编号：1001-828X（2015）018-000-02

一、前言

建筑设备更新是建筑企业生产发展和技术进步的客观需求，对建筑企业的经济效益有着举足轻重的作用。所谓建筑设备更新是指对在技术上或经济上不宜继续使用的建筑设备，用新的设备更换或用先进的技术对原有设备进行局部改造。或者说是以结构先进、技术完善、效率高、耗能少的新设备，来代替物质上无法继续使用，或经济上不宜继续使用的陈旧设备。随着建筑行业的发展，如何合理有效的进行设备更新使建筑公司利益最大化，已成为建筑行业研究的一个重要课题。同时也吸引了大批学者对建筑设备更新进行研究，得到了许多好的研究成果，详见文献[1-4].

本文首先讨论在第一年年初购买设备，之后每年仅购买一台设备的情形，且不考虑设备的折旧与收益，建立建筑设备更新问题的简化模型，并结合假定数据，应用该模型借助Lingo对问题进行求解。其次，在此基础上，进而假设某企业在研究之初就有一台运行若干年的旧设备，通过对建筑企业盈余、设备的运行维护费用、设备更新的购置费用、变量的约束等方面分析，建立建筑设备更新的一般性模型。最后，分别针对具体数据，利用建立的模型，采用Lingo软件进行高效求解。

二、设备更新问题的整数模型

（一）设备更新问题的简化模型

1.模型的建立

（1）模型假设

1.第一年年初将购买p台设备。

2.每年能够购进q台设备，或者不购买。

3.旧设备的折旧费不予计算。

4.每台设备的运营维护成本仅与设备服役年限有关。

5.不考虑每台设备的运行收益。即，我们只考虑设备的购买与运营维护产生的费用，且使其最小的企业运作方案。

（2）问题分析

设第i年初购进设备的单价为ai（i=1，2，…，n），引入0-1变量xi（i=1，2，…，n）表示是否要购买设备。

从而在计划年限内设备的总购置费用为：。

企业成本支出的另一部分是，由设备服役当年产生的运营维护费用。首先，只要有设备在役运行，设备产生的维护费用是每年都要支出的，且计划年限内总维护费为每年产生的维护费用之和。而后，我们考虑一年内，第i年的设备维护费取决于设备的使用年限j（1≤j≤i ）。设bi（i=1，2，…，n）为设备使用时段（ j-1）～ j年的维护费用。下文中，为表述方便，把设备使用时段为（ j-1）～ j年统一记设备使用年限为 j年。表1给出的是每年可能产生的维护费用情况。

根据表1的分析，我们可以得知，第i 年产生的所有可能维护费用取决于年份i 的取值。而届时产生的实际维护费用取决于实际使用年限 j。从而引入0-1变量：

若j≤i 时，yij的值为0或1，其实际意义为，在第i年设备的运行时段为j年或不是j年，当在第i年设备的运行年限为j年时yij=1，否则yij=0。进而，得到计划年限内的总的运营维护费用为，同时，显然有。由于设备的运行年限应该在购进设备的年份以后，我们发现xi与yij之间存在着制约与守衡的关系。它们的关系可以表述为，当xi+1为0时，在第i+1年不购买新设备，此时，设备的运行年限应该为第i年的运行年限加1。当xi+1为1时，第i+1年设备的运行年限为1年。

把上面的逻辑关系，用数学表达式描述为：

综上，我们可以得到下面的规划模型：

2.模型的应用

下面，我们假定了某一建筑设备5年的运营费用的具体数据，为了简化计算假定p=1， q=1应用建立的整数规划模型，采用Lingo软件[8]进行编程求解。

表2 某一建筑设备5年的运营费用

购买时间（年） 第1年 第2年 第3年 第4年 第5年

设备单价（万元） 10 13 15 18 20

设备使用年限 0-1 1-2 2-3 3-4 4-5

维护费用（万元） 4 7 8 10 16

由于篇幅有限，这里不再赘述求解该问题的Lingo软件代码，只给出软件运行的结果以供参考，更多关于Lingo软件的详细的内容，可以参阅文献[8]。

研究期限内目标函数的最优解为55，即5年内的设备更新成本支出最小为55万元，目标函数的最优解在x1和x4等于1时取得，即在第一年与第三年年初购进新设备。

（二）设备更新问题的一般模型

在前述中，简化模型中的假设3、假设4与假设5都是为了引入我们要分析的问题和方便计算所设定的。这些假设的引入，会导致简化模型求解实际问题时，可能造成求解不精确的问题，即所求解不是最优结果。为了进一步改进所提及模型，我们将这些假设去掉，建立一般模型。

1.模型的建立

在去掉假设3、假设4与假设5的同时，将假设2修改为：在考虑的时段内，第一年初企业已经拥有了一台运行了m年的设备。通过对建筑企业盈余、设备的运行维护费用、设备更新的购置费用、变量的约束等方面分析，建立建筑设备更新的一般性模型。

（1）企业盈余

因为，每台设备为企业创造的收益，不仅与讨论的年份i有关，还与该设备在年初的役龄j有关。役龄，即设备投入生产，服役的年限。在简化模型中yij表示的是第i年末设备的役龄。在当前讨论的问题中，我们将yij的含义设定为：表示第i年运行的设备的役龄。当yij=1时，表示第i年运行的设备的役龄为j。进而，在第i年，j的取值范围是区间[0， m+i-1]。设dij表示第i年役龄为j的设备为企业创造的收益。则研究年限内企业总的收益为：。

（2）设备的运行维护费用

同（1），设备的运行维护费用不只是与设备当前运行的年份i有关，还与设备的出厂年份有关。我们把出厂年份等价的转换成设备役龄。设bij为第i年役龄为j的设备的运行维护费用，则研究年限内设备的总维护费用为：。

（3）设备的购置费

设cij为第i年初卖掉役龄为j的旧设备所得的折旧费。引入0-1变量zij，当zij=1时，表示第i年初旧设备的役龄为j，当zij=0时，第i年初旧设备的役龄不是j，表示。从而，对于第i年来说，j的取值范围区间为[1， m+i-1]。则研究的年限内设备总的购置费用为：，这里的ai和xi的含义与简化模型的一致。

（4）变量的约束

从上面的分析中我们得知，初始情形与yij的含义发生了变化，这直接导致模型中的对应约束条件也发生了相应的变化。直接反应为yij与xi的制约关系上，故把相邻两年设备的约束改为：

此外，由变量yij与zij的含义，它们的逻辑关系是，第i+1年的初设备的役龄为第i年在役设备的役龄加1，故：

通过上面的分析，我们可以得到建筑设备更新问题的一般性规划模型：

2.模型应用

现假设我们研究的年限为n=5，第一年初企业已经拥有一台役龄m=1的设备，由左表3给出其余各项参数

由Lingo求解的结果得知：目标函数取得最优解为43，即在研究期限内，该企业的最大收益为43万元。变量x的取值情况是：仅x2取1，即只在第二年初卖掉役龄为2的旧设备，购买新设备。

三、总结

本文建立建筑设备更新问题的非线性0-1规划模型，并针对具体的数据，应用优化建模软件Lingo高效求解技术，进行模型求解，得到了正确的结果。在建模过程中，阐述了建立静态规划模型的关键技术和具体方法。优化建模软件Lingo的高效求解，使得我们对研究的问题进行优化和延拓，这也正是本文创作的初衷。研究建筑设备更新问题，不论是采用动态规划模型，还是运用图论中的最短路问题，建模以后都要设计对应的算法，即逆序算法与Dijkstra算法，同时还必须用程序语言对算法进行描述，以实现问题的求解。本文建立的模型缺点有两方面，其一是模型应用后，求解的结果是预测性的。这是由于研究期限内的各项数据都是假定的，必然导致计算的结果与实际有一定程度的偏差；其二是我们在研究问题时，为了简化计算，计算的前提都是一台设备，必须指出的是，把这个模型推广到多台设备或多种决策的情况，并不是一件困难的事。

参考文献：

[1]李天民.设备更新问题的动态规划解法[J].系统工程，1987，5（3）：52-59.

篇4

中图分类号: TP301.6

文献标志码:A

Effective branch algorithm for integer linear programming problems

GAO Pei-wang

(

Department of Mathematics and Statistics, Guangxi University of Finance and Economics, Nanning Guangxi 530003, China

)

Abstract:

In order to improve the computational efficiency, a branch algorithm for general integer linear programming problems on the objective function hyperplane shifts was presented. First, for a given integer value of the objective function, the lower and upper bounds of the variables are determined by the optimum simplex tableau of the linear programming relaxation problem. Then the conditions on the bounds are added to the constraints as cuts to the associated objective function hyperplane. Finally, a branch procedure of the branch-and-bound algorithm is applied to finding a feasible solution on the objective function hyperplane. The computational test on some classical numerical examples shows that, compared with the classical branch-and-bound principle, the algorithm greatly decreases the number of branches and the number of iterations in computation, and therefore, is of practical interest.

In order to improve the computational efficiency, a branch algorithm for general integer linear programming problems on the objective function hyperplane shifts was presented. First, for a given integer value of the objective function, the lower and upper bounds of the variables were determined by the optimum simplex tableau of the linear programming relaxation problem. Then the conditions on the bounds were added to the constraints as cuts to the associated objective function hyperplane. Finally, a branch procedure of the branch-and-bound algorithm was applied to finding a feasible solution on the objective function hyperplane. The computational test on some classical numerical examples shows that, compared with the classical branch-and-bound principle, the algorithm greatly decreases the number of branches and the number of iterations in computation, and therefore, is of practical value.

Key words:

linear programming; integer programming; objective function hyperplane; simplex method; branch algorithm

0 引言

整数线性规划(Integer Linear Programming,ILP)在电子、控制和决策等许多领域中有着广泛的应用[1-3]。然而,整数线性规划问题是NP-难的,因此,找到一种高效且方便的算法对于整数线性规划的应用是非常有意义的。

经典的割平面法和分支定界法是最早用于求解整数线性规划问题的数值算法,这两种方法需要求解一系列由切割或分支产生的线性规划子问题。于是,探寻更好的切割和分支技术,以减少所求解的线性规划子问题数量,提高计算效率,成为了整数规划研究的一个重点和热点。在许多研究者持续不断的努力下,已经产生了一些深切割技术[4-5]和新的分支准则[6-7]等重要成果。

另一方面,整数线性规划的最优解常常位于整数值目标函数超平面上。注意到这一点,人们把目标函数作为一个参数,令其从线性规划松弛问题的最优值处离散变化,然后提出了一些直接或隐数算法[8-9]用于在目标函数超平面上搜寻求解。然而,这些方法在计算凸多面体的极顶点时也许需要非常复杂的枢轴计算。

本文把上述两种思想结合起来,提出了目标函数超平面上的分支算法。在这个算法中,对于给定的目标函数整数值,首先利用线性规划松弛问题的最优单纯形表确定变量的上、下界,然后将变量的上、下界条件加入约束条件中对相应的目标函数超平面进行切割,最后应用分支定界算法中的分支方法来搜寻目标函数超平面上的可行解。如果目标函数超平面上不存在可行解,则目标函数超平面移动一个单位,继续上述计算过程。应用该算法求解计算了一些经典的数值例子并与经典的分支定界算法进行了比较,结果表明,该算法的计算效率比经典的分支定界算法要高得多。

1 目标函数超平面上变量上、下界的确定

考虑如下形式的整数线性规划问题:

max f=cTx

s.t. Ax≤b

x≥0,x∈Z

这里,A=(aij)是一个m×n阶的整数矩阵,b,c是相应维数的整数列向量。与ILP相应的线性规划松弛问题,本文用RILP表示。

假设通过应用单纯形算法[10],获得了RILP的一个基本最优解:xB*=b*, xN*=0,相应的最优值为f*,这里,xB*和xN*分别是最优基变量和非基变量。令N*表示与非基变量对应的缩减费用,则目标函数和约束条件可表示为:

(ILP)f=f*-TN*xN* (1)

xB* = b*-B*-1N*xN* (2)

xB*≥0, xN*≥0(3)

其中,B*和N*分别是最优基矩阵和非基矩阵。

如果RILP的基本最优解是整数向量,则它也是ILP的最优解,否则,ILP的最优值肯定小于或等于f*。为此,令目标函数f作为一个参数从最优值f*处向下变化来生成一系列目标函数超平面,用Sf表示。显然,如果ILP有可行解的话,其可行解常位于整数值目标函数超平面上。本算法就是令参数f从大到小取满足f≤[f*](这里,[•]表示取小于或等于变量的最大整数)的离散整数值,然后依次在相应的目标函数超平面上搜寻求解。按照这种方式,一旦在某个目标函数超平面Sf中找到ILP的一个可行解,它也是ILP的一个最优解,算法终止。

接下来,对给定的f的整数值,可以确定变量xB*i(i=1,…,m)在相应的目标函数超平面Sf上取值的一个上、下界,分别用xIUB*i(f)和xILB*i(f)表示。

┑4期 吲嗤:整数线性规划问题的一种高效的分支算法

┆扑慊应用 ┑30卷

定理1 对给定的f的整数值,令Δf=f*-f,令αij表示矩阵-B*-1N*的第i行、第j列元素,对任意i∈{1,…,m},取pLi=┆min1≤j≤n{αijN*j|N*j>0},pUi=┆max1≤j≤n{αijN*j|N*j>0},如果对所有j=1,…,n,有N*j>0或N*j=0但αij

xIUB*i(f)=[b*i+pUiΔf] (4)

如果对所有j=1,…,n,有N*j>0或N*j=0但αij>0,则变量xB*i(i=1,…,m)有一个下界估计:

xILB*i(f)=〈max(b*i+pLiΔf,0)〉(5)

这里,〈•〉表示大于或等于•的最小整数。

证明 对给定的f的整数值和任意i∈{1,…,m},将式(1)×(-pUi)+式(2)的第i个等式条件,有:

xB*i-pUiΔf=b*i+∑nj=1(αij-pUiN*j)xN*j(6)

注意到pUi=┆max1≤j≤n{αijN*j|N*j>0},对任意j∈{1,…,n},当N*j>0时,应有pUi≥αijN*j,即有αij-pUiN*j≤0;当N*j=0但αij>0时,αij-pUiN*j≤0显然成立。因此,如果对所有j=1,…,n,有N*j>0或N*j=0但αij

xB*i≤b*i+pUiΔf

注意到xB*i在ILP的可行解中取整数值,由上式即得变量xB*i的上界表达式(4)。 类似地,可以证明变量xB*i的下界表达式(5)。证毕。

如果某个变量xB*i不存在式(4)所表示的上界估计,则置xIUB*i(f)=+∞;若变量xB*i不存在式(5)所表示的下界估计,则置xILB*i(f)=0。如果变量xB*i存在式(4)所表示的上界估计或式(5)所表示的下界估计,将其加入ILP的约束条件中相当于对相应的目标函数超平面进行“切割”,这种切割有助于提高下一节将引入的在目标函数超平面上分支算法的效率。

2 目标函数超平面上的分支算法

给定f满足f≤[f*]的一个固定整数值,如果对某个i∈{1,…,m},存在xILB*i(f)>xIUB*i(f),根据数论性质,则相应的目标函数超平面Sf上不存在ILP的可行解,目标函数超平面应下移一个单位;否则,如果xIUB*i(f)0,加入变量的下界限制xB*i≥xILB*i(f),构造在相应的目标函数超平面上搜寻求解的整数线性规划问题如下:

(ILP-f) max cTx

s.t. Ax≤b

cTx≤f

xB*i≤xIUB*i(f),满足:xIUB*i(f)

xB*i≥xILB*i(f),满足:xILB*i(f)>0,i=1,…,m

x≥0,x∈Z

显然,如果在Sf上存在ILP的可行解,它肯定是(ILP-f)的一个最优解。接下来,应用分支定界算法中的分支方法来搜寻在Sf上的可行解。为了使搜寻求解过程在有限次分支后完成,本文假定RILP的可行域与Sf的截(交)集是有限的。

在Sf上进行分支求解的基本思想是:求(ILP-f)对应的松弛问题,如果该根问题无解或存在目标值小于f的最优解,则将目标函数超平面下移一个单位,重复上述过程。否则,如果该根问题存在目标值等于f的最优整数解,在目标函数超平面上的搜寻求解结束;如果该根问题存在目标值等于f的最优非整数解,则选择一个取非整数值的变量进行分支产生两个子问题。求解一个子问题,若该子问题无解或存在目标值小于f的最优解,则剪掉该分支;否则,如果该子问题存在目标值等于f的最优整数解,在目标函数超平面上的搜寻求解结束;如果该子问题存在目标值等于f的最优非整数解,则选择一个取非整数值的变量继续分支。当所有分支都被剪掉时,在目标函数超平面上的搜寻求解结束。

根据上述算法理论,给出相应的算法步骤如下:

步骤1 求解RILP得到一个基本最优解xB*=b*, xN*=0和相应的最优目标值f*后,转下一步。

步骤2 如果xB*=b*是整数向量,算法输出ILP的一个最优解后终止;否则,给定一个适当小的整数M(满足M

步骤3 检查f

步骤4 如果对某个i∈{1,…,m},有xILB*i(f)>xIUB*i(f),则赋值f-1给f,然后返回步骤3;否则,转下一步。

步骤5 求解(ILP-f)对应的线性规划松弛问题,如果该根问题无解或存在目标值小于f的最优解,则赋值f-1给f,然后返回步骤3);否则,转下一步。

步骤6 检查该子(根)问题的最优解是否是目标值等于f的整数解:如果是,则已经获得ILP的一个最优解,算法结束;否则,转下一步。

步骤7 选择最优解中取非整数值的一个变量xj=j,将其分为两支:xj≤[j]和xj≥[j]+1,生成两个相应的子问题后转下一步。

步骤8 选择一个子问题进行求解计算。如果该子问题无解或存在目标值小于f的最优解,则剪掉该分支,然后转步骤9;否则,返回步骤6。

步骤9 检查是否还有尚未求解的子问题。如果存在尚未求解的子问题,则返回步骤8;否则,赋值f-1给f,然后返回步骤3。

通过执行上述算法步骤,我们或者获得ILP的一个最优解,或者当目标值下降到M时得到一个没有可行解的事实。这里,在min{cTx|Ax≤b,x≥0}有最优解的情形,令f┆min是它的最优值或一个估值,取M=[f┆min];否则,根据计算时间的限制给M一个适当小的整数来终止分支搜寻过程。

3 数值计算

通过下面的例子来详细说明本算法的计算过程。

例1 所考虑的问题:

(ILP) max -x3

s.t. -5x1-8x2+7x3≤89

6x1-5x2-x3≤-11

-3x1+5x2-2x3≤-29

x1,x2,x3≥0,x∈Z

引入松弛变量xj≥0(j=4,5,6),然后用对偶单纯形法求解相应的线性规划松弛问题,获得:

x1=1.344+0.167x4+0.211x5+0.478x6

x2=0.878+0.167x4+0.344x5+0.411x6

x3=14.678+0.167x4+0.544x5+0.811x6

显然,RILP的最优解:x1=1.344,x2=0.878,x3=14.678是非整数的,相应的目标最优值为f*=-14.678。接下来,对满足f≤-15的整数目标值f,确定变量在相应的目标函数超平面上取值的上、下界:

xIU1(f)=[1.344+Δf]xIL1(f)=〈max(1.344+0.3878Δf,0)〉

xIU2(f)=[0.878+Δf]xIL2(f)=〈max(0.878+0.5068Δf,0)〉

xIU3(f)=[14.678+Δf]xIL3(f)=〈max(14.678+Δf,0)〉

这里,Δf=f*-f

取f=-15,有:xIU1(f)=1

再置f为f-1=-16,有:xIU1(f)=2≥xIL1(f)=2,xIU2(f)=2≥xIL2(f)=2,xIU3(f)=2≥xIL3(f)=16。此时,应用分支算法求解相应的问题(ILP-f),(ILP-f)对应的松弛根问题无解。因此,目标函数超平面:-x3=-16上没有ILP的可行解。

类似地,由于与f=-17对应的(ILP-f)的松弛根问题无解,故相应的目标函数超平面上也没有ILP的可行解。

当f下降到-18时,有:xIU1(f)=4≥xIL1(f)=3,xIU2(f)=4≥xIL2(f)=3,xIU3(f)=18≥xIL3(f)=18。此时,求解相应的(ILP-f)的松弛根问题,得到目标函数超平面上的一个解:x1=(3.666B7,3.000B0,18.000B0)。将变量x1的取值分支为x1≤3和x1≥4,求解分支x1≤3对应的子问题,得到目标函数超平面上的一个解:x2=(3,3,18)。至此,我们获得了目标函数超平面:-x3=-18上的一个可行解:

x1=3, x2=3, x3=18

它也是ILP的一个最优解,算法结束。

本文提出的算法仅仅求解了5个子(根)问题,执行了30次枢轴计算,就获得了原问题的解。而经典的分支定界算法需要求解13个子(根)问题,执行62次枢轴计算,才能获得原问题的解。

整数线性规划问题是一个NP-难问题,其计算复杂度难以评估。为了进一步验证本算法的计算效率并与经典的分支定界算法进行比较,我们使用Matlab 6.5对两种算法进行了编程并在HΛSEE S262C计算机上求解计算了由文献[11]在第7章提供的9个典型算例。

选择了所求解的线性规划子(根)问题数(用Lp num.表示),所需要的枢轴(迭代)数(用Iters表示)和所花费的计算时间(用Time表示)作为比较两种算法计算效率的主要指标,计算结果如表1所示。

表格(有表名)

表1 本算法与经典的分支定界算法的比较

算例经典的分支定界算法

Lp num Iters Time/s

本文提出的算法

Lp num Iters Time/s

135120 0.359250.031

237159 0.468 630 0.109

3111 604 1.843 423 0.110

447463 1.375 41 4451.282

5201 600 2.4851013971.375

6203 708 2.797240.578

7203 708 2.797240.578

883773 2.766315 0.094

9***80316B11351.937

表1中*表示该问题使用经典的分支定界算法在求解了3B000个子问题后仍未找到最优解。

从表1可以看到,与经典的分支定界算法相比,本文提出的算法使用了少得多的单纯形迭代和计算时间,求解了更少的线性规划子(根)问题,其计算效率高于经典的分支定界算法。

4 结语

本文提出的算法改进了经典的分支定界算法的计算效率,尤其是当ILP的最优值远离RILP的最优值时,其优越性体现得更加明显。尽管在本算法中,目标函数超平面每次只移动一个单位,但大部分情况下,分支定界算法在每次连续分支时导致目标值的下降更加缓慢(远远不足一个单位)。如果在目标函数超平面上的分支效率更高,本算法将是有实用价值的,这已经得到了一些经典算例的部分验证。

在ILP中加入变量界的约束条件对提高在目标函数超平面上的分支效率是至关重要的。只要存在至少一个变量有比较好的上、下界估计,对目标函数超平面上的可行域进行有效切割,就能提高分支的效率,这从典型算例中得到了验证;如果所有变量的上、下界都无法估计,本算法就退化为文献[12]中提出的分支算法,其计算效率比经典的分支定界算法还要低。

需要指出的是,本文引入的变量界的约束也许对目标函数超平面上的可行域切割得很少,甚至不能产生有效切割。因此,若能获得更好的变量上、下界条件,对目标函数超平面上可行域的切割就会越深,这样,将会进一步改进目标函数超平面上分支算法的效率。

参考文献:

[1]GUPTA A, HAYES P. CLIP: Integer-programming-based optimal layout synthesis of 2D CMOS cells [J]. ACM Transactions on Design Automation of Electronic Systems, 2000, 5(3): 510-547.

[2]

MAHESHWARI N, SAPATNEKAR S. Retiming control logic integration [J]. The VLSI Journal, 1999, 28(1):33-53.

[3]LOTFI V. Implementing flexible automation: A multiple criteria decision making approach [J]. International Journal of Production Economics, 1995, 38(2):255-268.

[4]CERIA S, CORDIER C, MARCHAND H,et al.Cutting planes for integer programs with general integer variables[J]. Mathematical Programming, 1998, 81(2):201-214.

[5]ECKSTEIN J, NEDIAK M. Depth optimized convexity cuts [J]. Annals of Operations Research, 2005, 139(1): 95-129.

[6]ACHTERBERG T, KOCH T, MARTIN A. Branching rules revisited[J]. Operations Research Letters, 2005, 33(1):42-54.

[7]ELHEDHLI S, GOFFIN J L. The integration of an interior-point cutting plane method with a branch-and price algorithm[J]. Mathematical Programming, 2004, 100(2):267-294.

[8]JOSEPH A, GASS S I, BRYSON N A. An objective hyperplane search procedure for solving the general all-integer linear programming problem[J]. European Journal of Operational Research, 1998, 104(3):601-614.

[9]GAO PEIWANG. An efficient bound-and-stopped algorithm for integer linear programs on the objective function hyperplane [J]. Applied Mathematics and Computation, 2007, 185(1):301-311.