混合整数规划是数学优化的一个分支,其中一部分决策变量必须取整数值,其他变量则可以连续取值。它为兼具离散选择与数量决策的问题提供了统一的描述语言:离散选择包括是否开设设施、选择哪条路线或是否启动机器,数量决策则涉及产量、运输量或运行时间等。这里的“规划”指的是数学意义上的计划安排,而不是计算机编程。
应用最广泛的形式是混合整数线性规划,其目标函数和约束条件均为线性。混合整数二次规划、混合整数锥规划和混合整数非线性规划则将这一框架扩展到其他数学关系。这些模型在运筹学中占据核心地位,因为许多运营和战略决策仅靠连续优化无法得到充分表达。
混合整数优化将建模与算法相结合,在搜索离散备选方案的同时,计算可达到的最优目标值的界。其实际求解效果取决于模型表述的强度、连续松弛、搜索、数学推断与数值计算之间的相互配合。因此,一种求解方法既可能给出可实施的决策,也可能提供量化证明,说明该决策距离最优还有多远。
数学表述与适用范围
标准的混合整数线性规划(MILP)具有如下形式:
其中, 为连续变量, 为整数变量,矩阵和向量则给出约束及目标系数。等式约束、下界和上界既可以直接纳入模型,也可以用不等式表示。取值限于 的二元变量尤其常见,因为它们可以表示“是或否”的决策。可行集由同时满足代数约束与变量取值范围限制的所有赋值组成。
严格来说,混合整数模型同时包含连续变量和整数变量。不过,在软件及许多文献中,“MIP”也指更广泛的一类问题,其中包括所有变量均为整数变量或二元变量的模型。因此,整数规划既是一个密切相关的领域,在这种较宽泛的用法下也是混合整数规划的特例。去除混合整数线性规划中的所有整数性要求,就得到一个线性规划。相比之下,向非线性模型中加入整数约束,则得到混合整数非线性规划,其求解难度在很大程度上取决于连续部分是否具有凸结构。
一个简单的固定费用生产模型可以说明离散决策与连续决策的区别。设 为生产数量, 表示是否启动生产。若产能为 、启动生产的固定成本为 、单位生产成本为 ,则模型可包含:
当 时,关联约束强制 。当 时,生产数量最多可达到产能上限。再加上 这样的需求约束,就构成了一个基本的生产决策模型。二元变量表示了一种实质性的不连续性:只要生产数量大于零,就会产生一笔固定成本,而这无法仅用关于 的普通线性成本来表示。
混合整数规划描述的是一种数学结构,而非对不确定性或时间的某种特定处理方式。模型可以是确定性的,也可以纳入多种未来情景,或涵盖多个规划期。其目标函数可以衡量成本、利润、延误、排放,或这些指标的加权组合。多个目标也可以按字典序处理,或通过对次要指标施加约束来处理。这些选择决定了规划问题的具体内容;整数性则决定了离散决策如何进入其数学表示。
松弛、几何与计算复杂性
求解混合整数线性规划(MILP)的主要出发点是其线性规划松弛,即允许整数变量取实数值。对于最小化问题,这会扩大可行集,从而给出一个下界:
任何混合整数可行解都能给出一个上界。上下界之差衡量了最优目标值尚存的不确定性。良好的松弛不仅能近似最优值,还能在不显式枚举的情况下排除整类离散备选方案。
从几何角度看,线性松弛的可行集是一个多面体,而混合整数可行集只保留其中指定坐标取整数值的点。混合整数可行点的凸包是优化线性目标时理想的连续表示。对于由有理数线性数据描述的非空有界可行域,这个凸包是一个有理多胞体。然而,精确描述它可能需要数量庞大的不等式,而找出这一描述中有用的部分,是整数优化的核心任务之一。
整数最优值与松弛最优值之间的差距通常称为整数性间隙。根据具体问题及符号约定,这一术语可以指两者之差,也可以指两者之比。例如,考虑满足
的二元变量,目标是最大化 。整数最优值为 ,但连续松弛允许 、,此时目标值为 。加入 即可消除这一间隙。某些具有特殊结构的线性系统不需要这样的强化:在右端项为适当整数的条件下,全幺模约束矩阵可保证所有顶点均为整数点。这解释了为什么一些重要的网络流问题和指派问题虽然具有离散性质,却仍可通过线性规划求解。
一般的混合整数线性规划具有NP难性,而有界二元线性可行性问题是NP完全的。这些结论针对的是最坏情形复杂性,并不意味着每个大规模实例都难以求解,也不意味着每个小规模实例都容易求解。伦斯特拉在1983年证明,当维数固定时,整数线性规划可以在多项式时间内求解,其中对维数的依赖体现于输入长度多项式之外的因子。这与一般情形形成对比:在一般情形下,整数变量的数量是输入的一部分。实际求解难度还取决于对称性、数值条件、松弛的强度以及约束之间的相互作用,因此,仅凭变量数量很难准确预测求解时间。
离散选择与逻辑关系的建模
二元变量可以将许多逻辑命题转化为线性不等式。若 ,则蕴含关系“ 蕴含 ”可表示为 。互斥关系可表示为 ,而在 个备选项中恰好选择一个则可表示为
若二元变量 表示二元变量 与 的合取,则不等式 、 和 构成这一关系的精确数学表达。这类构造将混合整数模型与命题逻辑联系起来,但其计算性能并不仅仅取决于逻辑上的正确性。
一种广泛使用的建模手段是大 建模法。若仅在 时施加约束 ,可以写成
常数 必须足够大,以免该不等式在 时排除本应保留的可行解。同时,在变量界和其他约束允许的范围内, 应尽可能小。取值过大会削弱线性松弛,并可能加剧数值计算中的困难。许多求解器提供指示约束,可直接表达这种蕴含关系,不过其内部处理仍依赖于变量界、分支或适当的重构。
当某个因子为二元变量时,一些非线性表达式可以用线性关系精确表示。若 、,且 ,则以下四个不等式
能够精确保证这一乘积关系。分段线性成本和物理关系同样可以利用选择区段的二元变量或特殊有序集来建模。这些表示方法适用于批量折扣、分档费率、生产模式以及光滑函数的近似,但近似表示与原始关系的精确表示仍有本质区别。
不同的建模方式可以描述相同的离散决策,却产生差异很大的松弛问题。例如,在设施选址问题中,单个汇总容量约束可能允许以分数值表示的设施开设状态支撑不合理的、过大的单个客户分配量;增加将客户分配与设施开设状态关联起来的不等式,可以加强松弛。模型可以通过增加变量和约束来换取更好的界。分解模型保留了聚合模型所掩盖的差异,而扩展模型则引入辅助变量,利用高维多面体的投影来表示所需的可行域。另一个重要选择是,是否消除由可互换标签带来的对称性。相同的机器或车辆可能产生许多等价解,而有效的对称性破除约束可以防止算法反复探索这些等价方案。
分支定界法与最优性搜索
分支定界法将离散搜索组织为一棵子问题树。在每个节点上,算法求解原问题在加入该节点所规定的限制条件后的松弛问题。假设某个变量必须取整数,而松弛问题给出的结果为 。分支操作会创建两个子节点:
父节点中的每个整数可行点都属于这两个子节点之一,而当前的分数点则不属于其中任何一个。重复这一过程,就能逐步划分剩余搜索空间,同时不遗漏任何整数可行解。
对于最小化问题,在以下任一情况下都可以剪除一个节点:其松弛问题不可行;其下界不优于当前已知最佳可行解的目标值;或者其松弛问题的某个最优解已经满足所有整数性限制。当前已知的最佳可行解称为当前最优解。在所有活跃节点中,最小的有效下界构成全局下界 ,而当前最优解则提供上界 。如果搜索消除了上下界之间的差距,就能在相应的数值容差范围内证明最优性。如果搜索因达到时间限制而中断, 这一对界仍能说明已经证明的结果。
分支规则和节点选择规则对性能有很大影响。强分支通过试探性地评估候选分支,估计它们对松弛界的影响。伪成本分支则从以往的分支中学习,估计改变某个变量的界通常能带来多大改进。可靠性分支将初期试探与累积得到的估计相结合。最优界节点选择侧重于改进全局最优性证明所依赖的界,而深度优先搜索占用的内存可能更少,也可能更早找到完整的整数解。现代方法会在这些目标之间权衡,而不是在整个搜索过程中始终采用同一条规则。
可行解往往是通过专门的启发式方法找到的,而不是等到松弛问题的最优解恰好满足整数性要求。简单舍入并不可靠,因为它可能违反容量约束、守恒方程或逻辑关系。更复杂的方法会修复舍入后的点,在当前最优解的邻域内搜索,或者将当前最优解与松弛解取值一致的变量固定下来。可行性泵在连续可行点与整数点之间交替迭代,试图兼顾可行性和整数性。这些方法可以迅速改善上界,但本身不能独立证明最优性。当整数变量的取值域有界时,穷尽式分支在理论上提供了一种有限搜索;实际应用中的成功,则依靠界和推理来避免其中几乎全部的枚举。
割平面与多面体强化
割平面法中的割平面,是指对所有混合整数可行解都成立、但当前松弛问题中的某个点不满足的不等式。加入这种不等式,可以排除不符合整数要求的分数解,同时不排除合法的离散决策。割平面既可以在分支开始前收紧根节点的松弛,也可以强化搜索树更深层节点上的松弛。将割平面与分支定界法相结合的方法称为分支切割法,是求解混合整数线性规划(MILP)的主流通用框架。
一个简单的例子来自具有非负权重的二元背包约束:
如果某个子集 满足 ,那么就不可能选中 中的所有物品。由此得到覆盖不等式:
当权重为 、容量为 时,任意两个物品都构成一个覆盖,因此有 。另一个有效不等式是 ,它比仅使用这些两两约束更强。这些例子说明,重要的是不等式的强度及其组合方式,而不只是数量。
通用的割平面族包括 Gomory 混合整数割、混合整数舍入割和分裂割。它们利用连续松弛中的点与整数性限制之间的不相容性来构造割平面。针对特定问题的割平面则利用额外的结构。在旅行商问题中,仅靠度数等式仍会允许出现多个互不连通的回路。子回路消除不等式可以排除这些不连通的巡回路线,而更强的不等式族还能进一步改进松弛。分离过程在某个不等式族中搜索被违反的不等式,无须事先列出所有可能的不等式。高效的分离过程使实际求解所用的模型能够保持紧凑,即使完整的数学表述包含指数数量的约束也是如此。
并非所有有效割平面都有助于计算。每加入一个不等式,连续子问题的规模都会增大;而系数尺度不佳的割平面还可能损害数值可靠性。因此,求解器会评估违反程度、稀疏性以及与已有割平面的相似性等指标,同时移除不再有用的割平面。全局有效割平面适用于整棵搜索树;局部有效割平面则可能依赖某个特定节点上施加的界限,因此仅在相应的子树内有效。这一区别对保证正确性至关重要。割平面理论旨在寻求对整数可行集的强刻画,而求解器工程则必须在界限的改善与维护、求解规模不断扩大的松弛问题所需的成本之间取得平衡。
分解方法与大型结构化模型
大型混合整数模型往往包含一些关联决策,将许多原本相互独立的子问题耦合起来。雅克·F. 本德斯于1962年提出的本德斯分解,利用主问题变量与子问题变量之间的划分来求解模型。在一种常见应用中,主问题选择离散的基础设施建设决策,而连续子问题则确定运营成本。对于
子问题的对偶解可以生成不等式,用于在主问题中逼近补救函数 。
最优对偶解会生成一个最优性割,将主问题中表示运营成本的变量与离散决策 联系起来。如果某个候选 使子问题不可行,则可以通过适当的对偶不可行性证书生成可行性割。整个过程交替进行:先提出主问题决策,再修正对这些决策所产生后果的估计。这一方法的有效性取决于能否生成信息量充足的割、维持有效的界,以及控制反复求解相似子问题所带来的开销。基于逻辑的本德斯分解通过对子问题的求解结果推导有效的逻辑解释,将这一基本思想推广到线性子问题之外。
乔治·丹齐格和菲利普·沃尔夫于1960年提出的丹齐格—沃尔夫分解则采用另一种思路,通过可行模式或极点来表示各个决策块。主问题选择这些模式的组合,而定价子问题则寻找能够改善目标值的、具有有利约化成本的新模式。这就是列生成。在切割下料模型中,一列可以描述将原料卷切割成较小片材的一种可行模式。在车辆路径问题中,一列可以代表一条完整的可行路线。全部列的数量可能极其庞大,因此只生成有用的列,就能避免构建完整的模型。
通过列生成求解连续主问题,通常并不能保证决策变量满足整数要求。将列生成与分支结合,就得到分支定价法;进一步加入割,则得到分支定价割法。分支决策的选择必须确保定价问题仍然易于求解。一种相关方法是拉格朗日对偶中的拉格朗日松弛:利用乘子将选定的约束移入目标函数,从而有可能将模型分解为更易求解的子问题。这些方法在多情景规划中尤为重要,因为许多针对不同情景的运营模型共享相同的第一阶段决策。它们的优势源于模型结构,并非必然出现:分解可以降低内存需求并利用并行计算,但割的强度不足、定价问题难解或协调过程缓慢,都可能抵消这些收益。
二次、锥与非线性扩展
混合整数二次规划允许采用二次目标函数,其典型形式为
并对 施加线性约束,对其中选定的分量施加整数性限制。当 为半正定矩阵时,其连续松弛是一个凸优化问题。当离散选择与跟踪误差、平滑性、方差等二次惩罚项相互作用时,就会出现这类模型。引入二次约束便得到混合整数二次约束规划;此时,凸性同样决定了能否用凸优化方法求得连续子问题的全局最优解。
混合整数锥模型将离散变量与如下形式的约束相结合:
二阶锥约束可以表示某些范数界、鲁棒优化中的鲁棒对应形式,以及涉及二次数量的关系。这类模型的凸连续松弛可在分支定界过程中提供有效的全局界。关键区别并不只是模型是否含有非线性表达式,而在于其松弛是否具有可用可靠方法进行全局优化的结构。
混合整数非线性规划(MINLP)允许采用更一般的非线性目标函数和约束。对于凸 MINLP,外逼近法将固定整数变量取值后的非线性子问题与一个混合整数线性主问题相结合。如果 可微且为凸函数,则其一阶近似满足
因此,线性化不等式
是 的必要条件,可以用来构造外松弛。在适当假设下,通过反复线性化并利用相应的界,可以构建有限步求解过程。其他方法则直接在分支树中求解凸非线性松弛问题。
非凸 MINLP 需要格外谨慎,因为对于最小化问题,连续子问题的局部最优值并不能提供有效的全局下界。全局优化方法会构造凸下估计函数,而且除了对整数变量分支外,还可能对连续变量分支。McCormick 包络为有界双线性项提供了标准的凸松弛;随着变量区间缩小,这些松弛会变得更紧。透视重构利用启用变量与其对应的连续活动量之间的联系,可以强化凸启停成本的建模。这些扩展保留了混合整数方法的核心原则——将离散搜索与有效界相结合——但用于求界的连续优化问题可能比线性规划(LP)困难得多。因此,必须区分求解器所声称的局部可行性与全局最优性证明。
数值计算、证书与软件
实际的求解器首先进行预处理,在保留模型相关数学性质的同时简化模型。预处理可以固定变量、收紧界限、删除冗余约束、利用等式进行代换,以及检测矛盾。整数性本身也能增强约束传播:如果整数变量满足 ,它也必然满足 。在多个约束之间反复进行传播,可以揭示从任何单个约束中都看不出的隐含关系。探测法通过暂时为某个二元变量赋值,并追踪由此产生的推论,可能发现可以固定的变量、隐含关系或不可行的赋值。
大多数大规模计算采用浮点运算,因此,可行性检验依据的是容差,而非精确的符号等式。一个看似为整数的值,可能与最近的整数略有偏差;约束残差也可能只要处于指定阈值内就被接受。系数跨度过大或大- 值设置过大,都可能放大这些容差在实际计算中的影响。在约束 中,当 非常大时, 的一个极小非零值就可能允许 取一个不可忽略的值。因此,缩放、有效且紧的界限以及审慎的模型构建,既影响求解速度,也影响计算结果的可靠性。
求解器报告会区分几种不同的结果。当前最佳可行解不一定是最优解;达到时间限制并不能证明问题不可行;未找到可行解,本身也不能说明可行解不存在。对于最小化问题,报告的下界 与当前最佳可行解的目标值 对应的目标绝对间隙为 。各求解器计算相对间隙的公式有所不同,尤其是在目标值接近零或正负号不同时。对于适合的问题类别和求解器工作流程,精确算术和可独立核验的证明证书能够增强验证的可靠性,但这类认证不同于常规的浮点优化。
商业系统包括 CPLEX、Gurobi 和 FICO Xpress;开源系统包括 SCIP、CBC 和 HiGHS。AMPL、GAMS、Pyomo 和 JuMP 等建模环境将数学模型的构建与底层求解引擎分离。回调、热启动和并行搜索等功能支持高度定制。对于不可行模型,冲突分析或不可约不可行子系统工具能够找出由相互不兼容的要求构成的子集,但不一定能找到足以解释不可行性的最小子集。要进行可复现的性能比较,需要提供模型文件、软件版本、硬件详情、参数设置和停止准则,并关注随机化或并行执行带来的波动。
应用与解的解读
设施选址是混合整数规划的典型应用。二元变量 表示是否开设设施,连续变量 则表示从设施 运往客户 的货物数量。一个基本模型为
该模型在设施开设成本、运输成本与容量之间进行权衡。扩展模型还可加入服务距离限制、设施类型、多种货物或需求不确定性。一个看似不大的改动,例如要求每位客户只能由一处设施提供服务,就会引入额外的离散分配决策,并可能大幅改变模型的形式。
生产计划与调度将生产准备、排序和产量决策结合起来。批量规划模型在某一时期发生生产时计入生产准备成本,并通过库存平衡方程将不同时期的生产与需求联系起来。调度模型可以用二元先后关系变量表示作业顺序,也可以将作业分配到离散时段。基于先后关系的模型可能较为紧凑,但其析取型时间约束依赖于足够紧的界。时间索引模型可以提供较强的松弛,但其规模会随着规划期延长和时间粒度细化而增大。因此,表示方式的选择既影响调度方案的含义,也影响计算负担。
在电力系统机组组合问题中,二元变量表示发电机组是否处于运行、启动或停机状态,连续变量则表示出力和备用容量。约束用于刻画爬坡限制、最小开机与停机时间、需求平衡以及输电网络的近似关系。在交通运输领域,混合整数模型在协调时间与容量的同时,选择路线并分配车辆或乘务人员。车辆路径模型通常将二元弧选择变量与连续的载荷或到达时间变量结合起来。网络设计同样将离散投资选择与连续流量相结合。这些应用说明,即使纯连续方案满足总体资源平衡方程,在实际运行中也可能毫无意义。
混合整数方法也用于统计学习和自动化决策系统。基数约束可以限制所选预测变量的数量,二元变量则可以用于编码分类规则或树结构。在这些场景中,优化证书针对的是所指定的经验目标,而不是预测有效性或因果解释。更一般地说,数学最优性以模型为前提:它并不能证明需求预测正确、被省略的约束无关紧要,或所选的目标权重涵盖了组织机构关切的所有方面。敏感性分析也不如在线性规划中那样直接,因为数据的微小变化就可能使离散配置发生切换。因此,情景比较、反复优化,以及对其他可行决策的评估,都是解读混合整数规划结果的重要环节。
历史发展与研究方向
混合整数规划是在经济计划、组合优化与电子计算相互交融的过程中发展起来的。乔治·丹齐格于1947年提出的单纯形法,使大规模线性规划的实际求解成为可能,也为后来利用连续优化确定整数规划的界奠定了基础。1954年,丹齐格、雷·富尔克森和塞尔默·约翰逊发表了一项成果,利用线性规划和附加不等式求解了一个包含49座城市的旅行商问题实例。这项工作表明,利用松弛问题,同时逐步排除与所求离散解不相容的结构,是一种有效的思路。
拉尔夫·戈莫里于20世纪50年代末提出了整数规划的通用割平面方法。艾尔莎·兰德和艾莉森·多伊格在1960年的论文中提出了一套系统的离散规划求解程序,成为分支定界法的基础之一。丹齐格–沃尔夫分解的论文也发表于1960年,随后于1962年出现了本德斯分解。这些进展确立了几项相辅相成的原则:通过不等式表示离散结构,通过分支划分备选方案,以及通过分解利用可分结构。任何一项原则都未能单独解决一般性的实际问题,但它们的结合为现代方法奠定了基础。
此后数十年间,研究日益转向将这些思想整合到求解器系统中。多面体研究为路径规划、匹配、设施选址及其他具有特定结构的问题找到了强不等式。线性规划算法、稀疏线性代数、预求解、分支规则、原始启发式算法和割管理等方面的改进,共同大幅提升了计算性能。MIPLIB基准测试库于1992年首次发布,后续又推出了更新的实例集,为比较不同方法提供了共用的测试实例。基准测试也清楚地表明,评估进展必须考察多种不同的问题结构,而不能仅凭某个有利的例子。
当前的研究仍在探索数学结构与自适应计算之间的相互作用。研究主题包括更强的模型表述、自动分解、对称性处理、证明日志记录、并行搜索,以及针对随时间反复变化的模型的求解方法。机器学习已被用于分支、割选择及求解器的其他决策,但学习得到的策略仍须在能够保证界的有效性和求解正确性的框架内运行。另一个长期存在的问题是如何解释求解性能:规模相近的模型表述可能表现迥异,而有利于某一类实例的改动,也可能不利于另一类实例。这些问题将离散优化理论与数值分析、软件架构以及算法的实证研究联系起来。