通过运算次数统计来分析和比较快速数据包络分析程序

《European Journal of Operational Research》：Counting operations to analyze and compare Fast DEA procedures

　　

• 代表操作计数（ROC）作为向DEA报告的指标。
• 通过求解线性规划（LP）的数量和规模衡量计算工作量。
• 环境无关的工作量表达式。
• 在最优、最差和平均场景下的两两比较。
• 补充执行时间并解释性能。

引言

在过去五十年间，数据包络分析（Data Envelopment Analysis, DEA）在方法论上取得了大量进展，并在众多领域中得到广泛应用（Mergoni等人，2025）。DEA的各种数学形式，如原始径向模型、加性模型和基于松弛变量的测度（Cooper等人，2011），都需要求解线性规划（LP）以根据规模报酬假设及其投入-产出指标，将一组称为决策单元（Decision Making Units, DMUs）的实体分类为有效或无效。第一个DEA线性规划形式出现在Charnes等人（1978）的开创性研究中，在该研究中，必须为每个需要"评分"的DMU重新构建并求解一个新的线性规划。对DEA计算问题的关注很快在Bessent和Kennington（1980）的研究中浮现。这一兴趣的推动力在于需要处理DMU数量不断增加、且具有多个投入和产出的DEA数据集，而所有这些都会影响需要求解的线性规划的数量和规模。这催生了一系列新的程序，它们运用新颖的理论结果和算法开发来处理计算负担，而这一负担主要来源于需要求解线性规划。

标准做法是使用执行时间来比较计算结果。然而，执行时间严重依赖于特定的硬件和软件——尤其是线性规划求解器——以及程序的实现方式。因此，执行时间的比较可能不一致、难以复现、很快过时，并且无法解释程序的内在算法工作量。此外，执行时间反映的是特定的计算环境，对于程序的工作原理及其随问题规模变化的扩展能力提供的洞察有限。因此，仅依赖执行时间会限制将结果推广到特定实验环境之外的能力。

为解决这些局限性，我们提出在分析和比较DEA程序时，用一种环境无关的计算工作量度量——即代表操作计数（Representative Operation Counts, ROC）（Ahuja & Orlin, 1996）——来补充执行时间。在现代DEA程序中，主要操作是求解线性规划。ROC通过统计所求解的线性规划的数量及其规模来衡量程序的计算工作量。这可以通过解析方式进行，如本文所示，也可以通过在执行过程中跟踪线性规划及其规模来进行经验性测量。在概念上，ROC沿袭了Knuth（1973）引入的操作计数传统，即通过计算基本操作而非执行时间来衡量算法工作量。虽然ROC不是一种渐近复杂度度量，但它提供了一种基于所求解线性规划的计算工作量的实例特定度量，与附属操作相解耦。ROC独立于计算环境，即独立于硬件（机器）和软件配置（编程平台、求解器、单纯形法等），捕捉了DEA程序的内在计算工作量。另一方面，执行时间反映了计算工作量在特定环境中的实现方式。因此，执行时间回答了程序在给定环境中的运行速度，而ROC则解释了不同程序在计算工作量上的差异原因。类似于计算复杂度分析，ROC可以提供解析的最优、最差和平均情况的工作量表达式，将计算工作量与数据的结构特性相关联，并支持公平、可复现且具有持久性的比较。

ROC非常适合用于比较DEA中的程序，在这些程序中，计算工作量主要由求解线性规划驱动。所提出的ROC方法适用于采用包络类型线性规划形式的DEA程序，且基于标准规模报酬假设。在运筹学的其他领域中也会出现类似情况，其中算法求解一系列相关的线性规划，例如整数规划和Dantzig-Wolfe分解（Dantzig & Wolfe, 1960）。在这些情况下，大部分计算工作量可以用所求解的线性规划来表达。除测量线性规划工作负载外，ROC还能够在DEA程序之间进行解析和半解析的两两比较，针对有趣的情景（如最优、最差或平均情况），从而评估它们的相对性能。虽然ROC度量与环境无关，但线性规划工作负载可用于估计执行时间。这需要一个优化文献中已广泛接受的前提，即基于单纯形的算法的执行时间大致与工作负载成正比。我们经验性地观察到这一点，并报告其主要适用于大型线性规划，且依赖于基于单纯形的实现。

本文专注于使用ROC分析并比较三种"快速"DEA程序，以及基础的"传统"（TRAD）方法（Banker等人，1984；Charnes等人，1978）。我们将分析的快速DEA程序包括Ali（1993）提出的"约化基进入"（Reduced Basis Entry, RBE）、Barr和Durchholz（1997）提出的"层次分解"（Hierarchical Decomposition, HD）的一个版本，以及Dulá（2011）提出的"构建包络"（BuildHull, BH）。这四种程序在某种意义上都是原型，因为它们代表了塑造DEA计算发展的不同算法范式。TRAD通过基于线性规划使DEA变得实用。每个快速程序都新颖地应用了某种关于线性规划理论和/或几何性质的结果，从而在DEA中带来了显著的性能提升。

本研究使用ROC来分析基础的TRAD方法以及三种具有代表性的快速DEA程序RBE、HD和BH。具体而言，它们以原始形式处理，即不包含预处理方案、加速器、混合方法或实现特定的增强。其他计算DEA方法不在本次ROC分析的范围内。尽管如此，许多这些方法对计算DEA做出了重要贡献。它们旨在探索生产可能性集（Production Possibility Set, PPS）的几何特性（Korhonen和Siaatarri, 2007, 2009），限制DEA线性规划的规模（Chen和Cho, 2009; Chen和Lai, 2017），以及识别锚点和特殊DMU（Bougnol和Dulá, 2009; Mostafaee和Soleimani-damaneh, 2014）。其他重要研究引入了预处理和预评分启发式方法（Chen和Ali, 2002; Jie, 2020; Khezrimotlagh等人, 2019; Sueyoshi和Chang, 1989; Zelenyuk, 2020）。

本文其余部分组织如下：第2节介绍全文使用的符号、定义和假设，并对所考察的DEA程序进行简要描述。第3节提出ROC方法，并推导TRAD和快速DEA程序（RBE、HD和BH）的解析线性规划工作量表达式，包括适用的最优、最差和平均情况分析。第4节经验性地检验在何时以及如何可以使用ROC来估计执行时间。我们观察到，当使用基于单纯形的方法求解足够大的线性规划时，ROC与执行时间之间存在近似线性关系。这包括从数据和环境中推导出该假设所需的比例因子。最后，第5节对本文进行总结，并讨论其启示和未来的研究方向。三个附录分别提供了伪代码、关于RBE平均ROC的证明，以及对在不同计算环境中使用具有不同特征的大规模数据集进行测试结果讨论和总结。

章节片段

符号、术语、假设和约定

点集使用花体字母表示；例如 ?? 等。子集可通过标记或上标来标识：???、??? 等。集合的基数表示为 |?|。我们从DEA数据集 ?? 和由投入与产出给出的模型开始。数据集 ?? 的可变规模报酬（VRS）PPS（Banker等人，1984）将被称为VRS包络，或等价地称为 ??????(??)。局部包络是数据集子集的VRS包络；例如，如果 ??????，则 ??????(???)。

四种DEA程序的代表操作计数

ROC作为可移植的、环境无关的计算工作量指标。它在不断演进的硬件和软件环境中为结果提供持久性，并且提供了更客观的、因此更公平的比较，跨越不同的实现和线性规划求解器。ROC可以为一般情况或某些有趣的特殊情况解析推导。它始终可以通过在执行过程中实时统计线性规划的数量并跟踪其规模来进行经验性计算。

使用基于单纯形的方法检验ROC与执行时间之间的关系

有强有力的经验证据表明，单纯形算法求解线性规划表现出线性行为，即与约束数量或变量数量成正比地扩展。关于约束与枢轴操作之间线性性的观察最早出现在Dantzig（1963, 第160页）。此后，这一具体的经验观察在文献和重要学术著作中被广泛讨论（Bertsimas和Tsitsiklis, 1997; Nocedal和Wright, 2006; Todd, 2002; 另见Adl, 1986）。

结论

本工作引入代表操作计数（ROC）来分析并比较DEA程序，通过衡量其主要操作——即求解线性规划——的数量和规模。我们将ROC应用于基础的（TRAD）DEA方法和三种"快速"DEA程序，即RBE、HD和BH，因为它们利用关于线性规划理论和/或PPS几何性质的基本洞见来加速DEA计算，并且它们是近期贡献中的原型。ROC度量的一项重要好处是

CRediT作者贡献声明

Gregory Koronakos：撰写——初稿、方法论、概念化。José H. Dulá：撰写——初稿、方法论、概念化。Dimitris K. Despotis：撰写——初稿、方法论、概念化。

利益冲突声明

作者声明不存在已知的可能影响本文所报告工作的竞争财务利益或个人关系。

Gregory Koronakos | José H. Dulá | Dimitris K. Despotis