1 基本概念
组合优化研究的是在有限或离散的候选方案中，依据某个评价标准选出最优或近似最优的方案。与连续优化相比，它更强调对象的离散性，例如整数、序列、图结构、集合划分等，因此往往具有更强的组合爆炸特征。该领域既关注问题本身的数学结构，也关注如何高效求解。
1.1 离散优化与组合优化的定义
离散优化通常指变量取值于离散集合的优化问题，组合优化则更强调问题由离散组合结构构成，例如排列、子集、匹配、路径或覆盖关系。两者范围高度重叠，但组合优化往往更突出“从有限组合中选优”的特征。
在实际文献中，某些问题既可归入离散优化，也可归入组合优化，例如整数规划、图上的最优化问题和资源分配问题。前者偏重数学表达，后者偏重结构分析。
1.2 可行解、目标函数与最优解
组合优化问题通常由可行解集合、目标函数和约束条件共同定义。可行解是满足全部限制的方案，目标函数用于衡量方案优劣，最优解则是在所有可行解中目标值最小或最大的解。
在不同问题中，目标函数的形式差异较大。它可以表示路径长度、成本、收益、冲突数、覆盖率或调度完成时间等。若多个解达到同一最优值，则它们都属于最优解集。
1.3 约束条件与搜索空间
约束条件限定了允许选择的方案范围，常见形式包括容量限制、先后顺序限制、互斥限制和结构限制。约束越复杂，搜索空间通常越大，问题也越难求解。
搜索空间是所有候选解构成的集合。对于含有大量离散变量的问题，搜索空间往往呈指数级增长，因此不能简单依靠穷举，而需要借助结构分析、剪枝、分解或近似策略。
1.4 问题规模与复杂度
问题规模一般由变量个数、节点数、任务数或约束数量衡量。规模扩大时，求解时间和内存消耗可能迅速上升，这种现象被称为组合爆炸。
复杂度用于描述问题或算法所需资源的增长速度。组合优化中的许多核心问题在理论上具有较高复杂度，因此“可求得精确解”与“能否在合理时间内求得”是两个不同层面的问题。
2 典型问题类型
组合优化覆盖的问题类型十分广泛，但许多经典模型可按结构大致归类为路径、分配、选择、调度和图论相关问题。不同类型之间常有交叉，实际应用中也经常相互组合。
2.1 路径与巡回类问题
这类问题通常要求在图中寻找满足条件的路径、回路或访问顺序，常见目标是最短、最便宜或最符合约束的行走方案。它们在运输、巡检、布线和访问规划中很常见。
2.1.1 旅行商问题
旅行商问题要求访问一组城市各一次并最终回到起点，使总路程最短。它是组合优化中最著名的问题之一，也常被用作检验算法性能的基准实例。
该问题的难点在于路径排列数量极大，且局部最优并不一定接近全局最优。它在物流配送、设备巡检和电路布线等场景中具有代表性。
2.1.2 最短哈密顿路径
最短哈密顿路径要求在图中经过每个顶点恰好一次，并使路径总成本最小，但不要求回到起点。与巡回问题相比，它少了闭合约束，结构上略有差异。
这一问题常作为路线安排、访问顺序设计和序列优化的抽象模型。在某些图结构中，它也与其他路径优化任务密切相关。
2.2 分配与匹配类问题
这类问题关注资源、任务或对象之间的一对一或一对多对应关系，目标通常是成本最小、收益最大或匹配质量最优。其基础模型在理论和应用中都非常重要。
2.2.1 指派问题
指派问题研究将若干任务分配给若干执行者，使总成本最低或总收益最高，并通常要求每个任务和每个执行者都恰好对应一次。它是典型的二分匹配优化模型。
在人员排班、机器任务分派和作业分配中，该问题具有直接应用。由于结构规整，许多实例可以用高效算法精确求解。
2.2.2 最大匹配与最优匹配
最大匹配是在图中选出尽可能多的互不冲突边，使得参与匹配的顶点数最大。最优匹配则进一步考虑边权或其他代价，追求总体质量最优。
匹配问题广泛出现在配对、资源连接和关系网络分析中。它既可作为独立问题研究，也常作为更复杂模型的子结构。
2.3 选择与覆盖类问题
此类问题的核心是从若干候选对象中选择子集，使其满足覆盖、容量或收益方面的要求。它们往往涉及“选哪些、不选哪些”的决策。
2.3.1 背包问题
背包问题要求在容量限制下，从多个物品中选择若干件，使总价值最大。其经典形式是0-1背包，即每件物品要么选，要么不选。
背包模型简单却非常典型，常用于资源受限条件下的选择优化。它也是许多动态规划方法和近似方法的重要试验场。
2.3.2 集合覆盖问题
集合覆盖问题要求从若干集合中选择尽量少的子集，使得目标元素全部被覆盖。若附带权重，则通常要在覆盖完整的前提下最小化总成本。
该问题广泛出现在设施选址、测试覆盖和传感器部署中。由于可选方案众多，通常需要借助近似算法或启发式方法。
2.3.3 装箱问题
装箱问题研究如何将若干物品装入容量有限的箱子中，并尽量减少箱子数量或提高利用率。它与背包问题相似，但决策重点不同。
装箱问题在仓储、运输和切割材料等场景中很常见。其解的结构复杂，常被用来研究近似算法与元启发式策略。
2.4 排序与调度类问题
这类问题关注任务执行顺序、开始时间、完成时间及资源占用，目标通常是缩短工期、减少延迟或提高效率。排序只是其一部分，调度更强调时间与资源约束。
2.4.1 作业调度问题
作业调度问题研究多个作业在给定资源上如何安排执行。常见目标包括最小化完工时间、等待时间或延迟总和。
这类问题在生产线、计算系统和服务流程中都有对应模型。由于约束类型丰富，常会形成不同难度的变体。
2.4.2 车间调度问题
车间调度问题是作业调度的重要分支，通常考虑多台机器、工序顺序以及加工时间限制。经典形式中，作业需要按既定工艺路线经过若干设备。
该问题模型能够反映制造系统中的真实约束，因此在工业优化中地位突出。其求解往往依赖精确算法与经验策略结合。
2.5 图论相关问题
许多组合优化问题可直接建模为图上的优化任务。图结构提供了清晰的关系表达方式，也便于引入匹配、路径、覆盖和割等概念。
2.5.1 图着色问题
图着色问题要求给图的顶点分配颜色，使相邻顶点颜色不同，并尽量减少颜色种类。它常用于资源冲突消解和时间安排。
在考试排程、频率分配和编译器寄存器分配中，图着色都具有典型意义。该问题在理论上也非常重要。
2.5.2 最小生成树变体
最小生成树变体研究在连通图中选取连接所有顶点的边集，并使总代价尽量低。与标准最小生成树相比，变体可能附加度数限制、可靠性要求或其他结构条件。
这类问题常见于网络骨架设计和基础设施规划。由于约束更复杂，求解难度通常高于经典生成树问题。
2.5.3 网络流与割问题
网络流问题研究在容量限制下如何从源点向汇点输送尽可能多的流量。割问题则关注如何划分顶点集或边集，使跨越分割的代价最小或最大。
网络流与割理论在通信、运输和图分割中都很重要，也经常被作为其他组合优化模型的子模块或松弛工具。
3 理论基础
组合优化的理论基础来自计算复杂性、离散结构和数学规划。三者共同构成了该领域的核心支撑，使研究者能够从“问题难度”“结构特征”和“可计算性”三个角度分析模型。
3.1 计算复杂性
计算复杂性研究问题在时间和空间资源上的内在难度。它帮助区分哪些问题可高效求解，哪些问题在一般情况下难以避免指数级开销。
3.1.1 P类与NP类问题
P类问题是指可在多项式时间内求解的问题，通常被视为“高效可解”。NP类问题则是指其解可在多项式时间内验证的问题。
许多组合优化问题的判定版本属于NP类，这意味着解答虽然容易验证，但寻找过程可能很难。正因如此，该领域形成了精确算法、近似方法和启发式方法等多条路线。
3.1.2 NP完全性与NP困难性
NP完全性表示某个问题既属于NP类，又与NP类中最难的问题一样难。若一个问题被证明为NP完全，通常意味着不存在已知的通用多项式时间算法。
NP困难性则更宽泛，表示问题至少和NP类最难问题一样难，但不一定属于NP类。许多重要组合优化模型都具有这一性质，因此研究重点常转向特殊情形、近似求解或参数化方法。
3.2 组合结构与图论基础
组合优化常依赖于对象之间的关系结构，例如图、树、匹配和覆盖。这些结构为问题提供了可视化和可分析的表达方式。
3.2.1 图、超图与树结构
图由顶点和边构成，用于表达二元关系；超图允许一条边连接多个顶点，适合刻画更复杂的关联。树则是一类无环连通图，常作为简化结构或递归基础。
这些结构在路径规划、网络设计和覆盖问题中非常常见。通过研究结构性质，可以推导出更强的算法和界限。
3.2.2 匹配、覆盖与独立集
匹配关注边之间的互不冲突选择，覆盖强调用较少的元素覆盖全部目标，独立集则要求所选顶点之间彼此不相邻。三者彼此关联，常通过对偶或变换联系起来。
这些概念在图优化中具有基础地位。许多复杂问题可以借由它们分解成较易处理的子问题。
3.3 数学规划基础
数学规划为组合优化提供了统一的建模语言。通过变量、约束和目标函数的形式化表达，复杂问题可以转化为标准优化模型。
3.3.1 线性规划
线性规划研究线性目标函数在一组线性约束下的最优值。虽然其变量可以是连续的，但它常被用于组合优化的松弛模型。
线性规划可帮助获得下界、构造近似算法，或为整数模型提供求解方向。它是许多高级算法的基础工具。
3.3.2 整数规划
整数规划要求部分或全部变量取整数值，因而更适合表达选择、分配和路径等离散决策。组合优化中的大量模型都可以写成整数规划形式。
整数规划的难点在于整数约束会显著增加计算复杂度。但它也因表达能力强而广泛用于精确建模。
3.3.3 混合整数规划
混合整数规划允许部分变量为整数，部分变量连续。它兼具表达灵活性和数学可处理性，因此在工程应用中十分常见。
许多实际组合优化问题会被写成混合整数规划，以便同时处理离散决策和连续资源分配。现代求解器对此类模型支持较强。
4 求解方法
组合优化的求解方法大致可分为精确算法、近似算法、启发式算法和元启发式方法。不同方法适用于不同规模、不同结构和不同精度要求的问题。
4.1 精确算法
精确算法追求找到真正最优解，适合结构较清晰或规模适中的问题。其优势在于结果可靠，缺点是面对大规模实例时可能代价过高。
4.1.1 分支定界法
分支定界法通过不断划分问题空间并计算上下界来排除不可能成为最优解的分支。若界估计足够紧，搜索空间可被显著缩小。
该方法广泛用于旅行商、整数规划和调度问题。它的效率往往取决于分支策略和界函数质量。
4.1.2 动态规划
动态规划通过将问题分解为若干重叠子问题，并保存中间结果来避免重复计算。对于具有阶段结构或最优子结构的问题，它尤其有效。
在背包问题、路径问题和某些调度问题中，动态规划常能得到精确解。不过它通常受状态数量限制，规模增大时易出现状态爆炸。
4.1.3 割平面法
割平面法从松弛模型出发，逐步加入额外约束，将非整数解逐渐逼近整数最优解。这些新增约束称为割。
该方法在整数规划中非常重要，也常与分支定界结合形成更强的混合框架。其核心在于发现能够有效排除非法解的结构性不等式。
4.2 近似算法
近似算法不一定返回最优解，但能保证结果与最优解之间存在可控偏差。对于难解问题，这类方法具有较高实用价值。
4.2.1 近似比与性能保证
近似比用于衡量算法输出与最优解之间的质量差距。若一个最小化问题的算法近似比为r，则意味着其结果不会比最优解差到某个固定倍数以上。
性能保证使算法结果具有理论可解释性。与纯经验方法相比，它提供了更明确的质量边界。
4.2.2 多项式时间近似方案
多项式时间近似方案通常指可在多项式时间内达到任意给定精度的算法。对某些特定问题，它能在可接受时间内逼近最优解到极高精度。
此类方案并不适用于所有组合优化问题，但在部分结构良好的模型中非常有价值。它体现了理论可解性与实际可用性的平衡。
4.3 启发式算法
启发式算法依赖经验规则和问题结构，通常能快速找到较好解，但不保证最优性或严格误差界。它们适合大规模实例和实时场景。
4.3.1 贪心算法
贪心算法每一步都选择当前看起来最优的局部决策。其实现简单、速度快，常作为初始解生成器或基线方法。
贪心策略并不总能获得全局最优，但在某些结构中效果很好。它常与其他方法结合以提升解质量。
4.3.2 局部搜索
局部搜索从一个初始解出发，不断在邻域内寻找更优解。若邻域设计合理，它可以快速改进解的质量。
这种方法易于实现，也便于与不同问题结构结合。其局限在于容易陷入局部最优，因此常需要扰动或重启机制。
4.3.3 随机化方法
随机化方法利用随机选择、随机扰动或概率决策来探索解空间。它可以减少对固定规则的依赖，并在复杂问题中提高搜索多样性。
随机性有助于跳出局部最优，并在多次运行后获得更稳健的结果。许多现代启发式框架都包含随机成分。
4.4 元启发式方法
元启发式方法是一类更高层次的搜索策略，通常用于引导、协调或增强基本启发式过程。它们强调平衡全局探索与局部开发。
4.4.1 遗传算法
遗传算法模拟生物进化过程，通过选择、交叉和变异逐步改进种群中的解。它适合复杂编码和多峰搜索空间。
在组合优化中，遗传算法常用于路径、排程和配置类问题。其表现依赖编码方式、适应度设计和算子选择。
4.4.2 模拟退火
模拟退火借鉴物理退火思想，允许在一定概率下接受较差解，以避免过早收敛。随着“温度”降低，算法逐渐转向更保守的搜索。
该方法结构简洁，应用广泛，尤其适合存在大量局部极值的场景。合理设置降温策略通常决定其效果。
4.4.3 蚁群算法
蚁群算法模拟蚂蚁通过信息素寻找路径的过程。多个搜索个体在正反馈机制下逐渐强化较优解附近的区域。
它在路径规划和组合路径优化中很常见，特别适合图上的顺序决策问题。信息素更新规则是其关键组成部分。
4.4.4 禁忌搜索
禁忌搜索通过记录近期访问过的状态或操作，避免搜索反复回到已探索区域。它能有效扩大搜索范围，并增强跳出局部最优的能力。
这种方法常用于调度、选址和图优化问题。其性能与禁忌表长度、候选规则和特赦条件密切相关。
5 重要模型与技术
组合优化的建模方法不仅服务于问题表达，也影响算法设计与理论分析。不同模型之间往往可以相互转换或近似。
5.1 图模型
图模型把对象及其关系表示为顶点与边的组合，便于刻画连接、冲突和覆盖等结构性约束。
5.1.1 路径模型
路径模型关注从起点到终点的访问顺序与代价累积，适用于路线规划、序列访问和流程安排。它常与最短路、巡回和哈密顿类问题联系在一起。
5.1.2 覆盖模型
覆盖模型用于描述若干对象是否能够覆盖全部需求点，常见于设施选址、传感器布设和检测系统。它强调覆盖率与成本之间的平衡。
5.1.3 匹配模型
匹配模型刻画对象之间的一对一或受限配对关系，广泛出现在分配和网络连接场景。它结构清晰，常能导出较强的理论结果。
5.2 规划模型
规划模型通过变量、约束和目标函数统一表达优化问题，是组合优化最常用的形式化工具之一。
5.2.1 0-1整数规划
0-1整数规划要求变量只能取0或1，适合表示“选与不选”“是与否”之类决策。许多经典组合问题都能转换为这一形式。
该模型表达简洁、适用性强，但通常求解困难。它也是许多分支定界与割平面技术的基础。
5.2.2 半定规划
半定规划研究矩阵变量在半正定约束下的优化问题。它在组合优化中常用于构造强松弛和高质量近似算法。
半定规划在图优化、编码和排序问题中具有重要作用。相比线性松弛，它能提供更丰富的结构信息。
5.2.3 拉格朗日松弛
拉格朗日松弛通过将部分难处理约束并入目标函数，降低原问题难度。被松弛的约束用乘子加以惩罚，从而形成可求解的子问题。
该技术常用于分解大规模组合优化模型，并产生有用的下界。它在调度、网络设计和设施选址中应用广泛。
5.3 随机与鲁棒优化
现实问题中常存在需求波动、成本变化和数据不完整等不确定因素，因此随机与鲁棒方法成为重要研究方向。
5.3.1 随机组合优化
随机组合优化考虑参数或输入具有随机性时的决策问题。目标可能是期望成本最小、风险最小或长期收益最大。
这类模型适合处理随机需求、随机到达或随机故障等情形。它通常比确定性模型更贴近真实场景。
5.3.2 不确定性建模
不确定性建模研究如何描述未知参数的变化范围、概率分布或偏差区间。合理建模是后续求解与分析的前提。
不同建模方式对应不同求解策略。若建模过于乐观，结果可能脆弱；若过于保守，则可能牺牲太多性能。
5.3.3 鲁棒决策
鲁棒决策要求在参数波动下仍能保持较好表现，而不是仅在单一理想条件下最优。它强调方案的稳定性和抗扰性。
在供应链、网络规划和排程中，鲁棒性常比单点最优更重要。该思想也越来越多地与组合优化结合。
6 应用领域
组合优化的应用覆盖工程、信息、制造和服务系统等多个方面。很多实际问题虽然表面不同，但都可以抽象成若干组合决策变量的优化。
6.1 物流与运输
物流与运输是组合优化最典型的应用领域之一，涉及路线选择、装载安排和配送顺序等问题。
6.1.1 车辆路径规划
车辆路径规划研究如何安排多辆车服务多个客户，并尽量减少总里程、时间或成本。它是旅行商问题的扩展，约束通常更多。
这一问题在快递、冷链、零售配送中极为常见。车辆容量、时间窗和服务顺序都会显著影响模型复杂度。
6.1.2 货物装载与配送
货物装载与配送关注如何在运输能力有限的条件下安排货物摆放与运送次序。它兼具装箱与调度的特点。
优化目标可能是提高空间利用率、降低搬运次数或减少延误。实际操作中常需要考虑重量分布和装卸便利性。
6.2 制造与生产
制造系统中的任务安排、设备分配和工艺排序都离不开组合优化。其目标通常是提升效率并减少等待和切换成本。
6.2.1 生产排程
生产排程研究多个订单或作业在生产线上的时间安排。常见指标包括完工时间、交付延迟和设备空闲率。
该领域需要兼顾工艺约束、设备能力和订单优先级，因此常采用混合整数规划和启发式算法相结合的方式。
6.2.2 资源分配
资源分配涉及将人力、机器、原料或预算等有限资源分配给若干任务。优化重点在于让整体收益最大或总成本最小。
由于资源之间可能存在竞争、依赖或互斥关系，这一问题常呈现较强的组合特征。
6.3 计算机科学
组合优化在计算机科学中用途广泛，既涉及系统设计，也涉及算法工程和数据分析。
6.3.1 网络设计
网络设计问题研究如何构建满足性能和成本要求的连接结构。典型目标包括降低建网成本、提高连通性和减少传输延迟。
这类问题在路由、服务器连接和基础网络搭建中都很重要。图模型是其核心工具。
6.3.2 芯片布局与布线
芯片布局与布线要求在有限空间内安排元件位置并连接导线，同时满足面积、时延和干扰约束。它是非常典型的高难度组合优化任务。
由于规模巨大且约束复杂，通常需要多阶段优化、局部搜索和专用启发式方法共同处理。
6.3.3 机器学习中的子集选择
机器学习中的子集选择指从特征、样本或模型集合中挑选一部分，以提高泛化能力、降低计算成本或增强可解释性。它常被视为组合优化任务。
这类问题在特征筛选、模型压缩和稀疏学习中很常见。由于搜索空间庞大，往往需要近似或贪心策略。
6.4 通信与网络
通信与网络系统中，频谱、链路和拓扑都具有明显的离散结构，因此非常适合用组合优化描述。
6.4.1 频谱分配
频谱分配研究如何将有限频段分给多个通信对象，同时减少干扰并提高利用率。它常与图着色模型联系密切。
该问题在无线通信网络中十分常见，且常需兼顾覆盖范围、优先级和稳定性等因素。
6.4.2 拓扑设计
拓扑设计关注如何构造网络连接结构，使其在成本、冗余和性能之间达到平衡。目标可能是连通性更强、延迟更低或维护更方便。
它在通信骨干、传感网络和分布式系统中都很重要，通常需要将图论方法与优化模型结合。
7 经典结果与研究方向
组合优化的发展伴随着一系列重要理论结果与算法框架的形成。经典定理为问题难度提供了界定，而新的研究方向则不断推动方法更新。
7.1 经典定理与界
经典定理主要用于刻画问题的可求解性、下界以及近似性能极限。它们构成了该领域的理论基石。
7.1.1 近似界与下界
近似界描述算法能达到的误差范围，下界则反映问题最优值或算法性能无法突破的限制。二者共同决定了算法设计的理论空间。
在许多组合优化问题中，近似界不仅是性能指标，也常揭示问题结构是否适合进一步改进。
7.1.2 可解性与不可解性结果
可解性结果说明某些问题或其特殊情形可以在多项式时间内求解，不可解性结果则指出一般形式难以高效求解。两者共同帮助研究者区分“易实例”与“难实例”。
这些结论推动了分类研究，也促使人们转向参数化复杂度、特殊图类和受限模型。
7.2 典型算法框架
许多组合优化算法都可归纳为若干经典框架，这些框架往往可组合使用，并在不同问题中反复出现。
7.2.1 枚举与剪枝
枚举与剪枝通过系统遍历候选方案，并尽早排除不可能优于当前最优解的分支。它是搜索类算法的基础思路。
合理的剪枝规则能够显著减少搜索树规模，因此在高难度问题中仍然非常重要。
7.2.2 分解与递归
分解与递归将大问题拆成若干子问题，再逐层组合子结果。它适合具有自相似结构或可分离结构的问题。
这种思路既可用于精确求解，也可用于近似和启发式设计。许多复杂模型都依赖分而治之的思想。
7.3 当前研究热点
随着数据规模扩大和应用场景变化，组合优化的研究重点也在不断转移。新问题往往要求更高的实时性、稳定性和可解释性。
7.3.1 大规模实例求解
大规模实例求解关注如何处理变量数量巨大、约束复杂的实际问题。重点通常不是理论上的最坏情况，而是如何在可接受时间内得到高质量解。
这要求算法在建模、分解和并行计算方面不断改进。工业级求解器和专用启发式在这一方向上都很活跃。
7.3.2 在线与动态组合优化
在线与动态组合优化研究输入随时间变化时的决策问题。决策者需要在信息不完全的情况下逐步作出选择，并根据新信息调整方案。
这类问题适用于实时调度、动态分配和流式环境。它比静态模型更贴近实际运行条件。
7.3.3 数据驱动优化
数据驱动优化将历史数据、统计规律或学习模型引入组合决策过程。它尝试利用数据预测参数变化，再据此制定更有效的方案。
该方向常与机器学习、预测分析和不确定优化结合，形成“预测—优化”一体化流程。
8 历史与发展
组合优化的形成经历了从具体问题研究到统一理论体系建立的过程。随着数学、计算机和工程应用的发展，它逐渐成为应用数学中的核心方向之一。
8.1 早期问题与起源
组合优化的早期研究多源于实际需求，例如路线安排、资源分配、网络连接和排班问题。许多经典题目在现代术语出现之前就已经存在。
随着图论和运筹学的发展，这些具体问题逐步被抽象成统一的数学模型，并开始形成系统的理论分析方法。
8.2 计算机时代的推动
电子计算机的出现极大促进了组合优化的发展。原本依靠手工或小规模计算处理的问题，开始可以在更大规模上测试算法。
同时，算法设计、复杂性理论和求解软件的进步，使得组合优化从“能否算出”转向“如何更快、更稳、更优地算出”。
8.3 现代应用与交叉发展
进入现代之后，组合优化与人工智能、数据科学、通信工程和制造系统等领域的联系日益紧密。很多问题不再只是抽象数学对象，而是直接服务于现实系统。
当前研究呈现出多学科交叉的特点：一方面追求理论深度，另一方面也强调大规模应用中的可实施性与鲁棒性。