整数规划：模型、应用及求解
整数规划的历史可以追溯到20世纪50年代,美国学者丹齐格（G.B. Dantzig）首次发现可以通过0-1变量来刻画最优化模型中的固定费用、变量上界、非凸分片线性函数等.此后, 丹齐格等对旅行商问题(traveling salesman problem,TSP)的研究,成为分支定界法和现代混合整数规划算法的开端. 1958年,戈莫里（R.E.Gomory）提出了求解一般整数线性规划模型的收敛算法——割平面方法,至此整数规划成为最优化领域的一个独立分支.
近年来,随着整数规划理论和算法的不断发展以及计算机计算速度和功能的迅猛提升,整数规划已逐渐成为应用最广泛的最优化方法之一,在社会、军事、生物、计算机以及经济等各大领域得到了更广泛的应用和长足的发展.
模型和应用角度
整数规划在实际应用中十分广泛, 很多优化问题都可以抽象为同一类整数规划模型. 如经典的旅行商问题、背包问题 (knapsack problem)、切割下料 (cutting stock problem) 问题等.
其中研究最为广泛的问题为旅行商问题, 其在运筹学和理论计算机科学中扮演着非常重要的角色. 目前许多优化方法都将其作为一个测试基准.
旅行商问题是指给定一系列城市和每对城市之间的距离, 求解访问每一座城市一次并回到起始城市的最短回路. 旅行商问题最初应用在交通运输领域, 例如飞机航线安排、邮件派送、快递服务、校车行进路线设计等. 随着时间的推移, 其应用范围扩展到了许多其他领域, 例如电路板印制、晶体结构分析、数据串聚类等.
整数规划在背包问题方面的研究最早可追溯到1897 年, 至今已经延续了一 个多世纪. 其问题可以描述为：给定一组物品, 每种物品都有自己的重量和价值, 如何选择物品才能在限定总重量内使得背包内物品的总价值最高.
自从背包问题被提出之后, 众多学者对其进行了深入细致的研究和拓展, 关于背包问题理论的文献和研究也是不计其数. 同时, 背包问题在现实中也有着广泛的应用, 很多实际问题都被抽象为背包问题, 例如股市投资、国家预算、资源分配、工业生产和运输等. 因此, 背包问题也是组合优化领域中重要的基石之一.
切割下料问题是整数规划在生产领域中最经典的应用之一. 其问题可以描述 为：给定一组原材料, 如何通过切割、剪裁、冲压等手段, 按照工艺要求将原材料加工成规定大小的成材, 从而使所用材料最少或利润最大.
此外, 随着越来越多的复杂系统使用数学框架建模, 集划分问题 (set partition problem)、选址问题 (facility location problem)、网络设计问题 (network design problem) 等一系列整数规划问题都广泛应用于生产以及生活的方方面面, 未来将会有更多的整数规划应用模型被发掘.
目前, 整数规划应用研究的总体发展趋势主要有两个方面：
整数规划与管理科学、网络科学、生命科学、服务科学等学科的交叉融合日益增强;
现有算法往往还不能解决交通规划、生产调度、通信、金融投资等领域中出现的大规模混合整数规划模型, 因此整数规划研究正朝着大规模混合整数规划模型的算法设计方向发展.
模型求解角度
由于整数约束使得整数规划模型变得难以求解, 目前整数规划模型求解算法的效率通常比不上求解线性规划模型的单纯形法.
影响求解算法计算时间的最大因素是整数变量的数目, 以及问题是否具有容易处理的特殊结构.
在整数变量数目一定时, 0-1整数规划模型通常比一般整数规划模型更容易求解. 针对具有特殊结构的大规模0-1 整数规划模型, 采用特殊的算法求解通常更加容易; 而不具有特殊结构的问题, 即使整数变量数目较少也难以求解.
此外, 基于实际问题建立的整数规划模型通常含有不相关或冗余信息, 这些信息也会降低算法求解效率.
自 20 世纪 50 年代以来, 针对整数线性规划的研究一直是整数规划研究的核心内容. 一般整数线性规划模型的求解算法主要是基于分支定界的算法.
目前提高分支定界算法效率的主要途径有两个：
提高求解线性松弛模型的速度;
利用割平面和有效不等式加快收敛速度.
一方面, 分支定界算法需要求解许多可行域不断缩小的线性规划子问题, 改进的单纯形算法(对偶单纯形算法) 可以利用热启动方法加速求解子问题; 另一方面, 自从割平面方法被提出以来, 基于不同问题结构性质的有效不等式理论得到了很好发展.
针对背包问题、旅行商问题和网络流相关问题等, 通过许多简单或复杂的强有效不等式以及结合这些有效不等式的分支切割方法, 大大提高了分支定界算法的速度和效率. 针对具有特殊结构的大规模问题, 如具有分块结构的大规模整数线性规划模型, Dantzig-Wolfe 分解和 Benders 分解 (本德尔斯分解) 是有效的分解方法, 列生成和 Benders 分解算法分别是求解相应分解模型的高效算法策略.
20 世纪中期, 迫于实际需求, 能够快速求解整数规划模型的启发式算法应运而生. 伴随近年来计算机技术的发展, 如禁忌搜索算法 (tabu search algorithm)、模拟退火算法 (simulated annealing algorithm)、遗传算法 (genetic algorithm) 等启发式算法取得了巨大的成功.
不同于整数线性规划, 对于整数非线性规划的研究始于 20 世纪 80 年代, 两者无论从理论的系统性还是算法的有效性上都有很大的差距. 整数非线性规划的 研究策略和途径往往依赖于问题的特殊结构和性质, 一些求解整数线性规划模型的基本方法 (例如分支定界法、动态规划和 0-1 隐枚举法, 其中最常用的是分支定界法) 也可以被用于求解整数非线性规划模型.
20 世纪 90 年代, 半定规划内点算法的提出给二次 0-1 整数规划的研究提供了有力的工具, 给该领域注入了新的活力. 针对最大割问题、二次指派问题和其他特殊二次 0-1 整数规划问题, 半定规划松弛和随机化算法取得了巨大的成功. 本质上, 整数规划只能使用隐枚举法或枚举法的思想来求解问题的最优解. 随着问题规模的扩大, 算法的计算时间也迅猛增加, 而最简单的连续优化问题的 可行解也可以达到无穷多个. 尽管存在理论上的困难性, 应用领域对整数规划的需求还是推动它不断前进和发展.
近年来, 随着整数规划算法技术和商业求解软件的发展和推广, 许多原来不能解决的大规模整数规划模型, 都可以在合理的时间内使用新算法以及更快速的计算机来解决. 然而, 由于对整数规划模型认识的不足和数学工具的局限, 许多整数规划模型仍不能得到很好的求解，亟需针对具体的整数规划模型设计高效算法.
——以上内容摘自由殷允强、王杜娟、余玉刚主编的《整数规划：基础、扩展及应用》
内容简介
本书主要聚焦于大规模整数规划模型的求解方法和策略, 深入浅出地阐明了求解大规模整数规划模型主流方法的基本思想、原理、执行步骤以及在实际问题中的应用, 共分为引言、整数规划建模、线性规划、精确离散优化方法、割平面法、列生成算法、拉格朗日松弛算法、Benders 分解算法和启发式算法九章. 每种算法和分析都注重结合问题实际, 加入众多现实案例, 并配有相应习题. 书中还附有相关阅读材料, 以便有兴趣的读者进一步钻研探索.
作为一本研究性与教学性并重的专业教材, 本书既可以作为高等院校经济管理类和理工类等专业本科生、研究生的必修教材, 又可作为研究人员、专业人员的自学及参考用书.
本书特色
与已有教材相比, 本书主要聚焦于大规模整数规划模型的求解方法和策略, 深入浅出地阐明了求解大规模整数规划模型主流方法的基本思想、原理、执行步骤以及在实际问题中的应用. 每种算法和分析都注重结合问题实际, 加入众多现实案例, 并配有相应习题, 符合 “新工科” 人才培养的理念与要求, 是一部新颖且具有较强实践指导性的教材. 书中还附有相关阅读材料, 以便有兴趣的读者进一步钻研探索.
