整数规划:基础、扩展及应用

**章引言 　　1.1*优化 　　*优化是一门适应性强、内容丰富的学科领域，不仅在学术界一直受到学者的关注，而且在社会生活领域对实际问题的解决也发挥着至关重要的作用.*优化研究是指在一定约束条件下，从众多可行选择中选出*优方案，使系统的目标函数在约束条件下达到*大或*小.它通过组建模型，掌握相关要素之间的关联，推测各种可行的办法以及可能发生的结果，从而选取能完成既定任务的*佳决策方案. 　　一个*优化模型，也称为数学规划模型，通常包含以下三个基本要素. 　　决策变量 *优化问题待定的量值，通过模型计算来确定的决策因素. 　　目标函数 度量决策方案优劣的标准，通常是与决策变量有关的待求极值(*大值或*小值)函数. 　　约束条件 限制决策选择的约束，即求目标函数极值时，决策变量必须满足的限制.*基本的约束条件是明确变量的类型. 　　*优化模型的一般形式为 　　min或max目标函数(可以是多个) 　　s.t. 　　主约束; 　　变量类型约束.(1.1) 　　其中s.t.代表subjectto(使服从). 　　将问题的决策用决策变量表示，其目标是在满足给定约束的条件下，寻求能够*大化或者*小化目标函数的决策变量取值. 　　(单目标)*优化模型的一般代数形式为 　　min或maxf(x1， ，xn) 　　s.t. 　　其中，x1， ，xn是决策变量，f(x1， ，xn)是目标函数，gi(x1， ，xn)(i=1， ，m)是约束函数，参数bi(i=1，2， ，m)是约束右端系数，每一个约束都可以是“≤”，“=”或者“≥”的形式. 　　决策变量的某个取值组合称为模型(1.2)的一个解.满足模型(1.2)的所有约束条件的解称为一个可行解，所有可行解构成的集合称为可行域.可行域中能使目标函数达到*优的解称为*优解.求解模型(1.2)的方法称为优化算法. 　　当f(x1， ，xn)和gi(x1， ，xn)(i=1， ，m)是决策变量x1， ，xn的线性函数时，称模型(1.2)为线性规划模型. 　　1.2整数规划 　　当决策变量中含有取值被约束为整数的变量(即存在整数变量)时，称模型(1.2)为整数规划模型.其中，所有决策变量都是整数变量的优化问题称为纯整数规划或全整数规划模型，而部分变量是整数变量的优化问题称为混合整数规划模型.目标函数和约束函数均是线性函数的整数规划模型，称为整数线性规划模型;否则，称为整数非线性规划模型. 　　取值为0或1的整数变量称为0-1变量或逻辑变量，常被用来表示系统是否处于某个特定状态，或者决策时是否选择某个特定方案.如当问题含有多项要素，而每项要素皆有两种选择时，可用一组0-1变量来描述.含有0-1变量的整数规划模型称为0-1整数规划模型.0-1整数规划模型在整数规划中具有重要地位，一方面，许多实际问题都可以归结为该类问题，另一方面，任何不含有无界变量的整数规划模型都与0-1整数规划模型等价，此外许多非线性规划模型也可以转化为等价的0-1整数规划模型. 　　整数规划是运筹学和管理科学中使用*广泛的优化模型之一.整数规划在现实生活中尤其是企业的管理和运营中应用广泛.在资源有限的条件下，针对提升生产和运营效率的问题进行建模优化，如原料分配、生产调度等;同时也可以针对其他计划问题进行建模优化，如生产计划问题、车辆路径问题、物流运输问题、设施选址、资金预算计划等.此外，整数规划的应用领域还包括：公共交通调度和班次安排、民航航班与机组调度安排、电厂发电计划、通信与网络设计、金融投资组合、大规模集成电路设计等.许多组合优化、图论以及计算逻辑问题，也都可以归结为整数规划问题.尽管整数规划模型在解空间结构上优于连续型模型，然而其求解计算的复杂程度却更高，目前一些著名的难题都是整数规划问题.因此，如何求解整数规划模型是学界研究的关键. 　　在求解整数规划模型时，如果可行域有界，*简单的求解方法是穷举所有的可行整数解，然后代入目标函数进行比较，得到*优解.当问题规模较小时，可以轻易穷举所有满足约束条件的整数解，这时穷举的方法是可行且有效的.然而，当问题规模变大或可行域无界时，难以在短时间内甚至无法穷举所有整数解.此时穷举法失效，需要设计有效的优化算法进行模型求解. 　　目前，关于整数规划模型的求解方法主要包括以下三种：精确算法、启发式算法和近似算法. 　　精确算法是指能够求出问题*优解的算法.整数规划精确算法的一般步骤如下： 　　生成一个相关问题，称为原问题的衍生问题; 　　在衍生问题基础上，进一步生成一个更易于求解的松弛问题; 　　通过求解松弛问题间接得到原问题的解. 　　由于整数线性规划模型与线性规划模型有着密切的关系，而线性规划模型易于求解，因此，整数规划模型的精确算法通常是针对相应线性规划模型的*优解设计有效的算法，主要包括分支定界算法、分支定切算法、分支定价算法和分支定价定切算法.分支定界算法的主要思路是求解整数规划模型对应的线性规划模型，把其可行域反复地分割为越来越小的子集(每个子集对应一个子线性规划模型的可行域)，这称为分支;然后计算每一支对应子整数规划模型的一个目标下界(对于*小值问题)，这称为定界;在每次分析后，凡是界限超出已知*好可行解目标值的那些子集不再进一步分支.因此许多子集可不予考虑，这称为剪枝.加快分支定界算法收敛速度的一种有效途径是加强每一支对应子整数规划模型的目标下界.常用的方法包括 　　动态地增加相应线性规划模型的有效不等式(切)，相应方法称为分支定切算法; 　　将相应线性规划模型转化为等价的Dantzig-Wolfe模型(丹齐格–沃尔夫模型)，进而利用列生成方法进行求解，相应方法称为分支定价算法; 　　针对每一支相应的Dantzig-Wolfe模型，既通过列生成方法进行求解，又动态地加切，相应方法称为分支定价定切算法. 　　启发式算法没有严格的理论分析，是算法设计者根据观察到的经验或问题结构性质设计的，在可接受的花费(指计算时间和空间)下给出待解决整数规划模型每一个实例的一个可行解.因此，该可行解与*优解的偏离程度一般不能被预计.当精确算法运行时间长或者无法在有限的时间内求出*优解时，启发式算法可作为备选方法.通常，许多*优化问题往往需要庞大的计算量.虽然启发式算法不能求出精确的*优值，但其至少在可控范围内找到相对较好的可行解，因此启发式算法在现实生活中应用广泛.目前，启发式算法包括构造型方法、局部搜索算法、松弛方法、智能算法等. 　　近似算法没有严格的定义，一般来说能求出可行解的算法都能归为近似算法.该类算法是针对特定问题使用贪婪策略、限制、松弛等方法设计的，需要进行算法的近似比和复杂度分析.因此，该类算法的求解规模通常是受限制的，*后获得的解也可能不是*优解.但相比于启发式算法，该类算法可以有效度量求得的可行解与*优解的偏离程度.常见的近似算法有贪婪算法、局部搜索算法、松弛算法、近似动态规划等. 　　1.3整数规划的发展历程 　　整数规划的历史可以追溯到20世纪50年代，美国学者G.B.Dantzig(丹齐格)首次发现可以通过0-1变量来刻画*优化模型中的固定费用、变量上界、非凸分片线性函数等.此后，Dantzig等对旅行商问题(traveling salesman problem，TSP)的研究，成为分支定界法和现代混合整数规划算法的开端.1958年，R.E.Gomory(戈莫里)提出了求解一般整数线性规划模型的收敛算法——割平面方法，至此整数规划成为*优化领域的一个独立分支.近年来，随着整数规划理论和算法的不断发展以及计算机计算速度和功能的迅猛提升，整数规划已逐渐成为应用*广泛的*优化方法之一，在社会、军事、生物、计算机以及经济等各大领域得到了更广泛的应用和长足的发展. 　　1.3.1模型和应用角度 　　整数规划在实际应用中十分广泛，很多优化问题都可以抽象为同一类整数规划模型.如经典的旅行商问题、背包问题(knapsack problem)、切割下料(cutting stock problem)问题等.其中研究*为广泛的问题为旅行商问题，其在运筹学和理论计算机科学中扮演着非常重要的角色，目前许多优化方法都将其作为一个测试基准.旅行商问题是指给定一系列城市和每对城市之间的距离，求解访问每一座城市一次并回到起始城市的*短回路.旅行商问题*初应用在交通运输领域，例如飞机航线安排、邮件派送、快递服务、校车行进路线设计等.随着时间的推移，其应用范围扩展到了许多其他领域，例如电路板印制、晶体结构分析、数据串聚类等. 　　整数规划在背包问题方面的研究*早可追溯到1897年，至今已经延续了一个多世纪.其问题可以描述为：给定一组物品，每种物品都有自己的重量和价值，如何选择物品才能在限定总重量内使得背包内物品的总价值*高.自从背包问题被提出之后，众多学者对其进行了深入细致的研究和拓展，关于背包问题理论的文献和研究也是不计其数.同时，背包问题在现实中也有着广泛的应用，很多实际问题都被抽象为背包问题，例如股市投资、国家预算、资源分配、工业生产和运输等.因此，背包问题也是组合优化领域中重要的基石之一. 　　切割下料问题是整数规划在生产领域中*经典的应用之一.其问题可以描述为：给定一组原材料，如何通过切割、剪裁、冲压等手段，按照工艺要求将原材料加工成规定大小的成材，从而使所用材料*少或利润*大.此外，随着越来越多的复杂系统使用数学框架建模，集划分问题(set partition problem)、选址问题(facility location problem)、网络设计问题(network design problem)等一系列整数规划问题都广泛应用于生产以及生活的方方面面，未来将会有更多的整数规划应用模型被发掘. 　　目前，整数规划应用研究的总体发展趋势主要有两个方面：.1整数规划与管理科学、网络科学、生命科学、服务科学等学科的交叉融合日益增强;.2现有算法往往还不能解决交通规划、生产调度、通信、金融投资等领域中出现的大规模混合整数规划模型，因此整数规划研究正朝着大规模混合整数规划模型的算法设计方向发展. 　　1.3.2模型求解角度 　　由于整数约束使得整数规划模型变得难以求解，目前整数规划模型求解算法的效率通常比不上求解线性规划模型的单纯形法.影响求解算法计算时间的*大因素是整数变量的数目，以及问题是否具有容易处理的特殊结构.在整数变量数目一定时，0-1整数规划模型通常比一般整数规划模型更容易求解.针对具有特殊结构的大规模0-1整数规划模型，采用特殊的算法求解通常更加容易;而不具有特殊结构的问题，即使整数变量数目较少也难以求解.此外，基于实际问题建立的整数规划模型通常含有不相关或冗余信息，这些信息也会降低算法求解效率. 　　自20世纪50年代以来，针对整数线性规划的研究一直是整数规划研究的核心内容.一般整数线性规划模型的求解算法主要是基于分支定界的算法.目前提高分支定界算法效率的主要途径有两个：.1提高求解线性松弛模型的速度;.2利用割平面和有效不等式加快收敛速度.一方面，分支定界算法需要求解许多可行域不断缩小的线性规划子问题，改进的单纯形算法(对偶单纯形算法)可以利用热启动方法加速求解子问题;另一方面，自从割平面方法被提出以来，基于不同问题结构性质的有效不等式理论得到了很好发展.针对背包问题、旅行商问题和网络流相关问题等，通过许多简单或复杂的强有效不等式以及结合这些有效不等式的分支切割方法，大大提高了分支定界算法的速度和效率.针对具有特殊结构的大规模问题，如具有分块结构的大规模整数线性规划模型，Dantzig-Wolfe分解和Benders分解(本德尔斯分解)是有效的分解方法，列生成和Benders分解算法分别是求解相应分解模型的高