关键词：线性整数规划；分支定界；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.
很多人对于如何做好数据管理的规划以及战略调整感到困惑，笔者根据自己从业多年的经验，总结出自己的见解。
第一，明确目标愿景。信息管理最终要落实到数据管理，走好这一过程能够大大节省IT成本，提高管理效率。
信息系统是以数据说话的。往往信息化的过程就是数字化的过程，如何走好这一过程就要进行两头抓，即信息实践开始的一端信息应用系统的实施；信息成果收获即信息展示一端。即数据的收集、加工(挖掘)、展现。数据管理应当围绕这三阶段进行管理，而不是单单放在数据的备份、转移、恢复、复制、存储的方面。
信息有时效性，数据自然也有生命周期，要在信息时效性较强的时间，极快的组织数据，最大化发挥信息的作用。这就要求对数据的结构进行细化，能够在应用系统细化的基础上进行更大的细化与匹配。做到细节丰富，逻辑合理，结构清晰，以便于应用系统进行全面的展示。
规划应当自上而下的组织、应用系统目标的分解，也应自下而上的数据结构进行实现。既有全面的数据应用目标，又有细化的数据应用基础。全面、细化的程度则需要视成本、时间允许的情况下进行最大化的取舍，既依靠管理人员的经验，先进可靠的管理工具进行实现。做到重点突出，又不失细节实现。即要关注高楼的高度，功能性，又要关注最终实现的基础砖块的质量。
第二，提高数据战略管理，实现真正的战略调整。数据管理规划应当依符与企业的IT规划，与IT规划匹配越高，则IT成本越低，匹配程度往往决定于IT的应用程度。事实上一个好的IT应用，往往是数据匹配度是极其依靠(IT规划下的)IT应用进行匹配的。
再上一层说，企业的IT活动要依符于企业的战略规划，在战略规划下进行一个IT方面的规划，IT规划不同于企业的其他规划，在规划范围上受技术的限制较大，当然随之着技术的发展，这种限制变得越来越容易打破。但技术发展的迅速，却又带来了IT规划的难度。这就造成了规划的不确定性。这些都给IT规划带来了不同于常规的规划，当然数据管理也存在于这种不确定之中，而且更甚于这种规划。那就需要采用既满足目前应用目标，又能满足于以后变化的应用目标的产品，所以要选择符合企业实际的产品，又要解决企业未来(规划)问题的产品。
第三，设立安全级别，评估安全风险，实现在风险控制的基础上进行数据规划，保证重点数据，重点规划，重点管理。
数据管理的安全性，是数据管理的又一种大内容，首先针对不同的风险设立不同的规避方式，针对规避重点进行重点投入。
物理方面，对硬件设备进行双备、多备(硬盘、阵列、电源、网络)，保证解决硬件存储方面的设备故障，运行着的系统进行(集群、互备)保证对于应用服务设备出现的故障。备份系统，保证数据的可恢复性，可用性，容灾异地备份，保证自然、社会事件的备份等等各种方式的灵活应用。以保证实现数据的持继输出。保证数据的完整性，以及数据系统的可持续性。
整数规划是一类要求问题中的全部或一部分变量为整数的数学规划。如果所有变量都限制为整数，则称为纯整数规划；如果仅一部分变量限制为整数，则称为混合整数规划。在数学规划问题中，有些最优解可能是分数或小数，但对于某些具体问题，常要求结果必须是整数。本文采用整数规划的方法建立排课问题的数学模型，优化高等院校的排课。
1.排课问题描述
1.1 排课问题要素
从本校的实际情况来看，排课主要考虑时间、班级、课程、教室和教师这五个要素。对这些要素进行透彻的分析以及适当的预处理，是建立排课模型的基础。
（1）时间：排课问题中涉及的时间概念有学年、学期、周、天、时间段等。结合本校上课时间安排，只考虑按周来组织课表。每周5天教学日，每天10节课，分5个时间段，每2节课为一个时间段，每学期每周课表固定。
（2）课程：每门课程都有自己的编号、名称、学时和学分等要求，每门课程每周需要安排的学时体现为课程的学分，1学分的概念就是在每个教学周安排1个学时；周学时为奇数的课程，排课时的实际周学时，取为比该课程周学时数大的最小偶数。
（3）教室：每个教室要有自己的编号和类别名称（如普通教室、多媒体教室、微机室等）等，每个教室在同一时间只能上一门课，且满足教室的类型和教室的容量等要求。
（4）班级：每个班级要有自己的编号和名称，在同一时间一个班级只能上一门课程。
（5）教师：每个教师要有自己的工号和名称，在同一时间一个教师只能上一门课程。
1.2 排课问题约束条件
因为排课问题要满足多种约束条件，为了降低问题复杂度，可将排课的约束条件按照程度分为两大类：硬性约束和软性约束。前者是排课问题中必须遵循的原则，是衡量排课方案是否切实可行的标准，后者是排课过程中应当予以考虑，不一定必须满足，但如果满足可使排课结果更加合理，是衡量排课方案优劣的标准。
2.排课数学模型的建立
基于排课问题涉及的要素和约束条件建立如下排课问题的数学模型，主要对排课问题进行严格的数量关系描述。
2.1 模型参数
3.结论
虽然我们给出了排课问题的目标方程。但是，在不同的教学环境和不同的评价人的主观因素下，很难确定各个目标方程的权重。所以，对于课表优劣的衡量仍然是一个模糊的概念。基于以上的情况，我们不需要寻找问题的最优解，而应该寻找满足约束条件（F，C，L，R，T）的较优组合，从中选择一个作为较优课表。后续我们将进一步研究求解整数规划问题的算法，使排课达到最优组合。
参考文献
[1]鄂强金.基于混沌遗传算法的排课问题研究[硕士学位论文].哈尔滨工程大学，2009.
[2]A.S.Asratian.Investigation of some mathematical model of scheduling theory[D].Moscow University，1980.
[3]于艳东.基于遗传模拟退火算法的智能组卷系统研究[硕士学位论文].内蒙古大学，2011.
【 关键词 】 数据库架构；全局数据库；中心数据库；数据清洗；数据转换
The Overall Planning of University Data Integration
Du Wei
( Southwest University of Science and Technology Network Information Center SichuanMianyang 621010 )
【 Abstract 】 database integration is the cornerstone of University information, as the University information system and the rapid development of digital campus, university data integration approach can not meet its requirements. The following three models from the start database integration, itemized analysis of the advantages and disadvantages of each method, and data from which to seek consistent development model integrated university program.
【 Keywords 】 database structure;global database;center database;data cleaning;data conversion
目前很多高校的数据集成仍旧停留在“按需集成、自下而上”的单点工作模式。随着高校业务系统逐渐增加，系统间的数据关系也日趋多元化。如果仍然使用原有的构架对数据进行集成显然是不科学的，同时也无法满足信息化校园建设的需求。因此从整体上重新规划数据的集成构架，设计出符合高校信息化建设要求的数据集成环境，已成为当务之急。
1 高校数据库集成现状分析
1.1 架构分析
现行高校的业务系统，一般采用相互独立的业务系统，如：财务系统、人事系统都有其相对独立的数据系统。这种单一的存储方式虽然简化了各个部门的管理，提高了独立部门的工作效率，但是就整个校园的数据架构而言，数据之间并没有构成相互的连接通道，每个部门都是一个单独的信息源。换言之各个部门的数据形式存在方式为孤岛点。
另一方面，就实际的系统搭建环境而言，其环境可能在时间、存储格式、存储形式上也是不统一的。
1.2 工作环境关系分析
毕竟，学校是一个整体，每个部门之间存在着相互的工作关系，其数据是需要交互的。例如：财务系统需要从人事系统中提取新招聘教工的相关信息；教务系统需要从财务系统获取学生的缴费情况等。
目前很多高校都是从“需要到实现”，并没有从整个的工作环境去分析，只是单纯的从工作需要去进行被动的数据交互，其弊端所显现的杂、乱是显而易见的。
综上所述，如何对高校的数据库进行科学、合理的集成设计尤为重要。
2 数据库集成框架讨论
2.1 网状架构
网状架构是数据库集成的最初雏形，它是一个点对点的结构，在高校信息化建设的初期，各个部门的的业务系统刚刚使用，数据集成是一种自发的“按需集成”。
当某个部门需要某数据时才会进行数据的提取、交换、集成。方式多采用的是邮件传输、磁盘拷贝等方式。集成周期也不确定通常是“即用即采”。
数据集成在点对点架构中存在着：集成范围小、质量差、周期混乱、方式落后等弊端，从根本上就满足不了快速增长的高校信息化建设。
2.2 星形架构
所谓的星形架构就是每两个业务系统之间互有关联，从而形成一个大的星形结构。
在星形架构下，任意两点间需要数据交换、集成；
另一方面，操作方式，开始使用ETL（Extract、Transform、Load）等工具对数据进行抽取、转换、集成、清洗等工作，当然对异构的数据结构集成也做到了相应的加强。
这里要特别强调的是，星形结构使高校数据集成彻底了告别了“信息孤岛”。
但是星形结构下还是存在着以下问题：
虽然星形结构解决了单点问题，但是在可扩展性、抗干扰、数据统一、安全等方面还是存在着不足的地方。
试想如果在星形结构中添加一个中心节点，类似于在多个计算机之间加一个集线器以完成它们之间的通信。以上星形结构中所显现的问题是否可以解决呢？
2.3 中心节点结构
通过设计一个中心节点，使得星形结构成为辐射状。也就是说，在核心节点做一个数据的集成，使得各个系统对于其自身感兴趣的数据进行集成，其工作的具体流程如下：
(1)所有的业务系统按照统一的模型将自己的数据加载到中心节点；
(2)按照各个部门所感兴趣的数据，集成到各个业务系统中去。
中心节点的数据结构充分的解决了星形结构中的问题，是较为先进的一种数据集成方式。
以上我们分析了数据库集成的三种方式，从中找到了一种适合高校数据库集成的架构，下面我们对“中心节点”进一步的分析，使其更加符合高校的数据库集成环境。
首先我看下面这张图2，下图展示的是高校数据集成的一个模板图，可以在此基础上进行扩展、衍生。
名词解释：
* 业务系统数据库：业务系统数据库是高校中各个部门最基础数据的提供者、受益者。各个库把互相感兴趣的数据提交到中心数据库，已达到互相交换的目的。
* 全局数据库：全局数据库是面向综合应用的业务数据源.
* 数据仓库：主要功能是数据的统计、分析挖掘等数据存储。其基本数据来源是从数据集成平台提供数据，按照相应的约定、规则（如：时间）来进行数据的存储和集成。
* 数据集成平台：数据集成平台主要完成的是数据的集成过程，主要完成的功能有集成、调用、转换以及加载。一般情况下使用的工具有Oracle的ODI等。
数据集成平台提供的功能主要有：
在数据集成平台存在一个临时的数据存储空间，一般我们定义它为数据集成中心库，该库的作用是：保证数据及时、有效的集成。它不面向任何一般的用户，其中存在时间戳、操作位等明显的字段标识。
3 符合高校数据集成架构特点
3.1 数据库集成流程图
整个集成过程分为三个阶段：
第一阶段：数据集成平台通过ETL过程把业务系统中的数据抽取到集成中心数据库，抽取到集成中心数据库的数据经过清洗转换，使格式变得标准能够供其他业务系统所用。各个业务系统根据自身需要，从集成中心数据库中提取自身需要的数据，经过集成平台清洗转换为自有业务系统所要求的格式；
第二阶段：数据集成平台提供数据给全局数据库，用以支撑全局数据应用；
第三个阶段：数据仓库从数据集成平台中获取各业务系统中的主题数据，为统计数据分析、数据挖掘所用。
将整个数据集成工作划分为以上三个阶段，在条理、结构上变得清晰。并且能够和应用进行关联，可以了解到每个阶段的用户价值。
3.2 架构中的数据流向
在整体架构中，从数据流向上来看，数据集成平台与业务系统之间的数据流是双向的，即业务系统中的业务数据可以上行到数据集成中心，数据集成平台的数据也可以下行给各业务系统；数据集成平台与全局数据库之间的数据流也是双向的，即数据集成平台中的数据下行至全局数据库，提供基础业务数据，全局数据库提供校数据标准，为其他业务系统使用；数据集成平台与数据仓库的数据流是单项的，即数据集成平台的数据提供给数据仓库，用户数据的分析和辅助决策。
3.3 以数据集成平台为中心节点
通过以上分析不难看出，我们建立了一个以数据集成平台为中心的交互平台，一方面提供了包含全局，一致的、细节的、当前或接近当前的数据，用于系统间集成；另一方面，通过对集成过程中数据的沉淀，起到了全局数据落定的效果。
此平台可以保证：
(1)保证数字化校园信息编码的统一；
(2)保证任何两个业务系统之间没有冗余业务数据；
(3)保证“谁产生、谁维护”原则；
(4)保证所有的数据都只有唯一的维护者；
(5)保证提供反映整个学校的全面信息；
(6)保证为整个学校决策提供所需的数据信息。
4 分析
4.1 将全局库作为中心节点的不合理性
在很多高校的数据库集成部署方案中，将全局数据库作为整个架构的中心节点。从全局的部署来看是合理的，能够满足我们以上所提出的架构方案，但是在具体的实践中却暴露出很多问题：
我们定义的全局数据库是为上层应用服务的，是为数据需求者进行数据分析、查询等工作提供基础数据的。既然是最“基层”的数据提供者，那么对其本身的架构要求必然是稳定的，而实际数据库集成过程中是要经常变动的。
其次，从整个系统性能上来讲：假设全局数据库即为上层应用服务又要完成中心数据库的工作，那么势必影响整个系统架构的性能。
最后，从安全性的角度出发，如果经常在全局数据库上操作，势必影响其为“上层应用”服务。
综上所述，把全局数据库作为中心节点是不科学的。只能将其脱离出来，只完成其为上层应用服务的功能就能够解决以上问题。
5 结束语
信息化校园建设要达成高效、统一的建设目标需要校内各个部门相互协作，而各个部门的数据库关联又是重中之重，只有找到一种科学的、合理的集成方案才能达到其目的。所以说一个合理的数据库架构集成方案才是信息化校园建设的基石！
参考文献
[1] 《异构数据库集成中数据传输问题的研究》张良,佟俐鹃.北京机械工业学院.
[2] 《数据仓库元数据集成技术研究与应用》 李瑞旭,李扬.烟台大学.
[3] 《基于共享数据库的数据集成方案的改进》周长春,徐宏炳,张小伟.东南大学.
关键词：分布估计算法；非线性整数规划；概率模型；解空间
中图分类号：O224；TP183 文献标识码：B 文章编号：1004-373X(2008)10-129-03オ
Method of Estimation Distribution Algorithm for Solving Nonlinear Integer Programming
XIONG Shengwu1,LIU Mingfang1,LIU Xinliang2
(1.School of Computer Science and Technology,Wuhan University of Technology,Wuhan,430070,China;
2.Information System and Management College,National University of Defense Technology,Changsha,410073,China)オ
Abstract：Estimation of Distribution Algorithms (EDAs) acquire solutions by statistically learning and sampling the probability distribution of the best individuals of the population at each iteration of the algorithm.An estimation distribution algorithm is developed for nonlinear integer programming in this paper.It is shown that the method is efficient by the numerical experiment.
Keywords：estimation of distribution algorithms;nonlinear integer programming;probability model;solution space
1 引 言
整数规划是数学规划中较复杂的一大类问题。Murty[1]证明了非线性规划问题为NP-hard问题,作为其子集的非线性整数规划也必为NP-hard问题,求解该问题精确解的算法具有指数复杂度。整数规划广泛应用于许多工程领域,如资源管理、生产调度、可靠性优化、目标分配、超大规模集成电路设计等。对于变量规模较小的整数规划,传统的求解方法有分支定界法、割平面法和隐枚举法等。但对于较大规模的问题,传统的方法比较耗时,近年来随着进化计算的发展,许多学者运用遗传算法(GA)、模拟退火算法(SA)、微粒群算法(PSO)、蚁群算法(AA)等方法来求解整数规划问题[2-6]。遗传算法吸取了生物进化和遗传变异论的研究成果,是一种群体性全局寻优方法,但算法执行到一定阶段后向最优解收敛速度缓慢,且遗传算法的性能依赖于遗传因子（选择概率、交叉概率、变异概率、种群规模、染色体长度等）的取值,并且会出现早熟收敛情况。模拟退火算法模拟物质材料的冷却与结晶过程,通过退火温度控制搜索过程,但当问题规模较大时,系统进入热平衡状态(对应于最优解)的时间较长。粒子群算法和蚁群算法性能也依赖于设定参数（如强度的衰减系数等）,参数设定的优劣直接影响算法的运算效果。分布估计算法提出一种全新的进化模式,通过统计学习的手段建立解空间内个体分布的概率模型,然后对概率模型随机采样产生新的群体,如此反复进行,实现群体的进化。本文将分布估计算法推广应用到整数规划的解空间中,提出一种求解整数规划的新算法。
2 分布估计算法
分布估计算法（Estimation of Distribution Algorithms,EDAs）[7-9]是在进化计算领域兴起了一类新型的优化算法,是一种全新的进化模式。EDAs是在1996年由M[AKu¨]hlenbein 和Paaβ提出的一种广义型求解法。相对于传统的GA,在EDAs生成后代种群的过程中不需要交叉、变异操作,取而代之的是从一个概率分布中采样新的个体生成新的种群,而此概率模型是根据包含有从前代种群中挑选出来的个体的数据集估计而来。分布估计算法通过一个概率模型描述候选解在空间的分布,采用统计学习手段从群体宏观的角度建立一个描述解分布的概率模型,然后对概率模型随机采样产生新的种群,如此反复进行,实现种群的进化,直到满足停止准则。
根据概率模型的复杂程度以及不同的采样方法,分布估计算法发展很多不同的具体实现方法,但是都可以归纳为下面的基本步骤：首先随机生成M个个体,并有这些个体决定初始群体D0,并且对所有的个体进行评估。然后执行第一步,挑选N（N≤M）个个体（通称他们都拥有最好的目标函数值）。然后生成一个能最好的反映出n个变量相互依赖关系的n维概率模型。在根据上一步所得的概率分布获得M个新的个体组成新的种群。然后循环这3步,直到满足停止准则。И
其伪代码形式如下：
Pseudo-code of EDAs：
D0：Generate M individuals (the initial population) at random
Repeat for t=1,2,… until the stopping criterion is met
Dst－1：SelectN≤Mindividuals from Dt－1according to the selection method
Pt(x)=P(xDst－1)：Estimate the probability distribution of an individual being among the selected individuals
Dt：Sample M individuals (the new population) from Pt(x)
3 非线性整数规划问题
有约束的整数规划模数学模型为：
И[WB]Minimizef(X)=f(x1,x2,…,xn)
Subjecttoli≤xi≤ui i=1,2,…,n
xi∈Z i=1,2,…,nИ
上式中：[WTHZ]Z为整数空间；变量xi的下、上限li,ui为整数,w=ui－li+1为xi的可能取的个数。对很多类实际应用组合优化问题,xi的可行域可以枚举。
可行解空间如图1所示,xi有ai个节点,每个变量取一个值就构成空间一个解。如xi取第mi个节点,则对应的解为(x1,x2,…,xn)=(l1+m1－1,l2+m2－1,…,ln+mn－1)。И
图1 可行解空间
对于有约束的整数规划可以把原约束方程作为罚函数项加入到原目标中,变成无约束的优化问题。基于此,本文主要研究无约束整数规划问题的求解方法。
4 整数规划的分布估计算法
4.1 解空间的概率模型
在讨论的非线性整数规划问题中,描述解空间的概率模型用简单的概率向量p=(p1,p2,…,pn)表示,p表示群体的概率分布。
4.2 初始化群体
初始群体D0在解空间按照均匀分布随机抽样产生。即概率向量p0(x)=p0(x1,x2,…,xn)=∏ni=1p0(xi),其中p0(xi=li+mj－1)=1w,i=1,2,…,n；j=1,2,…,ui-li+1。群体规模为2s,通过适应值函数f(x)计算各个个体的适应值。
4.3 新解产生
在此选择截断方法作为选择策略,选择种群的一半,即选择适应值较高的s个个体,Dsl。因此Dsl表示第l代选择后的优势群体。概率向量p通过表达式p1(x)=p1(x1,x2,…,xn)=∏ni=1p(xi|Dsl-1)更新。根据这个概率向量p通过随机采样的方法产生新一代群体,至此分布估计算法完成了一个周期。可见在不断重复产生新解的过程中,适应值高的个体的出现概率越来越大。按照这个步骤改变个体在解空间的概率分布,使适应值高的个体分布概率变大,适应值低的个体分布概率变小,如此反复进化,最终将产生问题的最优解。
4.4 停止准则
由于概率向量p的作用,当迭代次数足够多时,概率向量p会逐渐增大到1,这时产生问题的最优解。即停止准则为p=1。
4.5 算法步骤
算法步骤为：
（1） 随机产生2s个个体（即初始群体）D0；
（2） 通过适应值函数f(x)计算各个个体的适应值；
（3） 以截断方法作为选择策略,选择种群的一半,即选择适应值较高的s个个体,Dsl-1；
（4） 估计选择的s个个体中每个个体的概率分布pl(x)=p(x|Dsl－1),并通过这个表达式更新概率向量p；
（5） 根据概率向量p通过随机采样的方法产生新一代群体Dsl；
（6） 如果没有满足停止准则,返回第（2）步。И
5 算 例
为了验证上述分布估计算法求解非线性整数规划的有效性,用EDAs解下列算例[10]：
算例F1： min F1=|x1|+|x2|+…+|x10|И
St.В10≤xi≤10,xi∈Z(i=1,2,…,10)И
算例F2： min F2=x21+x22+…+x210И
St.В10≤xi≤10,xi∈Z(i=1,2,…,10)И
算例F3： min F3=(x1－10x2)2+5(x3－x4)2+(x2－2x3)4+10(x1－10x4)4И
St.В10≤xi≤10,xi∈Z(i=1,2,…,4)И
采用本文所提出的算法,利用Java语言编程求解算例。随机产生100个个体组成初始种群D0（s=50）,计算适应值之后以截断方法作为选择策略,选取适应值较高的50个个体,估计这50个个体的概率分布更新向量p,在根据p[WTBZ]通过随机采样的方法产生100个个体的新一代群体。反复执行直到满足停止准则,求得全局最优解,最优解取值如表1所示。
图2 采用EDA算法的算例计算结果图
6 结 语
分布估计算法是进化计算领域内一个崭新的分支,他通过对整个群体建立数学模型,直接描述整个群体的进化趋势,是对生物进化“宏观”层面上的数学建模。分布估计算法通过概率模型可以描述变量之间的相互关系,对于解决非线性整数问题更加有效。通过算例,说明本文给出的算法有效。
参 考 文 献
［1］Katta G Murty.Some NP-complete Problem in Quadratic and Nonlinear Programming［J］.Mathematical Programming.1987(39):117-129.
［2］Rudolph G．An Evolutionary Algorithm for Integer Programming．Parallel Problem Solving from Natures―PPSN Ⅲ［M］.Lecture Notes in Computer Science,Springer,Berlin.1994．
［3］丰建荣,刘志河,刘正和.混合整数规划问题遗传算法的研究及仿真实现［J］.系统仿真学报,2004,16(4):845-848．
［4］谢云．用模拟退火算法并行求解整数规划问题［J］．高技术通讯,1991,1(10):21-26.
［5］谭瑛,高慧敏,曾建潮.求解整数规划问题的微粒群算法［J］.系统工程理论与实践,2004,24(5):126-129.
［6］黄樟灿,吴方才,胡晓林.基于信息素的整数规划的演化求解［J］.计算机应用研究,2001,18(7):27-29.
［7］Bengoetxea E,Larra[AKnˇ]aga P,Bloch I,et al.Solving graph Matching with EDAs Using a Permutation-based Representation.Estimation of Distribution Algorithms.A New Tool for Evolutionary Computation.Kluwer Academic Publishers,2002.
［8］Zhang Qingfu,Sun Jianyong,Edward Tsang,et al.Estimation of Distribution Algorithm with′2-opt Local Search for the Quadratic Assignment Problem.StudFuzz,2006:281-292.
［9］Jiri Oceanasek.Entropy-based Convergence Measurement in Discrete Estimation of Distribution Algorithms.StudFuzz,2006:39-50.
［10］Pearl J.Probabilistic Reasoning in Intelligent System[M].Morgan Kaufmann Publishers,1988.
作者简介 熊盛武 男，1967年出生,湖北武汉人,博士,教授,武汉理工大学计算机科学与技术学院。主要研究方向为智能计算、机器学习。
刘明芳 女，1980年出生,山东滨州人,硕士研究生,武汉理工大学计算机科学与技术学院。主要研究方向为智能计算、计算机软件理论及可靠性分析。
关键词:线性规划;整数规划;目标函数超平面;单纯形算法;分支算法
中图分类号: 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.
[10]DANTZIG G B. Linear programming and extensions[M]. New Jersey:Princeton University Press, 1963: 94-246.
关键词：混合整数双层线性规划 全局最优解 对偶间隙
层次性是大系统和复杂系统的主要特征。多层规划产生的主要目的是为了研究层次性，在研究的过程中逐渐形成一个新的运筹学分支。由于人们一般将决策系统看作双层决策系统，从而使得双层规划成为多层规划中最常见的形式。要使双层规划的情况下作出符合全局利益决策的规划，就必须将非合作层进行有序组合，首先让上层给下层一定的信息，下层按照自己的利益对这些信息给予一定的反应，上层再根据下层的反应做出决策，这样才能够使得决策体现全局性。
一、混合整数双层线性规划的全局优化方法模型及其定义
1.混合整数双层线性规划的全局优化方法模型
双层优化问题中，在变量的取值上面都有一定的要求，一般要求取整数值的变量较多。比较有代表性的规划是城市交通网络的设计中、企业生产设备的分配中、企业人力资源的规划等，对于这些规划的变量一般都要求取整数值。变量的离散性分析一般会使得一些较为简单的混合整数双层线性规划问题出现无解的情况。为了保证分支定界求解算法收敛，采用Moore和Bard讨论上下层都有离散变量的混合整数上层线性规划问题，当分支定界求解算法上层无连续变量的时候，就会出现收敛现象。Moore和Bard主要研究的是上下层变量为0～1型变量的混合整数上层线性规划问题，对参数整数的规划求解从中得到分支定界的方法。
假设x为上层决策者控制的n维列向量，y为下层决策者控制的m维列向量，可以将混合整数双层线性规划问题的一般形式写为：
（P1）minF（x，y）=c1x+d1y，s.t.A1x+B1y≤b1 xj=0或1（1≤j≤n）。
其中，y解为（P2）minyf（x，y）=d2y，s.t.A2x+B2y≤b2 y≥0。
其中 ，（P1）为混合整数双层线性规划的全局优化方法的上层问题，（P2）为混合整数双层线性规划的全局优化方法的下层问题。MIBLPP的约束域为S，其中S={（x，y）：A1x+B1y≤b1A2x+B2y≤b2，xj=0或1（1≤j≤n），y≥0}，设T为S在上层决策空间上的投影，则T={x：（x，y）∈S}。对于规划中的x∈T，记作S（x）={y：（x，y）∈S}。
2.混合整数双层线性规划的全局优化方法定义
（1）下层问题的合理反应集为P（x）={y：y∈argmin[f（x，y）：y∈S（x）]}，则混合整数双层线性规划的全局优化方法的诱导域为IR={（x，y）∈S：y∈P（x）}。
（2）对于一个集合（x，y）∈IR，如果存在（X*，y*）∈IR满足条件F（x*，y*）≤F（x，y），则可以将（x*，y*）称为混合整数双层线性规划的全局优化方法的全局最优解。
下层问题的合理反应集Px一定程度上定义了下层决策者的反应情况，IR作为可行解集合对上层决策者给出了一定的优化空间，通常情况下，可以将连续双层线性规划问题称作混合整数双层线性规划的全局优化方法的松弛问题：
（RP）minF（x，y）=c1x+d1y s.t.A1x+B1y≤b1 x≥0
其中y解为minf（x，y）=d2y 当s.t.A2x+B2y≤b2 得出y≥0
将S={（x，y）：A1x+B1y[b1，A2x+B2y≤b2，x≥0，y≥0}记作是（RP）的约束，域，从中可以得出S在上层决策空间上的投影即：T={x：（x，y∈S）}。综合定义可以得到P（x）为（RP）下层问题的合理反应集，IR为（RP）的诱导域。如果将S设为非空紧凸集，并且满足决策x∈T，此外，（RP）的下层问题都有唯一最优解，就可以得到如下结论。
结论1：S∈S，IRIR，结论2：如果S≠φ则IR≠φ，IR中的可行点就会落在凸多面体S的边界上，结论3：如果S≠φ，则混合整数双层线性规划的全局优化方法一定会有最优解，并且其最优解可以在S的边界上面找到。
二、双层线性规划的理论与算法
为了将混合整数双层线性规划的全局优化方法的问题方便地叙述出来，需要将枚举数中节点的序号用k表示出来。
当上层给出x∈T的决定之后，混合整数双层线性规划的全局优化方法的下层就会及时反应为解线性规划问题：（Px）minyf（x，y）=d2y s.t.B2y≤b2-A2x y≥0。
从中可以得出Px的对偶规划为（Dx）maxz（x，u）=u（A2x-b2） s.t.-uB2≤d2 u≥0 uT∈E，U={uT∈Eq：-uB2≤d2，u≥0}，其中，U中所有极点组成的集合为uT。通过线性规划对偶理论可以得到两个定理。
定理1：当存在u*∈UE，（x*，y*，u*）是一个特定函数的最优解时，则有（x*，y*）是混合整数双层线性规划的全局优化方法的最优解，具体证明如下：
当（x*，y*）为混合整数双层线性规划的全局优化方法的最优解时，对于给定的x*，y*，则认为其为下层问题的唯一最优解。通过对偶理论可以得出u*∈UE，其中u*为（Dx*）的最优解。并且d2y*=u*（A2x*-b2）由对偶理论得出y，u分别为Px的最优解。通过上述证明可以得出当给定x∈T时候，就会有（x，y）∈IR，F（x，y）
定理2：（xk，yk）是混合整数双层线性规划的全局优化方法的全局最优解。
证明：通过结论3和定理1可以得出5个步骤：
1.令F=+∞，使用线性规划的方式求出UE={u1，u2…ut}然后再转向步骤2。
2.使用混合整数线性规划的方法可以解出MILP（uk），如果不能得到有效解，可以转向步骤4，若是能够算出有效解，可以将最优解记作（xk，yk），将最优目标函数记作Fk=F（xk，yk）然后再转向步骤3。
3.若是Fk≥F，将计算转向步骤4，否则，令（x*，y*）=（xk，yk），F=Fk，再转向步骤4。
4.如果k
5.若F=+∞则混合整数双层线性规划的全局优化方法无可行解，否则，混合整数双层线性规划的全局优化方法的一个全局最优解为（x*，y*），从中可以找出对应的目标函数值F。
通过算法可以得出，双层规划作为多层规划的特例，主要对两个各具目标函数决策者之间非合作和有序的方法相互作用情况进行分析。上下层之间的行为和决策是相互影响相互作用的，但是上下层之间的选择行为不受对方的控制和左右。在双层规划性问题中，不论上层所取的允许决策如何，下层对偶问题的可行域都不会发生相应的变化。一定程度上也会使得可行域所对应的有限个极点保持不变。从整个问题的角度进行考虑，当下层问题的规模和变量都不大时，就会使得线性规划问题的极点比较容易实现。算法的关键也就是线性规划的极点问题。通过讨论混合整数双层线性规划问题，对于U中对求的最优解的问题起到关键作用和不起作用的现象应该进行深层研究和探讨。
三、结语
在经济模型领域或是网络交通、数据库、集成电路设计、化学工程、图像处理等控制中，全局优化的应用相当广泛。传统的非线性问题只能用于求得局部最优解，不能将其应用于全局优化问题中。由于全局优化在各个领域的重要性使得全局优化分析方法相对复杂，从而出现了一种混合整数双层线性规划的全局优化分析方法。本文主要针对上层所有变量0～1型变量和下层所有变量为连续型变量的混合整数上层线性规划问题进行求解，从中寻找全局最优解的方法。在求解的过程中，首先对下层问题的对偶问题可行域上的极点进行计算，使用的方法是线性规划技术。求出极点以后，再将问题转化为标准的混合整数线性规划问题，可以得出原问题的最优解是目标函数达到最小值的混合整数线性规划的最小值。
参考文献
[1]贾新花 赵茂先 胡宗国 等 一类混合整数双层线性规划的枚举法[J].山东科技大学学报（自然科学版），2009，（1）。
[2]武莹莹 刘卫伟 混合整数双层线性规划的全局优化算法[J].中国科技博览，2009，（21）。
[3]刘浪 陈建宏 郑海力 等 模糊预测型线性规划在矿山产能分配中的应用[J].中南大学学报（自然科学版），2012，（2）。
[关键词] 禁忌搜索算法 整数线性规划问题 技术处理
1 算法的技术问题
禁忌搜索算法的技术问题主要有：可行解的形式、解邻域的定义、禁忌的对象、禁忌的长度、局部最优解候选集、计算终止条件等等。对于这些技术问题的预处理，关系到算法计算结果的优劣。这些技术问题没有固定的模式生搬硬套，可以因问题而异，因人对问题的认识理解而异，从而产生的算法结果也有差异。
2 整数线性规划问题及其技术处理
整数线性规划问题的数学模型为：求解 维向量 ，使之满足：
,；
，
设 ， ， ，则整数线性规划问题可以表示为：
，
， ，
整数线性规划问题从计算复杂性划分，它属于NP问题。
采用禁忌搜索算法，有关的技术问题作如下的预处理：
对于可行解采用通常的 维向量表示法。任取初始可行解 。 表示可行解 的邻域，这里 定义为可行解 的恰有一个分量的数值改变的可行解全体构成集合，这样的 至多含有 个元素。
对于禁忌对象的选择，可以以改变数值的分量位置、或目标值、或可行解 作为禁忌对象。禁忌对象全体组成的集合称为禁忌表 。其中每一个元素都附有当前的禁忌代数，禁忌代数随着迭代次数变化而变化，一旦其数值超过禁忌长度时，该元素将解除禁忌。
本文的局部最优解候选集 是新的局部最优可行解的搜索区域， 就是从 的邻域
中去掉禁忌表中相应的元素而得。禁忌长度 取 或 。
取评价函数选择目标函数为之。在 中根据评价函数搜索新的可行解 。
特赦原则基于评价函数值的原则。即当= 时，从 中释放出使得评价函数值最小的禁忌对象。
计算终止条件为： = 或最大迭代上限或最佳评价值出现的频数，当而且仅当其中一个条件满足时，计算终止，输出结果。
3 算法流程图
流程图如下所示。其中，生成邻域 、禁忌表 、 的算法如下：
① 生成邻域 。设置数组 ， 的第 个分量变化后，得到新的可行解，否则 置 －1，而且 ， 。
② 生成禁忌表 、
本文以评价值为禁忌对象。如果，则 的所有元素禁忌长度分别加1，长度为 的禁忌元被释放；
查寻新的禁忌对象：如果 ，则 ， ，相应的禁忌长度置初值1。
如果 的邻居 满足条件：0，而且相应的 不在 中出现，则
， 。
③ 执行特赦命令，修正
如果，则要执行特赦。特赦时重点考虑释放对象的影响力及承担最小的错误诸原则。在 中查找使得评价值最小的禁忌元作为特赦对象，相应的可行解添加到 中。
4 实践与探讨
针对以下问题，采用适当的建立邻域的规则，使用C语言将算法编制成程序，在计算机上运行，得到较好结果。
例1
， ，是整数。
技术处理：取初始可行解 。 定义为可行解 恰有一个分量数值增加1的可行解全体构成集合，＝3， ＝8，禁忌长度取3。计算过程列表如下：
计算结束，得到最优解 ＝ ，相应的目标值 =12，其中 中向量的第1个分量是禁忌评价值，第2个分量是禁忌代数。
例2
， ， ，
技术处理：取初始可行解 ， 定义为可行解 恰有一个分量数值在0、1之间变化的可行解全体构成集合，＝3， ＝8，禁忌长度取3，计算过程列表如下。得到最优解 = ，相应的目标值 =2。
购物车(0)
