仿真优化是一种结合仿真模型与优化算法的技术，旨在通过计算机仿真实验找到最优决策，已广泛应用于物流、医疗、金融等多个领域。当今，随着实际需求的持续增长和计算能力的快速提升，决策问题所面临的可行解空间规模日益庞大，亟须更高效的仿真优化方法以应对这一挑战。对此，同济大学经济与管理学院管理高等研究院范薇薇副教授开展深入研究，与团队合作撰写的论文“The (Surprising) Sample Optimality of Greedy Procedures for Large-Scale Ranking and Selection”（贪婪算法在大规模排序择优问题中出人意料的样本复杂度最优性）被管理学和运筹学领域的国际顶级期刊Management Science录用并发表。

　　期刊 ： Management Science (Vol. 71, 2025)

　　作者：Zaile Li (复旦大学), Weiwei Fan (同济大学经济与管理学院), L. Jeff Hong (复旦大学)

　　关键词：ranking and selection, sample optimality, greedy, boundary-crossing

　　论文内容介绍

　　随着社会的快速发展和算力的持续提升，现代决策问题往往需要在数量庞大的可行决策集合中选择最优解。在这一背景下，如何设计高效算法来解决大规模排序与择优问题，已经成为仿真优化领域的核心研究方向，并引发了广泛关注。

　　在大规模选择排序问题中，样本复杂度是衡量算法效率的关键指标。不同于以往主要聚焦于设计复杂精巧算法的研究，本文在数值实验中意外发现，朴素的贪婪算法展现出了最优的样本复杂度，成为解决此类大规模问题的一种重要选择。为理解这一反直觉现象，本文对贪婪算法的运行机制进行了系统分析，发现其采样过程表现出一种边界跨越特性。基于此发现，本文推导出贪婪算法在渐进准确度上的理论下界，并进一步证明了其具有样本复杂度最优性。此外，本文提出了一类广义贪婪算法，在保留样本复杂度最优性的同时，可更高效地求解大规模选择排序问题。

　　本文通过发现贪婪算法具有样本复杂度最优性这一反直觉的现象，不仅揭示了大规模选择排序问题与传统中小规模问题之间存在本质的区别，也为求解大规模问题开辟了全新的研究思路。同时，本文突破了对贪婪算法的传统认知，系统地分析了其内在采样机制，从理论上揭示了其具有高效性的根本原因。这一研究不仅为仿真优化领域提供了全新的理论基础，还为设计高效算法提供了重要的实践指导，具有一定的学术价值与广阔的应用前景。

　　科研经验分享

　　科研的魅力在于，重要的研究成果往往源于意外的发现，例如牛顿因被苹果砸中而发现万有引力。本文的研究同样源于一次意外：在大量实验中，我们惊讶地发现，最简单的贪婪算法在解决大规模选择排序问题时，竟然展现了样本复杂度最优性。然而，意外的发现并不是终点，而是研究的起点和契机。本文正是以这一意外为切入点，通过深入剖析和挖掘贪婪算法的内在采样机制，成功解释了意外背后的“不意外”。这一过程不仅让我们更深刻地理解了贪婪算法的高效性，还为大规模问题的算法设计与理论分析提供了全新的研究视角。从意外发现到理论突破的过程，于我是一次充满乐趣且值得铭记的科研经历。

　　教授简介

　　范薇薇

　　同济大学经济与管理学院副教授，博士生导师。香港科技大学工业工程与物流管理系博士，中国科学技术大学应用数学学士。主持国家自然科学基金委青年项目（B类）、面上项目、青年项目（C类）等。在《Management Science》《Operations Research》《系统工程理论与实践》等国内外管理学权威期刊发表过多篇论文。目前担任管理科学与工程学会服务科学与工程分会副秘书长，运筹学会随机服务分会和医疗运作管理分会、“双法” 研究会服务科学与运作管理分会、管理现代化研究会风险管理专业委员会等学术组织理事。研究领域：仿真优化、鲁棒优化，及其在医疗管理、供应链管理等方面的应用。