数学规划求解器综述：理论、发展与最新进展

文章作者：黄蕾^1,2，肖璠³，葛冬冬⁴，印卧涛⁵，梁哲¹
作者单位：1.同济大学经济管理学院，2.上海海事大学交通运输学院，3.上海大学悉尼工商学院，4.上海交通大学安泰经济与管理学院，5.阿里巴巴达摩院

1 引言

数学规划求解器是一类运用数学规划算法，解决公共机构与商业组织面临的大规模复杂问题的工程软件。这类技术已广泛应用于制造、交通、通信、金融、能源、供应链、人员排班、物流与零售运营等多个领域，能够显著提升有限资源在规划、分配与调度环节的决策效率。

先进的数学规划求解器主要解决实际应用中的两大核心问题：线性规划（LP）与混合整数线性规划（MILP）。但现实世界的问题往往超出这两类范畴，因此学界与产业界开发了多款能够处理更复杂非线性问题的求解器，包括二次规划（QP）、二阶锥规划（SOCP）、半定规划（SDP）以及非凸优化问题。进一步引入整数决策变量的扩展模型，如混合整数二次规划（MIQP）、混合整数二阶锥规划（MISOCP）、混合整数非线性规划（MINLP），也在学术研究与求解器开发中受到了越来越多的关注。数学规划求解器的构建依托于一系列成熟的数学规划理论与算法体系，包括单纯形法、内点法、对偶理论、分支定界法、一阶方法、有效集法以及各类启发式算法。近年来，随着并行计算、人工智能等新兴技术的兴起，数学规划求解器的发展正迎来新一轮变革。这些技术创新为提升求解器性能、解决日益复杂的优化问题创造了新的机遇。

数学规划求解器的研发面临着极高的技术挑战，不仅要求研发人员具备深厚的数学优化理论功底，还要求其具备强大的软件工程能力，尤其是数据结构、算法设计与底层实现能力。此外，求解器的研发过程周期长、资源投入大，且存在固有风险。从发展历程来看，这类求解器的早期技术突破与产品化主要由欧美的头部企业与科研机构主导，代表性的商用求解器包括CPLEX、Gurobi、Mosek、Knitro与Xpress。1992年由企业与学术机构联合构建的MIPLIB基准测试集（Bixby et al., 1992），以及CBLIB（Friberg, 2016）、QPLIB（Furini et al., 2019）等测试集，已被广泛用于对比优化求解器的性能，同时推动了该领域的学术研究。基于这些测试库，美国亚利桑那州立大学的汉斯・米特尔曼（Hans Mittelmann）教授搭建了一套持续维护的基准测试平台，可实现LP、MILP、SDP、MIQP、MINLP等多类问题的求解器性能对比。尽管这些基准测试仅能代表现实世界优化问题的一小部分，但仍直观体现了过去几十年间求解器性能的爆发式提升。

近年来，总部位于中国的机构和企业研发的求解器已成为优化领域的重要贡献者，并推动全球优化技术取得了重要进展。代表性求解器包括：杉数科技2019年发布的COPT、阿里巴巴2020年发布的MindOpt、华为分别于2021年与2024年发布的OptVerse与TAYLOR、联想2022年发布的LeOPT。目前，其中多款求解器已在米特尔曼维护的LP单纯形、障碍法与MILP基准测试中跻身全球顶尖行列。尽管它们进入市场的时间相对较晚，但崛起速度极为迅猛。

目前，学界已出现多篇关于数学规划求解器的综述研究：部分研究专门聚焦CPLEX求解器，覆盖了20世纪90年代至21世纪初的发展历程（Achterberg and Wunderling, 2013; Bixby, 2002; Bixby et al., 2004）；另有研究重点关注LP/MILP求解器（Koch et al., 2022）；还有部分综述专门针对MINLP求解器展开（Bussieck and Vigerske, 2010）。但绝大多数已有综述并未覆盖近年新兴的求解器。

本综述旨在全面梳理数学规划求解器的相关研究，涵盖其理论基础、历史发展与最新技术突破，同时介绍并行化技术、图形处理器（GPU）加速、人工智能（AI）算法等新兴技术在求解器中的应用。

本文后续章节安排如下：第2章阐述数学规划求解器的理论基础，梳理优化领域数学算法的发展历程，重点介绍线性规划、混合整数线性规划与非线性规划三大核心方向；第3章简述数学规划求解器的发展历史，梳理当前主流求解器的发展现状，重点介绍中国头部自研求解器；第4章重点阐述求解器领域的最新技术进展，包括并行计算、GPU加速与AI算法三大方向；第5章探讨求解器评估面临的挑战，尤其是现实应用场景中的评估难题；第6章为全文结论。

2 理论基础

2.1 线性规划

线性规划研究的是在线性等式和/或不等式约束条件下，对线性目标函数进行最小化或最大化的问题，其决策变量为连续型。求解器中最常用的线性规划算法为单纯形法、内点法及其各类改进变体。本章将梳理这两类方法的核心基础文献，并比较其理论原理及其在不同类型、不同特征问题中的性能表现。

乔治·伯纳德·丹齐格（George B. Dantzig）被公认为线性规划的开创者。他于1947年提出了具有里程碑意义的单纯形法（Dantzig, 2002），该方法也成为20世纪最具影响力的算法之一。尽管列昂尼德·坎托罗维奇（Leonid V. Kantorovich）早在1939年就构建了同类问题的模型并提出了求解方法，但其研究成果直到1959年才被学界知晓（Bazaraa et al., 2010）。因此丹齐格被普遍认为是通用线性规划理论体系的主要奠基者。1955年，丹齐格与其合作者正式确立了单纯形法的理论体系，构建了基构造、基可行解、有界性与有限终止性等核心概念（Dantzig et al., 1955）。单纯形法的核心原理是，在线性规划中，若可行域为多面体且最优解存在，则最优解必然可以在可行域的某个极点（顶点）处找到。单纯形法从初始极点出发，沿着可行域的边迭代移动，从一个极点转移到另一个极点，直至找到最优解。1954年，莱姆基（Lemke）提出了对偶单纯形法，该方法在处理原问题不可行性的同时保持对偶可行性，为线性规划求解提供了另一种思路（Lemke, 1954），且在重优化场景中表现出显著优势。尽管单纯形法的最坏情况复杂度为指数级（Klee and Minty, 1972），但平均情况分析表明，在对输入数据做出特定假设的前提下，单纯形法的平均时间复杂度可达到多项式级别（Borgwardt, 1982a, 1982b; Smale, 1983a, 1983b）。在此基础上，现代实现又通过算法改进进一步提升了单纯形法的效率。例如，绝大多数求解器并不直接计算基矩阵的逆，而是计算并维护其LU分解。其原因在于LU分解的稀疏性更强，且计算过程的数值稳定性更优（Duff et al., 2017）。为了在转轴步骤中高效更新该分解，求解器普遍采用Forrest-Tomlin更新方法，通过置换变换与稀疏三角替换，避免在每次迭代都重新计算LU因子（Forrest and Tomlin, 1972）。

哈奇扬（Khachiyan）于1979年提出了椭球法，首次证明了线性规划问题可在多项式时间内求解。尽管该方法在理论上取得了突破，但受数值稳定性差、单轮迭代成本较高等因素影响，其实际计算表现并不理想，因此在工程应用中受到较大限制。据目前所知，椭球法并未在任何一款广泛应用的商用或开源求解器中实现。1984年，卡马卡（Karmarkar）取得了重大突破，提出了投影尺度法。这是一种内点算法，也是首个可实际应用的线性规划多项式时间算法（Karmarkar, 1984）。后续研究进一步衍生出原始-对偶对数障碍法。该方法结合梅赫罗特拉（Mehrotra）的预测-校正策略（Mehrotra, 1992）后，逐渐成为许多现代求解器的重要算法（Klotz and Newman, 2013）。与沿可行域边界迭代的单纯形法不同，内点法在可行域内部进行迭代，并在收敛时趋近于最优解。尽管不同的改进变体采用了不同的搜索方向计算策略，但所有内点法在每一轮迭代中都需要求解一个线性方程组，这也是该方法计算量最大的核心步骤。为提升计算效率，绝大多数求解器会提前对系统矩阵进行符号乔列斯基分解，利用其固定的稀疏模式，仅需在迭代过程中更新数值即可（Klotz and Newman, 2013）。

单纯形法与内点法的性能表现会随线性规划问题的结构不同而有所差异。卢斯蒂格等人（Lustig et al., 1994）的研究表明，经过精细优化的内点法实现，在大规模问题上的性能可超越单纯形法。特拉基（Terlaky, 2009）梳理了内点法25年的发展历程，探讨了其各类变体、优势与局限性。克洛茨与纽曼（Klotz and Newman, 2013）提出了基于线性规划问题的结构选择求解方法的一些经验性原则：例如，变量与约束的数量比n/m常被用作启发式判断依据，当约束数量远小于变量数（m≪n）或目标函数频繁变动时，原始单纯形法更具优势；而当变量数远小于约束数（n≪m）或需要迭代添加约束时，对偶单纯形法的表现更优，因为它能始终保持对偶可行性。但这类启发式规则并非普遍适用，也不存在基于m和n的绝对条件能保证某一种方法的性能更优。正因如此，绝大多数商用线性规划求解器都实现了多种算法，通常同时包含原始单纯形法、对偶单纯形法，以及至少一种内点法，并内置了动态选择与切换策略，有时在单次求解过程中会多次切换算法以提升效率。部分求解器还会采用多算法并行执行策略，或采用“交叉”策略，即先通过内点法快速找到近最优的内点解，再通过单纯形法收敛到精确的顶点最优解。

2.2 混合整数线性规划

混合整数线性规划是线性规划的自然延伸，其部分或全部决策变量被限定为离散型或整数型。尽管线性规划是MILP的理论基础，但MILP凭借其广泛的适用性，在现实世界的优化问题中占据主导地位（Bixby, 2012）。MILP的起源可追溯至丹齐格、富尔克森与约翰逊1954年关于旅行商问题的经典论文，该论文也被普遍认为是整数规划的诞生标志（Dantzig et al., 1954）。在过去70年间，MILP已发展为一个充满活力的研究领域，实现了重大的理论突破与广泛的实际应用。绝大多数现代MILP求解器都基于分支定界法构建，下文将对该方法进行详细介绍。

分支定界法由马科维茨与曼恩（Markowitz and Manne）于1957年首次提出，通过智能枚举的方式求解MILP问题的最优解。该方法构建了一棵搜索树，其中每个节点代表原问题的一个受限版本，通过添加额外约束强制特定变量取整数解。在每个节点处，算法都会求解该问题的线性规划松弛模型。与此同时，割平面法由丹齐格等人（Dantzig et al., 1954, 1959）与戈莫里（Gomory, 1958）开创，通过迭代不断收紧线性规划松弛模型。1957年，马科维茨与曼恩将分支定界法与割平面法相结合，提出了分支切割法（Markowitz and Manne, 1957）。二十年后，研究者成功将分支切割法应用于实际问题求解（Crowder et al., 1983; Van Roy and Wolsey, 1987）。此后的研究主要致力于改进分支切割法的两个核心组成部分，即分支策略与割平面。

分支策略是决定基于线性规划的分支切割算法最坏情况下指数复杂度的核心因素。如何将原问题拆分为子问题，直接决定了最终生成的搜索树规模，进而影响在合理时间内完成问题求解的效率（Benichou et al., 1971）。常见的分支规则包括：最不可行分支，即选择取整方向最不明确的变量进行分支（Achterberg et al., 2005）；伪成本分支，以行的系数与对偶解值作为权重；强分支，通过评估分数候选变量筛选出最有可能显著提升解质量的分支变量（Applegate et al., 1995）。近年来，混合分支方法的应用愈发广泛。例如，强分支/伪成本混合分支策略，在搜索树的上层（达到预设深度前）采用强分支，在更深层切换为伪成本分支；另一类方法是在伪成本分支中引入强分支初始化，通过强分支为伪成本未初始化的变量计算初始估计值（Linderoth and Savelsbergh, 1999）。可靠性分支则进一步拓展了这一思路，不仅对伪成本未初始化的变量执行强分支，还会对伪成本值不可靠的变量执行强分支（Achterberg et al., 2005）。此外，学界还提出了更多精细化的混合分支规则，进一步优化了分支过程（Achterberg and Berthold, 2009）。

割平面法通过剔除不可行区域来优化线性规划松弛模型，同时又不排除可行的整数解。最经典的割平面算法之一是戈莫里混合整数割（Gomory, 1960），它是戈莫里分数割（Gomory, 1958）的推广形式，适用于通用混合整数规划问题，无需利用问题的特定结构。此后，学界又提出了多种其他类型的割平面，包括析取割（Balas, 1979）、背包覆盖割（Johnson and Padberg, 1982; Weismantel, 1997）、流路径割（Van Roy and Wolsey, 1985）、隐含界割（Hoffman and Padberg, 1991）、提升投影割（Balas et al., 1993）、GUB覆盖割（Gu et al., 1998）、流覆盖割（Padberg et al., 1985; Gu et al., 1999）、团割（Johnson and Padberg, 1982; Atamtürk et al., 2000）、混合整数舍入割（Marchand and Wolsey, 2001）以及多商品网络流割（Achterberg and Raack, 2010）。比克斯比与罗思伯格（Bixby and Rothberg, 2007）指出，由于各类割平面法之间存在复杂的相互作用，单独评估新型割平面法的性能极具挑战。为解决这一问题，该研究在多种割平面中每次禁用一种方法，以评估其单独的影响。结果表明，尽管戈莫里混合整数割是提出时间最早的割平面方法，但移除该方法后求解器的性能下降幅度最大，充分证明了其有效性。此外，尽管多数割平面法在各类问题算例中都具备广泛有效性，但部分割平面具有更强的专用性，在特定类型的模型中表现更优（Achterberg and Wunderling, 2013）。

除前文介绍的分支切割法外，下文将介绍MILP求解器中另外两种广泛应用的加速求解技术：预处理与原始启发式算法。

预处理（也称为前处理）是整数规划高效求解的核心环节，布雷利等人（Brearley et al., 1973）与萨韦尔斯贝格（Savelsbergh, 1994）均强调了其重要性。预处理的目标是快速识别并剔除冗余的约束与变量，同时收紧变量边界，从而得到规模更小、更易求解的问题模型。这一点对于分支定界法尤为重要，因为该方法通常需要求解大量的线性规划问题（Wolsey, 2020）。预处理技术既可应用于根节点（求解首个线性松弛模型之前），也可应用于搜索树的后续节点（Achterberg et al., 2020）。多项研究表明，预处理能够显著提升混合整数规划求解器的性能（Achterberg et al., 2020; Achterberg and Wunderling, 2013; Bixby et al., 2004）。

原始启发式算法的目标是快速找到高质量的可行解，通过提前剪枝子树，缩减分支定界算法的搜索树规模。在实际应用中，很多场景下只需得到高质量的可行解即可，因为证明最优性可能需要极高的计算成本，甚至无法实现（Achterberg and Wunderling, 2013）。这类启发式算法通常分为两类：一类是启动启发式，也称为构造启发式，用于生成初始可行解；另一类是改进启发式，用于优化已有的可行解。启动启发式的代表包括潜水固定法（Berthold, 2006; Wolsey, 2020）、邻域舍入法（Berthold, 2006; Wolsey, 2020）、松弛强制邻域搜索（Berthold, 2006）与可行性泵法（Fischetti et al., 2005）；改进启发式的代表包括局部分支法（Fischetti and Lodi, 2003）、邻近搜索法（Fischetti and Monaci, 2014）、松弛诱导邻域搜索（RINS）（Danna et al., 2005）与优化打磨法（Rothberg, 2007）。启动启发式与改进启发式具有较强的相互依赖性：启动启发式为改进启发式提供了优化所需的初始解，而改进启发式则能够提升启动启发式生成的低质量解的精度（Achterberg and Wunderling, 2013）。

2.3 非线性规划

在实际应用中，除前文介绍的LP/MILP模型外，很多问题都具有非线性特征，涵盖了广泛的非线性优化类型，包括二次规划、二阶锥规划、半定规划与通用非线性规划（NLP）。若问题中包含离散变量，则会转化为混合整数非线性规划问题，这类问题同时兼具整数规划的组合复杂度与非线性优化的求解难度。

二次规划是指目标函数为二次型、约束为线性等式或不等式的优化问题。带线性约束的QP可视为线性规划的推广，区别在于其目标函数为二次型。若约束中包含二次项，则该问题被称为二次约束二次规划（QCQP）。一般二次规划问题属于NP难问题（Floudas and Visweswaran, 1995），但若目标函数中二次项对应的矩阵为半正定或正定矩阵，则该问题为凸问题，可在多项式时间内求解。凸二次规划的研究始于20世纪50年代（Frank and Wolfe, 1956），学界已在此后开发出多种高效求解方法。求解凸QP问题的常用方法包括有效集法（Wolfe, 1959）、内点法（Wright, 1997），以及交替方向乘子法（ADMM）等一阶方法（Boyd, 2010）。其中，内点法是当前商用求解器中默认的核心算法。

二阶锥规划是指在仿射集与二阶锥笛卡尔积的交集上，对线性目标函数进行最小化的问题（Nesterov and Nemirovskii, 1994）。SOCP问题属于非线性凸规划问题，是线性规划与凸二次规划的扩展，但其通用性弱于SDP问题。尤其是凸二次约束二次规划，可通过特定的重构方式转化为等价的SOCP问题。SOCP问题具有广泛的应用场景，包括天线阵列权重设计、抓取力优化、有限长单位冲激响应滤波器设计、带损失风险约束的投资组合优化、二阶锥可表示函数与集合，以及鲁棒线性规划等（Lobo et al., 1998）。由小岛等人（Kojima et al., 1989）与蒙泰罗、阿德勒（Monteiro and Adler, 1989）首次提出的原始-对偶内点法，是当前求解SOCP问题的核心算法。

半定规划是指在对称矩阵的仿射组合为半正定矩阵的约束下，对线性目标函数进行最小化的问题。尽管半定约束具有非线性、非光滑的特征，但SDP仍属于凸优化的子类（Vandenberghe and Boyd, 1996; Gärtner and Matoušek, 2012）。SDP是线性规划、凸二次规划与二阶锥规划的推广形式，是一类通用的优化建模框架（Alizadeh and Goldfarb, 2003）。目前学界已开发出多种求解SDP问题的方法，包括椭球法（Gärtner and Matoušek, 2012）、内点法（Vandenberghe and Boyd, 1996）、一阶方法（Wen et al., 2010）与近似算法（Gärtner and Matoušek, 2012）。其中，内点法凭借其求解通用线性SDP问题的鲁棒性与高效性，成为应用最广泛的算法，也是绝大多数现代求解器的核心基础。

通用非线性规划问题在众多工业场景中发挥着核心作用，例如石油化工行业的过程优化、电力、水务、燃气输配系统中的非线性网络流问题、城市交通均衡模型与经济规划模型等（Lasdon and Waren, 1980）。其核心求解方法主要包括序列二次规划与内点法。序列二次规划由威尔逊（Wilson）于1963年首次提出，通过求解一系列QP子问题逼近原问题，其核心是对目标函数构建二次模型，同时对约束进行线性化处理（Nocedal and Wright, 2006）。内点法则通过在松弛后的障碍模型上应用牛顿类算法，直接求解原始-对偶最优性条件。此外，研究者还提出了多种针对大规模或结构化NLP问题的求解策略，包括梯度投影法（Kelley, 1999）、线性约束增广拉格朗日法（Gill et al., 2019）与凸差（DC）规划方法（Tao and An, 1997）。其中，DC规划将非凸目标函数重构为两个凸函数之差，学界已开发出多种求解DC规划的算法，包括DC算法（DCA）（An and Tao, 2005）、凸-凹过程（CCP）（Yuille and Rangarajan, 2003），以及多种用于提升收敛性的邻近项或惩罚项改进变体（Lipp and Boyd, 2016; Wen et al., 2018）。

与MILP类似，许多非线性规划的实际问题也包含整数变量，从而形成了MINLP问题。根据问题结构的不同，前文介绍的各类非线性规划问题都可扩展为相应的混合整数形式，如MIQP/MIQCQP、MISOCP、MISDP或通用MINLP。MINLP的应用场景包括期权定价、投资组合优化、网络设计与运营、统计学、排班调度与物流等（Benson and Sağlam, 2013）。根据整数约束松弛后得到的问题是否为凸问题，MINLP可分为凸MINLP与非凸MINLP两大类（Burer and Letchford, 2012; D’Ambrosio and Lodi, 2013）。针对凸MINLP，学界已提出多种求解方法，包括广义Benders分解（Geoffrion, 1972）、分支定界法（Gupta and Ravindran, 1985）、外逼近法（Duran and Grossmann, 1986）、基于LP/NLP的分支定界法（Quesada and Grossmann, 1992）、扩展割平面法（Westerlund and Pettersson, 1995）、分支切割法（Stubbs and Mehrotra, 1999）以及混合方法（Bonami et al., 2008; Abhishek et al., 2010）。对于非凸MINLP，其连续松弛通常构成非凸全局优化问题，并且一般为NP难问题（Sherali and Adams, 2013）。求解非凸MINLP的算法包括空间分支定界法（Vigerske and Gleixner, 2018）、分支约简法（Ryoo and Sahinidis, 1995）以及α-分支定界法（Androulakis et al., 1995）。这些技术构成了BARON、ANTIGONE、Couenne等确定性全局优化求解器的算法基础（D’Ambrosio and Lodi, 2013）。

除上述通常依赖梯度信息的确定性方法外，学界还开发了一类独立的无导数优化（DFO）算法，用于求解导数不可用、不可靠或获取成本过高的优化问题（Rios and Sahinidis, 2013）。这类算法大致可以分为两类。一类是局部方法，如直接搜索法，例如Nelder-Mead单纯形法（Lagarias et al., 1998）和信赖域插值法（Conn et al., 2000）；另一类是全局方法，如响应面法（Khuri and Mukhopadhyay, 2010）以及模拟退火等启发式方法（Metropolis et al., 1953）。尽管无导数优化方法通常缺乏严格的全局最优性保证，但已被广泛应用于基于仿真的优化、工程设计、超参数调优与设施选址问题中。

3数学规划求解器的历史与发展

首个基于单纯形算法求解线性规划问题的系统化计算机代码，是由兰德公司的奥查德-海斯（Orchard-Hays）与丹齐格合作开发的。他们的最初实现采用了一种名为卡片可编程计算器的设备（Orchard-Hays, 1990），尽管该设备并非真正意义上的计算机，但已是一款可执行复杂计算的可编程计算器。1954年至1956年间，这些算法成功在IBM 701、IBM 704等科学计算机上实现。此后，奥查德-海斯从兰德公司加入CEIR公司，与其同事共同开发了LP/90/94代码。LP/90/94是优化领域的里程碑式产品，是公认的首个基于分支定界法的商用混合整数规划代码。20世纪80年代，LINDO、Xpress、CPLEX等现代数学规划求解器相继问世，标志着优化领域迎来了重大技术突破（Bixby, 2012）。

基于上述历史背景，本章后续内容将简要介绍多款具有代表性的现代数学规划求解器，总结其许可模式与设计适配的问题类型，并探讨中国自研数学规划求解器的最新发展。

3.1 现代数学规划求解器的分类

按照许可模式划分，数学规划求解器可大致分为商用与开源两大类。下表列出了两类中应用最广泛的部分求解器，并汇总了各求解器的开发主体、发布年份、许可类型，以及支持的问题类型，包括LP、MILP、QP/MIQP、QCQP/MIQCQP、SOCP/MISOCP、SDP/MISDP、NLP/MINLP与约束规划（CP）。

注：a) “学术免费” 指提供全功能免费学术许可；“学术（折扣）” 指为学术用户提供折扣许可，该分类不包含试用许可与社区版。

欧美主流商用求解器中，IBM ILOG CPLEX（2022）、Gurobi（Gurobi Optimization, 2025）与FICO Xpress（2025）具有较强代表性，下文对这三款求解器进行简要介绍。

CPLEX是一款应用极为广泛的数学规划求解器，由罗伯特・比克斯比（Robert Bixby）博士于20世纪80年代在 CPLEX 优化公司主导开发。1988年，CPLEX 1.0版本正式发布。2009年，CPLEX被IBM收购，被纳入IBM ILOG CPLEX优化工作室。从1.0版本到7.1版本，CPLEX的求解速度提升了50倍以上；结合算法优化与硬件性能提升，其整体速度提升达到103倍（Bixby, 2002）。最新版本为2022年发布的CPLEX 22.1.2，支持线性规划、混合整数规划、二次规划（包括凸二次规划与非凸二次规划）、二阶锥规划与约束规划等全类型优化问题。

顾宗浩、爱德华・罗思伯格与罗伯特・比克斯比于2008年创立了Gurobi公司，公司名称由三位创始人姓氏的前两个字母组合而成。2009年，Gurobi求解器的首个版本Gurobi 1.0正式发布。根据米特尔曼维护的基准测试结果，该版本的性能与CPLEX 11.0基本相当（Bixby, 2012）。目前，Gurobi支持线性规划、二次规划、二次约束二次规划、混合整数线性规划、混合整数二次规划、混合整数二次约束二次规划等全类型优化问题（Gurobi Optimization, 2025），最新版本为2024年11月发布的Gurobi 12.0。

Xpress最初由Dash Optimization公司开发，核心开发者为鲍勃・丹尼尔与罗伯特・阿什福德。该求解器于1983年首次发布，最初是用于线性规划问题建模与求解的工具，1986年扩展了混合整数规划模型的求解能力（Ashford, 2007）。2008年，Xpress被FICO公司收购。Xpress可求解线性规划、整数规划、二次规划、非线性规划与随机规划等多类优化问题（Laundy et al., 2009），最新版本为2025年4月发布的Xpress 9.6。此外，Xpress还集成了专门用于求解约束规划问题的Knitro求解器。

除商用求解器外，开源生态系统对优化技术的发展也起到了至关重要的推动作用。COIN-OR（运筹学计算基础设施）是该领域的标志性项目，由IBM研究院于（IBM Research）2000年发起，并于2004年正式成立非营利基金会（Lougee-Heimer, 2003）。该项目包含60多个子项目，均聚焦于计算优化领域，包括用于线性规划求解的Clp、用于整数规划求解的Cbc、用于混合整数非线性规划求解的Couenne等。

此外，HiGHS（Huangfu and Hall, 2018）是一款性能优异的线性与混合整数线性问题开源求解器，在米特尔曼等机构维护的基准测试中表现稳定。另一款领先的开源求解器是柏林祖思研究所开发的SCIP（Bolusani et al., 2024），该求解器于2005年首次发布，是目前混合整数规划问题求解速度最快的开源求解器之一，同时为约束整数规划、分支切割定价技术提供了强大的框架支持。

3.2 中国自研数学规划求解器的发展

近年来，中国科研机构以及总部位于中国的跨国企业研发团队相继推出了多款自主研发的求解器。2017年，上海财经大学交叉科学研究院发布了LEAVES，这是国内首个开源优化求解器平台，支持LP、SDP、几何规划等多类凸优化问题求解。2018年，中国科学院数学与系统科学研究院发布了CMIP 1.0，这是国内首个自主研发的混合整数规划求解器。

2020年前后，国内求解器发展迎来重大突破，一系列高性能商用求解器相继问世，包括杉数科技的COPT（2019年首次发布）、阿里巴巴达摩院的MindOpt（2020年首次发布）、华为的OptVerse（2021年）与TAYLOR（2024年）、深圳大数据研究院的XOPT（2024年）等。下文将重点介绍COPT、MindOpt、OptVerse与TAYLOR四款求解器，它们相较其他国产求解器展现出了更突出的性能表现。

2019年，杉数科技发布了国内首款商用线性规划求解器COPT，首个版本COPT 1.0于2019年5月28日正式发布。后续版本持续扩展了求解能力：2021年5月发布的COPT 2.0新增了整数规划支持；2021年10月上线的COPT 3.0，成为国内首款支持二阶锥规划的商用求解器。2022年，COPT实现了进一步技术突破：2月发布的COPT 4.0新增了凸二次规划与凸二次约束规划支持；6月发布的COPT 5.0上线了半定规划求解器；截至2022年11月，该求解器已完成混合整数二阶锥规划功能的开发。目前，COPT已支持多类优化问题求解，包括线性规划、混合整数线性规划、二次规划与凸二次规划、半定规划、通用非线性规划，以及混合整数二阶锥规划、混合整数凸二次规划、混合整数凸二次约束规划等各类混合整数规划模型。

2020年，阿里巴巴达摩院决策智能实验室发布了商用求解器MindOpt。首个公开版本MindOpt Solver 0.9.0于2020年8月14日发布，核心功能为基于单纯形法的线性规划问题求解。2022年5月，0.19.0版本新增了凸二次规划支持；2022年8月，0.20.0版本上线了混合整数线性规划求解功能；2022年11月，0.23.0版本新增了半定规划能力。2023年10月，MindOpt Solver 1.0正式发布，成为其发展历程中的重要里程碑。最新版本为2024年11月发布的MindOpt Solver 2.0.0，新增了二次约束规划、混合整数二次规划、混合整数二次约束规划的支持。除经典求解器外，MindOpt还内置了黑盒调优器（Zhang et al., 2023b），可用于优化MILP求解器的性能（Sun et al., 2024），同时推出了MindOpt Studio开发平台，覆盖了优化建模、分布式计算与全栈开发的全流程环节。

2021年9月，华为在华为全联接大会2021上正式发布了OptVerse优化求解器，当前1.0.0版本仅在华为云平台上线，支持大规模线性规划、二次规划与混合整数线性规划问题求解，同时可适配线性、非线性、混合整数、二次约束规划等多类算法模型。2024年，华为泰勒实验室推出了TAYLOR求解器，可求解大规模混合整数规划、线性规划、二次规划与非线性规划问题。

COPT、MindOpt与OptVerse在首次发布时，均在米特尔曼的LP基准测试中取得了第一名的成绩。后续的基准测试快照数据，进一步印证了中国自研求解器的强劲性能。例如，在最新的测试结果中，COPT与OptVerse在LPfeas与LPopt两项基准测试（分别对应障碍法与单纯形法）中均分别位列第一与第二；而在MIPLIB2017基准测试中，COPT、OptVerse与TAYLOR包揽了前三名。在非线性优化领域，COPT目前在SDP、SOCP、MISOCP、AMPL-NLP与QPLIB等多个类别中位列第一，OptVerse与TAYLOR同样表现强劲，分别在SOCP与AMPL-NLP基准测试中位列第二。尽管MindOpt于2024年12月退出了公开基准测试，但其此前的测试结果仍体现了优异的性能。例如，2024年10月28日的测试中，其在LPfeas与LPopt两项测试中均位列第三；2024年10月28日与10月9日的测试中，分别在AMPL-NLP与QPLIB测试中位列第二。

尽管最新的基准测试结果体现了这些求解器的强劲性能，但仍需注意一些实际应用层面的问题。上述排名均基于求解器默认参数设置，以及特定硬件环境下的挂钟运行时间测试结果：LP基准测试的运行环境为Intel i7-11700K处理器（3.6GHz，64GB内存，Linux系统），MIPLIB2017的测试环境为AMD Ryzen 9 5900X处理器（12核，128GB内存，Linux系统）。在实际应用中，求解器的性能会随问题结构、参数调优与运行环境的不同发生显著变化。此外，上述所有中国商用求解器目前均未提供免费学术许可，这可能会限制其在科研与教育领域的普及度。

除商用求解器外，包含中国研究者在内的研发团队还推出了多款开源求解器，尤其是基于GPU的求解器。例如，Lu等人（2024）推出了基于GPU的LP求解器cuPDLP-C，Han等人（2024）推出了基于GPU的SDP求解器cuLoRADS。在NVIDIA RTX A6000 GPU的测试环境下，两款求解器均在米特尔曼的LP基准测试中取得了顶尖排名。尽管基于GPU的求解器通常数值精度有限（容差通常在1e-4左右），但这些测试结果表明，若搭载更高性能的GPU，或应用于性态相对良好的问题，这类求解器具备极大的实际应用潜力。

4最新进展

在实际应用中，计算机技术的发展显著影响了数学规划求解器的性能。随着计算机技术的迭代，求解器的相关算法理论与实现技术也在持续演进。部分求解器经过了架构调整与重构，以更好适配现代高性能计算架构并优化性能。此外，部分求解器还融合了多领域的算法，尤其是人工智能领域的算法，通过集成机器学习、深度学习与强化学习方法，提升求解器的能力与计算效率。本章将重点探讨并行计算、GPU加速与AI算法对数学规划求解器发展的影响。

4.1 并行计算

随着多核CPU架构的普及，并行化已成为加速优化问题求解的核心手段。现代MILP求解器大多针对多核系统的共享内存并行性进行了优化，大幅提升了计算效率。米特尔曼等研究者也已在AMD Ryzen 9 5900X（12核，128GB内存）等高性能硬件上，基于MIPLIB 2017等数据集完成了基准测试。

除共享内存环境外，学界还开发了基于网格计算、超级计算机与大规模分布式系统的分布式内存并行技术。例如，ParaSCIP已分别在HLRN II与Titan超级计算机上调用了7000核与8万核，在两小时的时间限制内，成功求解了MIPLIB2010中多个此前未被破解的算例（Shinano et al., 2016）。

并行化技术随问题类型的不同存在差异。对于LP问题，相关研究主要聚焦于内点（障碍）法的并行优化（Andersen and Andersen, 2000; Gondzio and Sarkissian, 2003）。对于MIP问题，基于分支切割算法的主流求解器采用了不同粒度的并行化策略，包括并行搜索多棵树的树并行、同时探索多个子树的子树并行；更细粒度的策略包括同时处理多个节点的节点并行，以及在单个节点内实现任务并行的子节点内并行。子节点内并行技术可应用于强分支、LP求解、启发式算法执行、割平面生成与问题分解等环节（Ralphs et al., 2018）。

尽管共享内存并行化能够在单计算节点的能力范围内显著提升求解速度，但其最终仍会受到内存与核心数量的限制。分布式内存并行化通过调用多计算节点的海量计算资源解决了这一问题，大幅提升了超大规模、高难度算例的可求解性。其中最具代表性的案例是ParaSCIP，它在大规模超算平台上调用最多8万核，在两小时的时间限制内，成功求解了MIPLIB2003与MIPLIB2010基准测试集中14个此前未被破解的MILP算例（Shinano et al., 2016）。

4.2 GPU加速

在过去10至15年间，GPU已成为科学计算领域的核心组件之一（Dongarra, 2022）。GPU由多个核心组成，每个核心都是一个支持多线程的单指令多线程（SIMT）处理器。与CPU相比，GPU主要有两大核心差异。其一，GPU的核心数量远多于CPU。绝大多数CPU的核心数量在2至64核之间（AMD EPYC 9005系列最高配备192核），而GPU的核心数量通常可达数千甚至更多，能够同时处理海量并行任务。其二，GPU基于SIMT架构运行，多个线程可在不同数据单元上执行相同的指令。此外，GPU在线程块内采用共享内存架构，同时配备所有核心均可访问的全局内存。这些特性使得GPU在矩阵运算、仿真等数据并行任务中具备极高的效率，而CPU在需要复杂控制逻辑的任务中仍保持优势。

尽管GPU已受到求解器开发者的广泛关注，但绝大多数主流商用求解器仍未实现GPU的规模化应用。例如，Gurobi曾明确表示，GPU并不适配LP/MIP/QP求解器，核心原因有两点：一是GPU难以处理线性规划的核心——稀疏线性代数运算；二是GPU针对SIMT操作优化，而并行MIP求解需要在搜索树的每个节点执行不同的计算任务（Gurobi Optimization, 2023）。尽管如此，仍有部分研究者探索了GPU在数学规划求解器中的应用潜力，并在特定场景中取得了较有前景的结果，具体如下。

在线性规划领域，研究者发现，基于重启原始-对偶混合梯度（PDHG）方法的GPU加速实现cuPDLP，更适配GPU上的并行计算。研究者还提出了重启Halpern原始-对偶混合梯度法（rHPDHG）及其扩展版本r2HPDHG，并通过针对性的实现策略，缓解了传统基于单纯形法或内点法的LP求解器在GPU实现中面临的若干瓶颈。Lu与Yang（2024b）指出，稀疏线性代数是传统LP求解器的核心瓶颈。基于MIPLIB数据集的LP松弛模型初步测试表明，cuPDLP在特定大规模算例中展现出了优异的性能，而r2HPDHG在特定问题场景中的表现超越了传统求解器。在后续研究中，Lu等人（2024）使用C语言重新实现了cuPDLP，即cuPDLP-C，相较最初的Julia版本实现了50%的速度提升。此外，对于超大规模LP问题，cuPDLP-C相较传统内点法与单纯形法展现出了显著优势。

在非线性规划领域，Schubiger等人（2020）提出利用GPU加速ADMM方法，用于大规模二次规划问题求解。类似地，Lu与Yang（2024a）提出了一种名为重启加速原始-对偶混合梯度法（rAPDHG）的一阶方法，用于求解凸二次规划问题，并基于QPLIB数据集的算例给出了测试结果。Huang等人（2024）基于该框架进一步开发了重启原始-对偶混合共轭梯度法（PDHCG），在特定大规模测试中，其速度相较rAPDHG最高提升5倍，相较其他求解器提升近100倍。在半定规划领域，Han等人（2024）提出了GPU加速的低秩分解方法，并基于低秩ADMM分裂方法开发了GPU求解器cuLoRADS。在NVIDIA H100 GPU上，该求解器仅需10-60秒即可求解矩阵变量规模达10^7×10^7的最大割问题算例，而此前基于CPU的求解器求解单个算例至少需要数十小时。

但对于混合整数线性规划，GPU加速的可行性仍然较低。MILP求解器中的并行工作负载（尤其是LP子问题）可能存在极大差异，搜索树的每个节点都可能需要执行不同的计算任务，导致GPU难以被高效利用（Rothberg, 2020）。

4.3 AI算法

人工智能技术，包括机器学习、深度学习与强化学习，擅长从海量历史数据中提取规律，这一能力引发了学界与产业界利用AI优化求解过程的广泛兴趣。其中，AI与组合优化的融合已成为近年来的重要研究方向，其核心目标是加速传统求解方法，提高复杂大规模问题的求解效率。

近年来，AI算法已被应用于混合整数规划等优化问题的求解。部分研究采用端到端学习的方式，训练模型直接从输入数据生成解，该方法已在旅行商问题、车辆路径问题等场景中得到成功应用（Bengio et al., 2021）。另有研究将AI与大规模邻域搜索、可行性泵等启发式方法融合，提升了搜索效率与解质量（Zhang et al., 2023a）。尽管这些方法取得了不错的效果，但其解质量存在不稳定性，且难以集成到传统求解器中。相比之下，一个更具工程应用前景的方向，是将AI与分支切割法等精确算法相结合，以提升求解效率（Bengio et al., 2021; Zhang et al., 2023a）。这种通过AI提升精确算法效率的思路，在数学规划求解器的实际工程集成中具备最大的潜力。

AI算法与分支切割法的融合，主要聚焦于分支变量选择、割平面筛选，以及原始启发式等高级子程序。分支变量选择之所以关键，是因为搜索树规模会呈指数级增长，不当的分支决策可能导致搜索树规模急剧扩大。该领域的主流方法是通过模仿强分支规则学习分支策略。例如，Nair等人（2021）采用二分图表示MILP问题，提出了一种神经分支方法，该方法能够在更小的搜索树规模下缩小目标函数间隙，并相较SCIP实现了显著的性能提升。在割平面筛选领域，通过训练AI模型识别高价值割平面，能够收紧线性规划松弛模型，从而加快问题求解速度。例如，Tang等人（2020）构建了马尔可夫决策过程模型，训练强化学习智能体优化割平面的选择，提升了LP松弛的性能。在原始启发式领域，AI算法的目标是快速生成高质量解，为最小化问题提供更紧的上界，从而实现更多的搜索树剪枝。例如，Nair等人（2021）提出了神经潜水方法，通过深度神经网络生成整数变量的多个部分分配，将原问题简化为规模更小的MIP问题，优化了求解流程。

近年来，图神经网络（GNN）已被广泛用于优化问题求解，例如上述Nair等人（2021）的研究。GNN与约束优化模型的置换不变结构具有较好的匹配性，因此非常适合在二分图上进行学习。基于这一特性，Chen等人（2023a, 2023b）证明，设计合理的GNN能够预测LP与可展开MILP的可行性、有界性，并逼近最优解，该成果还被进一步推广至线性约束二次规划及其混合整数变体（Chen et al., 2024）。此外，Chen等人（2025）提出了2-FGNNs模型（second-order folklore GNNs），并证明其能够在通用MILP问题中高精度逼近强分支分数。这些研究成果为未来基于GNN的数学优化AI方法研究奠定了理论基础。

目前，AI方法在优化领域的规模化应用仍面临多项挑战。第一，数据采集与生成是核心障碍。正如Smith-Miles与Bowly（2015）所述，算法的有效性很大程度上取决于测试算例的精细选择。此外，若不对数据分布做出强假设，很难评估计算复杂度与样本复杂度，导致难以收集足够多样化的数据提升模型性能。第二，跨异构算例分布（例如MIPLIB中的算例）的泛化能力仍存在问题，性能提升通常仅局限于特定的窄场景中（Chen et al., 2023a）。第三，基于小规模算例训练的模型通常难以实现规模扩展，而基于大规模算例训练又会带来计算效率问题。

5优化问题的多样性与求解器评估

5.1 问题的广泛多样性

优化问题（尤其是MIP问题）具有极高的多样性，广泛产生于物流、制造、金融、能源等多个工业领域。而这些领域特定的运营需求与商业目标，会显著影响问题的建模方式。将现实世界的问题转化为标准优化问题的过程，对建模者的能力提出了极高的要求，需要对决策变量、目标函数、约束条件，以及图、特殊有序集等特殊结构做出关键选择。这一过程本身就会带来显著的多样性：对于同一个底层问题，不同的建模者可能会选择不同的建模方式，应用不同的数学方法，接受不同程度的近似。即便不考虑MIP求解本身的固有复杂度，这一差异也会导致最终生成的优化问题在特征与求解难度上存在巨大差异。

此外，变量与约束的数量、问题矩阵中非零元素的分布，以及数值性态，都会进一步加剧问题的多样性。总而言之，外部应用领域、问题内部的数学结构，以及建模过程中的人为因素三者的相互作用，使得优化问题的整体范畴具备极高的多样性。尽管MIPLIB等标准基准库已尽可能做到全面、公平，但仍不可避免地仅能代表真实多样性中的极小一部分。此外，出于商业保密考虑，公开可用的现实工业数据极为稀缺，进一步限制了这些基准测试的代表性。

5.2 房间里的大象：求解器对基准测试的过拟合

在竞争压力与营销需求的驱动下，求解器开发者自然会使用公开基准库测试、优化并展示其软件的性能。随着时间的推移，求解器内的算法选择、默认参数设置、预处理流程与启发式策略，会逐渐向在这些已知算例上实现最优性能的方向演进。当面对工业界的现实问题算例时，这一问题可能会变得极为突出——这类算例通常处于保密状态，导致公开可用的问题类型极为有限。

基准驱动的开发模式，确实能让求解器在基准测试集上实现显著的性能提升。已有研究表明，即便是旧版本的CPLEX，通过针对公开基准测试调整配置参数，也能实现顶尖的性能表现（Sun et al., 2024）。但这种在特定问题集上经过高度调优的性能，未必能泛化到未见过的新算例中。一些原本对更广泛问题类型有效的策略可能会被关闭，或者参数设置会向基准算例倾斜，最终导致求解器在基准分布外的问题上性能下降。

对于闭源商用求解器，这一问题的验证难度更高，因为其内部算法与详细的设计选择均为专有信息。尽管基准测试是追踪技术进步的必要且有价值的工具，但它可能无法全面反映求解器的真实性能。

5.3 终端用户：用户驱动的测试

当优化求解器的选择会直接影响项目周期、解质量、运营效率乃至最终商业成果时，仅依赖公开的基准测试结果或厂商的宣传材料是远远不够的。所谓“最优”的求解器具有强场景相关性，即性能评估必须基于用户的特定目标，包括：达到足够精度解的耗时、找到高质量可行解的耗时、固定时间限制内可实现的解质量、性能的鲁棒性与可靠性、所需的特殊功能（例如不可行性分析、序列优化的热启动）、文档质量，以及供应商提供软件定制化的能力。一款平均求解速度快，但在特定算例中性能波动极大甚至求解失败的求解器，其适用性可能不如一款表现更稳定、性能更可预测的求解器。

值得庆幸的是，当前的求解器生态为用户开展定制化评估提供了便利。绝大多数商用求解器都提供免费的试用许可或学术许可，标准化的编程接口（例如Python、C/C++与Java的API）与代数建模语言，使得用户只需完成一次问题建模，即可在多款求解器上进行测试。

因此，性能测试必须在能够反映用户实际应用中遇到的问题规模、结构、数据分布与其他复杂度的算例集上开展。鉴于闭源求解器的内部机制并不透明，在用户的实际业务问题上开展实证测试，是确定合适求解器的最可靠方法。

最后需要强调的是，求解器的选择并非一次性的静态决策。优化领域仍在快速发展，现有求解器在持续迭代优化，同时不断有新的开发者进入市场。

6结论

目前学界与产业界已开发出多款数学规划求解器，用于解决不同行业与不同机构面临的特定优化问题。每一类问题都对应着相关的数学理论，要求研发人员具备深厚的专业知识与多年的数值软件编程经验。这些复杂性导致求解器的研发成本高昂，行业准入门槛也极高。数学规划求解器的发展，不仅受到计算机硬件迭代的推动，也离不开优化理论的持续创新。

20世纪80年代前后，欧美国家的机构与企业率先开发出数学规划求解器，并在市场中占据了主导地位。但在过去五年间，中国自研求解器发展迅速，已开始挑战成熟求解器的长期垄断地位。这些新兴求解器已在公开基准测试中跻身全球领先行列，并获得行业关注。尽管MIPLIB等基准测试对推动行业进步起到了至关重要的作用，但它们仅能代表现实世界问题广泛多样性中的一小部分，还可能在无意中导致求解器策略向基准测试过度优化。终端用户必须优先在自身的特定问题算例上开展实证测试。

近年来，AI与GPU技术的发展，为进一步提升求解器性能提供了巨大潜力。AI技术可辅助分支、割平面选择、原始启发式等核心任务，而GPU硬件非常适合并行矩阵运算，能够优化数学规划求解器中的部分线性代数计算。但将这些技术创新与当前主流求解器架构的深度融合，仍面临诸多挑战，需要一定的时间落地。未来，这些创新有望推动数学规划求解器的整体设计发生更深层次的变化。

参考文献 （参见原文）

原文引用：Lei HUANG, Fan XIAO, Dongdong GE, Wotao YIN, Zhe LIANG. An overview of mathematical programming solvers: Theory, development, and recent advances. Eng. Manag, 2026, 13(1): 1-16 DOI:10.1007/s42524-026-5153-z.

文章链接：
https://journal.hep.com.cn/fem/EN/10.1007/s42524-026-5153-z
https://link.springer.com/article/10.1007/s42524-026-5153-z